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

Dominic W. Berry1, Craig Gidney2, Mario Motta3, Jarrod R. McClean2, and Ryan Babbush2

1Department of Physics and Astronomy, Macquarie University, Sydney, NSW 2109, Australia
2Google Research, Venice, CA 90291, United States
3Division of Chemistry, California Institute of Technology, Pasadena, CA 91125, United States

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 $\widetilde{\cal O}(N^{3/2} \lambda)$ T complexity, where $N$ is number of orbitals and $\lambda$ 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.

Simulation of quantum chemistry is one of the most important potential applications of quantum computers, because it could be used to design new molecules for a wide range of applications. For example, it could be used to gain understanding of biological Nitrogen fixation by simulation of the FeMoco molecule. We show how to greatly accelerate the simulation of quantum chemistry by taking advantage of the structure of the system, together with several other new advances in quantum algorithms. Our most efficient approach takes advantage of the fact that the description of the energy has many terms that are close to zero and can be ignored. Together with a more efficient way of inputting information about the nonzero terms into the quantum algorithm, for the example of FeMoco we achieve a speedup of about a factor of 700.

► BibTeX data

► References

[1] R. P. Feynman, International Journal of Theoretical Physics 21, 467 (1982).
https:/​/​doi.org/​10.1007/​BF02650179

[2] S. Lloyd, Science 273, 1073 (1996).
https:/​/​doi.org/​10.1126/​science.273.5278.1073

[3] M. Mohseni, P. Read, H. Neven, S. Boixo, V. Denchev, R. Babbush, A. Fowler, V. Smelyanskiy, and J. Martinis, Nature 543, 171 (2017).
https:/​/​doi.org/​10.1038/​543171a

[4] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Science 309, 1704 (2005).
https:/​/​doi.org/​10.1126/​science.1113479

[5] A. Y. Kitaev, arXiv:quant-ph/​9511026 (1995).
arXiv:quant-ph/9511026

[6] D. S. Abrams and S. Lloyd, Physical Review Letters 79, 2586 (1997).
https:/​/​doi.org/​10.1103/​PhysRevLett.79.2586

[7] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, Physical Review X 8, 011044 (2018a).
https:/​/​journals.aps.org/​prx/​abstract/​10.1103/​PhysRevX.8.011044

[8] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Physical Review X 8, 041015 (2018b).
https:/​/​doi.org/​10.1103/​PhysRevX.8.041015

[9] 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:1902.10673

[10] G. H. Low and N. Wiebe, arXiv:1805.00675 (2018).
arXiv:1805.00675

[11] R. Babbush, D. W. Berry, J. R. McClean, and H. Neven, npj Quantum Information 5, 92 (2019a).
https:/​/​doi.org/​10.1038/​s41534-019-0199-y

[12] J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Molecular Physics 109, 735 (2011).
https:/​/​doi.org/​10.1080/​00268976.2011.552441

[13] D. Wecker, B. Bauer, B. K. Clark, M. B. Hastings, and M. Troyer, Physical Review A 90, 022305 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.90.022305

[14] R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe, Physical Review A 91, 022311 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.91.022311

[15] D. Poulin, M. B. Hastings, D. Wecker, N. Wiebe, A. C. Doherty, and M. Troyer, Quantum Information and Computation 15, 361 (2015).
https:/​/​doi.org/​10.26421/​QIC15.5-6

[16] J. T. Seeley, M. J. Richard, and P. J. Love, Journal of Chemical Physics 137, 224109 (2012).
https:/​/​doi.org/​10.1063/​1.4768229

[17] K. Setia and J. D. Whitfield, The Journal of Chemical Physics 148, 164104 (2018).
https:/​/​doi.org/​10.1063/​1.5019371

[18] S. Bravyi, J. M. Gambetta, A. Mezzacapo, and K. Temme, arXiv:1701.08213 (2017).
arXiv:1701.08213

[19] M. Steudtner and S. Wehner, New Journal of Physics 20, 063010 (2018).
https:/​/​doi.org/​10.1088/​1367-2630/​aac54f

[20] Z. Jiang, J. McClean, R. Babbush, and H. Neven, arXiv:1812.08190 (2018).
arXiv:1812.08190

[21] L. Veis and J. Pittner, Journal of Chemical Physics 140, 214111 (2014).
https:/​/​doi.org/​10.1063/​1.4880755

[22] D. W. Berry, M. Kieferová, A. Scherer, Y. R. Sanders, G. H. Low, N. Wiebe, C. Gidney, and R. Babbush, npj Quantum Information 4, 22 (2018).
https:/​/​doi.org/​10.1038/​s41534-018-0071-5

[23] D. Poulin, A. Y. Kitaev, D. Steiger, M. Hastings, and M. Troyer, Physical Review Letters 121, 010501 (2017).
https:/​/​journals.aps.org/​prl/​abstract/​10.1103/​PhysRevLett.121.010501

[24] 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:1809.05523

