PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-optimal ground state preparation

Lin Lin, Yu Tong

arXiv:2002.12508v3quant-phmath.NA

TL;DR

Ground-state preparation and energy estimation remain hard even for quantum computers, so the paper assumes an efficiently preparable initial state with non-trivial ground-state overlap and a lower-bounded spectral gap. It develops QSP-based filtering and binary-search estimation, then combines them to prepare ground states without a known energy upper bound. The estimator exponentially improves the precision dependence of initial-state queries over Ge et al., while search and approximate-counting applications support near-optimal complexity.

  • Problem

    Ground-state preparation and energy estimation are computationally hard, including QMA-complete generic local-Hamiltonian energy decision.

  • Method

    The paper uses block-encoded Hamiltonians, QSP-based eigenstate filtering, binary search for ground-energy estimation, and combination of these procedures.

  • Results

    The ground-energy estimator exponentially improves the dependence of initial-state queries on precision h and improves Hamiltonian-query precision dependence by a 1/h factor compared with Ge et al.

  • Takeaways & Limitations

    The methods prepare ground states with or without a known ground-energy upper bound and have dependences supported as essentially optimal by unstructured search and approximate counting.

  • Takeaways & Limitations

    Ground-state preparation requires a lower bound on the spectral gap, although low-energy-state preparation can avoid gap knowledge and tolerate ground-state degeneracy.

Abstract

from arXiv · show

Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.

1 Introduction

Ground-state preparation and energy estimation are important but hard, motivating algorithms that exploit an efficiently preparable initial state, a spectral-gap lower bound, and block-encoded Hamiltonians. The paper introduces filtering and estimation methods that improve precision dependence and can be combined without a known ground-energy upper bound.

  • Ground-energy estimation and ground-state information matter in condensed matter physics, quantum chemistry, and quantum information, but generic local-Hamiltonian energy decision is QMA-complete.
  • The algorithms assume an efficiently preparable initial state whose ground-state overlap is at least γ and a spectral gap lower bound Δ.The initial state can be prepared by an oracle UI, while the Hamiltonian is supplied through a block-encoding UH.
  • The filtering method prepares the ground state when only an upper bound on the ground energy is known, rather than requiring its exact or high-precision value.It filters out eigenstates above a chosen threshold and has exponentially improved precision dependence compared with Kitaev’s phase estimation.
  • Ground-energy estimation uses filtering to test energy thresholds and binary search, enabling ground-state preparation without an a priori upper bound.The method is presented as a hybrid quantum-classical algorithm and is combined with the filtering procedure.
  • The ground-energy estimator exponentially improves the dependence of initial-state queries on estimate precision h and reduces Hamiltonian-oracle precision dependence by a 1/h factor.The comparison accounts for Ge et al.’s time-evolution oracle through Hamiltonian simulation and does not assume h = eO(Δ).
  • The paper argues that its overlap, gap, and precision dependences are essentially optimal through unstructured search and quantum approximate counting.These applications establish lower-bound evidence for the corresponding tasks.

2 Block-encoding of reflector and projector

The paper constructs approximate reflectors and projectors for Hamiltonian eigenspaces by shifting a block-encoded Hamiltonian and applying QSP to a polynomial approximation of the sign function. These operators support threshold filtering and approximate projective measurement.

  • The method approximates the sign function on [−1, −δ] ∪ [δ, 1] with an efficiently computable odd polynomial.The polynomial has error at most ϵ on that domain and is used as the central QSP ingredient.
  • QSP transforms the shifted block-encoded Hamiltonian into an approximate reflector about eigen-subspaces with eigenvalues below a threshold μ.The resulting operator is denoted REF(μ, δ, ϵ).
  • A circuit derived from the reflector produces an approximate block-encoding of the projector P<μ onto eigen-subspaces with eigenvalues smaller than μ.The construction is denoted PROJ(μ, δ, ϵ) and has the stated block-encoding normalization and ancilla overhead.
  • When the threshold is separated from the spectrum by at least Δ/2, the reflector and projector can be constructed with controlled approximation error using O(α/Δ) query scaling up to the displayed precision factors.The lemma also specifies the extra-qubit costs for both block-encodings.
  • PROJ can be interpreted as an approximate projective measurement, so an unsuccessful projection outcome may still reveal the component above the threshold.The circuit can also be viewed as phase estimation on a reflector using one ancilla qubit.

3 Algorithm with a priori ground energy bound

