PaperlayerView exact revision on arXiv

Source-linked AI summary

Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers

Lin Lin, Yu Tong

arXiv:2102.11340v2quant-ph

TL;DR

Ground state energy estimation needs Heisenberg-limited precision, while QPE’s ancilla, depth, and coherent-operation requirements challenge early fault-tolerant quantum computers. The paper proposes a one-ancilla circuit with stochastic CDF reconstruction and classical post-processing. The method achieves the targeted precision scaling and produces an approximate spectral CDF, under overlap and time-evolution assumptions.

  • Problem

    Ground state energy estimation requires Heisenberg-limited precision, but QPE uses multiple ancillas, inverse QFT, and circuit resources that are undesirable on early fault-tolerant quantum computers.

  • Method

    The algorithm samples a simple one-ancilla quantum circuit, stochastically approximates the spectral measure’s CDF, and estimates the ground state energy through classical post-processing.

  • Results

    The algorithm achieves Heisenberg-limited precision scaling while using at most one ancilla qubit and producing an approximate CDF of the spectral measure.

  • Takeaways & Limitations

    The approximate CDF can also be used to compute other spectral properties of the Hamiltonian.

  • Takeaways & Limitations

    Rigorous performance guarantees require knowledge of a lower bound η on the initial ground-state overlap, and costly controlled evolution motivates an alternative circuit with additional assumptions.

Abstract

from arXiv · show

Under suitable assumptions, the quantum phase estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground state energy. However, QPE requires a large number of ancilla qubits and large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer. We propose an alternative method to estimate the ground state energy of a Hamiltonian with Heisenberg-limited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical post-processing procedure. Besides the ground state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.

1 Introduction

The paper develops a one-ancilla alternative to QPE for ground state energy estimation, targeting Heisenberg-limited precision with reduced early fault-tolerant resource demands. It reconstructs an approximate spectral-measure CDF from simple-circuit samples and applies classical post-processing.

  • Motivation: Ground state energy estimation is important across condensed matter physics, quantum chemistry, and quantum information, but generic Hamiltonians require precision-dependent time scaling no better than linear in ϵ^-1.The linear scaling is identified as the Heisenberg limit.
  • Assumptions: The analysis assumes access to time evolution under H and a reasonably large known lower bound η on the initial ground-state overlap p0.The dependence on p0 is more accurately expressed through η, and such overlap knowledge is also needed for rigorous guarantees in related QPE algorithms.
  • Motivation: Textbook QPE reaches Heisenberg-limited precision but uses multiple ancillas, inverse QFT, and substantial depth that are undesirable on early fault-tolerant quantum computers.High-confidence QPE variants can require still more ancillas and an additional coherent circuit.
  • Method: The method samples a simple quantum circuit, approximately reconstructs the spectral measure’s CDF, and uses classical post-processing to estimate the ground state energy with high confidence.The same approximate CDF can support estimation of other spectral properties.
  • Resource analysis: With Trotter-formula simulation, the total runtime scales as ϵ^-1-o(1), approximately reaching but not strictly attaining the Heisenberg limit.The paper reports a polynomially better dependence on p0 than QPE in this setting, while noting the effect of simulation-method assumptions.

2 Overview of the method

The algorithm combines a simple one-ancilla quantum circuit with classical processing to approximate the spectral CDF and locate the ground state energy. It estimates the CDF through Fourier-related constructions and uses the resulting approximation in a binary search, with only one step requiring a quantum computer.

  • The algorithm uses a simple quantum circuit with one ancilla qubit, while a different sampling and post-processing strategy reduces evolution-time costs.The circuit requires controlled time evolution, but the algorithm changes how it is queried and how samples are classically processed.
  • The circuit estimates real and imaginary parts of Tr[ρe^−ijτH] by choosing W and recording measurement outcomes as random variables.W = I is used for the real part, while W = S† is used for the imaginary part.
  • The spectral measure of τH is extended periodically so its Fourier transform has a discrete spectrum, with support confined to (−π/3, π/3).The support condition follows from choosing τ such that τ∥H∥ < π/3.
  • An approximate CDF is constructed through a smoothed Fourier approximation and an ACDF whose inequalities enable estimation of the CDF’s jump locations.The jumps in the interval containing the eigenvalues identify the ground state energy location.
  • The ground state energy is located by approximately evaluating the ACDF at selected points and applying binary search to narrow the candidate interval.The final estimate is obtained through classical post-processing, and only Step (2) of the overall procedure requires a quantum computer.

3 Evaluating the ACDF

