Time-dependent Hamiltonian simulation with $L^1$-norm scaling

Dominic W. Berry1, Andrew M. Childs2,3, Yuan Su2,3, Xin Wang3,4, and Nathan Wiebe5,6,7

1Department of Physics and Astronomy, Macquarie University, Sydney, NSW 2109, Australia
2Department of Computer Science, University of Maryland, College Park, MD 20742, USA
3Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA
4Institute for Quantum Computing, Baidu Research, Beijing 100193, China
5Department of Physics, University of Washington, Seattle, WA 98195, USA
6Pacific Northwest National Laboratory, Richland, WA 99354, USA
7Google Inc., Venice, CA 90291, USA

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


The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm $\int_{0}^{t}\mathrm{d}\tau\lVert{H(\tau)}\rVert_{\max}$, whereas the best previous results scale with $t\max_{\tau\in[0,t]}\lVert{H(\tau)}\rVert_{\max}$. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry.

► BibTeX data

► References

[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 20–29, 2003. 10.1145/​780542.780546. arXiv:quant-ph/​0301023.

[2] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X, 8: 041015, Oct 2018a. 10.1103/​PhysRevX.8.041015. arXiv:1805.03662.

[3] 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: 011044, Mar 2018b. 10.1103/​PhysRevX.8.011044. arXiv:1706.00023.

[4] Dominic W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12 (1-2): 29–62, 2012. arXiv:0910.4157.

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

[6] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 283–292, 2014a. 10.1145/​2591796.2591854. arXiv:1312.1414.

[7] Dominic W. Berry, Richard Cleve, and Sevag Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Information and Computation, 14 (1-2): 1–30, January 2014b. arXiv:1211.4637.

[8] 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 (9): 090502, 2015a. 10.1103/​PhysRevLett.114.090502. arXiv:1412.4687.

[9] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, pages 792–809, 2015b. 10.1109/​FOCS.2015.54. arXiv:1501.01715.

[10] Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356 (3): 1057–1081, Dec 2017. ISSN 1432-0916. 10.1007/​s00220-017-3002-y. arXiv:1701.03684.

[11] Fernando G. S. L. Brandao and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, pages 415–426, 2017. 10.1109/​FOCS.2017.45. arXiv:1609.05537.

[12] Laurie J. Butler. Chemical reaction dynamics beyond the Born-Oppenheimer approximation. Annual Review of Physical Chemistry, 49 (1): 125–171, 1998. 10.1146/​annurev.physchem.49.1.125.

[13] Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical Review Letters, 123: 070503, Aug 2019. 10.1103/​PhysRevLett.123.070503. arXiv:1811.08017.

[14] 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, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. Quantum chemistry in the age of quantum computing. Chemical Reviews, 119 (19): 10856–10915, 2019. 10.1021/​acs.chemrev.8b00803. arXiv:1812.09976.

[15] Andrew M. Childs and Robin Kothari. Limitations on the simulation of non-sparse Hamiltonians. Quantum Information and Computation, 10 (7-8): 669–684, 2010. arXiv:0908.4398.

[16] Andrew M. Childs and Yuan Su. Nearly optimal lattice simulation by product formulas. Physical Review Letters, 123: 050503, Aug 2019. 10.1103/​PhysRevLett.123.050503. arXiv:1901.00564.

[17] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by quantum walk. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 59–68, 2003. 10.1145/​780542.780552. arXiv:quant-ph/​0209131.

[18] 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 (38): 9456–9461, 2018. 10.1073/​pnas.1801723115. arXiv:1711.10980.

[19] Andrew M. Childs, Aaron Ostrander, and Yuan Su. Faster quantum simulation by randomization. Quantum, 3: 182, September 2019. 10.22331/​q-2019-09-02-182. arXiv:1805.08385.

[20] Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Information and Computation, 17 (1-2): 41–64, 2017. arXiv:1603.02940.

[21] John Day Dollard and Charles N. Friedman. Product Integration with Application to Differential Equations. Cambridge University Press, 1984. 10.1017/​CBO9781107340701.

[22] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292 (5516): 472–475, 2001. 10.1126/​science.1057726. arXiv:quant-ph/​0104129.

[23] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4 (1): 169–190, 2008. 10.4086/​toc.2008.v004a008. quant-ph/​0702144.

[24] Antonio Fernández-Ramos, James A Miller, Stephen J Klippenstein, and Donald G Truhlar. Modeling the kinetics of bimolecular reactions. Chemical reviews, 106 (11): 4518–4584, 2006. 10.1021/​cr050205w.

[25] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6-7): 467–488, 1982. 10.1007/​BF02650179.

