PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for quantum simulation at finite energies

Sirui Lu, Mari Carmen Bañuls, J. Ignacio Cirac

arXiv:2006.03032v3quant-ph

TL;DR

Finite-energy and finite-temperature properties are challenging targets for existing quantum-simulation algorithms, which can require exponential time and be difficult to implement on small devices. This paper introduces a filtering-based hybrid algorithm that reconstructs observables without preparing the filtered state, and a quantum-assisted Monte Carlo method for ensemble quantities. The first has polynomial scaling under its stated parameters, while the second circumvents the sign problem when suitable-energy states can be prepared.

  • Problem

    Existing algorithms for excited-state and finite-temperature questions may require exponential time in N and remain challenging to implement on small quantum computers or analog simulators.

    Source: §I · p. 2

  • Method

    A cosine-filter-based hybrid algorithm reconstructs finite-energy observables from interferometric measurements, while a second method uses quantum-computed sampling probabilities within classical Monte Carlo.

    Source: §I · p. 2

  • Results

    The first algorithm has runtime polynomial in N, inverse error, and inverse filtering width, while quantum-assisted Monte Carlo circumvents the sign problem when suitable-energy states can be prepared.

    Source: §I · p. 2

  • Takeaways & Limitations

    The approaches target finite-energy observables and microcanonical or canonical quantities using efficiently preparable states and quantum-simulator measurements.

    Source: §I · p. 2

    Quantum-assisted sampling is not proven efficient and requires states of suitable energies.

    Source: §I · p. 2, §V · p. 7

Abstract

from arXiv · show

We introduce two kinds of quantum algorithms to explore microcanonical and canonical properties of many-body systems. The first one is a hybrid quantum algorithm that, given an efficiently preparable state, computes expectation values in a finite energy interval around its mean energy. This algorithm is based on a filtering operator, similar to quantum phase estimation, which projects out energies outside the desired energy interval. However, instead of performing this operation on a physical state, it recovers the physical values by performing interferometric measurements without the need to prepare the filtered state. We show that the computational time scales polynomially with the number of qubits, the inverse of the prescribed variance, and the inverse error. In practice, the algorithm does not require the evolution for long times, but instead a significant number of measurements in order to obtain sensible results. Our second algorithm is a quantum-assisted Monte Carlo sampling method to compute other quantities which approach the expectation values for the microcanonical and canonical ensembles. Using classical Monte Carlo techniques and the quantum computer as a resource, this method circumvents the sign problem that is plaguing classical Quantum Monte Carlo simulations, as long as one can prepare states with suitable energies. All algorithms can be used with small quantum computers and analog quantum simulators, as long as they can perform the interferometric measurements. We also show that this last task can be greatly simplified at the expense of performing more measurements.

I. Introduction

The introduction motivates finite-energy and finite-temperature properties as less-addressed targets than dynamics and ground states, noting that prior statistical-state algorithms can require exponential time and challenge near-term devices. It presents two approaches: an efficient hybrid method for observables at selected energies and quantum-assisted Monte Carlo for microcanonical and canonical quantities.

I. Introduction

  • Earlier algorithms for excited-state or finite-temperature questions may require exponential time in N and remain challenging to implement on small quantum computers or analog simulators.The introduction contrasts these limitations with the paper's focus on finite-energy properties.Source: §I · pp. 1–2
  • The first approach avoids preparing filtered states by reconstructing their observables from interferometric measurements at different stroboscopic evolution times.The measurements involve conditional evolution based on a single qubit.Source: §I · p. 2
  • The first algorithm computes observables around the energy of any efficiently preparable state in time polynomial in N, inverse error, and inverse filtering width.The filtering width is related to the targeted state's energy variance; the authors know of no classical algorithm with this polynomial scaling.Source: §I · p. 2
  • Quantum-assisted Monte Carlo combines quantum sampling probabilities with classical Monte Carlo to obtain microcanonical and canonical expectations and circumvent the sign problem when suitable-energy states can be prepared.The method is not proven efficient, but offers shorter coherence times than the first algorithm at the cost of more quantum measurements.Source: §I · p. 2

A. Setup

  • The setup assumes the Hamiltonian evolution can be efficiently implemented and the required time-dependent quantities can be measured with sufficiently small error.Repeating the experiment L times gives additive error scaling as L^-1/2.Source: A. Setup · p. 3

B. Initial states

The initial state must be efficiently preparable, and its mean energy determines which energies the method can target. The cosine filter narrows the state's energy support around a chosen energy, while an evolution-based expansion lets the simulator measure the quantities needed to reconstruct observables without preparing the filtered state.

