Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry
Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi‐Hao Cui, Wenyuan Liu, Michael J. Kastoryano, Ryan Babbush, John P. Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, Garnet Kin‐Lic Chan
Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem.
Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem.
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 nonheuristic methods being developed, it is challenging to assess what combination of these methods will ultimately be used in practice. One important metric for assessing utility is the runtime, which depends on the ground-state preparation (GSP) for most GSEE algorithms. 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 method. We introduce a criterion 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 molecule to larger systems like jellium. In the future, this approach may be used to abandon certain variational quantum eigensolver (VQE) ansatzes and other heuristics. Yet our findings do not provide evidence against using 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.
In ab-initio quantum chemistry, solving the electronic structure problem of a molecular system of interest to obtain an approximation of the ground and, in some cases, the excited state energies is a core and central task in various quantum chemistry processes. These include, but certainly not limited to, the calculation of the activation energy–that is the minimal energy required to launch a given chemical reaction–, the dipole and multipole moments which describe the polarity of the molecule, performing the optimization of the geometry of the molecule and searching for transition states. Furthermore, many quantum chemistry applications are predicated, not merely on the approximation of the ground state energy, but also on the corresponding first order derivatives. The body of literature of classical algorithms approximating the ground state energy and its first order derivative is extensively rich with a plethora of methods such as self-consistent mean-field methods, coupled-cluster methods, density matrix renormalization group and many more, each of which has intrinsic set of properties and characteristics that makes it suitable for specific tasks and cases. However, classical methods face a practically insurmountable challenge: the efficient computation of high accuracy approximation of ground state energies of large system sizes. This is fundamentally because the electronic structure problem provably belongs to the complexity class of QMA-hard problems. Which also means that it is out of reach for quantum algorithms as well in general. However, with certain assumptions that are expected to hold molecules of interest–that so far proved to be classically challenging because the required accuracy set by the standard of chemical accuracy threshold (generally held in quantum chemistry)– quantum algorithms can efficiently treat such cases. While originally theorized by Richard Feynmann as a potentially efficient way of simulating some classically intractable many-body systems, quantum computing has since proven to have a stronger and richer potential paving the way for the inception of new algorithms such as Shor’s algorithm for integer factorization, HHL for solving linear system of equation and Grover’s algorithm for constrained binary search, just to name a few. These algorithms provably exhibit an improvement rate that goes respectively exponentially and quadratically in the time complexity. Quantum chemistry is considered a prominent candidate to benefit from quantum computing given the variety of quantum algorithms put forth to solve the electronic structure problem of particular systems of interest. These quantum algorithm proposals can be broadly categorized in three main categories that span the spectrum: from noisy intermediate scale quantum (NISQ) computers to early and full scale fault tolerant quantum ((E)FTQC) computers. Firstly, the variational quantum eigensolver (VQE) family of quantum algorithms which variationally search for the ground state energy through the optimization of the energy of a parametrized state prepared in a quantum computer using an ansatz. Secondly, the quantum Krylov subspace diagonalization (QKSD) methods, which generate a subspace of the original Hilbert space and efficiently produce the lowest energy in said subspace as its output. Lastly, we have the quantum phase estimation (QPE) algorithms, which provably produce the ground state energy in Heisenberg scaling presenting hence a provable efficient solution. In this thesis, we firstly set to work on the problem of efficient Hamiltonian linear combination of unitaries (LCU) representation. This is mainly motivated by the wide-range impact an efficient compression of the Hamiltonian can potentially have on several quantum algorithms such as VQE, QPE...etc. We designed a method that efficiently compress the Hamiltonian representation in a way that is beneficially impactful across the set of the aforementioned quantum algorithms. Namely, we motivate and present in Sections 1.3 and 1.4 respectively, the regularized compressed double-factorization (RC-DF) and show how it reduces the energy measurement complexity both in terms of number of distinct observables and number of samples. Moreover, it also reduces the total depth of the quantum phase estimation circuit thanks to its low normalization factor. Secondly, given the importance of the energy derivatives, in Sections 2.1 and 2.2, we introduce and present an efficient quantum algorithm for the calculation of the analytic gradient of VQE energies of double-factorized Hamiltonians. Furthermore, in Section 2.1, we expand on the utility of RC-DF by presenting a quantum algorithm that determines the analytic gradient of energies measured with respect to RC-DF Hamiltonains. Third, in Section 3.1, we summarize the theoretical results of purification error-mitigation techniques, namely echo verification and virtual distillation. In Section 3.2, we report on the results of the experimental bench mark, of said techniques, performed on on Google’s Sycamore device to validate the theoretical scaling of error suppression and extrapolate the resources needed for classically intractable system sizes. Fourth, in Section 4 we establish the challenges of computing energy gradients in a quantum Krylov frame work. To overcome the problem, we provide, in Section 4.3, an efficient quantum algorithm for calculating energy derivative obtained through QKSD procedures. Our approach shows how the QKSD ground state can be prepared using quantum signal processing (QSP) and reduces the number of observables to O(1) per reduced density matrix (RDM). Lastly, in light of the importance of quantum RAMs due to their utility in a variety of quantum algorithms that require efficient initial state preparation, as explained in Section 5.5, we address the problematic exponential depth of the bucket-brigade QRAM (when decomposed). We present in Section 5.6 a very efficient Clifford+T decomposition of the bucket-brigade QRAM, which preserves the linear scaling of the depth of the circuit without introducing any additional ancilla.
At the heart of quantum chemistry and materials science lies the critical task of estimating ground-state properties. We present a quantum algorithm for this task by quantizing the density-functional theory (DFT). A key aspect of imple-menting DFT faithfully is the requirement for self-consistent calculations, which involve repeated di-agonalizations of the Hamiltonian. This procedure, however, creates a significant bottleneck, as a classical algorithm generally demands a computational complexity that grows cubically with the number of electrons, restricting the scalability of DFT for tackling large-scale problems that involve complex chemical environments and microstructures. This article presents the first quantum algorithm that has provided substantial speedup for the ground state computation, by improving the complexity to one with a linear scaling with the number of atoms. The algorithm leverages the exponential speedup by the quantum singular value transformation to generate a quantum circuit to encode the density-matrix, followed by an efficient estimation method for the output electron density, which constitutes a simple hybrid approach for achieving self-consistency. Moreover, the algorithm produces the ground state Hamiltonian, from which the ground state energy and band structures can be efficiently computed. The proposed framework is accompanied by a rigorous error analysis that establishes the convergence and quantifies various sources of error and the overall computational complexity. The combination of effi-ciency and precision opens new avenues for exploring large-scale physical systems.
Quantum algorithms for ground-state energy estimation of chemical systems require a high-quality initial state. However, initial state preparation is commonly either neglected entirely, or assumed to be solved by a simple product state like Hartree-Fock. Even if a nontrivial state is prepared, strong correlations render ground-state overlap inadequate for quality assessment. In this work, we address the initial state preparation problem with an end-to-end algorithm that and the quality of initial states, accomplishing the latter with a new metric—the energy distribution. To be able to prepare more complicated initial states, we introduce an implementation technique for states in the form of a sum of Slater determinants that exhibits significantly better scaling than all prior approaches. We also propose low-precision quantum phase estimation (QPE) for further state quality refinement. The complete algorithm is capable of generating high-quality states for energy estimation, and is shown in select cases to lower the overall estimation cost by several orders of magnitude when compared with the best single product state ansatz. More broadly, the energy distribution picture suggests that the goal of QPE should be reinterpreted as generating improvements compared to the energy of the initial state and other classical estimates: such an improvement can still be achieved even if QPE does not project directly onto the ground state. Finally, we show how the energy distribution can help in identifying potential quantum advantage. Published by the American Physical Society 2024
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.
Quantum simulation is widely regarded as one of the most promising routes to genuine quantum advantage, yet most existing approaches to quantum chemistry are formulated in terms of closed-system, unitary dynamics and ground-state preparation within the Born--Oppenheimer approximation. In this review, we discuss a broader perspective motivated by the observation that naturally occurring quantum systems are rarely isolated and often reach physically relevant states only through relaxation, decoherence, and thermalization. We first examine what is and is not known about exponential quantum advantage in chemistry, emphasizing that coherent Hamiltonian simulation provides the clearest formal case for speed-up, while many open questions remain for realistic problems. We then discuss how dissipation might ideally be integrated into quantum chemistry on a fault-tolerant quantum computer, using recent proposals for chemically motivated dynamical simulation as a guiding vision. More generally, we highlight the practical appeal of this approach to enhancing the robustness of quantum algorithms.