[25] G. H. Low and I. L. Chuang, Quantum 3, 163 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[26] R. Babbush, D. W. Berry, I. D. Kivlichan, A. Y. Wei, P. J. Love, and A. Aspuru-Guzik, New Journal of Physics 18, 33032 (2016).
https:/​/​doi.org/​10.1088/​1367-2630/​18/​3/​033032

[27] E. Campbell, Physical Review Letters 123, 070503 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503

[28] N. Cody Jones, J. D. Whitfield, P. L. McMahon, M.-H. Yung, R. V. Meter, A. Aspuru-Guzik, and Y. Yamamoto, New Journal of Physics 14, 115023 (2012).
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023

[29] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sciences 114, 7555 (2017).
http:/​/​www.pnas.org/​content/​114/​29/​7555.abstract

[30] D. Litinski, Quantum 3, 128 (2019a).
https:/​/​quantum-journal.org/​papers/​q-2019-03-05-128/​

[31] I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Proceedings of the National Academy of Sciences 105, 18681 (2008).
http:/​/​www.pnas.org/​content/​105/​48/​18681.abstract

[32] B. Toloui and P. J. Love, arXiv:1312.2579 (2013).
arXiv:1312.2579

[33] M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer, Quantum Information and Computation 15, 1 (2015).
https:/​/​doi.org/​10.26421/​QIC15.1-2

[34] K. Sugisaki, S. Yamamoto, S. Nakazawa, K. Toyota, K. Sato, D. Shiomi, and T. Takui, The Journal of Physical Chemistry A 120, 6459 (2016).
https:/​/​doi.org/​10.1021/​acs.jpca.6b04932

[35] F. Motzoi, M. P. Kaicher, and F. K. Wilhelm, Physical Review Letters 119, 160503 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.160503

[36] M. Motta, E. Ye, J. R. McClean, Z. Li, A. J. Minnich, R. Babbush, and G. K.-L. Chan, arXiv:1808.02625 (2018).
arXiv:1808.02625

[37] C. Gidney and A. G. Fowler, Quantum 3, 135 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-30-135

[38] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Physical Review A 86, 032324 (2012).
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324

[39] A. G. Fowler and C. Gidney, arXiv:1808.06709 (2018).
arXiv:1808.06709

[40] H. Beinert, R. Holm, and E. Munck, Science 277, 653 (1997).
https:/​/​doi.org/​http:/​/​science.sciencemag.org/​content/​277/​5326/​653

[41] M. Szegedy, in 45th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2004) pp. 32-41.
https:/​/​doi.org/​10.1109/​FOCS.2004.53

[42] A. M. Childs and N. Wiebe, Quantum Information and Computation 12, 901 (2012).
https:/​/​doi.org/​10.26421/​QIC12.11-12

[43] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Proceedings of the National Academy of Sciences 115, 9456 (2018).
https:/​/​doi.org/​10.1073/​pnas.1801723115

[44] G. H. Low, V. Kliuchnikov, and L. Schaeffer, arXiv:1812.00954 (2018).
arXiv:1812.00954

[45] Z. Li, J. Li, N. S. Dattani, C. J. Umrigar, and G. K.-L. Chan, The Journal of Chemical Physics 150, 024302 (2019).
https:/​/​doi.org/​10.1063/​1.5063376

[46] E. G. Hohenstein, S. I. L. Kokkila, R. M. Parrish, and T. J. Martinez, The Journal of Physical Chemistry B 117, 12972 (2013).
https:/​/​doi.org/​10.1021/​jp4021905

[47] J. L. Whitten, The Journal of Chemical Physics 58, 4496 (1973).
https:/​/​doi.org/​10.1063/​1.1679012

[48] E. G. Hohenstein and C. D. Sherrill, The Journal of Chemical Physics 132, 184111 (2010).
https:/​/​doi.org/​10.1063/​1.3426316

[49] N. H. F. Beebe and J. Linderberg, International Journal of Quantum Chemistry 12, 683 (1977).
https:/​/​doi.org/​10.1002/​qua.560120408

[50] H. Koch, A. S. de Meras, and T. B. Pedersen, The Journal of Chemical Physics 118, 9481 (2003).
https:/​/​doi.org/​10.1063/​1.1578621

[51] F. Aquilante, L. De Vico, N. Ferré, G. Ghigo, P.-Å. Malmqvist, P. Neogrády, T. B. Pedersen, M. Pitoňák, M. Reiher, B. O. Roos, L. Serrano-Andrés, M. Urban, V. Veryazov, and R. Lindh, Journal of Computational Chemistry 31, 224 (2010).
https:/​/​doi.org/​10.1002/​jcc.21318

[52] T. Helgaker, P. Jorgensen, and J. Olsen, Molecular Electronic Structure Theory (Wiley, 2002).
https:/​/​doi.org/​10.1002/​9781119019572

[53] B. Peng and K. Kowalski, Journal of Chemical Theory and Computation 13, 4179 (2017).
https:/​/​doi.org/​10.1021/​acs.jctc.7b00605

