Time-dependent unbounded Hamiltonian simulation with vector norm scaling

Dong An1, Di Fang1, and Lin Lin1,2,3

1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
3Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA

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

► 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] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, "A Theory of Trotter Error", arXiv:1912.08854.

The above citations are from SAO/NASA ADS (last updated successfully 2021-06-16 10:31:04). 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 2021-06-16 10:31:02).