RECORD
Near-optimal ground state preparation
Quantum Physics · Submitted 28 Feb 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. | background 1.00 | 0.06 | 0.02 | asserted 1.00 |
| s1 | However, given some additional information, these problems can be solved efficiently on a quantum computer. | background 0.93 | 0.09 | 0.12 | asserted 0.72 |
| s2 | 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. | background 0.44 | 0.13 | 0.04 | asserted 0.97 |
| s3 | 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. | contribution 0.74 | 0.94 | 0.24 | asserted 1.00 |
| s4 | 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]. | contribution 0.82 | 0.88 | 0.24 | asserted 0.98 |
| s5 | These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. | contribution 0.63 | 0.84 | 0.30 | asserted 0.97 |
| s6 | 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. | result 0.85 | 0.94 | 0.22 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
References
How later papers used it
99 later papers cite it
10 later papers by other authors are listed below: 8 used its method or tool and 2 compared their own results with it. 1 more paper by the same authors is listed: 1 compared its own results with it.
Uses its method or tool 8 of 11 papers with this label
-
Combined this paper's algorithm with time-dependent Hamiltonian simulation.
Fast digital methods for adiabatic state preparation (2020) · 0.91 · paraphrased: the licence does not allow quoting
-
We provide estimates for the cost of state preparation based on the $T$-gate count of implementations of Lin and Tong's $𝒰_SP()$ [ref] .
Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation (2022) · Introduction · 0.98
-
Followed Theorem 6 of this paper for its main algorithm and the correctness of its results.
Fullqubit alchemist: Quantum algorithm for alchemical free energy calculations (2025) · 0.88 · paraphrased: the licence does not allow quoting
-
Utilized the quantum algorithm for calculating matrix eigenvalues devised in this paper.
Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation (2024) · 1.00 · paraphrased: the licence does not allow quoting
-
Second, we use the method of [ref] to project into the ground state; this has complexity $O(1/δ') = O(1)$.
Nearly-frustration-free ground state preparation (2021) · Projecting to the Ground State · 1.00
-
Applied this paper's low-energy state preparation algorithm to an extended 2n-qubit Hamiltonian.
An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians (2026) · 0.99 · paraphrased: the licence does not allow quoting
-
Approached EE with the filtering method developed in this paper, relying on the general theory for quantum singular value transformations.
Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations (2022) · 1.00 · paraphrased: the licence does not allow quoting
-
We complement our quantum hardness results with classical containment results (of the classically guidable local Hamiltonian problem), obtained through a deterministic dequantized version of Lin and Tong's ground state energy estimation algorithm [ref] .
Guidable Local Hamiltonian Problems with Implications to Heuristic Ans\"atze State Preparation and the Quantum PCP Conjecture (2023) · Completeness results for the guidable local Hamiltonian problem · 0.93
Compares with it 3 of 14 papers with this label · 1 by the same authors
-
Noted that its scaling achieves the optimal Delta-scaling but, unlike this paper's algorithm, assumes no lower bound for the spectral gap and employs unitary time evolution through Trotterization instead of block-encoding.
Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering (2024) · 0.83 · paraphrased: the licence does not allow quoting
-
We analytically show that while our method exhibits a quadratic query complexity scaling $𝒪(Δ^-2)$—inferior to the linear scaling of Chebyshev-based QSVT [ref] —it offers a practical advantage by eliminating the need for block-encoding and variational optimization.
Deterministic Ground State Preparation via Power-Cosine Filtering of Time Evolution Operators (2026) · Introduction · 1.00
By the same authors
-
Although our algorithm has a near-optimal dependence on the precision, the dependence on $p_0$ (more precisely, on its lower bound $η$), which scales as $p_0^-2$ in Corollary [ref], is far from optimal compared to the $p_0^-1/2$ scaling in Refs. [ref] .
Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers (2021) (same authors) · Discussions · 1.00
How the literature uses it
24 arXiv papers cite this in 57 sentences
Papers citing it · 36 sentences without a confident label
Builds on it 1 paper
-
However, this problem is easily fixed by modifying one of the proofs in [ref] ; see Section [ref] for details.
Fast digital methods for adiabatic state preparation · Techniques for Algorithm [ref] · 0.82
Uses its method or tool 2 papers
-
Instead, we combine the algorithm of Lin and Tong [ref] with time-dependent Hamiltonian simulation [ref] .
Fast digital methods for adiabatic state preparation · Techniques for Algorithm [ref] · 0.91
-
Our technique can essentially be viewed as a dequantization of Lin and Tong's ground state energy estimation algorithm [ref] : here one assumes access to a unitary $U_H$ that implements a block-encoding of $H$.
Guidable Local Hamiltonian Problems with Implications to Heuristic Ans\"atze State Preparation and the Quantum PCP Conjecture · Overview of techniques · 0.97
Compares with it 3 papers
-
Algorithm [ref] essentially combines the approach of [ref] , which assumes access to a oracle that prepares an initial state with bounded overlap with the ground state, with an explicit procedure for this initial state preparation.
Fast digital methods for adiabatic state preparation · Faster preparation of ground states · 0.82
-
For ground-state preparation, we showed that, for $α=Θ(1)$, the joint dependence $1/(γΔ)$ on the initial overlap $γ$ and the spectral gap $Δ$ is unavoidable for a simple diagonal marked family, complementing QSVT-based eigenstate-filtering results [ref] .
Sample-Query Interconversion of Block Encoding of Unknown Quantum States · Conclusion · 0.87
-
Their setting is slightly different from ours, they focus on preparing the ground state[Because generalized maximum-finding (Lemma [ref]) actually outputs a state in addition to an estimate, our algorithms can be modified to also output a state that is close to the top eigenspace of $U$.] of a given Hamiltonian without a known bound on its spectrum, but [ref] implies a cost-$O(log(1/γ)log(1/δ)loglog(1/δ)/γδ)$ algorithm for our row 8.
Tight Bounds for Quantum Phase Estimation and Related Problems · Phase estimation with advice · 0.80
Cites it as background 3 papers
-
The block-encoding model has been proven useful for a variety of tasks, including phase estimation [ref] and ground-state preparation [ref] , and combined with quantum singular-value transformation unifies many quantum algorithms [ref] .
Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State · Our results · 0.97
-
Since then, various quantum simulation algorithms have been developed [ref] , with potential applications in studying condensed matter physics [ref] , quantum chemistry [ref] , quantum field theories [ref] , superstring/M-theory [ref] , as well as in designing other classical [ref] and quantum algorithms [ref] .
Nearly tight Trotterization of interacting electrons · Introduction · 0.99
-
It is well known that the spectral gap $γ(H)$, that is the difference between the energies of the ground state and the first excited state of $H$, plays an important role in how difficult this problem is [ref] .
Lower Bounds for Unitary Property Testing with Proofs and Advice · Ground state preparation of spectrally-gapped Hamiltonians · 0.97
What it cites · 5 sentences without a confident label
Cites as background 5 papers
-
Other such algorithms include quantum imaginary-time evolution, quantum Lanczos [ref] , and quantum filter diagonalization [ref] .
Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution · Introduction · 0.97
-
Other such algorithms include quantum imaginary-time evolution, quantum Lanczos [ref] , and quantum filter diagonalization [ref] .
Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation · Introduction · 0.97
-
Other such algorithms include quantum imaginary-time evolution, quantum Lanczos [ref] , and quantum filter diagonalization [ref] .
A Multireference Quantum Krylov Algorithm for Strongly Correlated Electrons · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.