B. Initial states

  • Product states are simple initial states for the algorithm, provided they can be prepared efficiently by the simulator.The state ψ is chosen from states the simulator can prepare.Source: B. Initial states · p. 4
  • For local Hamiltonians and finite-correlation-length states, both mean energy and energy variance scale as N; efficiently preparable states therefore bound the accessible energy range.Product states can cover an extensive interval for local Hamiltonians, with finding suitable product states amounting to an efficiently solvable mean-field problem; other easy-to-prepare states can extend access.Source: B. Initial states · p. 4

C. Cosine Filter

  • The cosine filter suppresses eigenstates whose energies lie far from the chosen E, producing a state with energy support concentrated around E.The width parameter δ can be constant or decrease with N.Source: C. Cosine Filter · p. 4
  • Rather than prepare the filtered state, the method expands the filter using evolution operators e^-iHt and measures the required quantities separately for classical postprocessing.The simulator runs for times t ≤ 2x/δ; the measurement count scales with 2R times the repetitions needed for the prescribed accuracy.Source: C. Cosine Filter · p. 4

D. Ising Model

The section establishes an efficient finite-energy measurement algorithm and describes an Ising model used for numerical calculations. The algorithm targets observables near a prepared state's mean energy, while the model provides tractable Fock-state inputs.

D. Ising Model

  • The Ising-model calculations use even-N fermionic modes with periodic boundary conditions, mapped by Jordan–Wigner to an Ising Hamiltonian.The benchmark is chosen because numerical results can be obtained for N around 100 qubits.Source: D. Ising Model · pp. 4–5
  • The model's Fock states form an orthonormal basis and are easy to handle at large N, although they are not eigenstates of H.Analytical formulas provide exact numerical results for this model.Source: D. Ising Model · p. 5
  • At zero temperature, the model has a phase transition at g = h; its ground state is the vacuum for h ≫ g and a superposition with paired-momentum excitations for h ≪ g.Source: D. Ising Model · p. 5

III. Efficient quantum algorithm for observables at finite energy

  • The algorithm expresses the filtered observable's numerator and denominator through interferometric measurements, then performs the sums and multiplications classically.Simulator evolution times are bounded by 2x/δ, and the required measurement count is 2R times the repetitions needed for the prescribed accuracy.Source: §III · p. 5
  • For efficiently preparable ψ and measurable A with ∥A∥∞≤1, the algorithm obtains finite-energy observables to additive error ϵ in polynomial time when δ is polynomially small in 1/N.The energy E is selected within a small interval around the mean energy Eψ.Source: §III · p. 5
  • The finite energy interval avoids relying on a single energy whose filtered overlap with ψ may be exponentially small in N.Varying E over a small interval is stated to avoid this issue.Source: §III · p. 5

IV. Practical computations

The practical-computations section introduces more efficient simulator use for quantities related to microcanonical and canonical ensembles. Its local-density-of-states example compares the original and optimized procedures.

A. Local density of states

  • The local density of states is estimated in broadened form, which converges to that quantity as δ → 0.Source: A. Local density of states · p. 6
  • The optimized procedure reduces the required measurements when the state has σψ ≤ N, by rescaling the filtering expansion using its energy spread.Source: A. Local density of states · p. 6
  • For δ = 0.1, the optimized method with r = 0.4 uses 120 measurements and maximum time t = 60, with error about 10^-2; at r = 1, error is about 10^-3.The figure compares the original method with optimized alternatives for 50 randomly chosen states at N = 100 and x = 3.Source: Figure 2 · p. 6, A. Local density of states · p. 6

B. Microcanonical observables

The section develops microcanonical observables through quantum-assisted Monte Carlo and tests the approach against exact calculations. It also examines how energy resolution affects results and where the methods encounter practical limits.

B. Microcanonical observables

V. Quantum assisted Monte Carlo algorithms for microcanonical and canonical observables

  • The quantum-assisted Monte Carlo algorithms circumvent the sign problem, but their efficiency is not proven; they may trade shorter coherence times for more measurements.The paper presents the method as viable on near-term devices and reports accurate results for an N = 100 Ising Hamiltonian despite certain noise.Source: §V · p. 7