The method estimates the ACDF by stochastically sampling Fourier terms collectively, avoiding the quadratic evolution-time dependence of term-by-term evaluation. The resulting ACDF supports heuristic ground-state energy estimation and closely resolves the ground-state jump in an 8-site Hubbard simulation.

  • Motivation: Evaluating all Fourier terms individually requires total evolution time Ω(τd^2), producing an ϵ^-2 runtime dependence when d scales inversely with precision.The stochastic alternative is introduced specifically to avoid this dependence.
  • Stochastic ACDF evaluation: The algorithm instead samples a frequency index J and evaluates the corresponding contribution as a whole, following an unbiased multilevel Monte Carlo-inspired construction.The sampled index ranges over {−d,…,d}, with probabilities determined by the Fourier coefficients’ magnitudes.
  • Stochastic ACDF evaluation: Averaging independent samples gives an unbiased ACDF estimator whose variance is at most 2F^2/Ns, requiring Ns = O(F^2/σ^2) samples for variance σ^2.The expected total evolution time is then obtained from the sampling cost and expected |J|.
  • Complexity: The resulting sampling analysis avoids the d^2 dependence that appears in term-by-term evaluation.This is the stated computational benefit of evaluating the full expression stochastically.
  • Numerical evaluation: The ACDF also provides a heuristic ground-state estimate x⋆/τ, with η chosen so that the initial ground-state overlap satisfies p0 ≥ η.A more elaborate procedure for prescribed accuracy and confidence is described later.
  • Numerical evaluation: For the 8-site half-filled Hubbard model, the estimated ACDF closely follows the CDF and clearly resolves the ground-state jump despite Monte Carlo noise.The simulation used a Hartree–Fock initial state with overlap around 0.4 with the exact ground state.

4 Estimating the ground state energy

Ground-state estimation is formulated as locating the first nonzero portion of the spectral CDF using its continuous approximation. The resulting procedure provides high-confidence additive-error guarantees and Heisenberg-limited precision scaling under an overlap assumption.

  • Problem formulation: The CDF is zero below τλ0 and at least p0 from τλ0 onward, so estimating λ0 reduces to finding the smallest x where the CDF becomes positive.The algorithm uses a known lower bound η satisfying p0 ≥ η.
  • Problem formulation: Because the CDF jumps at eigenvalues, its continuous approximation cannot uniformly reproduce it, so direct binary search on the CDF is unavailable.The search must use a criterion checkable through the estimated ACDF.
  • Accuracy guarantee: If x⋆ satisfies the ACDF criterion, then |x⋆ − τλ0| ≤ δ; choosing δ = τϵ makes x⋆/τ an estimate with additive error ϵ.The CDF inequalities on either side of x⋆ establish the error bound.
  • Complexity and confidence: With d = O(ϵ^-1τ^-1 log(ϵ^-1τ^-1η^-1)) and M = O(η^-2 log^2(d)(log log(ϵ^-1τ^-1)+log(ϑ^-1))), the estimate succeeds with probability at least 1 − ϑ.The stated classical post-processing cost is O(η^-2polylog(ϵ^-1τ^-1η^-1)).
  • Scope: The evolution-time scaling has no explicit system-size factor because system size enters indirectly through τ and η, with Hamiltonian-simulation overhead requiring separate accounting.This is the paper’s stated system-size scope boundary.

5 Inverting the CDF

The inversion procedure uses noisy ACDF estimates within a modified binary search to locate an interval containing the ground-state threshold. Batch majority voting controls certification errors while reusing the same quantum samples across search iterations.

  • Certification: CERTIFY decides whether C(x + δ) > η/2 or C(x − δ) < η by comparing ACDF estimates against thresholds derived from η.The procedure may choose randomly when both conditions hold.
  • Search procedure: INVERT CDF repeatedly calls CERTIFY during a binary-search-like procedure and stops when the interval width is at most 2δ.Any target within δ of τλ0 satisfies the required criterion, so the target need not be unique.
  • Certification: The ACDF estimator is formed from batches of samples, and majority voting determines whether the batch averages support one of the two CDF inequalities.Each batch average is compared with (3/4)η.
  • Error control: Choosing batch count Nb = O(log log(δ^-1) + log(ϑ^-1)) keeps the total certification error probability at most ϑ across L = O(log(δ^-1)) iterations.The per-call error is set to ϑ/L before applying the majority-vote bound.
  • Cost accounting: The expected total evolution time is NbNsE[|J|], while the maximal evolution time is governed by τd; the same samples can be reused across certification calls.Reusing samples avoids multiplying the total evolution cost by the number of search iterations.

6 Discussions