[54] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, in STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014) pp. 283-292.
https:/​/​doi.org/​10.1145/​2591796.2591854

[55] G. H. Low and I. L. Chuang, Physical Review Letters 118, 010501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501

[56] I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Physical Review Letters 120, 110501 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.120.110501

[57] D. A. Mazziotti, Physical Review Letters 108, 263002 (2012).
https:/​/​doi.org/​10.1103/​PhysRevLett.108.263002

[58] N. Rubin, R. Babbush, and J. McClean, New Journal of Physics 20, 053020 (2018).
http:/​/​iopscience.iop.org/​article/​10.1088/​1367-2630/​aab919/​meta

[59] W. A. Al-Saidi, S. Zhang, and H. Krakauer, Journal of Chemical Physics 124, 224101 (2006).
https:/​/​doi.org/​10.1063/​1.2200885

[60] D. Vanderbilt, Physical Review B 41, 7892 (1990).
https:/​/​doi.org/​10.1103/​PhysRevB.41.7892

[61] V. Giovannetti, S. Lloyd, and L. Maccone, Physical Review Letters 100, 160501 (2008).
https:/​/​doi.org/​10.1103/​PhysRevLett.100.160501

[62] C. Gidney, Quantum 2, 74 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[63] R. Babbush, D. W. Berry, and H. Neven, Physical Review A 99, 040301 (2019b).
https:/​/​doi.org/​10.1103/​PhysRevA.99.040301

[64] J. R. McClean, R. Babbush, P. J. Love, and A. Aspuru-Guzik, The Journal of Physical Chemistry Letters 5, 4368 (2014).
https:/​/​doi.org/​10.1021/​jz501649m

[65] D. Litinski, arXiv:1905.06903 (2019b).
arXiv:1905.06903

[66] S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, arXiv:quant-ph/​0410184 (2004).
arXiv:quant-ph/0410184

Cited by

[1] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven, "Quantum simulation of chemistry with sublinear scaling in basis size", npj Quantum Information 5 1, 92 (2019).

[2] Jarrod R. McClean, Kevin J. Sung, Ian D. Kivlichan, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Josh Izaac, Zhang Jiang, Xinle Liu, Sam McArdle, Matthew Neeley, Thomas O'Brien, Bryan O'Gorman, Isil Ozfidan, Maxwell D. Radin, Jhonathan Romero, Nicholas Rubin, Nicolas P. D. Sawaya, Kanav Setia, Sukin Sim, Damian S. Steiger, Mark Steudtner, Qiming Sun, Wei Sun, Daochen Wang, Fang Zhang, and Ryan Babbush, "OpenFermion: The Electronic Structure Package for Quantum Computers", arXiv:1710.07629.

[3] William M. Kirby and Peter J. Love, "Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers", arXiv:1904.02260, Physical Review Letters 123 20, 200501 (2019).

[4] Tyler Takeshita, Nicholas C. Rubin, Zhang Jiang, Eunseok Lee, Ryan Babbush, and Jarrod R. McClean, "Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources", arXiv:1902.10679.

[5] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", arXiv:1902.10673.

[6] Ryan Babbush, Dominic W. Berry, and Hartmut Neven, "Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization", Physical Review A 99 4, 040301 (2019).

[7] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749.

[8] Craig Gidney, "Windowed quantum arithmetic", arXiv:1905.07682.

[9] Craig Gidney and Austin G. Fowler, "Flexible layout of surface code computations using AutoCCZ states", arXiv:1905.08916.

[10] William J. Huggins, Jarrod McClean, Nicholas Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, and Ryan Babbush, "Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers", arXiv:1907.13117.

[11] Yuta Matsuzawa and Yuki Kurashige, "A Jastrow-type decomposition in quantum chemistry for low-depth quantum circuits", arXiv:1909.12410.

[12] Jarrod R. McClean, Fabian M. Faulstich, Qinyi Zhu, Bryan O'Gorman, Yiheng Qiu, Steven R. White, Ryan Babbush, and Lin Lin, "Discontinuous Galerkin discretization for quantum simulation of chemistry", arXiv:1909.00028.

[13] Kenji Sugisaki, Shigeaki Nakazawa, Kazuo Toyota, Kazunobu Sato, Daisuke Shiomi, and Takeji Takui, "Quantum chemistry on quantum computers: quantum simulations of the time evolution of wave functions under the S2 operator and determination of the spin quantum number S", Physical Chemistry Chemical Physics (Incorporating Faraday Transactions) 21 28, 15356 (2019).

[14] Yingkai Ouyang, David R. White, and Earl Campbell, "Compilation by stochastic Hamiltonian sparsification", arXiv:1910.06255.

The above citations are from Crossref's cited-by service (last updated 2019-12-15 05:32:56) and SAO/NASA ADS (last updated 2019-12-15 05:32:57). The list may be incomplete as not all publishers provide suitable and complete citation data.