Designing algorithms for estimating ground state properties on early fault-tolerant quantum computers

Simon J. Devitt, Austin G. Fowler, Lloyd C. L. Hollenberg

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.

Andrew M. Steane

Guoming Wang, Daniel Stilck França, Gumaro Rendon +1 more

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.

Gerald N. Gilbert, Yaakov S. Weinstein

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.