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:2112.05731

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

Trevor Keen, Eugene Dumitrescu, Yan Wang

Published Dec 10, 2021• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2112.05731

Related papers

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•189 citations

Computing Green's functions and improving ground state energy estimation on quantum computers with Liouvillian recursion

Jérôme Leblanc, Olivier Nahman-Lévesque, Julien Forget +3 more

We present a quantum-classical hybrid implementation of the Liouvillian recursion method to compute many-body Green's functions using a quantum computer. From an approximate ground state preparation circuit, this algorithm produces the local ($r=r'$) and inter-site ($r\neq r'$) Green's functions $G_{rr'}(ω)$ by measuring observables generated recursively. We demonstrate the approach on a superconducting quantum processor for the open-boundary four-site Hubbard model. We then use the computed Green's functions as input to the Galitskii-Migdal formula to produce better ground state energy estimation than the expectation value of the Hamiltonian for the approximate circuit. Empirical results indicate exponential convergence in the number of iterations, yielding a computational complexity polynomial in the Green's-function accuracy, as measured with the Wasserstein distance. Our results also indicate significant robustness to noise and to inaccuracies of the ground state preparation, providing evidence that Liouvillian recursion is well adapted to the constraints of near-term quantum computing.

quant-pharXiv:2603.05349•Mar 6, 2026•0 citations

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

Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded Hamiltonian evolution

Yulong Dong, Lin Lin

The preparation of the ground state of a Hamiltonian $H$ with a large spectral radius has applications in many areas such as electronic structure theory and quantum field theory. Given an initial state with a constant overlap with the ground state, and assuming that the Hamiltonian $H$ can be efficiently simulated with an ideal fast-forwarding protocol, we first demonstrate that employing a linear combination of unitaries (LCU) approach can prepare the ground state at a cost of $\mathcal{O}(\log^2(\|H\| Δ^{-1}))$ queries to controlled Hamiltonian evolution. Here $\|H\|$ is the spectral radius of $H$ and $Δ$ the spectral gap. However, traditional Quantum Signal Processing (QSP)-based methods fail to capitalize on this efficient protocol, and its cost scales as $\mathcal{O}(\|H\| Δ^{-1})$. To bridge this gap, we develop a multi-level QSP-based algorithm that exploits the fast-forwarding feature. This novel algorithm not only matches the efficiency of the LCU approach when an ideal fast-forwarding protocol is available, but also exceeds it with a reduced cost that scales as $\mathcal{O}(\log(\|H\| Δ^{-1}))$. Additionally, our multi-level QSP method requires only $\mathcal{O}(\log(\|H\| Δ^{-1}))$ coefficients for implementing single qubit rotations. This eliminates the need for constructing the PREPARE oracle in LCU, which prepares a state encoding $\mathcal{O}(\|H\| Δ^{-1})$ coefficients regardless of whether the Hamiltonian can be fast-forwarded.

arXiv:2406.02086•Jun 4, 2024•0 citations

Nearly-frustration-free ground state preparation

Matthew Thibodeau, Bryan K. Clark

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.

arXiv:2108.03249•Quantum•Aug 16, 2023•6 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•0 citations
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.
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 present a quantum-classical hybrid implementation of the Liouvillian recursion method to compute many-body Green's functions using a quantum computer. From an approximate ground state preparation circuit, this algorithm produces the local (r=r′r=r'r=r′) and inter-site (r≠r′r\neq r'r=r′) Green's functions Grr′(ω)G_{rr'}(ω)Grr′​(ω) by measuring observables generated recursively. We demonstrate the approach on a superconducting quantum processor for the open-boundary four-site Hubbard model. We then use the computed Green's functions as input to the Galitskii-Migdal formula to produce better ground state energy estimation than the expectation value of the Hamiltonian for the approximate circuit. Empirical results indicate exponential convergence in the number of iterations, yielding a computational complexity polynomial in the Green's-function accuracy, as measured with the Wasserstein distance. Our results also indicate significant robustness to noise and to inaccuracies of the ground state preparation, providing evidence that Liouvillian recursion is well adapted to the constraints of near-term quantum computing.
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.
The preparation of the ground state of a Hamiltonian HHH with a large spectral radius has applications in many areas such as electronic structure theory and quantum field theory. Given an initial state with a constant overlap with the ground state, and assuming that the Hamiltonian HHH can be efficiently simulated with an ideal fast-forwarding protocol, we first demonstrate that employing a linear combination of unitaries (LCU) approach can prepare the ground state at a cost of O(log⁡2(∥H∥Δ−1))\mathcal{O}(\log^2(\|H\| Δ^{-1}))O(log2(∥H∥Δ−1)) queries to controlled Hamiltonian evolution. Here ∥H∥\|H\|∥H∥ is the spectral radius of HHH and ΔΔΔ the spectral gap. However, traditional Quantum Signal Processing (QSP)-based methods fail to capitalize on this efficient protocol, and its cost scales as O(∥H∥Δ−1)\mathcal{O}(\|H\| Δ^{-1})O(∥H∥Δ−1). To bridge this gap, we develop a multi-level QSP-based algorithm that exploits the fast-forwarding feature. This novel algorithm not only matches the efficiency of the LCU approach when an ideal fast-forwarding protocol is available, but also exceeds it with a reduced cost that scales as O(log⁡(∥H∥Δ−1))\mathcal{O}(\log(\|H\| Δ^{-1}))O(log(∥H∥Δ−1)). Additionally, our multi-level QSP method requires only O(log⁡(∥H∥Δ−1))\mathcal{O}(\log(\|H\| Δ^{-1}))O(log(∥H∥Δ−1)) coefficients for implementing single qubit rotations. This eliminates the need for constructing the PREPARE oracle in LCU, which prepares a state encoding O(∥H∥Δ−1)\mathcal{O}(\|H\| Δ^{-1})O(∥H∥Δ−1) coefficients regardless of whether the Hamiltonian can be fast-forwarded.
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.
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.