Encoding electronic spectra in quantum circuits with linear T complexity

Ryan Babbush*, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    218 Citations (Scopus)
    67 Downloads (Pure)

    Abstract

    We construct quantum circuits that exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity O(λ/ϵ), where λ is an absolute sum of Hamiltonian coefficients and ϵ is the target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T-gate complexity O(N+log(1/ϵ)), where N is the number of orbitals in the basis. This scenario enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity O(N³/ϵ+N²log(1/ϵ)/ϵ). Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per-gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours.

    Original languageEnglish
    Article number041015
    Pages (from-to)041015-1-041015-36
    Number of pages36
    JournalPhysical Review X
    Volume8
    Issue number4
    DOIs
    Publication statusPublished - 23 Oct 2018

    Bibliographical note

    Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

    Fingerprint

    Dive into the research topics of 'Encoding electronic spectra in quantum circuits with linear T complexity'. Together they form a unique fingerprint.

    Cite this