The paper presents a one-ancilla algorithm achieving Heisenberg-limited ground-state energy estimation, while noting unfavorable overlap dependence and broader spectral applications.

  • 6 Discussions: The algorithm estimates ground state energy with Heisenberg-limited precision scaling using a quantum circuit requiring only one ancilla qubit.Its maximal evolution time per run depends poly-logarithmically on the ground-state overlap p0.
  • 6 Discussions: The algorithm’s dependence on the overlap lower bound η scales as p0^-2, which is far from the p0^-1/2 scaling achieved in prior references.
  • 6 Discussions: Achieving p0^-1/2 scaling without substantially larger maximal evolution time or techniques such as LCU or block-encoding remains open.
  • 6 Discussions: The approximate-CDF method is a general approach for evaluating expectation values from matrix functions and may support other spectral properties, including spectral density.The authors also discuss partial derandomization using multilevel Monte Carlo ideas.

A Constructing the approximate Heaviside function

This appendix constructs a polynomially represented mollifier and uses it to form an approximate periodic Heaviside function with controlled error and degree.

  • A Constructing the approximate Heaviside function: The constructed Md,δ(x) is a smeared Dirac function used as a mollifier for approximating the Heaviside function by convolution.Its plotted shape is described as roughly Dirac-like.
  • A Constructing the approximate Heaviside function: Because Fd,δ is formed by convolution with a degree-d Chebyshev polynomial, its nonzero Fourier coefficients are restricted to modes −d through d.
  • A Constructing the approximate Heaviside function: The mollifier is bounded outside the interval [-δ, δ] and has a global lower bound determined by Nd,δ.
  • A Constructing the approximate Heaviside function: The integral of |Md,δ(x)| over one period is bounded by 1 + 4π/Nd,δ.
  • A Constructing the approximate Heaviside function: The approximate Heaviside function Fd,δ(x) achieves error at most ϵ away from the transition region [−δ, δ] and its periodic boundary neighborhoods.
  • A Constructing the approximate Heaviside function: Choosing d = O(δ^-1 log(δ^-1ϵ^-1)) suffices to meet the approximation-error requirement.The same asymptotic degree choice is stated in equivalent order as O(δ^-1 log(ϵ^-1δ^-1)).

B The relation between the CDF and the approximate CDF

The appendix relates the exact CDF C(x) to shifted approximate-CDF bounds derived from smoothed Heaviside functions.

  • B The relation between the CDF and the approximate CDF: The construction defines shifted functions FL(x) = F(x − δ) and FR(x) = F(x + δ) from a periodic approximation F.
  • B The relation between the CDF and the approximate CDF: The auxiliary functions eCL(x) and eCR(x) bound the exact CDF using the support of the spectral density and the [0, 1] ranges of H and FL.
  • B The relation between the CDF and the approximate CDF: The right-side bound gives eCR(x) ≤ C(x + 2δ) + ϵ.
  • B The relation between the CDF and the approximate CDF: Combining the bounds yields C(x − 2δ) ≤ eC(x − δ) + ϵ and C(x + 2δ) ≥ eC(x + δ) − ϵ.

C Obtaining the ground state energy by solving the QEEP

The appendix explains how interval tests for the spectral measure can locate the ground-state energy, with refined error accumulation improving the basic QEEP cost analysis.

  • C Obtaining the ground state energy by solving the QEEP: The interval [−π/3, π/3] is divided into M equal bins smaller than 2ϵ, and the leftmost bin with sufficient spectral weight identifies the ground-state region.
  • C Obtaining the ground state energy by solving the QEEP: Knowing p0 ≥ η allows interval spectral weights to be estimated to error O(η), rather than the O(ϵ) precision used in generic QEEP.
  • C Obtaining the ground state energy by solving the QEEP: The straightforward Fourier-mode analysis requires total evolution time O(η^-2ϵ^-4), omitting polylogarithmic factors.
  • C Obtaining the ground state energy by solving the QEEP: Independent unbiased Fourier-mode errors accumulate sublinearly, so a more careful analysis can improve the dependence on ϵ.
  • C Obtaining the ground state energy by solving the QEEP: Estimating each Tr[ρe−ijH] to error O(ηϵ^-1/2) saves a factor of ϵ^-1 in total runtime, with further reduction possible through stochastic indicator evaluation.

D Complexity analysis for using Trotter formulas

