• Open Access

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, and Hartmut Neven
Phys. Rev. X 8, 041015 – Published 23 October 2018

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(N3/ε+N2log(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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
18 More
  • Received 9 May 2018
  • Revised 1 August 2018

DOI:https://doi.org/10.1103/PhysRevX.8.041015

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)

Quantum Information, Science & TechnologyCondensed Matter, Materials & Applied Physics

Authors & Affiliations

Ryan Babbush1,*, Craig Gidney2, Dominic W. Berry3, Nathan Wiebe4, Jarrod McClean1, Alexandru Paler5, Austin Fowler2, and Hartmut Neven1

  • 1Google Inc., Venice, California 90291, USA
  • 2Google Inc., Santa Barbara, California 93117, USA
  • 3Department of Physics and Astronomy, Macquarie University, Sydney, NSW 2109, Australia
  • 4Microsoft Research, Redmond, Washington 98052, USA
  • 5Institute for Integrated Circuits, Linz Institute of Technology, 4040 Linz, Austria

  • *Corresponding author. babbush@google.com

Popular Summary

Among the most anticipated applications of quantum computers is the simulation of physical quantum systems such as chemical reactions and solid-state materials. However, reliably solving these problems will likely require quantum error correction, which comes with high resource overheads. With fault-tolerant cost models in mind, we develop new algorithms to simulate systems of correlated electrons. These algorithms require millions of times fewer gates than prior state-of-the-art approaches, and they can solve interesting problems in chemistry near the threshold for those that cannot be solved with a classical computer.

Our approach involves realizing a quantum walk that exactly encodes the desired simulation results, but in a nonlinear fashion. To increase the efficiency of our algorithm, we introduce a novel form of quantum read-only memory that needs less data loaded into a quantum superposition by leveraging the symmetry of electron-electron interactions.

We investigate the cost of our method for simulating various real materials and models of strongly correlated electrons, and we compile the associated circuits all the way to the equivalent of “assembly language” for quantum error correction codes. We conclude that one would require approximately 1×106 physical qubits at error rates of one part in a thousand using the surface code.

These results position the simulation of materials as the first valuable application of quantum computing that will be viable within error correction.

Key Image

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 8, Iss. 4 — October - December 2018

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×