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:2304.09827 · Physical Review A

Efficient ground-state-energy estimation and certification on early fault-tolerant quantum computers

Guoming Wang, Daniel Stilck França, Gumaro Rendon, Peter D. Johnson

Published Jan 17, 2025• 8 citations
arXivHTMLPDF

Abstract

A major thrust in quantum algorithm development over the past decade has been the search for the quantum algorithms that will deliver practical quantum advantage first. Today's quantum computers---and even early fault-tolerant quantum computers---are limited in the number of operations they can implement per circuit. We introduce quantum algorithms for ground-state-energy estimation (GSEE) that accommodate this design constraint. The first algorithm estimates ground-state energies, offering a quadratic improvement on the ground-state overlap parameter compared to other methods in this regime. The second algorithm certifies that the estimated ground-state energy is within a specified error tolerance of the true ground-state energy, addressing the issue of gap estimation that beleaguers several ground-state preparation and energy estimation algorithms. We note, however, that the scaling of this certification technique is currently less favorable than that of the GSEE algorithm. To develop the certification algorithm, we propose an alternative use of quantum computers to facilitate rejection sampling. After a classical computer generates initial samples, the quantum computer is used to accept or reject these samples, resulting in a set of accepted samples that approximate draws from a target distribution. Although we apply this technique specifically for ground-state-energy certification, it may find broader applications. Our paper pushes the boundaries of what operation-limited quantum computers can achieve, bringing the prospect of quantum advantage closer to realization.

DOI
10.1103/physreva.111.012426

Related papers

Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation

Oriel Kiss, Utkarsh Azad, Borja Requena +3 more

We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems. In particular, we examine the computation of the cumulative distribution function (CDF) of the spectral measure of a Hamiltonian and the identification of its discontinuities. Scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states. To address these challenges, we propose a signal processing approach to find these estimates automatically, in the regime where the quality of the initial state is unknown. Rather than aiming for exact ground-state energy, we advocate for improving classical estimates by targeting the low-energy support of the initial state. Additionally, we provide quantitative resource estimates, demonstrating a constant factor improvement in the number of samples required to detect a specified change in CDF. Our numerical experiments, conducted on a 26-qubit fully connected Heisenberg model, leverage a truncated density-matrix renormalization group (DMRG) initial state with a low bond dimension. The results show that the predictions from the quantum algorithm align closely with the DMRG-converged energies at larger bond dimensions while requiring several orders of magnitude fewer samples than theoretical estimates suggest. These findings underscore that CDF-based quantum algorithms are a practical and resource-efficient alternative to quantum phase estimation, particularly in resource-constrained scenarios.

arXiv:2405.03754•Quantum•Apr 1, 2025•11 citations

Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision

Guoming Wang, Daniel Stilck França, Ruizhe Zhang +2 more

A milestone in the field of quantum computing will be solving problems in quantum chemistry and materials faster than state-of-the-art classical methods. The current understanding is that achieving quantum advantage in this area will require some degree of fault tolerance. While hardware is improving towards this milestone, optimizing quantum algorithms also brings it closer to the present. Existing methods for ground state energy estimation are costly in that they require a number of gates per circuit that grows exponentially with the desired number of bits in precision. We reduce this cost exponentially, by developing a ground state energy estimation algorithm for which this cost grows linearly in the number of bits of precision. Relative to recent resource estimates of ground state energy estimation for the industrially-relevant molecules of ethylene-carbonate and PF 6 − , the estimated gate count and circuit depth is reduced by a factor of 43 and 78, respectively. Furthermore, the algorithm can use additional circuit depth to reduce the total runtime. These features make our algorithm a promising candidate for realizing quantum advantage in the era of early fault-tolerant quantum computing.

arXiv:2209.06811•Quantum•Nov 6, 2023•60 citations

Low-depth Gaussian State Energy Estimation

Gumaro Rendon, Johnson, Peter D.

Recent progress in quantum computing is paving the way for the realization of early fault-tolerant quantum computers. To maximize the utility of these devices, it is important to develop quantum algorithms that match their capabilities and limitations. Motivated by this, recent work has developed low-depth quantum algorithms for ground state energy estimation (GSEE), an important subroutine in quantum chemistry and materials. We detail a new GSEE algorithm which, like recent work, uses a number of operations scaling as $O(1/Δ)$ as opposed to the typical $O(1/ε)$, at the cost of an increase in the number of circuit repetitions from $O(1)$ to $O(1/ε^2)$. The relevant features of this algorithm come about from using a Gaussian window, which exponentially reduces contamination from excited states over the simplest GSEE algorithm based on the Quantum Fourier Transform (QFT). We adapt this algorithm to interpolate between the low-depth and full-depth regime by replacing $Δ$ with anything between $Δ$ and $ε$. At the cost of increasing the number of ancilla qubits from $1$ to $O(\logΔ)$, our method reduces the upper bound on the number of circuit repetitions by a factor of four compared to previous methods.