With a known ground-energy upper bound, the algorithm applies the approximate projector below that threshold to an initial state with known overlap and amplifies successful applications. This prepares the ground state to the requested fidelity under the gap promise.

  • Applying PROJ(μ, Δ/4α, γϵ) to the initial state yields a state with fidelity at least 1 − ϵ to the ground state after successful projection.The construction uses P<μ = |ψ0⟩⟨ψ0| under the threshold promise.
  • Amplitude amplification raises the projection success probability to Ω(1) using O(1/γ) applications of the projector and its inverse.A reflector constructed from the same threshold-filtering ingredients can be used for amplification.
  • The algorithm assumes a block-encoding of H, an initial state prepared by UI, a lower overlap bound γ, and a threshold μ separated from the first excited energy.The spectral promise is λ0 ≤ μ − Δ/2 < μ + Δ/2 ≤ λ1.
  • The preparation procedure uses O(n + m) qubits.

4 Algorithm without a priori ground energy bound

Without a known upper bound on the ground energy, the algorithm uses binary amplitude estimation within a binary search to locate the ground energy, then applies a projector to prepare the ground state.

  • Ground energy estimation: The hybrid algorithm tests grid points over [−α, α] by binary search to locate the ground energy within a short interval.The grid spacing is h, and binary amplitude estimation determines whether candidate points lie to the left or right of the ground energy.
  • Ground energy estimation: Binary amplitude estimation distinguishes projector amplitudes associated with λ0 ≤ xk−1 and λ0 ≥ xk+1 using O((1/γ) log(1/δ)) oracle applications.The procedure estimates amplitudes separated by at least γ/2 and boosts success probability through repetition and majority voting.
  • Ground energy estimation: Conditional on no binary-estimation error, the outputs Bk and Bk+1 determine whether the ground energy lies below, above, or between neighboring search points.The algorithm uses Bk = 0 to infer λ0 > xk−1 and Bk = 1 to infer λ0 < xk+1.
  • Ground energy estimation: The ground energy can be estimated to precision h with probability 1 − ϑ under the stated block-encoding and initial-overlap assumptions.The theorem specifies query, qubit, and gate complexity bounds, with O(n + m + log(1/γ)) qubits and an optional O(1)-qubit reduction using Kitaev phase estimation.
  • Ground state preparation: After locating the ground energy in an interval of length at most ∆, applying the projector at its midpoint prepares a state with fidelity at least 1 − ϵ.Combining estimation with the projector yields ground-state preparation without an a priori ground-energy bound, under an additional lower bound on the spectral gap.
  • Ground state preparation: The procedure can also be viewed as producing a mixed state when success is not separately verified, with fidelity bounded using the failure probability and conditional output fidelity.The mixed-state analysis sets ϑ = ϵ = ξ/3 to achieve the target fidelity described in the passage.

5 Optimality of the query complexities

The paper establishes lower bounds for ground-state preparation and ground-energy estimation by reductions from unstructured search and approximate counting. Its algorithms match the relevant overlap and spectral-gap dependencies up to logarithmic factors and require inverse-precision scaling for energy estimation.

  • Lower-bound strategy: The lower-bound analysis applies ground-state preparation algorithms to unstructured search and quantum approximate counting.These reductions test dependence on the initial-state overlap, spectral gap, and energy-estimation precision.
  • Lower bounds: When ∆ = Ω(1) and γ → 0+, ground-state preparation requires Ω(1/γ) queries to UH.A faster algorithm would yield an impossible sub-Grover-query solution to unstructured search.
  • Lower bounds: When γ = Ω(1) and ∆ → 0+, ground-state preparation requires Ω(1/∆) queries to UH.The reduction constructs a Hamiltonian whose ground state encodes the marked search item while maintaining constant initial overlap.
  • Lower bounds: For constant spectral gap and vanishing overlap, O(1/γ^{1−θ}) queries to UI combined with O(poly(1/γ)) queries to UH cannot suffice for any θ > 0.The contradiction follows from preparing a search state with fewer than Ω(N^1/2) oracle queries.
  • Algorithm optimality: The a priori-bound algorithm essentially achieves optimal dependence on γ and ∆, while the algorithm without that bound matches it up to logarithmic factors.The latter uses less information while retaining the same asymptotic dependence modulo logarithmic factors.
  • Energy-estimation precision: Estimating the ground energy to precision h requires Ω(1/h) queries to UH.This lower bound is established by reducing quantum approximate counting to an eigenvalue-estimation problem.

6 Low-energy state preparation