[26] Robert B. Gerber, Victoria Buch, and Mark A. Ratner. Time-dependent self-consistent field approximation for intramolecular energy transfer. I. formulation and application to dissociation of van der Waals molecules. Journal of Chemical Physics, 77 (6): 3022–3030, 1982. 10.1063/​1.444225.

[27] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15): 150502, 2009. 10.1103/​PhysRevLett.103.150502. arXiv:0811.3171.

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

[29] Mária Kieferová, Artur Scherer, and Dominic Berry. Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Physical Review A, 99: 042314, 2019. 10.1103/​PhysRevA.99.042314. arXiv:1805.00582.

[30] Anthony W. Knapp. Basic Real Analysis. Birkhëuser, 2005. 10.3792/​euclid/​9781429799997.

[31] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, 1996. 10.1126/​science.273.5278.1073.

[32] Guang Hao Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51th ACM Symposium on Theory of Computing, pages 491–502. ACM, 2019. 10.1145/​3313276.3316386. arXiv:1807.03967.

[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118: 010501, 2017a. 10.1103/​PhysRevLett.118.010501. arXiv:1606.02685.

[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification, 2017b. arXiv:1707.05391.

[35] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, July 2019. 10.22331/​q-2019-07-12-163. arXiv:1610.06546.

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

[37] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92: 015003, Mar 2020. 10.1103/​RevModPhys.92.015003. arXiv:1808.10402.

[38] Michael A. Nielsen, Mark R. Dowling, Mile Gu, and Andrew C. Doherty. Optimal control, geometry, and quantum computing. Physical Review A, 73: 062323, Jun 2006. 10.1103/​PhysRevA.73.062323. arXiv:quant-ph/​0603160.

[39] Yingkai Ouyang, David R. White, and Earl T. Campbell. Compilation by stochastic Hamiltonian sparsification. Quantum, 4: 235, February 2020. 10.22331/​q-2020-02-27-235. arXiv:1910.06255.

[40] Shengshi Pang and Andrew N. Jordan. Optimal adaptive control for quantum metrology with time-dependent Hamiltonians. Nature Communications, 8: 14695, 2017. 10.1038/​ncomms14695. arXiv:1606.02166.

[41] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Physical Review Letters, 102: 130503, Apr 2009. 10.1103/​PhysRevLett.102.130503. arXiv:0809.2705.

[42] David Poulin, Angie Qarry, Rolando D. Somma, and Frank Verstraete. Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space. Physical Review Letters, 106 (17): 170501, 2011. 10.1103/​PhysRevLett.106.170501. arXiv:1102.1360.

[43] David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, and Matthias Troyer. The Trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Information and Computation, 15 (5-6): 361–384, 2015. arXiv:1406.4920.

[44] Orhan Talu and Alan L Myers. Reference potentials for adsorption of helium, argon, methane, and krypton in high-silica zeolites. Colloids and Surfaces A: Physicochemical and Engineering Aspects, 187: 83–93, 2001. 10.1016/​S0927-7757(01)00628-8.

[45] Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov. Locality and digital quantum simulation of power-law interactions. Physical Review X, 9: 031006, Jul 2019. 10.1103/​PhysRevX.9.031006. arXiv:1808.05225.

[46] John C. Tully. Mixed quantum–classical dynamics. Faraday Discussions, 110: 407–419, 1998. 10.1039/​a801824c.

[47] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/​9781316848142.

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

[49] Gregory S. Whittier and John C. Light. Quantum/​classical time-dependent self-consistent field treatment of Ar+HCO inelastic and dissociative scattering. Journal of Chemical Physics, 110 (9): 4280–4290, 1999. 10.1063/​1.478291.

[50] Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C Sanders. Higher order decompositions of ordered operator exponentials. Journal of Physics A, 43 (6): 065203, 2010. 10.1088/​1751-8113/​43/​6/​065203. arXiv:0812.0562.

[51] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2017. 10.1017/​9781316809976.

Cited by

[1] Patrick Rall, "Quantum algorithms for estimating physical quantities using block encodings", Physical Review A 102 2, 022408 (2020).

[2] Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe, "Quantum Algorithms for Simulating the Lattice Schwinger Model", Quantum 4, 306 (2020).

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

[4] Andrew M. Childs, Aaron Ostrander, and Yuan Su, "Faster quantum simulation by randomization", arXiv:1805.08385.

[5] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.

[6] Junyu Liu and Yuan Xin, "Quantum simulation of quantum field theories as quantum chemistry", arXiv:2004.13234.

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

The above citations are from Crossref's cited-by service (last updated successfully 2020-10-21 17:40:38) and SAO/NASA ADS (last updated successfully 2020-10-21 17:40:39). The list may be incomplete as not all publishers provide suitable and complete citation data.