Time-dependent unbounded Hamiltonian simulation with vector norm scaling

Dong An; Di Fang; Lin Lin

doi:10.22331/q-2021-05-26-459

Time-dependent unbounded Hamiltonian simulation with vector norm scaling

Dong An¹, Di Fang¹, and Lin Lin^1,2,3

¹Department of Mathematics, University of California, Berkeley, CA 94720, USA
²Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
³Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA

Published:	2021-05-26, volume 5, page 459
Eprint:	arXiv:2012.13105v3
Doi:	https://doi.org/10.22331/q-2021-05-26-459
Citation:	Quantum 5, 459 (2021).

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

Abstract

The accuracy of quantum dynamics simulation is usually measured by the error of the unitary evolution operator in the operator norm, which in turn depends on certain norm of the Hamiltonian. For unbounded operators, after suitable discretization, the norm of the Hamiltonian can be very large, which significantly increases the simulation cost. However, the operator norm measures the worst-case error of the quantum simulation, while practical simulation concerns the error with respect to a given initial vector at hand. We demonstrate that under suitable assumptions of the Hamiltonian and the initial vector, if the error is measured in terms of the vector norm, the computational cost may not increase at all as the norm of the Hamiltonian increases using Trotter type methods. In this sense, our result outperforms all previous error bounds in the quantum simulation literature. Our result extends that of [Jahnke, Lubich, BIT Numer. Math. 2000] to the time-dependent setting. We also clarify the existence and the importance of commutator scalings of Trotter and generalized Trotter methods for time-dependent Hamiltonian simulations.

► BibTeX data

