Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2108.03249 · Quantum

Nearly-frustration-free ground state preparation

Matthew Thibodeau, Bryan K. Clark

Published Aug 16, 2023• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2023-08-16-1084

Related papers

Near-Optimal Ground-State Preparation without Controlled Hamiltonian Evolutions

Dhrumil Patel, Steven T. Flammia, Raul Garcia-Patron

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 $U_H$ and its inverse $U_H^\dagger$, where $\|H\|\leα_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 $\widetilde O(α_H/(γη))$ queries to $U_H$ and $U_H^\dagger$, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to $\widetilde O(α_H/(γ\sqrtη))$. 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 $|ψ\rangle$ 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.

quant-pharXiv:2610.00520•Oct 2, 2026•0 citations

Optimal Query Complexity for Ground-State Preparation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. 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 $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ 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 $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt 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.

quant-pharXiv:2609.35668•Sep 29, 2026•1 citation

Near-optimal ground state preparation

Lin Lin, Yu Tong

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.

arXiv:2002.12508•Quantum•Dec 14, 2020•247 citations

On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma

András Gilyén, Or Sattath

A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.

arXiv:1611.08571•Annual Symposium on Foundations of Computer Science•Oct 1, 2017•17 citations

Spectral Gap Amplification

R. D. Somma, S. Boixo

Many problems can be solved by preparing a specific eigenstate of some Hamiltonian $H$. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of $H$ for that eigenstate and the cost of evolving with $H$ for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian $H'$ with the same eigenstate as $H$ but a bigger spectral gap, requiring that constant-time evolutions with $H'$ and $H$ are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when $H$ satisfies a frustration-free property and give $H'$ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.

arXiv:1110.2494•SIAM Journal on Computing•Jan 1, 2013•57 citations

Quantum Algorithms for Ground-State Preparation and Green's Function Calculation

Trevor Keen, Eugene Dumitrescu, Yan Wang

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}(-τ\hat{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, $\mathcal{O}(\frac{1}{γΔ} \log \frac{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 $\mathcal{O}(1/\sqrtΔ)$ 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Γ; \hat{H})$ in the LCU form derived from the Fourier-Laplace integral transform (FIT). Our resolvent algorithm has $\mathcal{O}(\frac{1}{Γ^2} \log\frac{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.

arXiv:2112.05731•Dec 10, 2021•36 citations
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 HHH only through queries to UHU_HUH​ and its inverse UH†U_H^\daggerUH†​, where ∥H∥≤αH\|H\|\leα_H∥H∥≤αH​ and τ=Θ(1/αH)τ=Θ(1/α_H)τ=Θ(1/αH​). Given an input state with ground-state weight at least ηηη and a spectral gap of HHH of at least γγγ, our first algorithm uses fresh copies of the input state and requires O~(αH/(γη))\widetilde O(α_H/(γη))O(αH​/(γη)) queries to UHU_HUH​ and UH†U_H^\daggerUH†​, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O~(αH/(γη))\widetilde O(α_H/(γ\sqrtη))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 ∣ψ⟩|ψ\rangle∣ψ⟩ 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.
We determine the optimal query complexity of ground-state preparation to trace-distance error ε\varepsilonε when an energy threshold in the spectral gap is known. Let UHU_HUH​ be an ααα-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ|\langleψ_0|U_I|0\rangle|\geγ∣⟨ψ0​∣UI​∣0⟩∣≥γ for a state-preparation oracle UIU_IUI​. The threshold lies at least Δ/2Δ/2Δ/2 above the ground-state energy and at least Δ/2Δ/2Δ/2 below every excited-state energy. We give two algorithms that prepare a state within trace distance ε\varepsilonε of the ground state. One uses O((α/Δ)(γ−1+log⁡(1/ε)))O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))O((α/Δ)(γ−1+log(1/ε))) calls to UHU_HUH​ in expectation; the other uses O((α/(γΔ))log⁡(1/ε))O((α/(γΔ))\log(1/\varepsilon))O((α/(γΔ))log(1/ε)) calls to UHU_HUH​ 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 UIU_IUI​ are O(1/γ)O(1/γ)O(1/γ) in expectation and O(γ−1log⁡(1/ε))O(γ^{-1}\log(1/\varepsilon))O(γ−1log(1/ε)) in the worst case. On (N+1)(N+1)(N+1)-dimensional systems, these UIU_IUI​ bounds are also optimal when the expected or worst-case count of UHU_HUH​ calls, respectively, is o((α/Δ)N)o((α/Δ)\sqrt N)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.
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.
A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.
Many problems can be solved by preparing a specific eigenstate of some Hamiltonian HHH. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of HHH for that eigenstate and the cost of evolving with HHH for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H′H'H′ with the same eigenstate as HHH but a bigger spectral gap, requiring that constant-time evolutions with H′H'H′ and HHH are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when HHH satisfies a frustration-free property and give H′H'H′ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.
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){\exp}(-τ\hat{H}^2)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(1γΔlog⁡1γη)\mathcal{O}(\frac{1}{γΔ} \log \frac{1}{γη})O(γΔ1​logγη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/Δ)\mathcal{O}(1/\sqrtΔ)O(1/Δ​) for ground-state preparation of frustration-free Hamiltonians, which we demonstrate with numerical results of the qqq-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^)R(ω+ iΓ; \hat{H})R(ω+iΓ;H^) in the LCU form derived from the Fourier-Laplace integral transform (FIT). Our resolvent algorithm has O(1Γ2log⁡1Γε)\mathcal{O}(\frac{1}{Γ^2} \log\frac{1}{Γε})O(Γ21​logΓε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.