Time-marching based quantum solvers for time-dependent linear differential equations

Di Fang; Lin Lin; Yu Tong

doi:10.22331/q-2023-03-20-955

Time-marching based quantum solvers for time-dependent linear differential equations

Di Fang^1,2,3, Lin Lin^1,4,3, and Yu Tong^5,1

¹Department of Mathematics, University of California, Berkeley, CA 94720, USA
²Simons Institute for the Theory of Computing, University of California, Berkeley, CA 94720, USA
³Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA
⁴Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
⁵Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA

Published:	2023-03-20, volume 7, page 955
Eprint:	arXiv:2208.06941v2
Doi:	https://doi.org/10.22331/q-2023-03-20-955
Citation:	Quantum 7, 955 (2023).

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

Abstract

The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general homogeneous linear differential equations $\frac{\mathrm{d}}{\mathrm{d} t} |\psi(t)\rangle = A(t) |\psi(t)\rangle, |\psi(0)\rangle = |\psi_0\rangle$, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state $|\psi_0\rangle$. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, which simplifies the implementation compared to high-order truncated Dyson series approach, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.

Popular summary

Quantum computers are naturally suited for simulating unitary dynamics, offering the prospect of simulating quantum systems that the best known classical algorithms cannot handle. Recent years have seen much effort in extending this advantage to general linear ordinary differential equations (ODEs) which are not necessarily unitary. On classical computers, these ODEs are usually solved via the time-marching strategy, i.e., dividing the time into short segments and evolving for one segment at a time. It was previously believed that implementing this strategy on a quantum computer would result in a computational cost that is exponential in the number of time steps. In this study, we present an efficient algorithm for solving linear ODEs using the time-marching strategy. Our algorithm can handle non-smooth coefficient matrices, requires fewer queries to the initial state, and is free of some of the technical constraints present in previous works. One main technical tool we develop is a "compression gadget" that enhances the success probability of a sequence of non-unitary operations, which could have independent interest.

► BibTeX data

