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

Research output: Contribution to journalArticleResearchpeer-review

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.

LanguageEnglish
Article number041015
Pages041015-1-041015-36
Number of pages36
JournalPhysical Review X
Volume8
Issue number4
DOIs
Publication statusPublished - 23 Oct 2018

Fingerprint

electronic spectra
coding
electronic structure
phase error
sampling
operators
orbitals
coefficients
synthesis
electrons

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.

Cite this

Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., ... Neven, H. (2018). Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X, 8(4), 041015-1-041015-36. [041015]. https://doi.org/10.1103/PhysRevX.8.041015
Babbush, Ryan ; Gidney, Craig ; Berry, Dominic W. ; Wiebe, Nathan ; McClean, Jarrod ; Paler, Alexandru ; Fowler, Austin ; Neven, Hartmut. / Encoding electronic spectra in quantum circuits with linear T complexity. In: Physical Review X. 2018 ; Vol. 8, No. 4. pp. 041015-1-041015-36.
@article{d870ca0278844018ac4415baa53e9ab4,
title = "Encoding electronic spectra in quantum circuits with linear T complexity",
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.",
author = "Ryan Babbush and Craig Gidney and Berry, {Dominic W.} and Nathan Wiebe and Jarrod McClean and Alexandru Paler and Austin Fowler and Hartmut Neven",
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.",
year = "2018",
month = "10",
day = "23",
doi = "10.1103/PhysRevX.8.041015",
language = "English",
volume = "8",
pages = "041015--1--041015--36",
journal = "Physical Review X",
issn = "2160-3308",
publisher = "American Physical Society",
number = "4",

}

Babbush, R, Gidney, C, Berry, DW, Wiebe, N, McClean, J, Paler, A, Fowler, A & Neven, H 2018, 'Encoding electronic spectra in quantum circuits with linear T complexity', Physical Review X, vol. 8, no. 4, 041015, pp. 041015-1-041015-36. https://doi.org/10.1103/PhysRevX.8.041015

Encoding electronic spectra in quantum circuits with linear T complexity. / Babbush, Ryan; Gidney, Craig; Berry, Dominic W.; Wiebe, Nathan; McClean, Jarrod; Paler, Alexandru; Fowler, Austin; Neven, Hartmut.

In: Physical Review X, Vol. 8, No. 4, 041015, 23.10.2018, p. 041015-1-041015-36.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Encoding electronic spectra in quantum circuits with linear T complexity

AU - Babbush, Ryan

AU - Gidney, Craig

AU - Berry, Dominic W.

AU - Wiebe, Nathan

AU - McClean, Jarrod

AU - Paler, Alexandru

AU - Fowler, Austin

AU - Neven, Hartmut

N1 - 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.

PY - 2018/10/23

Y1 - 2018/10/23

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85057335157&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP160102426

U2 - 10.1103/PhysRevX.8.041015

DO - 10.1103/PhysRevX.8.041015

M3 - Article

VL - 8

SP - 041015-1-041015-36

JO - Physical Review X

T2 - Physical Review X

JF - Physical Review X

SN - 2160-3308

IS - 4

M1 - 041015

ER -

Babbush R, Gidney C, Berry DW, Wiebe N, McClean J, Paler A et al. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X. 2018 Oct 23;8(4):041015-1-041015-36. 041015. https://doi.org/10.1103/PhysRevX.8.041015