Quantum simulation of real-space dynamics PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Quantum simulation of real-space dynamics

Andrew M. Childs1,2, Jiaqi Leng1,3, Tongyang Li4,5,6, Jin-Peng Liu1,3, and Chenyi Zhang7

1Joint Center for Quantum Information and Computer Science, University of Maryland
2Department of Computer Science, University of Maryland
3Department of Mathematics, University of Maryland
4Center on Frontiers of Computing Studies, Peking University
5School of Computer Science, Peking University
6Center for Theoretical Physics, Massachusetts Institute of Technology
7Institute for Interdisciplinary Information Sciences, Tsinghua University

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


Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a $d$-dimensional Schrödinger equation with $eta$ particles can be simulated with gate complexity $tilde{O}bigl(eta d F text{poly}(log(g’/epsilon))bigr)$, where $epsilon$ is the discretization error, $g’$ controls the higher-order derivatives of the wave function, and $F$ measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on $epsilon$ and $g’$ from $text{poly}(g’/epsilon)$ to $text{poly}(log(g’/epsilon))$ and polynomially improves the dependence on $T$ and $d$, while maintaining best known performance with respect to $eta$. For the case of Coulomb interactions, we give an algorithm using $eta^{3}(d+eta)Ttext{poly}(log(eta dTg’/(Deltaepsilon)))/Delta$ one- and two-qubit gates, and another using $eta^{3}(4d)^{d/2}Ttext{poly}(log(eta dTg’/(Deltaepsilon)))/Delta$ one- and two-qubit gates and QRAM operations, where $T$ is the evolution time and the parameter $Delta$ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.

We develop quantum algorithms for simulating the dynamics of interacting quantum particles in $d$ dimensions. Compared to the best previous results, our algorithm is exponentially better in terms of the discretization error $epsilon$ and polynomially better in terms of the simulation time $T$ and the dimension $d$. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.

► BibTeX data

► References

[1] Dong An, Di Fang, and Lin Lin, Time-dependent Hamiltonian simulation of highly oscillatory dynamics, 2021, arXiv:2111.03103.

[2] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum 4 (2020), 220, arXiv:1809.00643 https:/​/​doi.org/​10.22331/​q-2020-01-13-220.

[3] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon, Simulated quantum computation of molecular energies, Science 309 (2005), no. 5741, 1704–1707, arXiv:quant-ph/​0604193 https:/​/​doi.org/​10.1126/​science.1113479.

[4] Ryan Babbush, Dominic W. Berry, Ian D. Kivlichan, Annie Y. Wei, Peter J. Love, and Alán Aspuru-Guzik, Exponentially more precise quantum simulation of fermions in second quantization, New Journal of Physics 18 (2016), no. 3, 033032, arXiv:1506.01020 https:/​/​dx.doi.org/​10.1088/​1367-2630/​18/​3/​033032.

[5] 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 (2019), no. 1, 1–7, arXiv:1807.09802 https:/​/​doi.org/​10.1038/​s41534-019-0199-y.

[6] Ryan Babbush, Dominic W. Berry, Yuval R. Sanders, Ian D. Kivlichan, Artur Scherer, Annie Y. Wei, Peter J. Love, and Alán Aspuru-Guzik, Exponentially more precise quantum simulation of fermions in the configuration interaction representation, Quantum Science and Technology 3 (2017), no. 1, 015006, arXiv:1506.01029 https:/​/​dx.doi.org/​10.1088/​2058-9565/​aa9463.

[7] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe, Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation, Physical Review A 91 (2015), no. 2, 022311, arXiv:1410.8159 https:/​/​doi.org/​10.1103/​PhysRevA.91.022311.

[8] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan, Low-depth quantum simulation of materials, Physical Review X 8 (2018), no. 1, 011044, arXiv:1706.00023 https:/​/​doi.org/​10.1103/​PhysRevX.8.011044.

[9] Josh Barnes and Piet Hut, A hierarchical ${O}(n log n)$ force-calculation algorithm, nature 324 (1986), no. 6096, 446–449 https:/​/​doi.org/​10.1038/​324446a0.

[10] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan, Quantum algorithms for quantum chemistry and quantum materials science, Chemical Reviews 120 (2020), no. 22, 12685–12717, arXiv:2001.03685 https:/​/​doi.org/​10.1021/​acs.chemrev.9b00829.