A. Microcanonical observables

  • The direct auxiliary-state quotient approach has a denominator that typically decreases exponentially with N, making it impracticable already for N ≳ 20.The proposed alternative re-expresses the observable using an overcomplete basis of states.Source: A. Microcanonical observables · p. 8
  • Quantum-assisted sampling uses classical Monte Carlo to choose initial states and a quantum simulator to compute sampling probabilities and observables.Importance sampling proportional to Dδ,ψ(E) evaluates those quantities only for states where Dδ,ψ(E) is not negligible, avoiding a sum over all states and exponentially small measurement accuracy.Source: §V · p. 7, A. Microcanonical observables · p. 8
  • For N = 20, the Monte Carlo magnetization is compared with exact results, but both methods encounter convergence problems at low energies where Dδ,ψ(E) becomes very small.The exact summation shown is possible only for this 20-spin figure.Source: A. Microcanonical observables · pp. 8–9, Figure 4 · p. 8
  • For N = 100, Monte Carlo magnetization results resemble the exact values, with precision problems appearing below E < −60 for the exact method and E < −100 = Ep,min for Monte Carlo.Decreasing δ further leaves the results practically indistinguishable from δ = 1, but the program becomes unstable near Ep,min as Dδ,k(E) becomes extremely small.Source: A. Microcanonical observables · p. 9

B. Canonical observable:

The canonical-observable method combines quantum-simulator estimates with classical Monte Carlo sampling over states and energies. In the reported spin-model tests, it performs well at δ = 1, but becomes unreliable at lower temperatures when sampled energy weights are very small.

B. Canonical observable:

  • The proposed quantity converges to the canonical value as δ → 0.Source: B. Canonical observable · p. 9
  • Monte Carlo samples states and energies with probability proportional to e^−βEDδ,ψ(E); for observables diagonal in the chosen basis, sampling can instead be over states.The energy-integrated sampling probability can be reconstructed with the quantum simulator, with the energy dependence integrated analytically.Source: B. Canonical observable · pp. 9–10
  • For N = 100 spins, the Monte Carlo magnetization agrees well with the exact result at δ = 1, with a small bias toward lower magnetization at larger β.The simulations used δ = 1, x = 3, and energy steps of 0.5; lower-temperature estimates become unreliable when Dδ,ψ(E) is very small.Source: B. Canonical observable · p. 10

VI. Summary and Outlook

The paper presents cosine-filter algorithms for finite-energy and finite-temperature observables, using interferometric measurements instead of preparing filtered states. Their practical use trades shorter evolution times for measurement effort, while the Monte Carlo approach is numerically reliable in some energy regimes.

VI. Summary and Outlook

  • The first algorithm computes expectations over filtered states from an efficiently preparable initial state, with runtime polynomial in N, inverse variance, and inverse error.For δ = O(1), the simulator need only evolve for times ≤ 6/δ, but the practical simplification requires many more measurements.Source: §VI · p. 10
  • For N = 100, δ = 1, and error 10−2, the measurement estimate is about 3·10^5; the authors expect optimizations could reduce it to about 10^4.The proposed optimizations include exploiting small c_m, choosing smaller x, and using symmetries.Source: §VI · p. 10
  • The quantum-assisted Monte Carlo methods combine the first algorithm with classical sampling to estimate microcanonical and canonical observables, with reliable results in some energy regimes after tens of thousands of samples.They require suitable efficiently preparable states, evolution for times of order 6/δ, and interferometric measurements; standard Monte Carlo strategies can speed convergence.Source: §VI · p. 10
  • The approach can extend to fermionic, longer-range, or disordered systems when the device can emulate their Hamiltonians, and can be adapted to Green functions or structure factors.Source: §VI · p. 11

A. Ways to retrieve aA,ψ(t)

The appendix compares interferometric procedures for retrieving aψ(t) and aA,ψ(t), which differ in their control, state-preparation, and measurement requirements. Some approaches trade simpler hardware for additional measurements or require particular states or Hamiltonians.

1. Conditional dynamics

  • Conditional dynamics uses a control qubit to retrieve the desired quantity, but requires coupling it to all qubits throughout the evolution.This can be natural in trapped-ion or Rydberg-atom simulators.Source: §1 · p. 11

2. Additional internal states

  • An alternative uses four-level systems: the Hamiltonian acts on |0⟩ and |1⟩, while extra idle levels support the measurement procedure.The method uses additional two-body operations and a Hadamard operation between control levels.Source: §2 · p. 12

3. Cat-like states

  • Cat-like-state measurements can avoid both an ancilla and extra internal levels, provided suitable cat-like states can be prepared.When the overlap parameters are known, aψ(t) can be recovered by measurements at selected phase settings; otherwise, those settings can be identified experimentally.Source: §3 · p. 12
  • An easily prepared eigenstate can serve as the second state; for the stated Heisenberg Hamiltonian, |0,…,0⟩ is such an eigenstate for arbitrary Jn,m and hn.Source: §3 · p. 12