@article{An2021timedependent,
  doi = {10.22331/q-2021-05-26-459},
  url = {https://doi.org/10.22331/q-2021-05-26-459},
  title = {Time-dependent unbounded {H}amiltonian simulation with vector norm scaling},
  author = {An, Dong and Fang, Di and Lin, Lin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {459},
  month = may,
  year = {2021}
}

► References

[1] G. R. Ahokas. Improved algorithms for approximate quantum Fourier transforms and sparse Hmailtonian simulations. University of Calgary, 2004. doi:10.11575/PRISM/22839.
https://doi.org/10.11575/PRISM/22839

[2] T. Albash and D. A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90:015002, 2018. doi:10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002

[3] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Commun. Math. Phys., 270(2):359–371, 2007. doi:10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[4] D. W. Berry and A. M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information & Computation, 12(1-2):29–62, 2012. doi:10.26421/QIC12.1-2.
https://doi.org/10.26421/QIC12.1-2

[5] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 283–292, 2014. doi:10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854

[6] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114:090502, 2015. doi:10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502

[7] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, pages 792–809, 2015. doi:10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54

[8] D. W. Berry, A. M. Childs, Y. Su, X. Wang, and N. Wiebe. Time-dependent Hamiltonian simulation with $l^{1}$-norm scaling. Quantum, 4:254, 2020. doi:10.22331/q-2020-04-20-254.
https://doi.org/10.22331/q-2020-04-20-254

[9] D. W. Berry, R. Cleve, and S. Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Information and Computation, 14(1-2):1–30, 2014. doi:10.26421/QIC14.1-2-1.
https://doi.org/10.26421/QIC14.1-2-1

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

[11] E. Campbell. Random compiler for fast Hamiltonian simulation. Phys. Rev. Lett., 123(7):070503, 2019. doi:10.1103/PhysRevLett.123.070503.
https://doi.org/10.1103/PhysRevLett.123.070503

[12] C.-F. Chen, H.-Y. Huang, R. Kueng, and J. A. Tropp. Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees. 2020. arXiv:2008.11751.
arXiv:2008.11751

[13] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 59–68, 2003. doi:10.1145/780542.780552.
https://doi.org/10.1145/780542.780552

[14] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Nat. Acad. Sci., 115:9456–9461, 2018. doi:10.1073/pnas.1801723115.
https://doi.org/10.1073/pnas.1801723115

[15] A. M. Childs, A. Ostrander, and Y. Su. Faster quantum simulation by randomization. Quantum, 3:182, 2019. doi:10.22331/q-2019-09-02-182.
https://doi.org/10.22331/q-2019-09-02-182

[16] A. M. Childs and Y. Su. Nearly optimal lattice simulation by product formulas. Phys. Rev. Lett., 123(5):050503, 2019. doi:10.1103/PhysRevLett.123.050503.
https://doi.org/10.1103/PhysRevLett.123.050503

[17] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. Theory of trotter error with commutator scaling. Phys. Rev. X, 11:011020, 2021. doi:10.1103/PhysRevX.11.011020.
https://doi.org/10.1103/PhysRevX.11.011020

[18] B. F. Curchod and T. J. Martínez. Ab initio nonadiabatic quantum molecular dynamics. Chemical reviews, 118(7):3305–3336, 2018. doi:10.1021/acs.chemrev.7b00423.
https://doi.org/10.1021/acs.chemrev.7b00423

[19] C. M. A. Dantas, I. A. Pedrosa, and B. Baseia. Harmonic oscillator with time-dependent mass and frequency and a perturbative potential. Physical Review A, 45(3):1320–1324, 1992. doi:10.1103/PhysRevA.45.1320.
https://doi.org/10.1103/PhysRevA.45.1320

[20] S. Descombes and M. Thalhammer. An exact local error representation of exponential operator splitting methods for evolutionary problems and applications to linear Schrödinger equations in the semi-classical regime. BIT Numer. Math., 50(4):729–749, 2010. doi:10.1007/s10543-010-0282-4.
https://doi.org/10.1007/s10543-010-0282-4

[21] D. Dong and I. R. Petersen. Quantum control theory and applications: a survey. IET Control Theory & Applications, 4(12):2651–2671, 2010. doi:10.1049/iet-cta.2009.0508.
https://doi.org/10.1049/iet-cta.2009.0508

[22] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution. 2000. arXiv:quant-ph/0001106.
arXiv:quant-ph/0001106

[23] M. Feng. Complete solution of the Schrödinger equation for the time-dependent linear potential. Physical Review A, 64(3):034101 EP –, 2001. doi:10.1103/PhysRevA.64.034101.
https://doi.org/10.1103/PhysRevA.64.034101

[24] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[25] E. Hairer, C. Lubich, and G. Wanner. Geometric numerical integration: structure-preserving algorithms for ordinary differential equations, volume 31. Springer, 2006. doi:10.1007/3-540-30666-8.
https://doi.org/10.1007/3-540-30666-8

[26] E. Hairer, S. P. Nørsett, and G. Wanner. Solving ordinary differential equation I: nonstiff problems, volume 8. Springer, 1987. doi:10.1007/978-3-540-78862-1.
https://doi.org/10.1007/978-3-540-78862-1

[27] M. Hochbruck and C. Lubich. On Magnus integrators for time-dependent Schrödinger equations. SIAM J. Numer. Anal., 41(3):945–963, 2003. doi:10.1137/S0036142902403875.
https://doi.org/10.1137/S0036142902403875

[28] J. Huyghebaert and H. De Raedt. Product formula methods for time-dependent Schrödinger problems. J. Phys. A, 23(24):5777–5793, 1990. doi:10.1088/0305-4470/23/24/019.
https://doi.org/10.1088/0305-4470/23/24/019

[29] T. Jahnke and C. Lubich. Error bounds for exponential operator splittings. BIT, 40(4):735–744, 2000. doi:10.1023/A:1022396519656.
https://doi.org/10.1023/A:1022396519656

[30] J.-Y. Ji, J. K. Kim, S. P. Kim, and K.-S. Soh. Exact wave functions and nonadiabatic Berry phases of a time-dependent harmonic oscillator. Physical Review A, 52(4):3352–3355, 1995. doi:10.1103/PhysRevA.52.3352.
https://doi.org/10.1103/PhysRevA.52.3352

[31] I. D. Kivlichan, N. Wiebe, R. Babbush, and A. Aspuru-Guzik. Bounding the costs of quantum simulation of many-body physics in real space. J. Phys. A Math. Theor., 50:305301, 2017. doi:10.1088/1751-8121/aa77b8.
https://doi.org/10.1088/1751-8121/aa77b8

[32] A. W. Knapp. Basic Real Analysis. Springer Science & Business Media, 2005. doi:10.1007/0-8176-4441-5.
https://doi.org/10.1007/0-8176-4441-5

[33] R. J. LeVeque. Finite difference methods for ordinary and partial differential equations. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2007. Steady-state and time-dependent problems. doi:10.1137/1.9780898717839.
https://doi.org/10.1137/1.9780898717839

[34] S. Lloyd. Universal quantum simulators. Science, pages 1073–1078, 1996. doi:10.1126/science.273.5278.1073.
https://doi.org/10.1126/science.273.5278.1073

[35] G. H. Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 491–502, 2019. doi:10.1145/3313276.3316386.
https://doi.org/10.1145/3313276.3316386

[36] G. H. Low and I. L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, 2017. doi:10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501

[37] G. H. Low and N. Wiebe. Hamiltonian simulation in the interaction picture. 2019. arXiv:1805.00675.
arXiv:1805.00675

[38] Y. Maday, J. Salomon, and G. Turinici. Monotonic time-discretized schemes in quantum control. Numer. Math., 103(2):323–338, 2006. doi:10.1007/s00211-006-0678-x.
https://doi.org/10.1007/s00211-006-0678-x

[39] A. B. Magann, M. D. Grace, H. A. Rabitz, and M. Sarovar. Digital quantum simulation of molecular dynamics and control. 2020. arXiv:2002.12497.
arXiv:2002.12497

[40] R. Montalto. On the growth of Sobolev norms for a class of linear Schrödinger equations on the torus with superlinear dispersion. Asymptotic Analysis, 108:85–114, 2018. doi:10.3233/ASY-181470.
https://doi.org/10.3233/ASY-181470

[41] M. A. Nielsen and I. Chuang. Quantum computation and quantum information, 2000. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[42] M. A. Nielsen, M. R. Dowling, M. Gu, and A. C. Doherty. Optimal control, geometry, and quantum computing. Phys. Rev. A, 73(6):062323, 2006. doi:10.1103/PhysRevA.73.062323.
https://doi.org/10.1103/PhysRevA.73.062323

[43] S. Pang and A. N. Jordan. Optimal adaptive control for quantum metrology with time-dependent hamiltonians. Nature communications, 8(1):1–9, 2017. doi:10.1038/ncomms14695.
https://doi.org/10.1038/ncomms14695

[44] I. A. Pedrosa. Exact wave functions of a harmonic oscillator with time-dependent mass and frequency. Physical Review A, 55(4):3219–3221, 1997. doi:10.1103/PhysRevA.55.3219.
https://doi.org/10.1103/PhysRevA.55.3219

[45] I. A. Pedrosa, G. P. Serra, and I. Guedes. Wave functions of a time-dependent harmonic oscillator with and without a singular perturbation. Physical Review A, 56(5):4300–4303, 1997. doi:10.1103/PhysRevA.56.4300.
https://doi.org/10.1103/PhysRevA.56.4300

[46] D. Poulin, A. Qarry, R. Somma, and F. Verstraete. Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space. Phys. Rev. Lett., 106(17):170501, 2011. doi:10.1103/PhysRevLett.106.170501.
https://doi.org/10.1103/PhysRevLett.106.170501

[47] J. Roland and N. J. Cerf. Quantum search by local adiabatic evolution. Phys. Rev. A, 65(4):042308, 2002. doi:10.1103/PhysRevA.65.042308.
https://doi.org/10.1103/PhysRevA.65.042308

[48] E. Runge and E. K. U. Gross. Density-functional theory for time-dependent systems. Phys. Rev. Lett., 52:997, 1984. doi:10.1103/PhysRevLett.52.997.
https://doi.org/10.1103/PhysRevLett.52.997

[49] B. Şahinoğlu and R. D. Somma. Hamiltonian simulation in the low energy subspace. 2020. arXiv:2006.02660.
arXiv:2006.02660

[50] A. Schulze-Halberg. Form-Preserving Transformations of Time-Dependent Schrödinger Equation with Time- and Position-Dependent Mass. Communications in Theoretical Physics, 43(4):657–665, 2005. doi:10.1088/0253-6102/43/4/017.
https://doi.org/10.1088/0253-6102/43/4/017

[51] Y. Su, H.-Y. Huang, and E. T. Campbell. Nearly tight trotterization of interacting electrons. 2020. arXiv:2012.09194.
arXiv:2012.09194

[52] M. Suzuki. General decomposition theory of ordered exponentials. Proc. Japan Acad., 69:161–166, 1993. doi:10.2183/pjab.69.161.
https://doi.org/10.2183/pjab.69.161

[53] M. Thalhammer. High-order exponential operator splitting methods for time-dependent Schrödinger equations. SIAM J. Numer. Anal., 46(4):2022–2038, 2008. doi:10.1137/060674636.
https://doi.org/10.1137/060674636

[54] J. W. Thomas. Numerical partial differential equations: finite difference methods, volume 22 of Texts in Applied Mathematics. Springer-Verlag, New York, 1995. doi:10.1007/978-1-4899-7278-1.
https://doi.org/10.1007/978-1-4899-7278-1

[55] D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer. Solving strongly correlated electron models on a quantum computer. Phys. Rev. A, 92:062318, 2015. doi:10.1103/PhysRevA.92.062318.
https://doi.org/10.1103/PhysRevA.92.062318

[56] N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders. Higher order decompositions of ordered operator exponentials. J. Phys. A, 43(6):065203, 2010. doi:10.1088/1751-8113/43/6/065203.
https://doi.org/10.1088/1751-8113/43/6/065203

[57] W. Zhu and H. Rabitz. A rapid monotonically convergent iteration algorithm for quantum optimal control over the expectation value of a positive definite operator. J. Chem. Phys., 109(2):385–391, 1998. doi:10.1063/1.476575.
https://doi.org/10.1063/1.476575

Cited by

[1] Ryan Babbush, William J. Huggins, Dominic W. Berry, Shu Fay Ung, Andrew Zhao, David R. Reichman, Hartmut Neven, Andrew D. Baczewski, and Joonho Lee, "Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods", Nature Communications 14 1, 4058 (2023).

[2] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).

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

[4] Hsin-Yuan Huang, Yu Tong, Di Fang, and Yuan Su, "Learning Many-Body Hamiltonians with Heisenberg-Limited Scaling", Physical Review Letters 130 20, 200403 (2023).

[5] Yulong Dong, K. Birgitta Whaley, and Lin Lin, "A quantum hamiltonian simulation benchmark", npj Quantum Information 8 1, 131 (2022).

[6] Nicola Macrì, Luigi Giannelli, Elisabetta Paladino, and Giuseppe Falci, "Coarse-Grained Effective Hamiltonian via the Magnus Expansion for a Three-Level System", Entropy 25 2, 234 (2023).

[7] Leonardo Alchieri, Davide Badalotti, Pietro Bonardi, and Simone Bianco, "An introduction to quantum machine learning: from quantum logic to quantum deep learning", Quantum Machine Intelligence 3 2, 28 (2021).

[8] Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs, "Hamiltonian Simulation with Random Inputs", Physical Review Letters 129 27, 270502 (2022).

[9] Nhung H. Nguyen, Minh C. Tran, Yingyue Zhu, Alaina M. Green, C. Huerta Alderete, Zohreh Davoudi, and Norbert M. Linke, "Digital Quantum Simulation of the Schwinger Model and Symmetry Protection with Trapped Ions", PRX Quantum 3 2, 020324 (2022).

[10] Ali SIRMA, "Nonlocal Schrödinger Problem with Time Dependent Self-Adjoint Operator", Haliç Üniversitesi Fen Bilimleri Dergisi 4 2, 111 (2021).

[11] Xiantao Li, "Some error analysis for the quantum phase estimation algorithms", Journal of Physics A: Mathematical and Theoretical 55 32, 325303 (2022).

[12] Daniel Burgarth, Niklas Galke, Alexander Hahn, and Lauritz van Luijk, "State-dependent Trotter limits and their approximations", Physical Review A 107 4, L040201 (2023).

[13] Dong An, Di Fang, and Lin Lin, "Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation", Quantum 6, 690 (2022).

[14] Yizhi Shen, Katherine Klymko, James Sud, David B. Williams-Young, Wibe A. de Jong, and Norm M. Tubman, "Real-Time Krylov Theory for Quantum Computing Algorithms", Quantum 7, 1066 (2023).

[15] Di Fang and Albert Tres Vilanova, "Observable Error Bounds of the Time-Splitting Scheme for Quantum-Classical Molecular Dynamics", SIAM Journal on Numerical Analysis 61 1, 26 (2023).

[16] Changhao Yi, "Success of digital adiabatic simulation with large Trotter step", Physical Review A 104 5, 052603 (2021).

[17] Ignacio Loaiza, Alireza Marefat Khah, Nathan Wiebe, and Artur F Izmaylov, "Reducing molecular electronic Hamiltonian simulation cost for linear combination of unitaries approaches", Quantum Science and Technology 8 3, 035019 (2023).

[18] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).

[19] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).

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

[21] Marc Illa, Caroline E. P. Robin, and Martin J. Savage, "Quantum Simulations of SO(5) Many-Fermion Systems using Qudits", arXiv:2305.11941, (2023).

[22] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "A theory of quantum differential equation solvers: limitations and fast-forwarding", arXiv:2211.05246, (2022).

[23] Jin-Peng Liu and Lin Lin, "Dense outputs from quantum simulations", arXiv:2307.14441, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 20:52:06) and SAO/NASA ADS (last updated successfully 2023-09-21 20:52:07). 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.