The low-energy preparation procedure does not require knowledge of the spectral gap and can produce a state with energy at most a chosen threshold. When the initial state has sufficient low-energy overlap, its query complexity is bounded in terms of that overlap and the target energy tolerance.

  • Estimating the spectral gap is difficult, but this low-energy-state procedure requires no spectral-gap knowledge.
  • An initial state must have non-trivial overlap with the low-energy eigenspaces below the chosen threshold.The overlap condition is expressed quantitatively through parameters γ and δ.
  • The block-encoded projection operator filters the initial state toward eigencomponents below the energy threshold.
  • Choosing ϵ′ = O(γ2δ/α) yields a normalized state with expected energy at most µ.
  • With ground-state overlap at least γ, preparing energy at most λ0 + δ requires O(1/γ) queries to both UH and UI.
  • If the ground energy is unknown, the ground-energy estimation algorithm can be run first before preparing the low-energy state.

7 Discussions

The discussion situates the algorithms’ optimality, implementation requirements, near-term simplifications, and open limitations. The results rely on block-encoding, while lower bounds leave room for improved complexity under additional structure such as locality.

  • The paper combines upper-bound-based preparation, binary-search energy estimation, and preparation without a priori energy bounds.These are given as Theorem 6, Theorem 8, and Corollary 9, respectively.
  • All algorithms require a block-encoding of the target Hamiltonian, which can be constructed for several important Hamiltonian families.Examples include spin systems, Hubbard and quantum-chemistry Hamiltonians, and efficiently computable sparse Hamiltonians.
  • Replacing amplitude estimation with classical success-probability testing reduces circuit requirements but increases sampling complexity from O(log(1/ϑ)/γ) to O(log(1/ϑ)/γ2).
  • The simplified approach has circuit depth O((α/h) log(1/γ)) and avoids the O(log(1/γ)) qubits introduced by amplitude estimation.These features are described as suitable for near-to-intermediate-term devices.
  • Using the preparation algorithm along a quantum-Zeno eigenpath remains challenging when the initial state may be used only once per Hamiltonian.The paper identifies this setting as future work.
  • The lower-bound Hamiltonians are not local, so locality may permit better complexities.

A An example of block-encoding and constructing the reflector

The example constructs a block-encoding of a parameterized Hamiltonian and uses QSP polynomial transformation to approximate a reflector onto its negative-eigenvalue subspace. The approximation is accurate away from eigenvalues near zero, where the error spikes.

  • Polynomial construction: An odd polynomial S(x; δ, ϵ) is chosen with δ = 0.2 and residual error at most 10^-4, then converted into an odd polynomial P(x) through phase-factor optimization.The phase factors are computed by solving a least-squares problem and terminating when the real-part residual is below 10^-4.
  • QSP circuit: QSP implements the polynomial eigenvalue transformation using a sequence of phase factors, with Hadamard and Pauli-Z gates appearing in the circuit.The construction applies to the odd polynomial used in this example.
  • Approximation behavior: For eigenvalues in [−1, −δ] ∪ [δ, 1], Lemma 5 guarantees a good approximation to R<0(a).The guarantee fails when an eigenvalue lies in (−δ, δ), which occurs here for a ∈ (0.4, 0.6).
  • Approximation behavior: The operator-norm error is smaller than 10^-4 except for a ∈ (0.4, 0.6), where it spikes.The plotted error uses a logarithmic vertical axis.

B Gap and overlap in the unstructured search problem

For the unstructured-search Hamiltonian, the analysis reduces to the subspace spanned by |u⟩ and |t⟩, computes its eigenvalues, and derives the spectral gap and normalized ground state. The overlap term contributes to the state expression but is asymptotically unimportant.

  • Subspace reduction: The relevant analysis is confined to the subspace spanned by |u⟩ and |t⟩, while the orthogonal complement contributes only a multiple of the identity.In the non-orthogonal basis {|u⟩, |t⟩}, the Hamiltonian is represented by a two-dimensional matrix.
  • Gap calculation: Direct diagonalization of the two-dimensional representation yields the eigenvalues needed to derive the spectral gap.The resulting gap is recorded as equation (6).
  • Ground-state overlap: The ground state is obtained from an eigenvector corresponding to λ− and then normalized.This produces the normalized eigenstate given in equation (5).
  • Ground-state overlap: The third square-root term arises from the overlap between |u⟩ and |t⟩ but does not affect the asymptotic behavior significantly.The term is retained when forming the normalized ground-state expression.
Loading 2002.12508v3…