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] Yingkai Ouyang, David R. White, and Earl T. Campbell, "Compilation by stochastic Hamiltonian sparsification", Quantum 4, 235 (2020).

[2] 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", Physical Review X 10 1, 011004 (2020).

[3] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402, Reviews of Modern Physics 92 1, 015003 (2020).

[4] 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", Quantum 4, 296 (2020).

[5] Yuta Matsuzawa and Yuki Kurashige, "Jastrow-type Decomposition in Quantum Chemistry for Low-Depth Quantum Circuits", arXiv:1909.12410, Journal of Chemical Theory and Computation 16 2, 944 (2020).

[6] 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).

[7] Carlos Outeiral, Martin Strahm, Jiye Shi, Garrett M. Morris, Simon C. Benjamin, and Charlotte M. Deane, "The prospects of quantum computing in computational molecular biology", WIREs Computational Molecular Science (2020).

[8] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Benjamin Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Matthew P. Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William J. Huggins, Lev Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Murphy Yuezhen Niu, Thomas E. O’Brien, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J. Sung, Marco Szalay, Tyler Y. Takeshita, Amit Vainsencher, Theodore White, Nathan Wiebe, Z. Jamie Yao, Ping Yeh, and Adam Zalcman, "Hartree-Fock on a superconducting qubit quantum computer", Science 369 6507, 1084 (2020).

[9] Michael P. Kaicher, Simon B. Jäger, Pierre-Luc Dallaire-Demers, and Frank K. Wilhelm, "Roadmap for quantum simulation of the fractional quantum Hall effect", Physical Review A 102 2, 022607 (2020).

[10] 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.

[11] 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).

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

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

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

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

[16] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, "Quantum computing enhanced computational catalysis", arXiv:2007.14460.

[17] 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", New Journal of Physics 22 9, 093015 (2020).

[18] 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).

The above citations are from Crossref's cited-by service (last updated successfully 2020-10-28 08:11:41) and SAO/NASA ADS (last updated successfully 2020-10-28 08:11:42). The list may be incomplete as not all publishers provide suitable and complete citation data.