@article{Fang2023timemarchingbased,
  doi = {10.22331/q-2023-03-20-955},
  url = {https://doi.org/10.22331/q-2023-03-20-955},
  title = {Time-marching based quantum solvers for time-dependent linear differential equations},
  author = {Fang, Di and Lin, Lin and Tong, Yu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {955},
  month = mar,
  year = {2023}
}

► References

[1] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Leibniz Int. Proc. Informatics, LIPIcs, volume 14, pages 636–647, 2012. doi:10.4230/LIPIcs.STACS.2012.636.
https://doi.org/10.4230/LIPIcs.STACS.2012.636

[2] D. An, D. Fang, S. Jordan, J.-P. Liu, G. H. Low, and J. Wang. Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation, 2022. URL: http://arxiv.org/abs/2205.01141, arXiv:2205.01141, doi:10.48550/ARXIV.2205.01141.
https://doi.org/10.48550/ARXIV.2205.01141
arXiv:2205.01141

[3] D. An, D. Fang, and L. Lin. Time-dependent unbounded Hamiltonian simulation with vector norm scaling. Quantum, 5:1–49, may 2021. URL: https://doi.org/10.22331/q-2021-05-26-459, arXiv:2012.13105, doi:10.22331/Q-2021-05-26-459.
https://doi.org/10.22331/q-2021-05-26-459
arXiv:2012.13105

[4] D. An, D. Fang, and L. Lin. Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation. Quantum, 6:690, apr 2022. doi:10.22331/q-2022-04-15-690.
https://doi.org/10.22331/q-2022-04-15-690

[5] D. An and L. Lin. Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm. ACM Trans. Quantum Comput., 3(2):1–28, 2022. arXiv:1909.05500, doi:10.1145/3498331.
https://doi.org/10.1145/3498331
arXiv:1909.05500

[6] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510–1523, 1997. doi:10.1137/S0097539796300933.
https://doi.org/10.1137/S0097539796300933

[7] D. 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

[8] D. W. Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47(10):105301, feb 2014. doi:10.1088/1751-8113/47/10/105301.
https://doi.org/10.1088/1751-8113/47/10/105301

[9] 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. arXiv:0508139, doi:10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x
arXiv:0508139

[10] D. W. Berry and A. M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Inf. Comput., 12(1-2):29–62, 2012. arXiv:0910.4157, doi:10.26421/QIC12.1-2.
https://doi.org/10.26421/QIC12.1-2
arXiv:0910.4157

[11] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proc. Annu. ACM Symp. Theory Comput., pages 283–292, 2014. arXiv:1312.1414, doi:10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414

[12] 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(9):90502, 2015. arXiv:1412.4687, doi:10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502
arXiv:1412.4687

[13] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. Proc. - Annu. IEEE Symp. Found. Comput. Sci. FOCS, 2015-December:792–809, 2015. arXiv:1501.01715, doi:10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54
arXiv:1501.01715

[14] D. W. Berry, A. M. Childs, A. Ostrander, and G. Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356(3):1057–1081, 2017. doi:10.1007/s00220-017-3002-y.
https://doi.org/10.1007/s00220-017-3002-y

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

[16] D. W. Berry and P. C. S. Costa. Quantum algorithm for time-dependent differential equations using dyson series, 2022. URL: https://arxiv.org/abs/2212.03544, doi:10.48550/ARXIV.2212.03544.
https://doi.org/10.48550/ARXIV.2212.03544
arXiv:2212.03544

[17] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemp. Math., 305:53–74, 2002. arXiv:0005055, doi:10.1090/conm/305/05215.
https://doi.org/10.1090/conm/305/05215
arXiv:0005055

[18] F. Brauer and J. A. Nohel. The Qualitative Theory of Ordinary Differential Equations: An Introduction. Dover Books on Mathematics. Dover Publications, 2012. URL: https://books.google.com/books?id=9qPsbRl7hBkC.
https://books.google.com/books?id=9qPsbRl7hBkC

[19] R. L. Burden, J. D. Faires, and A. C. Reynolds. Numerical analysis. Brooks Cole, 2000.

[20] E. Campbell. Random Compiler for Fast Hamiltonian Simulation. Phys. Rev. Lett., 123(7):70503, 2019. arXiv:1811.08017, doi:10.1103/PhysRevLett.123.070503.
https://doi.org/10.1103/PhysRevLett.123.070503
arXiv:1811.08017

[21] S. Chakraborty, A. Gilyén, and S. Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. Leibniz Int. Proc. Informatics, LIPIcs, 132, 2019. arXiv:1804.01973, doi:10.4230/LIPIcs.ICALP.2019.33.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv:1804.01973

[22] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding Angles for Quantum Signal Processing with Machine Precision. 2020. URL: http://arxiv.org/abs/2003.02831, arXiv:2003.02831, doi:10.48550/arXiv.2003.02831.
https://doi.org/10.48550/arXiv.2003.02831
arXiv:2003.02831

[23] C.-F. Chen, Hsin-Yuan, Huang, R. Kueng, and J. a. Tropp. Concentration for random product formulas. arXiv:2008.11751, page 25, 2020. URL: http://arxiv.org/abs/2008.11751, arXiv:2008.11751, doi:10.1103/PRXQuantum.2.040305.
https://doi.org/10.1103/PRXQuantum.2.040305
arXiv:2008.11751

[24] Y. H. Chen, A. Kalev, and I. Hen. Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion. PRX Quantum, 2(3):30342, sep 2021. URL: https://doi.org/10.1103/PRXQuantum.2.030342, arXiv:2103.15334, doi:10.1103/PRXQuantum.2.030342.
https://doi.org/10.1103/PRXQuantum.2.030342
arXiv:2103.15334

[25] A. M. Childs, R. Kothari, and R. D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput., 46(6):1920–1950, 2017. arXiv:1511.02306, doi:10.1137/16M1087072.
https://doi.org/10.1137/16M1087072
arXiv:1511.02306

[26] A. M. Childs and J. P. Liu. Quantum Spectral Methods for Differential Equations. Commun. Math. Phys., 375(2):1427–1457, 2020. arXiv:1901.00961, doi:10.1007/s00220-020-03699-z.
https://doi.org/10.1007/s00220-020-03699-z
arXiv:1901.00961

[27] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci. U. S. A., 115(38):9456–9461, 2018. arXiv:1711.10980, doi:10.1073/pnas.1801723115.
https://doi.org/10.1073/pnas.1801723115
arXiv:1711.10980

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

[29] A. M. Childs and Y. Su. Nearly Optimal Lattice Simulation by Product Formulas. Phys. Rev. Lett., 123(5):50503, 2019. arXiv:1901.00564, doi:10.1103/PhysRevLett.123.050503.
https://doi.org/10.1103/PhysRevLett.123.050503
arXiv:1901.00564

[30] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. Theory of Trotter Error with Commutator Scaling. Phys. Rev. X, 11(1):11020, 2021. doi:10.1103/PhysRevX.11.011020.
https://doi.org/10.1103/PhysRevX.11.011020

[31] A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput., 12(11-12):901–924, nov 2012. URL: http://dx.doi.org/10.26421/QIC12.11-12, arXiv:1202.5822, doi:10.26421/qic12.11-12-1.
https://doi.org/10.26421/QIC12.11-12
arXiv:1202.5822

[32] P. C. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3:040303, Oct 2022. URL: https://doi.org/10.1103/PRXQuantum.3.040303, doi:10.1103/PRXQuantum.3.040303.
https://doi.org/10.1103/PRXQuantum.3.040303

[33] P. C. S. Costa, S. Jordan, and A. Ostrander. Quantum algorithm for simulating the wave equation. Physical Review A, 99(1):012323, 2019. arXiv:1711.05394. doi:10.1103/PhysRevA.99.012323.
https://doi.org/10.1103/PhysRevA.99.012323
arXiv:1711.05394

[34] I. Y. Dodin and E. A. Startsev. On applications of quantum computing to plasma simulations. Physics of Plasmas, 28(9):092101, 2021. doi:10.1063/5.0056974.
https://doi.org/10.1063/5.0056974

[35] Y. Dong, X. Meng, K. B. Whaley, and L. Lin. Efficient phase-factor evaluation in quantum signal processing. Phys. Rev. A, 103(4), 2021. arXiv:2002.11649, doi:10.1103/PhysRevA.103.042419.
https://doi.org/10.1103/PhysRevA.103.042419
arXiv:2002.11649

[36] A. Engel, G. Smith, and S. E. Parker. Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms. Physics of Plasmas, 28(6):062305, 2021. arXiv:2012.06681. doi:10.1063/5.0040313.
https://doi.org/10.1063/5.0040313
arXiv:2012.06681

[37] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv preprint arXiv:1806.01838, 2018. doi:10.48550/arXiv.1806.01838.
https://doi.org/10.48550/arXiv.1806.01838
arXiv:1806.01838

[38] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proc. 51st Annu. ACM SIGACT Symp. Theory Comput., pages 193–204, 2019. doi:10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[39] D. Gottlieb and C.-W. Shu. On the Gibbs phenomenon and its resolution. SIAM Rev., 39(4):644–668, 1997. doi:10.1137/S0036144596301390.
https://doi.org/10.1137/S0036144596301390

[40] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, Mar. 2014.
http://cvxr.com/cvx

[41] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. arXiv:1806.10236, doi:10.22331/q-2019-10-07-190.
https://doi.org/10.22331/q-2019-10-07-190
arXiv:1806.10236

[42] E. Hairer, C. Lubich, and G. Wanner. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations (Springer Series in Computational Mathematics), volume 31. Springer, 2006.

[43] E. Hairer, S. P. Nørsett, and G. Wanner. Solving ordinary differential equations I. nonstiff problems, volume 29. Springer, 1987. doi:10.1016/0378-4754(87)90083-8.
https://doi.org/10.1016/0378-4754(87)90083-8

[44] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103(15):150502, 2009. doi:10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[45] S. Jin and N. Liu. Quantum algorithms for computing observables of nonlinear partial differential equations, 2022. arXiv:2202.07834. doi:10.48550/arXiv.2202.07834.
https://doi.org/10.48550/arXiv.2202.07834
arXiv:2202.07834

[46] I. Joseph. Koopman-von Neumann approach to quantum simulation of nonlinear classical dynamics. Physical Review Research, 2(4):043102, 2020. arXiv:2003.09980. doi:10.1103/PhysRevResearch.2.043102.
https://doi.org/10.1103/PhysRevResearch.2.043102
arXiv:2003.09980

[47] M. Kieferová, A. Scherer, and D. W. Berry. Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Phys. Rev. A, 99(4), apr 2019. URL: http://dx.doi.org/10.1103/PhysRevA.99.042314, arXiv:1805.00582, doi:10.1103/PhysRevA.99.042314.
https://doi.org/10.1103/PhysRevA.99.042314
arXiv:1805.00582

[48] H. Krovi. Improved quantum algorithms for linear and nonlinear differential equations, 2022. URL: http://arxiv.org/abs/2202.01054, arXiv:2202.01054, doi:10.48550/ARXIV.2202.01054.
https://doi.org/10.48550/ARXIV.2202.01054
arXiv:2202.01054

[49] L. Lin and Y. Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. doi:10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[50] N. Linden, A. Montanaro, and C. Shao. Quantum vs. classical algorithms for solving the heat equation. Comm. Math. Phys., 395(2):601–641, 2022. doi:10.1007/s00220-022-04442-6.
https://doi.org/10.1007/s00220-022-04442-6

[51] J.-P. Liu, H. Ø. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs. Efficient quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, 118(35), 2021. arXiv:2011.03185. doi:10.1073/pnas.2026805118.
https://doi.org/10.1073/pnas.2026805118
arXiv:2011.03185

[52] S. Lloyd, G. De Palma, C. Gokler, B. Kiani, Z.-W. Liu, M. Marvian, F. Tennie, and T. Palmer. Quantum algorithm for nonlinear differential equations, 2020. arXiv:2011.06571. doi:10.48550/arXiv.2011.06571.
https://doi.org/10.48550/arXiv.2011.06571
arXiv:2011.06571

[53] G. H. Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proc. Annu. ACM Symp. Theory Comput., pages 491–502, 2019. arXiv:1807.03967, doi:10.1145/3313276.3316386.
https://doi.org/10.1145/3313276.3316386
arXiv:1807.03967

[54] G. H. Low and I. L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv:1707.05391, 2017. doi:10.48550/arXiv.1707.05391.
https://doi.org/10.48550/arXiv.1707.05391
arXiv:1707.05391

[55] G. H. Low and I. L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Phys. Rev. Lett., 118(1):10501, 2017. arXiv:1606.02685, doi:10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685

[56] G. H. Low and I. L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv:1610.06546, doi:10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546

[57] G. H. Low and N. Wiebe. Hamiltonian Simulation in the Interaction Picture. arXiv:1805.00675, 2018. URL: http://arxiv.org/abs/1805.00675, arXiv:1805.00675, doi:10.48550/arXiv.1805.00675.
https://doi.org/10.48550/arXiv.1805.00675
arXiv:1805.00675

[58] Y. Subaşl, R. D. Somma, and D. Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett., 122(6):60504, 2019. arXiv:1805.10549, doi:10.1103/PhysRevLett.122.060504.
https://doi.org/10.1103/PhysRevLett.122.060504
arXiv:1805.10549

[59] S. Takahira, A. Ohashi, T. Sogabe, and T. S. Usuda. Quantum algorithm for matrix functions by cauchy's integral formula. Quantum Inf. Comput., 20(1-2):14–36, 2020. arXiv:2106.08075, doi:10.26421/qic20.1-2-2.
https://doi.org/10.26421/qic20.1-2-2
arXiv:2106.08075

[60] Y. Tong, V. V. Albert, J. R. McClean, J. Preskill, and Y. Su. Provably accurate simulation of gauge theories and bosonic systems, 2021. URL: https://arxiv.org/abs/2110.06942, doi:10.48550/ARXIV.2110.06942.
https://doi.org/10.48550/ARXIV.2110.06942
arXiv:2110.06942

[61] Y. Tong, D. An, N. Wiebe, and L. Lin. Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions. Phys. Rev. A, 104(3), 2021. doi:10.1103/PhysRevA.104.032422.
https://doi.org/10.1103/PhysRevA.104.032422

[62] L. N. Trefethen. Approximation Theory and Approximation Practice, Extended Edition, volume 164. SIAM, 2019. doi:10.1137/1.9781611975949.
https://doi.org/10.1137/1.9781611975949

[63] L. N. Trefethen and J. A. Weideman. The exponentially convergent trapezoidal rule. SIAM Rev., 56(3):385–458, 2014. doi:10.1137/130932132.
https://doi.org/10.1137/130932132

[64] C. Tronci and I. Joseph. Koopman wavefunctions and Clebsch variables in Vlasov-Maxwell kinetic theory, 2021. doi:10.1017/S0022377821000805.
https://doi.org/10.1017/S0022377821000805

[65] J. Wang, Y. Dong, and L. Lin. On the energy landscape of symmetric quantum signal processing. Quantum, 6:850, Nov. 2022. doi:10.22331/q-2022-11-03-850.
https://doi.org/10.22331/q-2022-11-03-850

[66] 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 - At. Mol. Opt. Phys., 92(6):62318, 2015. arXiv:1506.05135, doi:10.1103/PhysRevA.92.062318.
https://doi.org/10.1103/PhysRevA.92.062318
arXiv:1506.05135

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

[68] L. Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, Oct. 2022. doi:10.22331/q-2022-10-20-842.
https://doi.org/10.22331/q-2022-10-20-842

[69] B. Şahinoğlu and R. D. Somma. Hamiltonian simulation in the low-energy subspace. npj Quantum Inf., 7(1), 2021. arXiv:2006.02660, doi:10.1038/s41534-021-00451-w.
https://doi.org/10.1038/s41534-021-00451-w
arXiv:2006.02660

Cited by

[1] Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying, "Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation", SIAM Journal on Computing 55 2, 376 (2026).

[2] Koichi Miyamoto, Soichiro Yamazaki, Fumio Uchida, Kotaro Fujisawa, and Naoki Yoshida, "Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos", Physical Review Research 6 1, 013200 (2024).

[3] Osama M. Raisuddin and Suvranu De, Quantum Computing for Engineers 267 (2026) ISBN:978-3-032-03324-6.

[4] Shi Jin, Nana Liu, and Chuwen Ma, "Quantum simulation of Maxwell’s equations via Schrödingerisation", ESAIM: Mathematical Modelling and Numerical Analysis 58 5, 1853 (2024).

[5] Dominic W. Berry and Pedro C. S. Costa, "Quantum algorithm for time-dependent differential equations using Dyson series", Quantum 8, 1369 (2024).

[6] Yu Cao, Shi Jin, and Nana Liu, "Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics", Physical Review Research 7 4, 043186 (2025).

[7] Dong An and Konstantina Trivisa, "Quantum algorithms for linear and non-linear fractional reaction-diffusion equations", Quantum 10, 1969 (2026).

[8] Xiantao Li, "From Linear Differential Equations to Unitaries: A Moment-Matching Dilation Framework with Near-Optimal Quantum Algorithms", PRX Quantum 7 2, 020350 (2026).

[9] Peter Brearley and Sylvain Laizet, "Quantum algorithm for solving the advection equation using Hamiltonian simulation", Physical Review A 110 1, 012430 (2024).

[10] I. Novikau, I.Y. Dodin, and E.A. Startsev, "Encoding of linear kinetic plasma problems in quantum circuits via data compression", Journal of Plasma Physics 90 4, 805900401 (2024).

[11] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "Quantum Differential Equation Solvers: Limitations and Fast-Forwarding", Communications in Mathematical Physics 406 8, 189 (2025).

[12] Sasan Moradi, "Hybrid classical-quantum computation of heat diffusion in multilayer materials", (2025).

[13] Javier Gonzalez-Conde, Dylan Lewis, Sachin S. Bharadwaj, and Mikel Sanz, "Quantum Carleman linearization efficiency in nonlinear fluid dynamics", Physical Review Research 7 2, 023254 (2025).

[14] Hsuan-Cheng Wu, Jingyao Wang, and Xiantao Li, "Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions", SIAM Journal on Scientific Computing 47 2, A943 (2025).

[15] Shi Jin, Nana Liu, and Yue Yu, "Schrödingerization based quantum algorithms for the time-fractional heat equation", Journal of Computational Physics 560, 114943 (2026).

[16] Alice V. Hu and Zbigniew J. Kabala, "Predicting and Reconstructing Aerosol–Cloud–Precipitation Interactions with Physics-Informed Neural Networks", Atmosphere 14 12, 1798 (2023).

[17] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).

[18] Chuwen Ma, Shi Jin, Nana Liu, Kezhen Wang, and Lei Zhang, "Schrödingerization-Based Quantum Circuits For Maxwell’s Equations With Time-Dependent Source Terms", Journal of Scientific Computing 108 2, 43 (2026).

[19] Philipp Pfeffer, Peter Brearley, Sylvain Laizet, and Jörg Schumacher, "Spectral quantum algorithm for passive scalar transport in shear flows", Scientific Reports 15 1, 41172 (2025).

[20] Angus Kan, Jessica Lemieux, Olga Okrut, and Burak Şahinoğlu, "Optimized quantum algorithms for simulating the Schwinger effect", Physical Review D 113 11, 114503 (2026).

[21] Kazuki Sakamoto and Keisuke Fujii, "On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality", Quantum 10, 2182 (2026).

[22] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes", SIAM Journal on Scientific Computing 46 5, A2951 (2024).

[23] Shi Jin, Nana Liu, and Yue Yu, "Schro¨dingerization based quantum algorithms for the time-fractional heat equation", (2025).

[24] Guang Hao Low and Yuan Su, "Quantum Eigenvalue Processing", 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1051 (2024) ISBN:979-8-3315-1674-1.

[25] Sergio Bengoechea, Paul Over, and Thomas Rung, "Quantum Time‐Marching Algorithms for Solving Linear Transport Problems Including Boundary Conditions", International Journal for Numerical Methods in Engineering 127 8, e70326 (2026).

[26] Zhong-Xia Shang, Naixu Guo, Dong An, and Qi Zhao, "Designing a Nearly Optimal Quantum Algorithm for Linear Differential Equations via Lindbladians", Physical Review Letters 135 12, 120604 (2025).

[27] Yue Wang and Qi Zhao, "Randomization accelerating series-truncated quantum algorithms", Physical Review A 113 4, 042423 (2026).

[28] Di Fang, Diyi Liu, and Rahul Sarkar, "Time-Dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence", Communications in Mathematical Physics 406 6, 128 (2025).

[29] Adam Husted Kjelstrøm, Andreas Pavlogiannis, and Jaco van de Pol, "Efficient Simulation of High-Level Quantum Gates", Quantum 10, 2093 (2026).

[30] Dong An, Jin-Peng Liu, and Lin Lin, "Linear Combination of Hamiltonian Simulation for Nonunitary Dynamics with Optimal State Preparation Cost", Physical Review Letters 131 15, 150603 (2023).

[31] Osama M. Raisuddin and Suvranu De, Quantum Computing for Engineers 197 (2026) ISBN:978-3-032-03324-6.

[32] Yuri Alexeev, Maximilian Amsler, Marco Antonio Barroca, Sanzio Bassini, Torey Battelle, Daan Camps, David Casanova, Young Jay Choi, Frederic T. Chong, Charles Chung, Christopher Codella, Antonio D. Córcoles, James Cruise, Alberto Di Meglio, Ivan Duran, Thomas Eckl, Sophia Economou, Stephan Eidenbenz, Bruce Elmegreen, Clyde Fare, Ismael Faro, Cristina Sanz Fernández, Rodrigo Neumann Barros Ferreira, Keisuke Fuji, Bryce Fuller, Laura Gagliardi, Giulia Galli, Jennifer R. Glick, Isacco Gobbi, Pranav Gokhale, Salvador de la Puente Gonzalez, Johannes Greiner, Bill Gropp, Michele Grossi, Emanuel Gull, Burns Healy, Matthew R. Hermes, Benchen Huang, Travis S. Humble, Nobuyasu Ito, Artur F. Izmaylov, Ali Javadi-Abhari, Douglas Jennewein, Shantenu Jha, Liang Jiang, Barbara Jones, Wibe Albert de Jong, Petar Jurcevic, William Kirby, Stefan Kister, Masahiro Kitagawa, Joel Klassen, Katherine Klymko, Kwangwon Koh, Masaaki Kondo, Dog̃a Murat Kürkçüog̃lu, Krzysztof Kurowski, Teodoro Laino, Ryan Landfield, Matt Leininger, Vicente Leyton-Ortega, Ang Li, Meifeng Lin, Junyu Liu, Nicolas Lorente, Andre Luckow, Simon Martiel, Francisco Martin-Fernandez, Margaret Martonosi, Claire Marvinney, Arcesio Castaneda Medina, Dirk Merten, Antonio Mezzacapo, Kristel Michielsen, Abhishek Mitra, Tushar Mittal, Kyungsun Moon, Joel Moore, Sarah Mostame, Mario Motta, Young-Hye Na, Yunseong Nam, Prineha Narang, Yu-ya Ohnishi, Daniele Ottaviani, Matthew Otten, Scott Pakin, Vincent R. Pascuzzi, Edwin Pednault, Tomasz Piontek, Jed Pitera, Patrick Rall, Gokul Subramanian Ravi, Niall Robertson, Matteo A.C. Rossi, Piotr Rydlichowski, Hoon Ryu, Georgy Samsonidze, Mitsuhisa Sato, Nishant Saurabh, Vidushi Sharma, Kunal Sharma, Soyoung Shin, George Slessman, Mathias Steiner, Iskandar Sitdikov, In-Saeng Suh, Eric D. Switzer, Wei Tang, Joel Thompson, Synge Todo, Minh C. Tran, Dimitar Trenev, Christian Trott, Huan-Hsin Tseng, Norm M. Tubman, Esin Tureci, David García Valiñas, Sofia Vallecorsa, Christopher Wever, Konrad Wojciechowski, Xiaodi Wu, Shinjae Yoo, Nobuyuki Yoshioka, Victor Wen-zhe Yu, Seiji Yunoki, Sergiy Zhuk, and Dmitry Zubarev, "Quantum-centric supercomputing for materials science: A perspective on challenges and future directions", Future Generation Computer Systems 160, 666 (2024).

[33] Osama Muhammad Raisuddin and Suvranu De, "A Review of Quantum Scientific Computing Algorithms Relevant to Computational Mechanics", Archives of Computational Methods in Engineering 33 1, 745 (2026).

[34] Osama M. Raisuddin and Suvranu De, Quantum Computing for Engineers 271 (2026) ISBN:978-3-032-03324-6.

[35] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", Quantum 8, 1558 (2024).

[36] Felix Tennie and Luca Magri, "Integration of the Fokker–Planck equation on quantum computers: a new path to modelling nonlinear dynamics", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 481 2326, 20250016 (2025).

[37] Gumaro Rendón, "Function extraction via Chebyshev interpolation of quantum integral estimates", Physical Review Research 8 2, 023095 (2026).

[38] Jin-Peng Liu and Lin Lin, "Dense outputs from quantum simulations", Journal of Computational Physics 514, 113213 (2024).

[39] I. Novikau and I. Joseph, "An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations", Journal of Computational Physics 564, 115132 (2026).

[40] David Jennings, Matteo Lostaglio, Robert B. Lowrie, Sam Pallister, and Andrew T. Sornborger, "The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts", Quantum 8, 1553 (2024).

[41] Efstratios Koukoutsis, George Vahala, Min Soe, Kyriakos Hizanidis, Linda Vahala, and Abhay K. Ram, "Time-Marching Quantum Algorithm for Simulation of Nonlinear Lorenz Dynamics", Entropy 27 8, 871 (2025).

[42] Yunya Liu, Jiakun Liu, Jordan R. Raney, and Pai Wang, "Quantum computing for solid mechanics and structural engineering – A demonstration with Variational Quantum Eigensolver", Extreme Mechanics Letters 67, 102117 (2024).

[43] Tyler Kharazi, Ahmad M. Alkadri, Jin-Peng Liu, Kranthi K. Mandadapu, and K. Birgitta Whaley, "Explicit block encodings of boundary value problems for many-body elliptic operators", Quantum 9, 1764 (2025).

[44] Kavitha Velusamy, Sowmiya Ramasamy, George Washington Samuelraj Chrysolite, Mallika Arjunan Mani, and Seenith Sivasundaram, "A Residual-Adaptive Preconditioned ψ-Fractional Quantum Pseudo-Spectral Method: Delay-Memory Differential Equations", Mathematics 14 15, 2842 (2026).

[45] Kevin Lively, Vittorio Pagni, and Gonzalo Camacho, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1926 (2025) ISBN:979-8-3315-5736-2.

[46] Dong An, Akwum Onwunta, and Gengzhi Yang, "Fast-forwarding quantum algorithms for linear dissipative differential equations", Quantum 10, 1986 (2026).

[47] Lin Lin, Volume 7: Invited Lectures: Sections 15–20 57 (2026) ISBN:978-1-61197-872-8.

[48] Osama Muhammad Raisuddin and Suvranu De, "qRLS: quantum relaxation for linear systems in finite element analysis", Engineering with Computers 40 5, 3273 (2024).

[49] Pedro C. S. Costa, Philipp Schleich, Mauro E. S. Morales, and Dominic W. Berry, "Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling", npj Quantum Information 11 1, 141 (2025).

[50] Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan, "Efficient Quantum Algorithm for Nonlinear Reaction–Diffusion Equations and Energy Estimation", Communications in Mathematical Physics 404 2, 963 (2023).

[51] Kaoru Mizuta and Keisuke Fujii, "Optimal Hamiltonian simulation for time-periodic systems", Quantum 7, 962 (2023).

[52] Sachin S. Bharadwaj and Katepalli R. Sreenivasan, "Compact quantum algorithms for time-dependent differential equations", Physical Review Research 7 2, 023262 (2025).

[53] Shi Jin, Xiantao Li, Nana Liu, and Yue Yu, "Quantum Simulation for Quantum Dynamics with Artificial Boundary Conditions", SIAM Journal on Scientific Computing 46 4, B403 (2024).

[54] Guang Hao Low and Yuan Su, "Quantum Eigenvalue Processing", SIAM Journal on Computing 55 1, 135 (2026).

[55] Dong An, Andrew M. Childs, and Lin Lin, "Quantum Algorithm for Linear Non-unitary Dynamics with Near-Optimal Dependence on All Parameters", Communications in Mathematical Physics 407 1, 19 (2026).

[56] Xinchi Huang, Hirofumi Nishi, Yoshifumi Kawada, Tomofumi Zushi, and Yu-ichiro Matsushita, "Fourier space readout method for efficiently recovering functions encoded in quantum states", Quantum Science and Technology 11 3, 035050 (2026).

[57] Chao Wang, Huan-Yu Liu, Cheng Xue, Xi-Ning Zhuang, Menghan Dou, Zhao-Yun Chen, and Guo-Ping Guo, "Quantum simulation of non-Hermitian special functions and dynamics via contour-based matrix decomposition", Quantum Science and Technology 11 3, 035027 (2026).

[58] Paul Over, Sergio Bengoechea, Peter Brearley, Sylvain Laizet, and Thomas Rung, "Quantum algorithm for the advection-diffusion equation by direct block encoding of the time-marching operator", Physical Review A 112 1, L010401 (2025).

[59] I. Novikau and I. Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", Computer Physics Communications 309, 109498 (2025).

[60] Guang Hao Low and Yuan Su, "Quantum linear system algorithm with optimal queries to initial state preparation", Quantum 10, 2041 (2026).

[61] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[62] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", Quantum 7, 913 (2023).

[63] Kaoru Mizuta, Tatsuhiko N. Ikeda, and Keisuke Fujii, "Explicit error bounds with commutator scaling for time-dependent product and multi-product formulas", arXiv:2410.14243, (2024).

[64] David Jennings, Kamil Korzekwa, Matteo Lostaglio, Andrew T Sornborger, Yigit Subasi, and Guoming Wang, "Quantum algorithms for general nonlinear dynamics based on the Carleman embedding", arXiv:2509.07155, (2025).

[65] Shi Jin, Nana Liu, and Yue Yu, "Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations", Journal of Computational Physics 487, 112149 (2023).

[66] Osama Muhammad Raisuddin and Suvranu De, "Quantum Multigrid Algorithm for Finite Element Problems", arXiv:2404.07466, (2024).

[67] Kevin Lively, Vittorio Pagni, and Gonzalo Camacho, "A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks", arXiv:2504.11181, (2025).

[68] Shi Jin, Nana Liu, Chuwen Ma, and Yue Yu, "Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schrödingerization", arXiv:2505.06866, (2025).

[69] Xinchi Huang, Hirofumi Nishi, Taichi Kosugi, Yoshifumi Kawada, and Yu-ichiro Matsushita, "A probabilistic imaginary-time evolution quantum algorithm for advection-diffusion equation: Explicit gate-level implementation and comparisons to quantum linear system algorithms", arXiv:2409.18559, (2024).

[70] Óscar Amaro and Diogo Cruz, "A Living Review of Quantum Computing for Plasma Physics", arXiv:2302.00001, (2023).

[71] Ivan Novikau and Ilon Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", arXiv:2410.03985, (2024).

[72] Nam Nguyen and Richard Thompson, "Solving Maxwells Equations using Variational Quantum Imaginary Time Evolution", arXiv:2402.14156, (2024).

[73] Songqinghao Yang and Jin-Peng Liu, "Circuit-Efficient Randomized Quantum Simulation of Non-Unitary Dynamics with Observable-Driven and Symmetry-Aware Designs", arXiv:2509.08030, (2025).

[74] Yue Wang, Xiao-Ming Zhang, Xiao Yuan, and Qi Zhao, "Efficient Preparation of Quantum States via Randomized Truncation", arXiv:2510.12247, (2025).

[75] Osama Muhammad Raisuddin and Suvranu De, "Quantum Relaxation for Linear Systems in Finite Element Analysis", arXiv:2308.01377, (2023).

[76] Abtin Ameri, Joseph Carolan, Andrew M. Childs, and Hari Krovi, "Quantum lower bounds for simulating fluid dynamics", arXiv:2603.12161, (2026).

[77] Tyler Kharazi, Ahmad M. Alkadri, Kranthi K. Mandadapu, and K. Birgitta Whaley, "Provable Quantum Speedups for Reaction-Rate Estimation in High-Dimensional Fokker-Planck Dynamics", arXiv:2601.15523, (2026).

[78] Xinchi Huang, Hirofumi Nishi, Yoshifumi Kawada, Tomofumi Zushi, and Yu-ichiro Matsushita, "Real and Fourier space readout methods: Comparison of complexity and applications to CFD problems", arXiv:2511.20017, (2025).

[79] Hari Krovi, "Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control", arXiv:2404.07303, (2024).

[80] Xabier Gutiérrez, Lorenzo Laneve, and Mikel Sanz, "Quantum Eigenvalue Transformations for Arbitrary Matrices", arXiv:2604.19688, (2026).

[81] Koichi Miyamoto, "Quantum algorithm for solving high-dimensional linear stochastic differential equations via amplitude encoding of the noise term", arXiv:2604.24133, (2026).

[82] Pierre-Antoine Bernard and Nathan Wiebe, "Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory", arXiv:2605.05321, (2026).

[83] Giacomo Antonioli, Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso, and Alessandro Poggiali, "Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth", arXiv:2607.13191, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 15:08:21) and SAO/NASA ADS (last updated successfully 2026-08-09 15:08:29). 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.