[11] Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather, Efficient distributed quantum computing, Proceedings of the Royal Society A 469 (2013), no. 2153, 20120686, arXiv:1207.2307 https:/​/​doi.org/​10.1098/​rspa.2012.0686.

[12] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics 270 (2007), 359–371, arXiv:quant-ph/​0508139 https:/​/​doi.org/​10.1007/​s00220-006-0150-x.

[13] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Physical Review Letters 114 (2015), no. 9, 090502, arXiv:1412.4687 https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502.

[14] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe, Time-dependent Hamiltonian simulation with ${L}^{1}$-norm scaling, Quantum 4 (2020), 254, arXiv:1906.07115 https:/​/​doi.org/​10.22331/​q-2020-04-20-254.

[15] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization, Quantum 3 (2019), 208, arXiv:1902.02134 https:/​/​doi.org/​10.22331/​q-2019-12-02-208.

[16] Jean Bourgain, On growth of Sobolev norms in linear Schrödinger equations with smooth time dependent potential, Journal d’Analyse Mathématique 77 (1999), no. 1, 315–348 https:/​/​doi.org/​10.1007/​BF02791265.

[17] John P. Boyd, Chebyshev and Fourier spectral methods, Courier Corporation, 2001.

[18] Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, vol. 3, Springer, 2008 https:/​/​doi.org/​10.1007/​978-0-387-75934-0.

[19] Earl Campbell, Random compiler for fast Hamiltonian simulation, Physical Review Letters 123 (2019), no. 7, 070503, arXiv:1811.08017 https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503.

[20] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, et al., Quantum chemistry in the age of quantum computing, Chemical Reviews 119 (2019), no. 19, 10856–10915, arXiv:1812.09976 https:/​/​doi.org/​10.1021/​acs.chemrev.8b00803.

[21] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization, Quantum 4 (2020), 221, arXiv:1809.01731 https:/​/​doi.org/​10.22331/​q-2020-01-13-221.

[22] Andrew M. Childs, Quantum information processing in continuous time, Ph.D. thesis, Massachusetts Institute of Technology, 2004.

[23] Andrew M. Childs and Robin Kothari, Limitations on the simulation of non-sparse Hamiltonians, Quantum Information & Computation 10 (2010), no. 7, 669–684, arXiv:0908.4398 https:/​/​doi.org/​10.26421/​QIC10.7-8-7.

[24] Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander, High-precision quantum algorithms for partial differential equations, Quantum 5 (2021), 574, arXiv:2002.07868 https:/​/​doi.org/​10.22331/​q-2021-11-10-574.

[25] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su, Toward the first quantum simulation with quantum speedup, Proceedings of the National Academy of Sciences 115 (2018), no. 38, 9456–9461, arXiv:1711.10980 https:/​/​doi.org/​10.1073/​pnas.1801723115.

[26] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, Theory of Trotter error with commutator scaling, Physical Review X 11 (2021), no. 1, 011020, arXiv:1912.08854 https:/​/​doi.org/​10.1103/​PhysRevX.11.011020.

[27] Andrew M. Childs and Nathan Wiebe, Hamiltonian simulation using linear combinations of unitary operations, Quantum Information & Computation 12 (2012), no. 11-12, 901–924, arXiv:1202.5822 https:/​/​doi.org/​10.26421/​QIC12.11-12-1.

[28] Yann N. Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, Advances in Neural Information Processing Systems, pp. 2933–2941, 2014, arXiv:1406.2572.

[29] Richard P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21 (1982), no. 6, 467–488 https:/​/​doi.org/​10.1007/​BF02650179.

[30] Yan V. Fyodorov and Ian Williams, Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity, Journal of Statistical Physics 129 (2007), no. 5-6, 1081–1116, arXiv:cond-mat/​0702601 https:/​/​doi.org/​10.1007/​s10955-007-9386-x.

[31] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204, 2019, arXiv:1806.01838 https:/​/​doi.org/​10.1145/​3313276.3316366.

[32] Gabriele Giuliani and Giovanni Vignale, Quantum theory of the electron liquid, Cambridge University Press, 2005 https:/​/​doi.org/​10.1017/​CBO9780511619915.

[33] Leslie Greengard and Vladimir Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics 73 (1987), no. 2, 325–348 https:/​/​doi.org/​10.1016/​0021-9991(87)90140-9.

