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

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 a novel 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 work pushes the boundaries of what operation-limited quantum computers can achieve, bringing the prospect of quantum advantage closer to realization.

The ground-state energy estimation algorithm has been revised and upgraded to a more efficient version. Numerical results have been added to demonstrate its advantage over an alternative method

References in corpus (34)

• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Entanglement-free Heisenberg-limited phase estimation
• Training variational quantum algorithms is NP-hard
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Amplitude estimation without phase estimation
• Accelerated Variational Quantum Eigensolver
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Optimal Quantum Measurements of Expectation Values of Observables
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• How to perform the most accurate possible phase measurements
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• A randomized quantum algorithm for statistical phase estimation
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Minimizing estimation runtime on noisy quantum computers
• Low depth algorithms for quantum amplitude estimation
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Limitations in quantum computing from resource constraints
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• On low-depth algorithms for quantum phase estimation
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• State Preparation Boosters for Early Fault-Tolerant Quantum Computation
• Foundations for Bayesian inference with engineered likelihood functions for robust amplitude estimation

Cited by in corpus (4)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Exponential distillation of dominant eigenproperties