PDF《Exponentially more precise quantum》

Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization Ryan Babbush,1, 2, ? Dominic W.

Berry,3, ? Ian D. Kivlichan,1,

4 Annie Y. Wei,1 Peter J. Love,5 and Al? an Aspuru-Guzik1, ?

1 Department of Chemistry and Chemical Biology, Harvard University, Cambridge, MA

02138 2 Google, Venice, CA 90291, USA

3 Department of Physics and Astronomy, Macquarie University, Sydney, NSW 2109, Australia

4 Department of Physics, Harvard University, Cambridge, MA 02138, USA

5 Department of Physics and Astronomy, Tufts University, Medford, MA

02155 (Dated: September 30, 2015) We introduce novel algorithms for the quantum simulation of molecular systems which are asymp- totically more e?cient than those based on the Trotter-Suzuki decomposition. We present the ?rst application of a recently developed technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision, an exponential improvement over all prior methods. The two algorithms developed in this work rely on a second quantized encoding of the wavefunction in which the state of an N spin-orbital system is encoded in O(N) qubits. Our ?rst algorithm requires at most O(N8 t) gates. Our second algorithm involves on- the-?y computation of molecular integrals, in a way that is exponentially more precise than classical sampling methods, by using the truncated Taylor series simulation technique. Our second algorithm has the lowest gate count of any approach to second quantized quantum chemistry simulation in the literature, scaling as O(N5 t). The approaches presented here are readily applicable to a wide class of fermionic models, many of which are de?ned by simpli?ed versions of the chemistry Hamiltonian. I. INTRODUCTION As small, fault-tolerant quantum computers come in- creasingly close to viability [1C4] there has been substan- tial renewed interest in quantum simulating chemistry due to the low qubit requirements and industrial impor- tance of the electronic structure problem. A recent se- ries of papers tried to estimate the resources required to quantum simulate a small but classically intractable molecule [5C9]. Although qubit requirements seem mod- est, initial predictions of the time required were daunting. Using arbitrarily high-order Trotter formulas, the tight- est known bound on the gate count of the second quan- tized, Trotter-based quantum simulation of chemistry is O(N8 t/ o(1) ) [10, 11]1 , where is the precision required and N is the number of spin-orbitals. However, using signi?cantly more practical Trotter decompositions, the best known gate complexity for this quantum algorithm is O(N9 t3/ ) [6]. Fortunately, numerics indicated that the average circuit depth for real molecules may be closer to O(N6 t3/ ) [7], or O(Z3 N4 t3/ ) when only trying to simulate ground states, where Z is the largest nuclear ? Corresponding author: [email protected] ? Corresponding author: [email protected] ? Corresponding author: [email protected]

1 We use the typical computer science convention that f ∈ Θ(g), for any functions f and g, if f is asymptotically upper and lower bounded by multiples of g, O indicates an asymptotic upper bound, O indicates an asymptotic upper bound up to polylog- arithmic factors, ? indicates the asymptotic lower bound and f ∈ o(g) implies f/g →

0 in the asymptotic limit. charge for the molecule [9]. While this improved scal- ing restores hope that fault-tolerant devices will have an impact on some classically intractable chemistry prob- lems, the Trotter-based quantum simulation of large (e.g. N >