Exponentially More Precise Algorithms for Quantum Simulation of Quantum Chemistry

Abstract

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 $\mathcal{O}(N)$ qubits for an $N$ spin-orbital system, and the highly compressed first-quantized encoding requires $\mathcal{O}(\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 $\widetilde{\cal O}(N^8t)$. 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 $\widetilde{\cal O}(N^5t)$. 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 $\widetilde{\cal O}(\eta^2N^3t)$ 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.