[34] Jeongwan Haah, Matthew Hastings, Robin Kothari, and Guang Hao Low, Quantum algorithm for simulating real time evolution of lattice Hamiltonians, Proceedings of the 59th Annual Symposium on Foundations of Computer Science, pp. 350–360, IEEE, 2018, arXiv:1801.03922 https:/​/​doi.org/​10.1137/​18M1231511.

[35] Matthew B. Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer, Improving quantum algorithms for quantum chemistry, Quantum Information & Computation 15 (2015), no. 1-2, 1–21, arXiv:1403.1539 https:/​/​doi.org/​10.26421/​QIC15.1-2-1.

[36] Francis Begnaud Hildebrand, Introduction to numerical analysis, Courier Corporation, 1987 https:/​/​doi.org/​10.1007/​978-0-387-21738-3.

[37] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan, Accelerated gradient descent escapes saddle points faster than gradient descent, Conference on Learning Theory, pp. 1042–1085, 2018, arXiv:1711.10456.

[38] Shi Jin, Xiantao Li, and Nana Liu, Quantum simulation in the semi-classical regime, Quantum 6 (2022), 739 arXiv:2112.13279 https:/​/​doi.org/​10.22331/​q-2022-06-17-739.

[39] Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501, arXiv:quant-ph/​0405146 https:/​/​doi.org/​10.1103/​PhysRevLett.95.050501.

[40] Stephen P. Jordan, Keith S.M. Lee, and John Preskill, Quantum algorithms for quantum field theories, Science 336 (2012), no. 6085, 1130–1133, arXiv:1111.3633 https:/​/​doi.org/​10.1126/​science.1217069.

[41] Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics, Proceedings of the National Academy of Sciences 105 (2008), no. 48, 18681–18686, arXiv:0801.2986 https:/​/​doi.org/​10.1073/​pnas.0808245105.

[42] Ian D. Kivlichan, Nathan Wiebe, Ryan Babbush, and Alán Aspuru-Guzik, Bounding the costs of quantum simulation of many-body physics in real space, Journal of Physics A: Mathematical and Theoretical 50 (2017), no. 30, 305301, arXiv:1608.05696 https:/​/​dx.doi.org/​10.1088/​1751-8121/​aa77b8.

[43] Joonho Lee, Dominic 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 (2021), no. 3, 030305, arXiv:2011.03494 https:/​/​doi.org/​10.1103/​PRXQuantum.2.030305.

[44] Seth Lloyd, Universal quantum simulators, Science (1996), 1073–1078 https:/​/​doi.org/​10.1126/​science.273.5278.1073.

[45] Guang Hao Low and Isaac L. Chuang, Hamiltonian simulation by qubitization, Quantum 3 (2019), 163, arXiv:1610.06546 https:/​/​doi.org/​10.22331/​q-2019-07-12-163.

[46] Guang Hao Low and Nathan Wiebe, Hamiltonian simulation in the interaction picture, 2018, arXiv:1805.00675.

[47] Richard M. Martin, Electronic structure, Cambridge University Press, 2004 https:/​/​doi.org/​10.1017/​CBO9780511805769.

[48] Sam McArdle, Earl Campbell, and Yuan Su, Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian, Physical Review A 105 (2022), no. 1, 012403, arXiv:2107.07238 https:/​/​doi.org/​10.1103/​PhysRevA.105.012403.

[49] Jarrod R. McClean, Ryan Babbush, Peter J. Love, and Alán Aspuru-Guzik, Exploiting locality in quantum computation for quantum chemistry, The Journal of Physical Chemistry Letters 5 (2014), no. 24, 4368–4380 https:/​/​doi.org/​10.1021/​jz501649m.

[50] 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 (2021), no. 1, 1–7, arXiv:1808.02625 https:/​/​doi.org/​10.1038/​s41534-021-00416-z.

[51] David Poulin, Matthew B. Hastings, David Wecker, Nathan Wiebe, Andrew C. Doberty, and Matthias Troyer, The Trotter step size required for accurate quantum simulation of quantum chemistry, Quantum Information & Computation 15 (2015), no. 5-6, 361–384, arXiv:1406.4920 https:/​/​doi.org/​10.26421/​QIC15.5-6-1.

