Quantum computers will enable high-accuracy quantum simulations of physical systems, provided that states with reasonable overlap with the ground state can be efficiently prepared. In this Letter, the authors articulate conditions in which quadratic runtime speedups are plausible for ground-state energy estimation by translating a near-optimal ground-state preparation scheme into explicit circuits and estimating the cost in a model relevant to their fault-tolerant implementation.
Quantum computers will enable high-accuracy quantum simulations of physical systems, provided that states with reasonable overlap with the ground state can be efficiently prepared. In this Letter, the authors articulate conditions in which quadratic runtime speedups are plausible for ground-state energy estimation by translating a near-optimal ground-state preparation scheme into explicit circuits and estimating the cost in a model relevant to their fault-tolerant implementation.
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.
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.
One promising field of quantum computation is the simulation of quantum systems, and specifically, the task of ground state energy estimation (GSEE). Ground state preparation (GSP) is a crucial component in GSEE algorithms, and classical methods like Hartree-Fock state preparation are commonly used. However, the efficiency of such classical methods diminishes exponentially with increasing system size in certain cases. In this study, we investigated whether in those cases quantum heuristic GSP methods could improve the overlap values compared to Hartree-Fock. Moreover, we carefully studied the performance gain for GSEE algorithms by exploring the trade-off between the overlap improvement and the associated resource cost in terms of T-gates of the GSP algorithm. Our findings indicate that quantum heuristic GSP can accelerate GSEE tasks, already for computationally affordable strongly-correlated systems of intermediate size. These results suggest that quantum heuristic GSP has the potential to significantly reduce the runtime requirements of GSEE algorithms, thereby enhancing their suitability for implementation on quantum hardware.
Quantum computing is believed to be particularly useful for the simulation of chemistry and materials, among the various applications. In recent years, there have been significant advancements in the development of near-term quantum algorithms for quantum simulation, including VQE and many of its variants. However, for such algorithms to be useful, they need to overcome several critical barriers including the inability to prepare high-quality approximations of the ground state. Current challenges to state preparation, including barren plateaus and the high-dimensionality of the optimization landscape, make state preparation through ansatz optimization unreliable. In this work, we introduce the method of ground state boosting, which uses a limited-depth quantum circuit to reliably increase the overlap with the ground state. This circuit, which we call a booster, can be used to augment an ansatz from VQE or be used as a stand-alone state preparation method. The booster converts circuit depth into ground state overlap in a controllable manner. We numerically demonstrate the capabilities of boosters by simulating the performance of a particular type of booster, namely the Gaussian booster, for preparing the ground state of N2 molecular system. Beyond ground state preparation as a direct objective, many quantum algorithms, such as quantum phase estimation, rely on high-quality state preparation as a subroutine. Therefore, we foresee ground state boosting and similar methods as becoming essential algorithmic components as the field transitions into using early fault-tolerant quantum computers.
While ground-state preparation is expected to be a primary application of quantum computers, it is also an essential subroutine for many fault-tolerant algorithms. In early fault-tolerant regimes, logical measurements remain costly, motivating adaptive, shot-frugal state-preparation strategies that efficiently utilize each measurement. We introduce the Shadow Enhanced Greedy Quantum Eigensolver (SEGQE) as a greedy, shadow-assisted framework for measurement-efficient ground-state preparation. SEGQE uses classical shadows to evaluate, in parallel and entirely in classical post-processing, the energy reduction induced by large collections of local candidate gates, greedily selecting at each step the gate with the largest estimated energy decrease. We derive rigorous worst-case per-iteration sample-complexity bounds for SEGQE, exhibiting logarithmic dependence on the number of candidate gates. Numerical benchmarks on finite transverse-field Ising models and ensembles of random local Hamiltonians demonstrate convergence in a number of iterations that scales approximately linearly with system size, while maintaining high-fidelity ground-state approximations and competitive energy estimates. Together, our empirical scaling laws and rigorous per-iteration guarantees establish SEGQE as a measurement-efficient state-preparation primitive well suited to early fault-tolerant quantum computing architectures.
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.