arXiv:2309.16790•Sep 28, 2023•0 citations

Computing Ground State Properties with Early Fault-Tolerant Quantum Computers

Ruizhe Zhang, Guoming Wang, Peter D. Johnson

Significant effort in applied quantum computing has been devoted to the problem of ground state energy estimation for molecules and materials. Yet, for many applications of practical value, additional properties of the ground state must be estimated. These include Green's functions used to compute electron transport in materials and the one-particle reduced density matrices used to compute electric dipoles of molecules. In this paper, we propose a quantum-classical hybrid algorithm to efficiently estimate such ground state properties with high accuracy using low-depth quantum circuits. We provide an analysis of various costs (circuit repetitions, maximal evolution time, and expected total runtime) as a function of target accuracy, spectral gap, and initial ground state overlap. This algorithm suggests a concrete approach to using early fault tolerant quantum computers for carrying out industry-relevant molecular and materials calculations.

arXiv:2109.13957•Quantum•Jul 11, 2022•47 citations

Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers

Lin Lin, Yu Tong

Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy.However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer.We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure.Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.

arXiv:2102.11340•PRX Quantum•Feb 2, 2022•176 citations

When to Reject a Ground State Preparation Algorithm

Katerina Gratsea, Chong Sun, Johnson, Peter D.

In recent years substantial research effort has been devoted to quantum algorithms for ground state energy estimation (GSEE) in chemistry and materials. Given the many heuristic and non-heuristic methods being developed, it is challenging to assess what combination of these will ultimately be used in practice. One important metric for assessing utility is runtime. For most GSEE algorithms, the runtime depends on the ground state preparation (GSP) method. Towards assessing the utility of various combinations of GSEE and GSP methods, we asked under which conditions a GSP method should be accepted over a reference method, such as the Hartree-Fock state. We introduce a criteria for accepting or rejecting a GSP method for the purposes of GSEE. We consider different GSP methods ranging from heuristics to algorithms with provable performance guarantees and perform numerical simulations to benchmark their performance on different chemical systems, starting from small molecules like the hydrogen atom to larger systems like the jellium. In the future this approach may be used to abandon certain VQE ansatzes and other heursitics. Yet so far our findings do not provide evidence against the use of VQE and more expensive heuristic methods, like the low-depth booster. This work sets a foundation from which to further explore the requirements to achieve quantum advantage in quantum chemistry.

