Here we describe an approach for simulating electronic structure on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantized representation of the molecular Hamiltonian, which we propagate using high-order product formulas. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O ˜ ( η ) complexity for a simulation with η particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t ( η 4 / 3 N 1 / 3 + η 1 / 3 N 2 / 3 ) ( η N t / ϵ ) o ( 1 ) gate complexity, where N is the number of grid points, ϵ is target precision, and t is the duration of time evolution. This is roughly a speedup by O ( η ) over most prior algorithms. We provide lower complexity than all prior work for N < η 7 (the regime of practical interest), with only first-quantized interaction-picture simulations providing better performance for N > η 7 . As with the classical fast multipole method, large particle numbers η ≳ 10 3 would be needed to realize this advantage.
Here we describe an approach for simulating electronic structure on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantized representation of the molecular Hamiltonian, which we propagate using high-order product formulas. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O ˜ ( η ) complexity for a simulation with η particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t ( η 4 / 3 N 1 / 3 + η 1 / 3 N 2 / 3 ) ( η N t / ϵ ) o ( 1 ) gate complexity, where N is the number of grid points, ϵ is target precision, and t is the duration of time evolution. This is roughly a speedup by O ( η ) over most prior algorithms. We provide lower complexity than all prior work for N < η 7 (the regime of practical interest), with only first-quantized interaction-picture simulations providing better performance for N > η 7 . As with the classical fast multipole method, large particle numbers η ≳ 10 3 would be needed to realize this advantage.
Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a d -dimensional Schrödinger equation with η particles can be simulated with gate complexity O~(ηdFpoly(log(g′/ϵ))) , where ϵ is the discretization error, g′ controls the higher-order derivatives of the wave function, and F measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on ϵ and g′ from poly(g′/ϵ) to poly(log(g′/ϵ)) and polynomially improves the dependence on T and d , while maintaining best known performance with respect to η . For the case of Coulomb interactions, we give an algorithm using η3(d+η)Tpoly(log(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.
Abstract We present a quantum algorithm for simulating quantum chemistry with gate complexity O~(N1/3η8/3) O ̃ ( N 1 ∕ 3 η 8 ∕ 3 ) where η is the number of electrons and N is the number of plane wave orbitals. In comparison, the most efficient prior algorithms for simulating electronic structure using plane waves (which are at least as efficient as algorithms using any other basis) have complexity O~(N8/3/η2/3) O ̃ ( N 8 ∕ 3 ∕ η 2 ∕ 3 ) . We achieve our scaling in first quantization by performing simulation in the rotating frame of the kinetic operator using interaction picture techniques. Our algorithm is far more efficient than all prior approaches when N ≫ η , as is needed to suppress discretization error when representing molecules in the plane wave basis, or when simulating without the Born-Oppenheimer approximation.
In quantum chemistry, the "electronic structure problem" refers to the process of numerically solving Schrodinger's equation for a given molecular system. These calculations rank among the most CPU-intensive computations that are performed nowadays, yet they are also crucial to the design of new drugs and materials. The idea behind quantum simulation of quantum chemistry is that a quantum computer could perform such calculations in a manner that is exponentially more efficient than what a classical computer could accomplish. In fact, quantum simulation is quite possibly the application most naturally suited to a quantum computer. In this work we introduce novel algorithms for the simulation of quantum chemistry, algorithms that are exponentially more precise than previous algorithms in the literature. Previous algorithms are based on the Trotter-Suzuki decomposition and scale like the inverse of the desired precision, while our algorithms represent the first practical application of the recently developed truncated Taylor series approach, and they achieve scaling that is logarithmic in the inverse of the precision. We explore algorithms for both second-quantized and first-quantized encodings of the chemistry Hamiltonian, where the second-quantized encoding requires mathcalO(N) qubits for an N spin-orbital system, and the highly compressed first-quantized encoding requires mathcalO(eta) qubits, where eta<<N is the number of electrons in the system. We first introduce a second-quantized algorithm that uses pre-computed molecular integrals, resulting in a gate count that scales like widetildecalO(N8t). Next we introduce algorithms that compute molecular integrals on the fly by carefully discretizing these integrals. Indeed, figuring out how to evaluate the integrals in an efficient manner is one of the main challenges of applying the truncated Taylor series approach to the chemistry problem: the complexity of a general quantum algorithm is traditionally formulated in terms of the number of queries made to an oracle whose assumption we just assume, but in this case, we actually construct the oracle for our specific problem. The evaluation of the oracle itself requires evaluating molecular integrals, which adds additional complexity to an algorithm. We find that the gate count of the second-quantized on-the-fly algorithm scales like widetildecalO(N5t). We also find that the first-quantized on-the-fly algorithm, which uses the configuration interaction (CI) matrix representation of the Hamiltonian, requires at most widetildecalO(eta2N3t) gates. In general, the discovery of exponentially more precise algorithms will allow for the simulation of larger molecular systems than was previously possible under Trotter-based methods. In addition, the results here can be generalized to the simulation of other fermionic systems beyond the electronic structure problem.
Discretizing electronic degrees of freedom into atomic orbitals is the default choice to accurately model electrons in molecules in a compact and flexible way. We consider the task of simulating such electronic structure models on a quantum computer for N orbitals, keeping the number of orbitals per atom constant. Atomic orbitals give rise to Hamiltonians with potentially up to O(N4) terms and little structure, which made it challenging to match the complexity of methods based on plane waves and real-space grids. In this work, we show that a Trotter step for atomic orbitals can be implemented in depth O(polylog(N)) without ancillas by combining a rigorous treatment of orbital localization, a hierarchical Hamiltonian decomposition based on the Fast Multipole Method, and shallow quantum Fourier arithmetic circuits. By bounding the Trotter error, we obtain sublinear simulation depth, and our total gate count N5/3+o(1) matches the best scaling known for any basis.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.
The quantum simulation of real molecules and materials is one of the most highly anticipated applications of quantum computing. Algorithms for simulating electronic structure using a first-quantized plane-wave representation are especially promising due to their asymptotic efficiency. However, previous proposals for preparing initial states for these simulation algorithms scale poorly with the size of the basis set. We address this shortcoming by showing how to efficiently map states defined in a Gaussian-type orbital basis to a plane-wave basis with a scaling that is logarithmic in the number of plane waves. Our key technical result is a proof that molecular orbitals constructed from Gaussian-type basis functions can be compactly represented in a plane-wave basis using matrix product states. While we expect that other approaches could achieve the same logarithmic scaling with respect to basis-set size, our proposed state-preparation technique is also highly efficient in practice. For example, in a series of numerical experiments on small molecules, we find that our approach allows us to prepare an approximation to the Hartree-Fock state using orders of magnitude fewer non-Clifford gates than a naive approach. By resolving the issue of state preparation, our work allows for the first quantum simulation of molecular systems the end-to-end complexity of which is truly sublinear in the basis-set size.