Abstract
We describe quantum circuits with only Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of arbitrary (e.g., molecular) orbitals. With 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 finite-sized 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- cycle times and physical gate-error rates no worse than .
13 More- Received 12 December 2020
- Revised 7 April 2021
- Accepted 24 May 2021
DOI:https://doi.org/10.1103/PRXQuantum.2.030305
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
Among the most promising applications of quantum computers is the simulation of chemical systems involving chemical bond formation and breaking. However, reliably solving these problems on quantum computers will likely require quantum error correction, which comes with high resource overheads. With fault-tolerant cost models in mind, we develop quantum algorithms to simulate quantum chemistry. Our approach results from leveraging a connection between cutting edge computer-science methods for Hamiltonian simulation, and a tensor representation of the quantum-chemistry problem.
The approach we describe scales better than any prior algorithm for chemistry, for all systems studied. In addition to the better asymptotic scaling, the constant prefactors appear to be lower since it also requires fewer quantum-computing resources to solve important benchmark problems that we focus on, such as FeMoCo: The primary cofactor of nitrogenase which is at the heart of nitrogen fixation. We compile our algorithms to protocols compatible with the most practical quantum error-correcting codes. We conclude that one would require approximately 4 million physical qubits and 4 days runtime to compute the energies of the FeMoCo with error rates of superconducting qubits that have already been demonstrated experimentally on such platforms with dozens of qubits.