Solving for quantum ground states is important for understanding the properties of quantum many-body systems, and quantum computers are potentially well-suited for solving for quantum ground states. Recent work [1] has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as δ−1 , i.e. inversely with their normalized gap. Here we consider instead the ground state preparation problem restricted to a special subset of Hamiltonians, which includes those which we term "nearly-frustration-free": the class of Hamiltonians for which the ground state energy of their block-encoded and hence normalized Hamiltonian α−1H is within δy of -1, where δ is the spectral gap of α−1H and 0≤y≤1 . For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as δy/2−1 , and show that this new dependence is optimal up to factors of logδ . In addition, we give examples of physically motivated Hamiltonians which live in this subclass. Finally, we describe an extension of this method which allows the preparation of excited states both for generic Hamiltonians as well as, at a similar speedup as the ground state case, for those which are nearly frustration-free.
Solving for quantum ground states is important for understanding the properties of quantum many-body systems, and quantum computers are potentially well-suited for solving for quantum ground states. Recent work [1] has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as δ−1 , i.e. inversely with their normalized gap. Here we consider instead the ground state preparation problem restricted to a special subset of Hamiltonians, which includes those which we term "nearly-frustration-free": the class of Hamiltonians for which the ground state energy of their block-encoded and hence normalized Hamiltonian α−1H is within δy of -1, where δ is the spectral gap of α−1H and 0≤y≤1 . For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as δy/2−1 , and show that this new dependence is optimal up to factors of logδ . In addition, we give examples of physically motivated Hamiltonians which live in this subclass. Finally, we describe an extension of this method which allows the preparation of excited states both for generic Hamiltonians as well as, at a similar speedup as the ground state case, for those which are nearly frustration-free.
Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian H only through queries to UH and its inverse UH†, where ∥H∥≤αH and τ=Θ(1/αH). Given an input state with ground-state weight at least η and a spectral gap of H of at least γ, our first algorithm uses fresh copies of the input state and requires O(αH/(γη)) queries to UH and UH†, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O(αH/(γη)). The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state ∣ψ⟩ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
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.
We determine the optimal query complexity of ground-state preparation to trace-distance error ε when an energy threshold in the spectral gap is known. Let UH be an α-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ for a state-preparation oracle UI. The threshold lies at least Δ/2 above the ground-state energy and at least Δ/2 below every excited-state energy. We give two algorithms that prepare a state within trace distance ε of the ground state. One uses O((α/Δ)(γ−1+log(1/ε))) calls to UH in expectation; the other uses O((α/(γΔ))log(1/ε)) calls to UH in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to UI are O(1/γ) in expectation and O(γ−1log(1/ε)) in the worst case. On (N+1)-dimensional systems, these UI bounds are also optimal when the expected or worst-case count of UH calls, respectively, is o((α/Δ)N). Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.
Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of M terms, this approach reduces the cost by a factor of O(M). We also combine the detectability lemma operator and quantum singular value transformation to implement ground state projection operators of frustration-free Hamiltonians, resulting in a quadratic speedup in the spectral gap dependence. Applying this method to Lindbladians for the Gibbs state of local commuting Hamiltonians, we achieve quadratically better dependence on the Lindbladian spectral gap.
We propose quantum algorithms for projective ground-state preparation and calculations of the many-body Green's functions directly in frequency domain. The algorithms are based on the linear combination of unitary (LCU) operations and essentially only use quantum resources. To prepare the ground state, we construct the operator exp(−τH^2) using Hubbard-Stratonovich transformation by LCU and apply it on an easy-to-prepare initial state. Our projective state preparation procedure saturates the near-optimal scaling, O(γΔ1logγη1), of other currently known algorithms, in terms of the spectral-gap lower bound Δ, the additive error η in the state vector, and the overlap lower bound γ between the initial state and the exact ground state. It is straightforward to combine our algorithm with spectral-gap amplification technique to achieve quadratically improved scaling O(1/Δ) for ground-state preparation of frustration-free Hamiltonians, which we demonstrate with numerical results of the q-deformed XXZ chain. To compute the Green's functions, including the single-particle and other response functions, we act on the prepared ground state with the retarded resolvent operator R(ω+iΓ;H^) in the LCU form derived from the Fourier-Laplace integral transform (FIT). Our resolvent algorithm has O(Γ21logΓε1) complexity scaling for the frequency resolution Γ of the response functions and the targeted error ε, while classical algorithms for FIT usually have polynomial scaling over the error ε. To illustrate the complexity scaling of our algorithms, we provide numerical results for their application to the paradigmatic Fermi-Hubbard model on a one-dimensional lattice with different numbers of sites.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA1 QMA 1 -complete (for k≥3 k ≥ 3 , and where QMA1 QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.