[52] John Preskill, Simulating quantum field theory with a quantum computer, The 36th Annual International Symposium on Lattice Field Theory, vol. 334, p. 024, SISSA Medialab, 2019, arXiv:1811.10085 DOI: https:/​/​doi.org/​10.22323/​1.334.0024.

[53] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer, Elucidating reaction mechanisms on quantum computers, Proceedings of the National Academy of Sciences 114 (2017), no. 29, 7555–7560, arXiv:1605.03590 https:/​/​doi.org/​10.1073/​pnas.1619152114.

[54] Vivek Sarin, Ananth Grama, and Ahmed Sameh, Analyzing the error bounds of multipole-based treecodes, SC’98: Proceedings of the 1998 ACM/​IEEE Conference on Supercomputing, pp. 19–19, IEEE, 1998 https:/​/​doi.org/​10.1109/​SC.1998.10041.

[55] Jacob T. Seeley, Martin J. Richard, and Peter J. Love, The Bravyi-Kitaev transformation for quantum computation of electronic structure, The Journal of Chemical Physics 137 (2012), no. 22, 224109, arXiv:1208.5986 https:/​/​doi.org/​10.1063/​1.4768229.

[56] Jie Shen and Tao Tang, Spectral and high-order methods with applications, Science Press Beijing, 2006, https:/​/​www.math.purdue.edu/​ shen7/​sp_intro12/​book.pdf.

[57] Bin Shi, Weijie J. Su, and Michael I. Jordan, On learning rates and Schrödinger operators, 2020, arXiv:2004.06977.

[58] Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, Fault-tolerant quantum simulations of chemistry in first quantization, PRX Quantum 2 (2021), no. 4, 040332, arXiv:2105.12767 https:/​/​doi.org/​10.1103/​PRXQuantum.2.040332.

[59] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, Nearly tight Trotterization of interacting electrons, Quantum 5 (2021), 495, arXiv:2012.09194 https:/​/​doi.org/​10.22331/​q-2021-07-05-495.

[60] Masuo Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics 32 (1991), no. 2, 400–407 https:/​/​doi.org/​10.1063/​1.529425.

[61] Barna Szabó and Ivo Babuška, Finite element analysis, John Wiley & Sons, 1991.

[62] Borzu Toloui and Peter J. Love, Quantum algorithms for quantum chemistry based on the sparsity of the CI-matrix, 2013, arXiv:1312.2579.

[63] 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 (2021), no. 3, 033055, arXiv:2007.14460 https:/​/​doi.org/​10.1103/​PhysRevResearch.3.033055.

[64] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer, Gate-count estimates for performing quantum chemistry on small quantum computers, Physical Review A 90 (2014), no. 2, 022305, arXiv:1312.1695 https:/​/​doi.org/​10.1103/​PhysRevA.90.022305.

[65] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik, Simulation of electronic structure Hamiltonians using quantum computers, Molecular Physics 109 (2011), no. 5, 735–750, arXiv:1001.3855 https:/​/​doi.org/​10.1080/​00268976.2011.552441.

[66] Stephen Wiesner, Simulations of many-body quantum systems by a quantum computer, 1996, arXiv:quant-ph/​9603028.

[67] Christof Zalka, Efficient simulation of quantum systems by quantum computers, Fortschritte der Physik: Progress of Physics 46 (1998), no. 6-8, 877–879, arXiv:quant-ph/​9603026.

[68] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points, Quantum 5 (2021), 529, arXiv:2007.10253v3 https:/​/​doi.org/​10.22331/​q-2021-08-20-529.

[69] Chenyi Zhang and Tongyang Li, Escape saddle points by a simple gradient-descent based algorithm, Advances in Neural Information Processing Systems, vol. 34, 2021, arXiv:2111.14069.

Cited by

[1] Hans Hon Sang Chan, Richard Meister, Tyson Jones, David P. Tew, and Simon C. Benjamin, “Grid-based methods for chemistry simulations on a quantum computer”, arXiv:2202.05864.

[2] Yonah Borns-Weil and Di Fang, “Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation”, arXiv:2208.07957.

The above citations are from SAO/NASA ADS (last updated successfully 2022-11-18 02:43:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2022-11-18 02:43:39).

  • Coinsmart. Europe’s Best Bitcoin and Crypto Exchange.Click Here
  • Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
  • Source: https://quantum-journal.org/papers/q-2022-11-17-860/

Time Stamp:

More from Quantum Journal