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.
Popular summary
► 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] 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, Physical Review X 10 1, 011004 (2020).
[2] 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 acs.jctc.9b00963 (2020).
[3] 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).
[4] 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.
[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] William M. Kirby and Peter J. Love, “Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers”, Physical Review Letters 123 20, 200501 (2019).
[8] Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, arXiv:1905.09749.
[9] Craig Gidney, “Windowed quantum arithmetic”, arXiv:1905.07682.
[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] Craig Gidney and Austin G. Fowler, “Flexible layout of surface code computations using AutoCCZ states”, arXiv:1905.08916.
[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] Yingkai Ouyang, David R. White, and Earl Campbell, “Compilation by stochastic Hamiltonian sparsification”, arXiv:1910.06255.
[14] 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-01-22 20:52:08) and SAO/NASA ADS (last updated successfully 2020-01-22 20:52:09). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Source: https://quantum-journal.org/papers/q-2019-12-02-208/
