The most advanced techniques using fault-tolerant quantum computers to estimate the ground-state energy of a chemical Hamiltonian involve compression of the Coulomb operator through tensor factorizations, enabling efficient block encodings of the Hamiltonian. A natural challenge of these methods is the degree to which block-encoding costs can be reduced. We address this challenge through the technique of spectral amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectral amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor Λ to just 2 Λ E gap , where E gap ≪ Λ is the lowest energy of the sum-of-squares Hamiltonian. To achieve this, we show that sum-of-squares representations of the electronic structure Hamiltonian are efficiently computable by a family of classical simulation techniques that approximate the ground-state energy from below. In order to further optimize, we also develop a novel factorization that provides a trade-off between the two leading Coulomb integral factorization schemes—namely, double factorization and tensor hypercontraction—that when combined with spectral amplification yields a factor of 4 to 195 speedup over the state of the art in ground-state energy estimation for models of iron-sulfur complexes and a CO 2 -fixation catalyst.
The most advanced techniques using fault-tolerant quantum computers to estimate the ground-state energy of a chemical Hamiltonian involve compression of the Coulomb operator through tensor factorizations, enabling efficient block encodings of the Hamiltonian. A natural challenge of these methods is the degree to which block-encoding costs can be reduced. We address this challenge through the technique of spectral amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectral amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor Λ to just 2 Λ E gap , where E gap ≪ Λ is the lowest energy of the sum-of-squares Hamiltonian. To achieve this, we show that sum-of-squares representations of the electronic structure Hamiltonian are efficiently computable by a family of classical simulation techniques that approximate the ground-state energy from below. In order to further optimize, we also develop a novel factorization that provides a trade-off between the two leading Coulomb integral factorization schemes—namely, double factorization and tensor hypercontraction—that when combined with spectral amplification yields a factor of 4 to 195 speedup over the state of the art in ground-state energy estimation for models of iron-sulfur complexes and a CO 2 -fixation catalyst.
We demonstrate an asymptotic gate complexity improvement in first-quantized ground-state energy estimation of electronic structure Hamiltonians in a plane wave basis by employing the sum-of-squares spectral gap amplification protocol. The improvement relies on identifying a sum-of-squares representation of the Hamiltonian which provides a lower bound certificate and low cost block encoding that leads to a provably lower quantum phase estimation gate cost. This is achieved by using a sum-of-squares operator generated by the total charge density operator resulting in a block encoding normalization improvement of λ=O(ηΔ−1.5+η1.5Δ−1) compared to prior work λ=O(ηΔ−2+η2Δ−1) where η is the number of electrons and Δ is the simulation grid spacing. The asymptotic reduction in block encoding normalization and similar block encoding costs to prior work is demonstrated to reduce resource estimates for materials and chemical systems by a factor of 2−44× corresponding to the lowest cost estimates for ab initio materials simulation.
We present sum-of-squares spectral amplification (SOSSA), a framework for improving quantum simulation relevant to low-energy problems. We show how SOSSA can be applied to problems like energy and phase estimation and provide fast quantum algorithms for these problems that significantly improve over prior art. To illustrate the power of SOSSA in applications, we consider the Sachdev-Ye-Kitaev model, a representative strongly correlated system, and demonstrate asymptotic speedups over generic simulation methods by a factor of the square root of the system size. Our results reinforce those observed in [G. H. Low et al., arXiv:2502.15882], where SOSSA was used to achieve state-of-the-art gate costs for phase estimation of real-world quantum chemistry systems.
We describe quantum circuits with only O(N ) Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary (e.g., molecular) orbitals.With O(λ/ ) repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of Hamiltonian coefficients and is the target precision.This is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis.Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can work only with orthogonal-basis functions diagonalizing the Coloumb operator (e.g., the plane-wave dual basis).Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a nonorthogonal basis defined by the THC factors.We then use qubitization to simulate the nonorthogonal THC Hamiltonian, in a fashion that avoids most complications of the nonorthogonal basis.We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work.In addition to having lower asymptotic scaling space-time volume, compilation of our algorithm for challenging finitesized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach.By laying out and optimizing the surface-code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under 4 days of runtime, assuming 1-μs cycle times and physical gate-error rates no worse than 0.1%.
While most work on the quantum simulation of chemistry has focused on computing energy surfaces, a similarly important application requiring subtly different algorithms is the computation of energy derivatives. Almost all molecular properties can be expressed an energy derivative, including molecular forces, which are essential for applications such as molecular dynamics simulations. Here, we introduce new quantum algorithms for computing molecular energy derivatives with significantly lower complexity than prior methods. Under cost models appropriate for noisy-intermediate scale quantum devices, we demonstrate how low-rank factorization and other tomography schemes can be optimized for energy derivative calculations. We numerically demonstrate that our techniques reduce the number of circuit repetitions required by many orders of magnitude for even modest systems, and that the cost of estimating an entire force vector may in some systems be lower than the cost of estimating the energy. In the context of fault-tolerant algorithms, we develop new methods of estimating energy derivatives with Heisenberg limited scaling, incorporating state-of-the-art techniques for block encoding fermionic operators. In contrast to our near-term results, we find that the cost of estimating forces with any of our Heisenberg-limited methods is bounded by the cost of estimating energies, due to inner loops requiring either energy estimation or reflections around the ground state. This implies that applications such as geometry optimization, coupling parameter estimation, and spectral prediction may be practical on fault-tolerant quantum devices, but tractable molecular dynamics simulations of large-scale systems requires further algorithmic advances.
Accurately predicting the properties of molecules and materials from first principles requires solving the electronic structure problem. However, the computational cost of solving the electronic structure problem scales prohibitively in the number of atoms, and the usual approximate methods designed to reduce the overhead are often inaccurate for strongly correlated systems. For this reason, quantum algorithms have been developed as a promising alternative. In this work, we develop algebraic tools to improve the efficiency of three quantum algorithms for the electronic structure problem, addressing key bottlenecks for both near-term and fault-tolerant quantum computers. The first is the variational quantum eigensolver (VQE), which suffers from a large measurement overhead needed to estimate the Hamiltonian expectation value. To this end, we introduce a general class of measurable fragments of the electronic Hamiltonian, which enable partitioning schemes that significantly reduce the sampling cost for energy estimation. The second are quantum subspace methods (QSMs). We introduce a new QSM, the quantum seniority-based subspace expansion algorithm, which is a scalable alternative to VQE that alleviates VQE's state preparation, measurement, and optimization challenges while reducing qubit requirements. The third is quantum phase estimation (QPE), which requires an encoding of the electronic Hamiltonian directly on the quantum computer, the cost of which scales indirectly with the Hamiltonian spectral range. To address this, we develop linear programming approaches to implement the Block Invariant Symmetry Shift protocol, a method which reduces the spectral range of the Hamiltonian, improving its block-encoding cost for QPE. Collectively, these methods demonstrate that one can exploit the Hamiltonian's algebraic structure to mitigate computational costs, accelerating the path toward practical quantum advantage for electronic structure.
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.