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.


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

[2] S. Lloyd, Science 273, 1073 (1996).

[3] M. Mohseni, P. Read, H. Neven, S. Boixo, V. Denchev, R. Babbush, A. Fowler, V. Smelyanskiy, and J. Martinis, Nature 543, 171 (2017).

[4] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Science 309, 1704 (2005).

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

[6] D. S. Abrams and S. Lloyd, Physical Review Letters 79, 2586 (1997).

[7] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, Physical Review X 8, 011044 (2018a).

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

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

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

[11] R. Babbush, D. W. Berry, J. R. McClean, and H. Neven, npj Quantum Information 5, 92 (2019a).

[12] J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Molecular Physics 109, 735 (2011).

[13] D. Wecker, B. Bauer, B. K. Clark, M. B. Hastings, and M. Troyer, Physical Review A 90, 022305 (2014).

[14] R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe, Physical Review A 91, 022311 (2015).

[15] D. Poulin, M. B. Hastings, D. Wecker, N. Wiebe, A. C. Doherty, and M. Troyer, Quantum Information and Computation 15, 361 (2015).

[16] J. T. Seeley, M. J. Richard, and P. J. Love, Journal of Chemical Physics 137, 224109 (2012).

[17] K. Setia and J. D. Whitfield, The Journal of Chemical Physics 148, 164104 (2018).

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

[19] M. Steudtner and S. Wehner, New Journal of Physics 20, 063010 (2018).

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

[21] L. Veis and J. Pittner, Journal of Chemical Physics 140, 214111 (2014).

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

[23] D. Poulin, A. Y. Kitaev, D. Steiger, M. Hastings, and M. Troyer, Physical Review Letters 121, 010501 (2017).

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

[25] G. H. Low and I. L. Chuang, Quantum 3, 163 (2019).

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

[27] E. Campbell, Physical Review Letters 123, 070503 (2019).

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

[29] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sciences 114, 7555 (2017).

[30] D. Litinski, Quantum 3, 128 (2019a).

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

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

[33] M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer, Quantum Information and Computation 15, 1 (2015).

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

[35] F. Motzoi, M. P. Kaicher, and F. K. Wilhelm, Physical Review Letters 119, 160503 (2017).

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

[37] C. Gidney and A. G. Fowler, Quantum 3, 135 (2019).

[38] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Physical Review A 86, 032324 (2012).

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

[40] H. Beinert, R. Holm, and E. Munck, Science 277, 653 (1997).

[41] M. Szegedy, in 45th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2004) pp. 32–41.

[42] A. M. Childs and N. Wiebe, Quantum Information and Computation 12, 901 (2012).

[43] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Proceedings of the National Academy of Sciences 115, 9456 (2018).

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

[45] Z. Li, J. Li, N. S. Dattani, C. J. Umrigar, and G. K.-L. Chan, The Journal of Chemical Physics 150, 024302 (2019).

[46] E. G. Hohenstein, S. I. L. Kokkila, R. M. Parrish, and T. J. Martinez, The Journal of Physical Chemistry B 117, 12972 (2013).

[47] J. L. Whitten, The Journal of Chemical Physics 58, 4496 (1973).

[48] E. G. Hohenstein and C. D. Sherrill, The Journal of Chemical Physics 132, 184111 (2010).

[49] N. H. F. Beebe and J. Linderberg, International Journal of Quantum Chemistry 12, 683 (1977).

[50] H. Koch, A. S. de Meras, and T. B. Pedersen, The Journal of Chemical Physics 118, 9481 (2003).

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

[52] T. Helgaker, P. Jorgensen, and J. Olsen, Molecular Electronic Structure Theory (Wiley, 2002).

[53] B. Peng and K. Kowalski, Journal of Chemical Theory and Computation 13, 4179 (2017).

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

[55] G. H. Low and I. L. Chuang, Physical Review Letters 118, 010501 (2017).

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

[57] D. A. Mazziotti, Physical Review Letters 108, 263002 (2012).

[58] N. Rubin, R. Babbush, and J. McClean, New Journal of Physics 20, 053020 (2018).

[59] W. A. Al-Saidi, S. Zhang, and H. Krakauer, Journal of Chemical Physics 124, 224101 (2006).

[60] D. Vanderbilt, Physical Review B 41, 7892 (1990).

[61] V. Giovannetti, S. Lloyd, and L. Maccone, Physical Review Letters 100, 160501 (2008).

[62] C. Gidney, Quantum 2, 74 (2018).

[63] R. Babbush, D. W. Berry, and H. Neven, Physical Review A 99, 040301 (2019b).

[64] J. R. McClean, R. Babbush, P. J. Love, and A. Aspuru-Guzik, The Journal of Physical Chemistry Letters 5, 4368 (2014).

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

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

Cited by

[1] Yingkai Ouyang, David R. White, and Earl T. Campbell, "Compilation by stochastic Hamiltonian sparsification", Quantum 4, 235 (2020).

