Time-dependent Hamiltonian Simulation With $L^1$-norm Scaling

Abstract

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}taulVert{H(tau)}rVert_{max}$, whereas the best previous results scale with $tmax_{tauin[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

<br /> @article{Berry2020timedependent, doi = {10.22331/q-2020-04-20-254}, url = {https://doi.org/10.22331/q-2020-04-20-254}, title = {Time-dependent {H}amiltonian simulation with {$L^1$}-norm scaling}, author = {Berry, Dominic W. and Childs, Andrew M. and Su, Yuan and Wang, Xin and Wiebe, Nathan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {4}, pages = {254}, month = apr, year = {2020}<br /> }<br />

► 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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.4086/toc.2008.v004a008
arXiv: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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevA.99.042314
arXiv:1805.00582

[30] Anthony W. Knapp. Basic Real Analysis. Birkhëuser, 2005. 10.3792/euclid/9781429799997.
https://doi.org/10.3792/euclid/9781429799997

[31] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073–1078, 1996. 10.1126/science.273.5278.1073.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1039/a801824c

[47] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/9781316848142.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1088/1751-8113/43/6/065203
arXiv:0812.0562

[51] Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2017. 10.1017/9781316809976.
https://doi.org/10.1017/9781316809976

Cited by

[1] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan, “Quantum computational chemistry”, arXiv:1808.10402.

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

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

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

[5] Michael Kreshchuk, William M. Kirby, Gary Goldstein, Hugo Beauchemin, and Peter J. Love, “Quantum Simulation of Quantum Field Theory in the Light-Front Formulation”, arXiv:2002.04016.

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

[7] Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe, “Quantum Algorithms for Simulating the Lattice Schwinger Model”, arXiv:2002.11146.

[8] Patrick Rall, “Quantum Algorithms for Estimating Physical Quantities using Block-Encodings”, arXiv:2004.06832.

The above citations are from SAO/NASA ADS (last updated successfully 2020-06-03 18:40:00). 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 2020-06-03 18:39:58).

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.

Generative Data Intelligence

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

Abstract

► BibTeX data

► References

Cited by

Maximizing Returns and Efficiency: The Role of Automated Crypto Solutions in Modern Investment Strategies

Maximizing Returns and Efficiency: The Impact of Automated Crypto Solutions on Your Investment Portfolio

Latest Intelligence

Mastering the Digital Marketplace: Navigating Cybercash, E-tail, and the Evolving Landscape of Online Transactions

Decoding Digital Finance: Navigating Cybercash, E-tail, and the Future of Online Transactions

Securing Your Wallet and Embracing the Future: The Ultimate Guide to Cybercash, E-tail, and the Digital Transaction Revolution

Digital Transactions Demystified: Navigating Cybercash and E-tail in the Evolving Online Marketplace

Securing Your Digital Wealth: A Comprehensive Guide to Cybercash, E-tail, and Safe Digital Transactions

Digital Transactions Demystified: Navigating Cybercash, E-tail, and Online Security