4. Product states

The product-state method connects states through a sequence of single-qubit changes, avoiding cat-like-state preparation at the cost of more measurements. A separate symmetry-based approach can simplify interferometric measurements for Hamiltonians satisfying specified operator conditions.

4. Product states

  • For product states, the method measures aA,ϕm(t) sequentially as one qubit changes at each step, extending to states connected by products of simple operators.It avoids cat-like states, but can require up to N measurements and accumulated errors.Source: §4 · p. 13

5. Symmetric Hamiltonians

  • The symmetry-based method assumes operators R and T satisfying the stated relation, with [T,H] = 0 and ψ an eigenstate; then aψ(t) is related to aψ(t) by a phase.Source: §5 · p. 13
  • When ψ is an eigenstate of A or [A,H] = 0, the method can recover aA,ψ(t) from its magnitude and sign, requiring only individual measurements.The sign can be inferred by tracking zeros; the paper notes that the relevant order is usually n = 1 or 2.Source: §5 · p. 13
  • Examples include bipartite-lattice Hamiltonians for which R is, up to single-qubit rotations, a parity operator, and the Hubbard model on a bipartite lattice.Source: §5 · p. 13

B. Ising model

The Ising Hamiltonian is rewritten in fermionic modes and reduced to independent four-level systems, enabling explicit calculation of product-state energies and ground-state behavior.

B. Ising model

  • The Jordan–Wigner mapping gives an Ising-like Hamiltonian with periodic fermionic boundary conditions.The appendix assumes periodic boundaries for the fermions.Source: B. Ising model · p. 14
  • The Hamiltonian separates into N/2 non-interacting four-level systems.Each mode is represented by a 4×4 matrix, with a direct-sum structure across two subspaces.Source: B. Ising model · p. 14
  • For k ≠ 0, the passage gives E1,2 k,± = ±z_k; for the zero mode, it gives eigenvalues ±x_0,+ and ±x_0,−, without stating zero eigenvalues for k ≠ 0.Source: B. Ising model · p. 14
  • At g = h, the gap closes as N grows, marking a quantum phase transition.The ground-state coefficients depend on g and h; for h ≫ g they approach α_k ∼ 1 and β_k ∼ 0.Source: B. Ising model · p. 15

1. Microcanonical average

The appendix gives formulas for evaluating microcanonical-average quantities for local observables in the Ising model.

1. Microcanonical average

  • The operator A is decomposed into contributions depending on fermionic modes; magnetization is one example of such a local-operator sum.A_k depends on paired modes, with a separate dependence for k = 0.Source: §1 · p. 15
  • The required simulation expressions can be computed from the mode-evolution formulas.The appendix also states that Eq. (28) can be computed directly.Source: §1 · p. 15
  • The coefficients r_m,0 are expressed using cosines, while s_m,k depends on the observable.The cosine expression combines x_0,+ and x_0,−.Source: §1 · p. 15

2. Canonical average

The appendix outlines a canonical-average calculation and proves an energy-interval bound used in the efficient-computation argument.

2. Canonical average

  • The appendix introduces a procedure for computing the canonical average.The supplied passage names the calculation but does not provide its formula.Source: §2 · p. 15

C. Efficient computation

  • A Gaussian approximation to the cosine filter is used to establish a sufficiently large energy interval within the target window.The proof seeks an interval where the approximating density is at least half its value at the interval center.Source: C. Efficient computation · p. 16
  • Bounding T(r) and then the derivative of the approximating density establishes a neighborhood where the required condition holds.The argument first finds an energy with sufficiently large density, then bounds the neighborhood around it.Source: C. Efficient computation · p. 16
  • Efficient computation depends on finding a state with the prescribed energy; product states have a rigorous bound of −DN for local Hamiltonians with spectrum in [−N, N], where D > 1/9.The text says tighter bounds can be found for specific models and that non-product states can access larger D.Source: C. Efficient computation · p. 17

D. Convergence to the microcanonical and canonical values for a non-integrable model

Numerical tests in a non-integrable Ising model show convergence toward microcanonical values as the filter width shrinks. The appendix also considers approximating the cosine filter with a Gaussian.

D. Convergence to the microcanonical and canonical values for a non-integrable model

E. Approximating the Cosine filter as Gaussian

  • The appendix bounds the difference between the cosine filter and its Gaussian approximation by considering nonnegative x, since both terms are even.For |x| < π/2, the passage states e^(−x^2/2) ≥ cos x.Source: E. Approximating the Cosine filter as… · p. 18

Related papers

This paper cites

Loading 2006.03032v3…