CoChat
Sign Up
Cited by 222Quantum Computing Algorithms and ArchitectureAdvanced Chemical Physics StudiesQuantum many-body systems

Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization

Open access
Berry, Dominic W., Gidney, Craig, Motta, Mario, McClean, Jarrod R., Babbush, Ryan·2019·Quantum
DOI 10.22331/q-2019-12-02-208
Open this paper in CoChat — free accountOpen PDF

Abstract

Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with O ~ ( N 3 / 2 λ ) T complexity, where N is number of orbitals and λ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.22331/q-2019-12-02-208

Cites

66 of 66 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Using measurement-based uncomputation, uncomputing each table lookup has a Toffoli count and measurement depth of 2√2^{c_mul+c_exp}, which is negligible compared to the lookup for the parameters used.

    “Using measurement-based uncomputation (appendix C of [8]), uncomputing each table lookup has a Toffoli count and measurement depth of 2 √ 2 c mul + c exp which is negligible compared to the lookup for the parameters we will be using.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [8]

    Appendix C gives a measurement-based method for uncomputing table lookups and states that, with clean ancillae and the optimizing choice of k, its Toffoli count is 2√d. Our copy does not give that value as a measurement depth or establish that the cost is negligible for the citing authors’ parameters. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Measurement-based uncomputation uses max(0, 2^{c_mul+c_exp}-n) ancillae, and this ancillae count is zero for the reasonable values considered in the paper.

    “The measurement-based uncomputation uses max (0 , 2 c mul + c exp -n ) ancillae (it starts by measuring away n logical qubits of the lookup output register). This ancillae count is always zero for the reasonable values of c mul , c exp , and classically intractable values of n , that we consider in this paper.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [8]

    Appendix C (page unavailable) describes measurement-based uncomputation of a table lookup by measuring its output qubits in the X basis. It does not give the claimed max(0, 2^{c_mul+c_exp}-n) ancilla count or say that the count is zero for the parameter values in the citing paper. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • In the 3 years since that publication, algorithmic advances have already lowered the time requirements by several orders of magnitude.

    “In the 3 years since that publication, algorithmic advances have already lowered the time requirements by several orders of magnitude [149].”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [149]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 13

  1. A. Y. Kitaev, arXiv:quant-ph/9511026 (1995). · arXiv
  2. I. D. Kivlichan, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, W. Sun, Z. Jiang, N. Rubin, A. Fowler, A. Aspuru-Guzik, R. Babbush, and H. Neven, arXiv:1902.10673 (2019). · arXiv
  3. Z. Jiang, J. McClean, R. Babbush, and H. Neven, arXiv:1812.08190 (2018). · arXiv
  4. N. M. Tubman, C. Mejuto-Zaera, J. M. Epstein, D. Hait, D. S. Levine, W. Huggins, Z. Jiang, J. R. McClean, R. Babbush, M. Head-Gordon, and K. B. Whaley, arXiv:1809.05523 (2018). · arXiv
  5. M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sciences 114, 7555 (2017).
  6. D. Litinski, Quantum 3, 128 (2019).
  7. I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Proceedings of the National Academy of Sciences 105, 18681 (2008).
  8. B. Toloui and P. J. Love, arXiv:1312.2579 (2013). · arXiv
  9. M. Motta, E. Ye, J. R. McClean, Z. Li, A. J. Minnich, R. Babbush, and G. K.-L. Chan, arXiv:1808.02625 (2018). · arXiv
  10. H. Beinert, R. Holm, and E. Munck, Science 277, 653 (1997).
  11. G. H. Low, V. Kliuchnikov, and L. Schaeffer, arXiv:1812.00954 (2018). · arXiv
  12. N. Rubin, R. Babbush, and J. McClean, New Journal of Physics 20, 053020 (2018). · DOI
  13. D. Litinski, arXiv:1905.06903 (2019). · arXiv

Cited by

Sorted by citations

Related

Authors
Berry, D. W., Gidney, C., Motta, M., McClean, J. R., & Babbush, R.
Affiliations
  • Macquarie University (AU)
  • Google (United States) (US)
  • Division of Chemistry, California Institute of Technology, Pasadena, CA 91125, United States
ORCID
Venue
Quantum
Publisher
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Published
2019-12-02
Volume
3
Pages
208
ISSN
2521-327X (ISSN-L)
DOI
10.22331/q-2019-12-02-208
OpenAlex
W2990442724
Cited by
222
References
66
Citations by year
2026: 20 · 2025: 38 · 2024: 33 · 2023: 49 · 2022: 32 · 2021: 29 · 2020: 18 · 2019: 3
FWCI
9.47
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
Funders
  • U.S. Department of Energy (DESC0019374)
  • Australian Research Council (DP160102426, DP190102633)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Advanced Chemical Physics Studies
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
qubitization, sparsity, low-rank tensor factorization, gate complexity, iron-molybdenum cofactor, nitrogen fixation, active space

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review