PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster ground state preparation and high-precision ground energy estimation with fewer qubits

Yimin Ge, Jordi Tura, J. Ignacio Cirac

arXiv:1712.03193v2quant-ph

TL;DR

The paper addresses efficient preparation of Hamiltonian ground states from a trial state, using filtering and related quantum linear-systems techniques. It reports improved error, overlap, spectral-gap, and qubit scaling over phase-estimation-based methods, while also supporting high-precision ground-energy estimation and degenerate ground spaces.

  • Problem

    Preparing physically relevant Hamiltonian ground states is difficult in general, despite their applications and the limitations of existing methods.

  • Method

    The paper uses filtering techniques and minimum label finding to approximately project a trial state onto the ground-state component.

  • Results

    The algorithms improve runtime scaling in allowed error, spectral gap, and trial-state overlap relative to phase estimation, use fewer qubits, and estimate unknown ground energies at high precision.

  • Takeaways & Limitations

    The approach offers ground-state preparation for known or unknown ground energies and extends to degenerate and approximately degenerate ground spaces.

  • Takeaways & Limitations

    The presentation assumes a non-degenerate ground energy for simplicity, although the algorithm generalizes to degenerate ground spaces.

Abstract

from arXiv · show

We propose a general-purpose quantum algorithm for preparing ground states of quantum Hamiltonians from a given trial state. The algorithm is based on techniques recently developed in the context of solving the quantum linear systems problem [Childs,Kothari,Somma'15]. We show that, compared to algorithms based on phase estimation, the runtime of our algorithm is exponentially better as a function of the allowed error, and at least quadratically better as a function of the overlap with the trial state. We also show that our algorithm requires fewer ancilla qubits than existing algorithms, making it attractive for early applications of small quantum computers. Additionally, it can be used to determine an unknown ground energy faster than with phase estimation if a very high precision is required.

I. INTRODUCTION

Ground-state preparation is important but difficult because many-body states are classically inaccessible and general ground-state energy problems can be QMA-complete. Existing phase-estimation and adiabatic approaches face unfavorable dependence on error, overlap, or spectral gaps, motivating a more efficient algorithm.

  • Many-body ground states have important scientific applications, but preparing them can be difficult in full generality because related energy problems are QMA-complete.
  • Phase estimation succeeds with probability proportional to |φ0|^2 and becomes expensive when very high fidelity is required.
  • Adiabatic preparation requires runtime bounds depending inversely on the minimum spectral gap along the entire Hamiltonian path, which may be exponentially small and difficult to bound.
  • The proposed algorithm improves phase estimation's role, with exponentially better error scaling and polynomial improvements in spectral-gap and trial-state-overlap dependence.
  • Unlike adiabatic methods, the analyzed algorithms require only a lower bound on the target Hamiltonian's spectral gap, a weaker assumption that can hold with inverse-polynomial scaling.

II. OVERVIEW OF RESULTS

The paper assumes efficient simulation of a normalized Hermitian Hamiltonian and a trial state with a known lower-bounded ground-state overlap. Its filtering-based algorithms prepare ground states with favorable error, gap, overlap, and qubit scaling, and extend to unknown ground energies and degenerate ground spaces.

  • The Hamiltonian is an N × N Hermitian matrix with spectrum in [0, 1], and efficient Hamiltonian simulation is assumed.
  • The trial circuit prepares |φ⟩ with overlap φ0 with the ground state, while a known lower bound χ on |φ0| is assumed to satisfy χ = e−O(log N).
  • For known ground energy, an ϵ-close ground state can be prepared with constant probability when the energy is known to precision O(∆/ log 1/χϵ).
  • The known-energy algorithm is reported to have the best scaling among existing algorithms for both runtime and qubit count, while phase-estimation amplitude amplification is exponentially worse in ϵ and quadratically worse in |φ0|.

Combined approaches

The paper combines phase estimation with its filtering-based approach to handle unknown ground energies and improve scaling in the spectral gap and precision. These combined methods also support high-precision energy estimation with logarithmic qubit dependence on system size and inverse precision.

  • Combined approaches: When Φ is not too large, the unknown-energy algorithm has better runtime scaling than naive phase estimation and uses significantly fewer qubits than the filtering-method adaptation.The same runtime advantage over phase estimation is reported for high-precision energy estimation under the stated condition.
  • Combined approaches: Choosing κ = 1 yields the optimal scaling in the spectral gap, proportional to ∆^-1.The combined theorem permits any κ ∈ [0, 1].
  • Combined approaches: The algorithm estimates the ground energy to additive precision ξ = ˜O(∆) using O(log N + log ξ^-1) qubits.The combined approach provides an alternative gate complexity with the same qubit count.
  • Combined approaches: The approach is based on Fourier-method techniques and implements functions of the Hamiltonian through linear combinations of unitaries and Hamiltonian simulation.The known-energy version approximates cos^M H, implements it using the LCU Lemma, and boosts the target overlap by amplitude amplification or fixed-point search.
  • Combined approaches: The unknown-energy algorithm uses the minimum label finding procedure to locate the smallest candidate whose residual state has large norm.A successful search produces a candidate energy within ξ of the true ground energy and a good ground-state approximation.
  • Combined approaches: The combined ground-state preparation algorithm uses an initial phase-estimation run to obtain a crude energy interval, then searches candidate energies within that interval.The candidates are processed using the unknown-energy preparation procedure.

III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY

For known ground energy, the algorithm shifts the Hamiltonian so the ground state lies near eigenvalue zero, then approximates a power of cos H to filter out excited states. LCU-based implementation and overlap amplification complete the preparation procedure.

  • III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY: The procedure assumes the ground-energy estimate is sufficiently precise for the filtering construction.The theorem analysis takes the estimate precision to be δ = O(...), while the supplied passage truncates the expression.
  • III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY: The shifted Hamiltonian has the target ground state at eigenvalue τ + δE, while all other eigenvalues are at least ∆ higher.Here δE = λ0 − E, with E a known lower estimate of the ground energy.
  • III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY: High powers of cos H approximately project the trial state onto the unique ground-state component.The excited-state contribution is bounded using the decay of cos^M H across the spectral gap.
  • III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY: The algorithm approximates cos^M H with a linear combination of unitaries e^-iHt_k and implements it using Hamiltonian simulation and the LCU Lemma.The resulting operation is applied with some amplitude before the final amplification step.
  • III. ALGORITHM FOR THE CASE OF KNOWN GROUND ENERGY: Amplitude amplification or fixed-point search boosts the overlap with the target state before measuring the ancillas.Fixed-point search avoids overshooting but requires a good lower bound on the initial overlap when used directly.

IV. ALGORITHM FOR THE CASE OF UNKNOWN GROUND ENERGY

When the ground energy is unknown, the paper replaces a classical search over candidate energies with a quantum minimum-label search. This reduces the search overhead and simultaneously identifies a suitable energy estimate and ground-state approximation.

  • IV. ALGORITHM FOR THE CASE OF UNKNOWN GROUND ENERGY: The known-energy algorithm can be run for increasing candidate values E, stopping at the first successful projection.The first successful value provides, with high probability, a good estimate of the ground energy.
  • IV. ALGORITHM FOR THE CASE OF UNKNOWN GROUND ENERGY: The minimum label finding algorithm quadratically improves the search overhead compared with the classical search.It finds the smallest candidate label associated with a sufficiently large-amplitude residual state.

A. Minimum label finding

Minimum label finding searches a superposition of labelled states for the smallest label carrying sufficient amplitude. It uses fixed-point search and binary digit tests to achieve a high-probability output within the permitted label interval.

  • A. Minimum label finding: The subroutine seeks the smallest label i among prepared states whose target component has at least a known amplitude threshold.The states are produced by unitaries U_i acting on zero registers, with residual components orthogonal to the target ancilla state.
  • A. Minimum label finding: The procedure performs a binary search over the label digits, testing successive prefixes with repeated fixed-point searches.The two-stage procedure handles consistent prefixes and then completes the search after an inconclusive result.
  • A. Minimum label finding: The minimum label algorithm prepares a normalized labelled state for some j in [˜J, J] with probability at least 1 − 5δ.Its resource bound includes q + n + m + 1 qubits, with additional gate complexity specified by the proposition.
  • A. Minimum label finding: Fixed-point search is used because it requires only a lower bound on the initial overlap and cannot overshoot the target state.This makes it suitable for distinguishing candidate labels with large versus small target amplitudes.
  • A. Minimum label finding: The fixed-point search succeeds with probability at least 1 − δ^2 when the target overlap meets the supplied lower bound, while its overlap is bounded when the target is below that bound.These two regimes support the binary digit tests used by minimum label finding.
  • A. Minimum label finding: If only the first n′ dominant binary digits are needed, the resource expressions can replace n with n′.The proposition also states that the ζ^2 dependence in one resource bound is optimal.

B. Proof of Theorems 2–4

The paper combines Hamiltonian-simulation-based filtering with minimum-label finding to prepare ground states and estimate unknown ground energies. A prior coarse energy estimate can improve spectral-gap scaling at the cost of overlap dependence.

  • Known and unknown ground energy: The algorithm uses controlled unitaries across energy labels and minimum-label finding to project the trial state onto a ground-state approximation.The label register estimates the ground energy, while the second register contains the desired state.
  • Implementation and cost: The algorithm implements the controlled family with one Hamiltonian-simulation call plus O(log L) additional gates, yielding the claimed overall gate cost.The construction uses an ancilla register L of ⌈log2 L⌉ qubits.
  • Known and unknown ground energy: The combined approach first obtains a crude ground-energy estimate, then applies the preparation algorithm over a narrowed interval.The interval width is O(∆^κ), with κ chosen to balance parameter dependences.
  • Ground-energy estimation: The method can estimate the ground energy to arbitrarily small precision by supplying a smaller lower bound ∆′ on the spectral gap.Running the algorithm with ∆′ ≪ ∆ gives precision ξ = ˜O(∆′).
  • Known and unknown ground energy: Choosing κ = 1 gives the combined algorithm scaling of approximately 1/∆ with the spectral gap.Other κ values can trade off the dependence on the remaining parameters.

V. CONCLUSION

The paper concludes that its algorithms prepare Hamiltonian ground states faster and with fewer qubits than previous methods, including when the ground energy is unknown. It also identifies limitations in distinguishing small-overlap energy cases and in some parameter regimes.

  • Conclusion: The algorithms improve runtime and qubit requirements for ground-state preparation with both known and unknown ground energy.For unknown ground energy, the algorithm also estimates the energy at high precision faster than phase estimation with amplitude amplification.
  • Conclusion: Straightforward phase estimation with amplitude amplification has exponentially worse error scaling and quadratically worse overlap scaling than the paper’s known-energy algorithm.The comparison is made for preparation using a trial state with ground-state overlap |φ0|.
  • Conclusion: The paper’s algorithms use significantly fewer qubits than Poulin and Wocjan’s filtering method, although the methods can have comparable runtime scaling.This motivates their use in early quantum-computing applications.
  • Limitations: When the ground energy is unknown, distinguishing a true ground-energy label from a lower-energy label with smaller overlap can require many amplitude-amplification repetitions.The paper describes this as a systematic difficulty for the methods considered.
  • Scope: The algorithm extends to degenerate and approximately degenerate ground spaces, with spectrum contained in [λ0, λ0 + ε] ∪ [λ0 + ∆, 1] when ε ≪ ∆.In the degenerate case, the target is the normalized projection of the trial state onto the ground space.
  • Scope: The Chebyshev-polynomial and quantum-walk alternative has the same runtime scaling but is restricted to sparse Hamiltonians with quantum-oracle access.The Hamiltonian-simulation approach applies to other Hamiltonian-access models with efficient simulation algorithms.

Appendix A: Finding the ground energy using phase estimation

Appendix A analyzes ground-energy estimation by phase estimation when the minimum eigenvalue is unknown. Finite precision creates false low-energy outcomes, forcing stronger dependence on the trial-state overlap.

  • Setup: The goal is to estimate the minimum eigenvalue λ0 of a unitary to n = ⌈log2 1/ξ⌉ binary digits of precision.The unitary eigenvalues are e2πiλi with λi ∈ [0, 1).
  • Phase estimation: Phase estimation uses controlled U, U^2, through U^2^(k−1), followed by an inverse quantum Fourier transform on k ancilla qubits.The resulting ancilla state has large overlap with the basis encoding the first n binary digits of each λi.
  • Naive cost: Naive measurement would find the ground energy with probability approximately |φ0|^2, suggesting O(1/|φ0|^2) repetitions or O(1/|φ0|) with amplitude amplification.These expectations do not account for the additional cost caused by unknown ground energy and finite precision.
  • Unknown ground energy: To prevent accidentally accepting an energy much smaller than λ0, phase estimation must use 2^k = ˜O(2^n/|φ0|^2).The runtime scales linearly with 2^k, while only a lower bound χ on |φ0| is assumed known.
  • Baseline proposition: The phase-estimation baseline finds λ0 to additive precision ξ using O(log N + log 1/ξ) qubits.The gate complexity is given in the proposition’s expression (A1).

Appendix B: Preparing the ground states using phase estimation

Appendix B analyzes phase-estimation-based ground-state preparation and shows that finite-precision imperfections accumulate in the residual state. The resulting baseline depends strongly on overlap, spectral gap, and the availability of prior ground-energy knowledge.

  • Error analysis: Finite-precision imperfections in phase estimation can accumulate into a non-negligible residual-state error, so ξ = ˜O(∆) is not generally sufficient.The appendix analyzes the minimum precision needed to control this error.
  • Known ground energy: If λ0 is known to precision O(|φ0|ϵ∆), phase estimation prepares an ϵ-close ground state with the gate complexity stated in Proposition 3.The qubit requirement is O(log N + log 1/ϵ + log 1/∆).
  • Known ground energy: The known-energy phase-estimation procedure post-selects the ancilla value encoding the first k binary digits of λ0.The residual-state error is controlled by choosing k according to the appendix’s bound.
  • Known ground energy: The required precision parameter k has explicit dependence on |φ0|, and the resulting state error can be O(ϵ).The appendix highlights the overlap dependence of this requirement.
  • Unknown ground energy: For unknown ground energy, phase estimation must first determine λ0 to precision O(χϵ∆), producing the stated preparation complexity and O(log N + log 1/ϵ + log 1/∆) qubits.The known lower bound χ substitutes for the unknown overlap |φ0| in the required precision.
  • Tightness: The phase-estimation baseline’s dependence on |φ0| is essentially tight for the analyzed algorithm, and its linear dependence on 1/∆ is also tight.These tightness statements are established for suitable Hamiltonians and trial states.

Appendix C: Filtering method by Poulin & Wocjan

The filtering method uses phase-estimation components and a filter function centered near the ground energy to suppress excited-state contributions. It supports ground-state preparation and ground-energy estimation, including when the ground energy is initially unknown.

  • Filtering idea: The filter function is centered around λ0 and falls off quickly, suppressing excited-state terms while retaining the ground-state contribution.The method applies repeated copies of a phase-estimation-derived circuit and a momentum state, then amplifies the desired ancilla outcome.
  • Known ground energy: For known ground energy, the filtering method prepares an ϵ-close ground state with the gate complexity stated in Proposition 4.The proposition assumes λ0 is known to a specified precision.
  • Amplification: O(η/|φ0|) uses of A† and Cµ, together with O(1/|φ0|) uses of Cφ, yield the amplified state with high probability.The number of filter repetitions depends inversely on the trial-state overlap through |φ0|.
  • Parameter choice: When |φ0| is unknown, η must be chosen beforehand so the algorithm works without knowing the trial-state overlap.The parameter choice is therefore designed to accommodate an unknown overlap.
  • Unknown ground energy: For unknown ground energy, minimum label finding identifies a suitable µ, after which filtering prepares the ground state using the same qubit count as the known-energy procedure.The selected label j lies in an interval whose values approximate λ0 sufficiently well.
  • Energy estimation: The filtering method can also estimate λ0 to additive precision ξ = ˜O(∆), and a combined filtering-plus-phase-estimation approach handles very small ∆.The choice κ = 1 gives the optimal inverse scaling in ∆ and ξ for the combined algorithm.

Appendix D: Chebyshev method

The Chebyshev method approximates a high power of a spectral filter, implements it with quantum walks and linear combinations of unitaries, and amplifies the target overlap. It uses logarithmic qubit resources and also extends to unknown-energy preparation and energy estimation.

  • Assumptions: The approach assumes sparse access to ˜H, with d = O(log N) nonzero entries per row or column, and quantum oracle access to their positions and values.The spectrum is assumed to lie in a bounded interval for the construction.
  • Ground-state filtering: A high power of 1−(H/d)^2 is approximately proportional to a projector onto |λ0⟩, while the residual term is bounded by |φ0|^-1e^-Ω(M(τ+δE)∆).This spectral suppression explains why the transformed trial state approaches the ground state.
  • Algorithm: The method approximates (1−(H/d)^2)^M with low-order Chebyshev polynomials, implements the combination using quantum walks and non-unitary LCU, then amplifies the target overlap.Amplitude amplification or fixed-point search boosts the overlap after the polynomial transformation.
  • Gate complexity: O(m0(Λ + log M + log N + log^(5/2)(m0d/ϵ|φ0|)) gates implement the LCU transformation under the stated accuracy requirement.The expression uses the oracle cost Λ and depends on the polynomial order, system size, sparsity, target error, and trial-state overlap.
  • Qubit complexity: O(log N + log M + log m0) qubits are required.The qubit count is logarithmic in the system dimension, polynomial degree parameter, and number of LCU terms.
  • Extensions: The Chebyshev approach can also prepare ground states with unknown ground energy and estimate the ground energy.These extensions are stated as analogous to the corresponding filtering constructions.
Loading 1712.03193v2…