arXiv:2212.09492•Dec 19, 2022•2 citations
A major thrust in quantum algorithm development over the past decade has been the search for the quantum algorithms that will deliver practical quantum advantage first. Today's quantum computers---and even early fault-tolerant quantum computers---are limited in the number of operations they can implement per circuit. We introduce quantum algorithms for ground-state-energy estimation (GSEE) that accommodate this design constraint. The first algorithm estimates ground-state energies, offering a quadratic improvement on the ground-state overlap parameter compared to other methods in this regime. The second algorithm certifies that the estimated ground-state energy is within a specified error tolerance of the true ground-state energy, addressing the issue of gap estimation that beleaguers several ground-state preparation and energy estimation algorithms. We note, however, that the scaling of this certification technique is currently less favorable than that of the GSEE algorithm. To develop the certification algorithm, we propose an alternative use of quantum computers to facilitate rejection sampling. After a classical computer generates initial samples, the quantum computer is used to accept or reject these samples, resulting in a set of accepted samples that approximate draws from a target distribution. Although we apply this technique specifically for ground-state-energy certification, it may find broader applications. Our paper pushes the boundaries of what operation-limited quantum computers can achieve, bringing the prospect of quantum advantage closer to realization.
We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems. In particular, we examine the computation of the cumulative distribution function (CDF) of the spectral measure of a Hamiltonian and the identification of its discontinuities. Scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states. To address these challenges, we propose a signal processing approach to find these estimates automatically, in the regime where the quality of the initial state is unknown. Rather than aiming for exact ground-state energy, we advocate for improving classical estimates by targeting the low-energy support of the initial state. Additionally, we provide quantitative resource estimates, demonstrating a constant factor improvement in the number of samples required to detect a specified change in CDF. Our numerical experiments, conducted on a 26-qubit fully connected Heisenberg model, leverage a truncated density-matrix renormalization group (DMRG) initial state with a low bond dimension. The results show that the predictions from the quantum algorithm align closely with the DMRG-converged energies at larger bond dimensions while requiring several orders of magnitude fewer samples than theoretical estimates suggest. These findings underscore that CDF-based quantum algorithms are a practical and resource-efficient alternative to quantum phase estimation, particularly in resource-constrained scenarios.
A milestone in the field of quantum computing will be solving problems in quantum chemistry and materials faster than state-of-the-art classical methods. The current understanding is that achieving quantum advantage in this area will require some degree of fault tolerance. While hardware is improving towards this milestone, optimizing quantum algorithms also brings it closer to the present. Existing methods for ground state energy estimation are costly in that they require a number of gates per circuit that grows exponentially with the desired number of bits in precision. We reduce this cost exponentially, by developing a ground state energy estimation algorithm for which this cost grows linearly in the number of bits of precision. Relative to recent resource estimates of ground state energy estimation for the industrially-relevant molecules of ethylene-carbonate and PF 6 − , the estimated gate count and circuit depth is reduced by a factor of 43 and 78, respectively. Furthermore, the algorithm can use additional circuit depth to reduce the total runtime. These features make our algorithm a promising candidate for realizing quantum advantage in the era of early fault-tolerant quantum computing.
Recent progress in quantum computing is paving the way for the realization of early fault-tolerant quantum computers. To maximize the utility of these devices, it is important to develop quantum algorithms that match their capabilities and limitations. Motivated by this, recent work has developed low-depth quantum algorithms for ground state energy estimation (GSEE), an important subroutine in quantum chemistry and materials. We detail a new GSEE algorithm which, like recent work, uses a number of operations scaling as O(1/Δ)O(1/Δ)O(1/Δ) as opposed to the typical O(1/ε)O(1/ε)O(1/ε), at the cost of an increase in the number of circuit repetitions from O(1)O(1)O(1) to O(1/ε2)O(1/ε^2)O(1/ε2). The relevant features of this algorithm come about from using a Gaussian window, which exponentially reduces contamination from excited states over the simplest GSEE algorithm based on the Quantum Fourier Transform (QFT). We adapt this algorithm to interpolate between the low-depth and full-depth regime by replacing ΔΔΔ with anything between ΔΔΔ and εεε. At the cost of increasing the number of ancilla qubits from 111 to O(log⁡Δ)O(\logΔ)O(logΔ), our method reduces the upper bound on the number of circuit repetitions by a factor of four compared to previous methods.
Significant effort in applied quantum computing has been devoted to the problem of ground state energy estimation for molecules and materials. Yet, for many applications of practical value, additional properties of the ground state must be estimated. These include Green's functions used to compute electron transport in materials and the one-particle reduced density matrices used to compute electric dipoles of molecules. In this paper, we propose a quantum-classical hybrid algorithm to efficiently estimate such ground state properties with high accuracy using low-depth quantum circuits. We provide an analysis of various costs (circuit repetitions, maximal evolution time, and expected total runtime) as a function of target accuracy, spectral gap, and initial ground state overlap. This algorithm suggests a concrete approach to using early fault tolerant quantum computers for carrying out industry-relevant molecular and materials calculations.
Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy.However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer.We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure.Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.
In recent years substantial research effort has been devoted to quantum algorithms for ground state energy estimation (GSEE) in chemistry and materials. Given the many heuristic and non-heuristic methods being developed, it is challenging to assess what combination of these will ultimately be used in practice. One important metric for assessing utility is runtime. For most GSEE algorithms, the runtime depends on the ground state preparation (GSP) method. Towards assessing the utility of various combinations of GSEE and GSP methods, we asked under which conditions a GSP method should be accepted over a reference method, such as the Hartree-Fock state. We introduce a criteria for accepting or rejecting a GSP method for the purposes of GSEE. We consider different GSP methods ranging from heuristics to algorithms with provable performance guarantees and perform numerical simulations to benchmark their performance on different chemical systems, starting from small molecules like the hydrogen atom to larger systems like the jellium. In the future this approach may be used to abandon certain VQE ansatzes and other heursitics. Yet so far our findings do not provide evidence against the use of VQE and more expensive heuristic methods, like the low-depth booster. This work sets a foundation from which to further explore the requirements to achieve quantum advantage in quantum chemistry.