[2] Kenji Sugisaki, Chikako Sakai, Kazuo Toyota, Kazunobu Sato, Daisuke Shiomi, and Takeji Takui, "Quantum Algorithm for Full Configuration Interaction Calculations without Controlled Time Evolutions", The Journal of Physical Chemistry Letters 12 45, 11085 (2021).

[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] A. K. Fedorov and M. S. Gelfand, "Towards practical applications in quantum computational biology", Nature Computational Science 1 2, 114 (2021).

[5] Matthew Amy and Neil J. Ross, "Phase-state duality in reversible circuit design", Physical Review A 104 5, 052602 (2021).

[6] Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang, "Resilience of Quantum Random Access Memory to Generic Noise", PRX Quantum 2 2, 020311 (2021).

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

[8] Nicholas P. Bauman, Hongbin Liu, Eric J. Bylaska, Sriram Krishnamoorthy, Guang Hao Low, Christopher E. Granade, Nathan Wiebe, Nathan A. Baker, Bo Peng, Martin Roetteler, Matthias Troyer, and Karol Kowalski, "Toward Quantum Computing for High-Energy Excited States in Molecular Systems: Quantum Phase Estimations of Core-Level States", Journal of Chemical Theory and Computation 17 1, 201 (2021).

[9] Élie Gouzien and Nicolas Sangouard, "Factoring 2048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory", Physical Review Letters 127 14, 140503 (2021).

[10] Jarrod R. McClean, Nicholas C. Rubin, Joonho Lee, Matthew P. Harrigan, Thomas E. O’Brien, Ryan Babbush, William J. Huggins, and Hsin-Yuan Huang, "What the foundations of quantum computer science teach us about chemistry", The Journal of Chemical Physics 155 15, 150901 (2021).

[11] Saad Yalouz, Bruno Senjean, Jakob Günther, Francesco Buda, Thomas E O’Brien, and Lucas Visscher, "A state-averaged orbital-optimized hybrid quantum–classical algorithm for a democratic description of ground and excited states", Quantum Science and Technology 6 2, 024004 (2021).

[12] 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 11 1(2021).

[13] Mathias Soeken and Martin Roetteler, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 366 (2020) ISBN:978-1-7281-8969-7.

[14] Zhendong Li, "Expressibility of comb tensor network states (CTNS) for the P-cluster and the FeMo-cofactor of nitrogenase", Electronic Structure 3 1, 014001 (2021).

[15] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, "Fault-Tolerant Quantum Simulations of Chemistry in First Quantization", PRX Quantum 2 4, 040332 (2021).

[16] Nicholas H. Stair and Francesco A. Evangelista, "Simulating Many-Body Systems with a Projective Quantum Eigensolver", PRX Quantum 2 3, 030301 (2021).

[17] William J. Huggins, Jarrod R. McClean, Nicholas C. Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, and Ryan Babbush, "Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers", npj Quantum Information 7 1, 23 (2021).

[18] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", arXiv:2012.09194, Quantum 5, 495 (2021).

[19] Javier Argüello-Luengo, Tao Shi, and Alejandro González-Tudela, "Engineering analog quantum chemistry Hamiltonians using cold atoms in optical lattices", Physical Review A 103 4, 043318 (2021).

[20] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).

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

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

[23] Emiel Koridon, Saad Yalouz, Bruno Senjean, Francesco Buda, Thomas E. O'Brien, and Lucas Visscher, "Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications", Physical Review Research 3 3, 033127 (2021).

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

[25] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", PRX Quantum 1 2, 020312 (2020).

[26] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, "Quantum computing enhanced computational catalysis", Physical Review Research 3 3, 033055 (2021).

[27] John M. Martinis, "Saving superconducting quantum processors from decay and correlated errors generated by gamma and cosmic rays", npj Quantum Information 7 1, 90 (2021).

[28] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, Quantum 5, 433 (2021).

[29] Thomas E. O’Brien, Stefano Polla, Nicholas C. Rubin, William J. Huggins, Sam McArdle, Sergio Boixo, Jarrod R. McClean, and Ryan Babbush, "Error Mitigation via Verified Phase Estimation", PRX Quantum 2 2, 020317 (2021).

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

[31] Mario Motta, Erika Ye, Jarrod R. McClean, Zhendong Li, Austin J. Minnich, Ryan Babbush, and Garnet Kin-Lic Chan, "Low rank representations for quantum simulation of electronic structure", npj Quantum Information 7 1, 83 (2021).

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

[33] Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques, and Francisco Rodríguez-Henríquez, "The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents", Journal of Cryptographic Engineering (2021).

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

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

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

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

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

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

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

[41] Torin F. Stetina, Anthony Ciavarella, Xiaosong Li, and Nathan Wiebe, "Simulating Effective QED on Quantum Computers", arXiv:2101.00111.

[42] Guang Hao Low, "Halving the cost of quantum multiplexed rotations", arXiv:2110.13439.

[43] Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2021-12-07 21:24:45) and SAO/NASA ADS (last updated successfully 2021-12-07 21:24:46). The list may be incomplete as not all publishers provide suitable and complete citation data.