The appendix translates evolution-time costs into Trotterized circuit depth and runtime, then compares these costs with Trotterized QPE. The proposed algorithm incurs a smaller precision- and overlap-dependent overhead than QPE.

  • D Complexity analysis for using Trotter formulas: The appendix analyzes circuit depth and total runtime directly when Hamiltonian evolution is implemented with Trotter formulas.The Hamiltonian is decomposed into terms that can be exponentiated efficiently, and a p-th order formula with r steps approximates the evolution operator.
  • D.1 The algorithm in this work: The algorithm approximates Eq. (10) to precision η, with η serving as a lower bound on p0/2 in Theorem 3.The required Trotter-step count is selected so that the approximation error meets this precision target.
  • D.1 The algorithm in this work: The maximal circuit depth is obtained by multiplying the maximal evolution time by the Trotter-step count r.The same analysis yields the corresponding total-runtime requirement.
  • D.1 The algorithm in this work: For fixed H and ϵ, η → 0, Trotterization adds factors ϵ^-1/pη^-1/p to both the circuit-depth and total-runtime costs.These factors are measured relative to the maximal evolution time and total evolution time, respectively.
  • D.2 Quantum phase estimation: The QPE analysis covers both multi-ancilla QPE and the single-ancilla version implemented with a semi-classical Fourier transform.The latter has the same Trotterized resource result under this analysis.
  • D.2 Quantum phase estimation: Trotterized QPE must keep the final measurement distribution within O(η) total variation distance of the exact distribution.This preserves a probability of obtaining an energy close to the ground state bounded below by Ω(η).
  • D.2 Quantum phase estimation: QPE requires J = O(τ^-1ϵ^-1η^-1) phase-estimation steps, with Trotterization applied to each time-evolution operation.The τ^-1 factor accounts for rescaling the Hamiltonian, while p0 is replaced by η in this analysis.
  • D.2 Quantum phase estimation: Trotterized QPE incurs extra factors ϵ^-1/pη^-2/p in circuit depth and total runtime, making it worse than the proposed algorithm by η^-1/p.This comparison is relative to the corresponding maximal and total evolution-time costs.

E The control-free setting

The control-free setting replaces controlled time evolution with a three-register circuit and classical processing of measurements. Under state-preparation and reference-eigenstate assumptions, the resulting estimator preserves the target relations without changing asymptotic complexity.

  • E The control-free setting: The appendix introduces an alternative circuit that does not require controlled time evolution and uses its measurements to construct a random variable eZ.The construction is based on earlier ideas and is intended to replace the circuit used in the main text.
  • E The control-free setting: The control-free construction requires the initial state to be a pure state efficiently prepared by a unitary circuit.This is one of the additional assumptions needed for removing controlled evolution.
  • E The control-free setting: It also assumes access to a reference eigenstate with known eigenvalue that can be efficiently prepared.The reference state is prepared using a separate unitary circuit.
  • E The control-free setting: Orthogonality between the reference eigenstate and the initial state makes their time-evolved overlap vanish for every real t.For second-quantized fermionic Hamiltonians, the vacuum and Hartree-Fock states provide a stated example because particle number is conserved.
  • E The control-free setting: The circuit evaluates the real or imaginary part of α by choosing K = I or the phase gate S.It uses two one-qubit registers and one n-qubit register.
  • E The control-free setting: Measurement outcomes define eX and eY by assigning a signed value when the third register is all zero and zero otherwise.The corresponding variables are combined to form eZ while satisfying the target relations.
  • E The control-free setting: The new random variable eZ has slightly larger variance than the main-text variable Z.The appendix states that this variance increase does not change asymptotic complexity.

F Details on the numerical experiments

The numerical experiment applies the CDF-reconstruction procedure to a one-dimensional open-boundary Fermi-Hubbard model. Sampling closely tracks the spectral CDF, resolves the ground-state jump, and exhibits the predicted inverse-error evolution-time scaling.

  • F Details on the numerical experiments: The experiment approximates the cumulative distribution function for the Fermi-Hubbard Hamiltonian using the procedure from Section 3.The Hamiltonian includes fermionic creation and annihilation operators and number operators on the model lattice.
  • F Details on the numerical experiments: The model sites form a one-dimensional chain with open boundary conditions.This geometry is stated explicitly for the numerical Hamiltonian.
  • F Details on the numerical experiments: The Hartree-Fock initial state has an overlap of around 0.4 with the exact ground state.The sampling experiment is performed by simulating the quantum-circuit samples on a classical computer.
  • F Details on the numerical experiments: The reconstructed CDF closely follows the true CDF, and Monte Carlo noise does not prevent the ground-state jump from being clearly resolved.This is the reported outcome for Figure 3.
  • F Details on the numerical experiments: The ground-state estimate x⋆/τ is obtained from a heuristic procedure in the numerical experiment.The expected estimate lies within [τλ0 − δ, τλ0 + δ], with η chosen so that p0 ≥ η.
  • F Details on the numerical experiments: Figure 4 reports the estimated-energy error together with total and maximal evolution times for the Hubbard model at U/t = 4.The rigorous procedure with provable error and confidence bounds is discussed elsewhere in the paper.
  • F Details on the numerical experiments: The total evolution time scales as δ^-1, matching the linear δ^-1 scaling of the maximal evolution time in the plotted regime.The conclusion follows from the parallel lines on logarithmic axes described for Figure 4.

G Frequently used symbols

Table 3 lists symbols used frequently throughout the work.

  • G Frequently used symbols: Table 3 provides a reference list of frequently used symbols in the paper.The supplied caption identifies the table as a symbol glossary.
Loading 2102.11340v2…