# High-precision quantum algorithms for partial differential equations

Andrew M. Childs1,2,3, Jin-Peng Liu1,2,4, and Aaron Ostrander1,2,5

1Joint Center for Quantum Information and Computer Science, University of Maryland, MD 20742, USA
2Institute for Advanced Computer Studies, University of Maryland, MD 20742, USA
3Department of Computer Science, University of Maryland, MD 20742, USA
4Department of Mathematics, University of Maryland, MD 20742, USA
5Department of Physics, University of Maryland, MD 20742, USA

### Abstract

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity $\mathrm{poly}(1/\epsilon)$, where $\epsilon$ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be $\mathrm{poly}(d, \log(1/\epsilon))$, where $d$ is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

### ► References

[1] Andris Ambainis, Variable time amplitude amplification and quantum algorithms for linear algebra problems, 29th Symposium on Theoretical Aspects of Computer Science, vol. 14, pp. 636–647, LIPIcs, 2012, doi:10.4230/​LIPIcs.STACS.2012.636.
https:/​/​doi.org/​10.4230/​LIPIcs.STACS.2012.636

[2] Richard Bellman, Dynamic programming, Princeton University Press, 1957.

[3] Ivo Babuška and Manil Suri, The $h-p$ version of the finite element method with quasiuniform meshes, Mathematical Modelling and Numerical Analysis 21 (1987), no. 2, 199–238, doi:10.1051/​m2an/​1987210201991.
https:/​/​doi.org/​10.1051/​m2an/​1987210201991

[4] 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 (2015), no. 9, 090502, doi:10.1103/​PhysRevLett.114.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[5] ________, Exponential improvement in precision for simulating sparse Hamiltonians, Forum of Mathematics, Sigma 5 (2017), e8, doi:10.1145/​2591796.2591854.
https:/​/​doi.org/​10.1145/​2591796.2591854

[6] Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numerica 13 (2004), 147–269, doi:10.1017/​S0962492904000182.
https:/​/​doi.org/​10.1017/​S0962492904000182

[7] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais, Quantum algorithm and circuit design solving the Poisson equation, New Journal of Physics 15 (2013), no. 1, 013021, doi:10.1088/​1367-2630/​15/​1/​013021.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​1/​013021

[8] Andrew M. Childs, Robin Kothari, and Rolando D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing 46 (2017), no. 6, 1920–1950, doi:10.1137/​16M1087072.
https:/​/​doi.org/​10.1137/​16M1087072

[9] Andrew M. Childs and Jin-Peng Liu, Quantum spectral methods for differential equations, doi:10.1007/​s00220-020-03699-z.
https:/​/​doi.org/​10.1007/​s00220-020-03699-z

[10] B. David Clader, Bryan C. Jacobs, and Chad R. Sprouse, Preconditioned quantum linear system algorithm, Physical Review Letters 110 (2013), no. 25, 250504, doi:10.1103/​PhysRevLett.110.250504.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.250504

[11] Daniel T. Colbert and William H. Miller, A novel discrete variable representation for quantum mechanical reactive scattering via the S-matrix Kohn method, Journal of Chemical Physics 96 (1992), no. 3, 1982–1991, doi:10.1063/​1.462100.
https:/​/​doi.org/​10.1063/​1.462100

[12] Pedro C. S. Costa, Stephen Jordan, and Aaron Ostrander, Quantum algorithm for simulating the wave equation, Physical Review A 99 (2019), no. 1, 012323, doi:10.1103/​PhysRevA.99.012323.
https:/​/​doi.org/​10.1103/​PhysRevA.99.012323

[13] Lawrence C. Evans, Partial differential equations (2nd ed.), American Mathematical Society, 2010, doi:10.1090/​gsm/​019.
https:/​/​doi.org/​10.1090/​gsm/​019

[14] François Fillion-Gourdeau and Emmanuel Lorin, Simple digital quantum algorithm for symmetric first-order linear hyperbolic systems, Numerical Algorithms 82 (2019), 1009–1045, doi:10.1007/​s11075-018-0639-3.
https:/​/​doi.org/​10.1007/​s11075-018-0639-3

[15] Călin Ioan Gheorghiu, Spectral methods for differential problems, Casa Cărţii de Ştiinţă Cluj-Napoca, 2007.

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

[17] Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, 2012, doi:10.1017/​CBO9780511810817.
https:/​/​doi.org/​10.1017/​CBO9780511810817

[18] Ian D. Kivlichan, Nathan Wiebe, Ryan Babbush, and Alán Aspuru-Guzik, Bounding the costs of quantum simulation of many-body physics in real space, Journal of Physics A: Mathematical and Theoretical 50 (2017), no. 30, 305301, doi:10.1088/​1751-8121/​aa77b8.
https:/​/​doi.org/​10.1088/​1751-8121/​aa77b8

[19] Andreas Klappenecker and Martin Rotteler, Discrete cosine transforms on quantum computers, Proceedings of the 2nd International Symposium on Image and Signal Processing and Analysis, pp. 464–468, 2001, doi:10.1109/​ISPA.2001.938674.
https:/​/​doi.org/​10.1109/​ISPA.2001.938674

[20] Benjamin P. Lanyon, James D. Whitfield, Geoff G. Gillett, Michael E. Goggin, Marcelo P. Almeida, Ivan Kassal, Jacob D. Biamonte, Masoud Mohseni, Ben J. Powell, Marco Barbieri, Alán Aspuru-Guzik, and Andrew G. White, Towards quantum chemistry on a quantum computer, Nature Chemistry 2 (2010), no. 2, 106, doi:10.1038/​nchem.483.
https:/​/​doi.org/​10.1038/​nchem.483

[21] Jianping Li, General explicit difference formulas for numerical differentiation, Journal of Computational and Applied Mathematics 183 (2005), no. 1, 29–52, doi:10.1016/​j.cam.2004.12.026.
https:/​/​doi.org/​10.1016/​j.cam.2004.12.026

[22] Ashley Montanaro and Sam Pallister, Quantum algorithms and the finite element method, Physical Review A 93 (2016), no. 3, 032324, doi:10.1103/​PhysRevA.93.032324.
https:/​/​doi.org/​10.1103/​PhysRevA.93.032324

[23] 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 (2011), no. 17, 170501, doi:10.1103/​PhysRevLett.106.170501.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.170501

[24] Markus Püschel, Martin Rötteler, and Thomas Beth, Fast quantum Fourier transforms for a class of non-abelian groups, International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pp. 148–159, 1999, doi:10.1007/​3-540-46796-3_15.
https:/​/​doi.org/​10.1007/​3-540-46796-3_15

[25] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer, Elucidating reaction mechanisms on quantum computers, Proceedings of the National Academy of Sciences 114 (2017), no. 29, 7555–7560, doi:10.1073/​pnas.1619152114.
https:/​/​doi.org/​10.1073/​pnas.1619152114

[26] Martin Rötteler, Markus Püschel, and Thomas Beth, Fast signal transforms for quantum computers, Proceedings of the Workshop on Physics and Computer Science, pp. 31–43, 1999.

[27] Norbert Schuch and Jens Siewert, Programmable networks for quantum algorithms, Physical Review Letters 91 (2003), no. 2, 027902, doi:10.1103/​PhysRevLett.91.027902.
https:/​/​doi.org/​10.1103/​PhysRevLett.91.027902

[28] Jie Shen, Tao Tang, and Li-Lian Wang, Spectral methods: algorithms, analysis and applications, vol. 41, Springer Science & Business Media, 2011, doi:10.1007/​978-3-540-71041-7.
https:/​/​doi.org/​10.1007/​978-3-540-71041-7

[29] Jie Shen and Haijun Yu, Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems, SIAM Journal on Scientific Computing 32 (2010), no. 6, 3228–3250, doi:10.1137/​100787842.
https:/​/​doi.org/​10.1137/​100787842

[30] Jie Shen and Haijun Yu, Efficient spectral sparse grid methods and applications to high-dimensional elliptic equations II. Unbounded domains, SIAM Journal on Scientific Computing 34 (2012), no. 2, A1141–A1164, doi:10.1137/​110834950.
https:/​/​doi.org/​10.1137/​110834950

[31] Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25 (2006), no. 6, 1000–1010, doi:10.1109/​TCAD.2005.855930.

[32] Sergei Abramovich Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Doklady Akademii Nauk, vol. 148, pp. 1042–1045, 1963.

[33] Daniel Spielman, Rings, paths, and Cayley graphs (course notes), 2014, http:/​/​www.cs.yale.edu/​homes/​spielman/​561/​lect05-15.pdf.
http:/​/​www.cs.yale.edu/​homes/​spielman/​561/​lect05-15.pdf

[34] Jie Shen and Tao Tang, Spectral and high-order methods with applications, 2006, Science Press Beijing, https:/​/​www.math.purdue.edu/​ shen7/​sp_intro12/​book.pdf.
https:/​/​www.math.purdue.edu/​~shen7/​sp_intro12/​book.pdf

[35] Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Zhiqiang Wei, and Yongjian Gu, Quantum fast Poisson solver: the algorithm and modular circuit design, Quantum Information Processing 19 (2020), no. 6, 1–25, doi:10.1007/​s11128-020-02669-7.
https:/​/​doi.org/​10.1007/​s11128-020-02669-7

[36] Jonathan Welch, Daniel Greenbaum, Sarah Mostame, and Alán Aspuru-Guzik, Efficient quantum circuits for diagonal unitaries without ancillas, New Journal of Physics 16 (2014), no. 3, 033040, doi:10.1088/​1367-2630/​16/​3/​033040.
https:/​/​doi.org/​10.1088/​1367-2630/​16/​3/​033040

[37] Stephen Wiesner, Simulations of many-body quantum systems by a quantum computer, arXiv:quant-ph/​9603028 (1996).
arXiv:quant-ph/9603028

[38] Christof Zalka, Efficient simulation of quantum systems by quantum computers, Fortschritte der Physik 46 (1998), no. 6-8, 877–879, https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199811)46:6/​8<877::AID-PROP877>3.0.CO;2-A.
https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199811)46:6/​8<877::AID-PROP877>3.0.CO;2-A

[39] Christoph Zenger, Sparse grids, (1991), https:/​/​www5.in.tum.de/​pub/​zenger91sg.pdf.
https:/​/​www5.in.tum.de/​pub/​zenger91sg.pdf

### Cited by

[1] Alexandre C. Ricardo, Gabriel P. L. M. Fernandes, Eduardo I. Duzzioni, Vivaldo L. Campo, and Celso J. Villas-Boas, "Alternatives to a nonhomogeneous partial differential equation quantum algorithm", Physical Review A 106 5, 052431 (2022).

[2] Fong Yew Leong, Wei-Bin Ewe, and Dax Enshan Koh, "Variational quantum evolution equation solver", Scientific Reports 12 1, 10817 (2022).

[3] A. K. Fedorov and M. S. Gelfand, "Towards practical applications in quantum computational biology", Nature Computational Science 1 2, 114 (2021).

[4] Carlos Outeiral, Martin Strahm, Jiye Shi, Garrett M. Morris, Simon C. Benjamin, and Charlotte M. Deane, "The prospects of quantum computing in computational molecular biology", WIREs Computational Molecular Science 11 1(2021).

[5] Tieyu Zhao, Tianyu Yang, and Yingying Chi, "Quantum Weighted Fractional Fourier Transform", Mathematics 10 11, 1896 (2022).

[6] Changpeng Shao and Jin-Peng Liu, "Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 478 2262, 20210797 (2022).

[7] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian Giacomo Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", Journal of The Royal Society Interface 19 196, 20220541 (2022).

[8] Ljubomir Budinski, "Quantum algorithm for the advection–diffusion equation simulated with the lattice Boltzmann method", Quantum Information Processing 20 2, 57 (2021).

[9] Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Marc Gerritsma, and Roeland De Breuker, "Review and perspectives in quantum computing for partial differential equations in structural mechanics", Frontiers in Mechanical Engineering 8, 914241 (2022).

[10] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, "Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance", Quantum 5, 481 (2021).

[11] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).

[12] Noah Linden, Ashley Montanaro, and Changpeng Shao, "Quantum vs. Classical Algorithms for Solving the Heat Equation", Communications in Mathematical Physics 395 2, 601 (2022).

[13] Muhammad Sahimi and Pejman Tahmasebi, "The Potential of Quantum Computing for Geoscience", Transport in Porous Media 145 2, 367 (2022).

[14] Shi Jin, Nana Liu, and Yue Yu, "Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations", Journal of Computational Physics 471, 111641 (2022).

[15] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).

[16] Koichi Miyamoto and Kenji Kubo, "Pricing Multi-Asset Derivatives by Finite-Difference Method on a Quantum Computer", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[17] Kai Li, Ming Zhang, Xiaowen Liu, Yong Liu, Hongyi Dai, Yijun Zhang, and Chen Dong, "Quantum Linear System Algorithm for General Matrices in System Identification", Entropy 24 7, 893 (2022).

[18] Paula García-Molina, Javier Rodríguez-Mediavilla, and Juan José García-Ripoll, "Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations", Physical Review A 105 1, 012433 (2022).

[19] Reuben Demirdjian, Daniel Gunlycke, Carolyn A. Reynolds, James D. Doyle, and Sergio Tafur, "Variational quantum solutions to the advection–diffusion equation for applications in fluid dynamics", Quantum Information Processing 21 9, 322 (2022).

[20] Cheng Xue, Xiao-Fan Xu, Yu-Chun Wu, and Guo-Ping Guo, "Quantum algorithm for solving a quadratic nonlinear system of equations", Physical Review A 106 3, 032427 (2022).

[21] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, "Quantum simulation of real-space dynamics", Quantum 6, 860 (2022).

[22] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving, "Solving nonlinear differential equations with differentiable quantum circuits", Physical Review A 103 5, 052416 (2021).

[23] Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, and Andrew M. Childs, "Efficient quantum algorithm for dissipative nonlinear differential equations", Proceedings of the National Academy of Science 118 35, e2026805118 (2021).

[24] Carlos Outeiral, Martin Strahm, Jiye Shi, Garrett M. Morris, Simon C. Benjamin, and Charlotte M. Deane, "The prospects of quantum computing in computational molecular biology", arXiv:2005.12792, (2020).

[25] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Simulating option price dynamics with exponential quantum speedup", arXiv:2101.04023, (2021).

[26] Noah Linden, Ashley Montanaro, and Changpeng Shao, "Quantum vs. classical algorithms for solving the heat equation", arXiv:2004.06516, (2020).

[27] Hai-Ling Liu, Yu-Sen Wu, Lin-Chun Wan, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen, "Variational quantum algorithm for the Poisson equation", Physical Review A 104 2, 022418 (2021).

[28] Ljubomir Budinski, "Quantum algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method", arXiv:2103.03804, (2021).

[29] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, "Quantum simulation of real-space dynamics", arXiv:2203.17006, (2022).

[30] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", arXiv:2202.01054, (2022).

[31] Mohsen Bagherimehrab, Yuval R. Sanders, Dominic W. Berry, Gavin K. Brennen, and Barry C. Sanders, "Nearly Optimal Quantum Algorithm for Generating the Ground State of a Free Quantum Field Theory", PRX Quantum 3 2, 020364 (2022).

[32] Zhao-Yun Chen, Cheng Xue, Si-Ming Chen, Bing-Han Lu, Yu-Chun Wu, Ju-Chun Ding, Sheng-Hong Huang, and Guo-Ping Guo, "Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output", arXiv:2102.03557, (2021).

[33] Jaewoo Joo and Hyungil Moon, "Quantum variational PDE solver with machine learning", arXiv:2109.09216, (2021).

[34] S. Biedron, L. Brouwer, D. L. Bruhwiler, N. M. Cook, A. L. Edelen, D. Filippetto, C. -K. Huang, A. Huebl, T. Katsouleas, N. Kuklev, R. Lehe, S. Lund, C. Messe, W. Mori, C. -K. Ng, D. Perez, P. Piot, J. Qiang, R. Roussel, D. Sagan, A. Sahai, A. Scheinker, M. Thévenet, F. Tsung, J. -L. Vay, D. Winklehner, and H. Zhang, "Snowmass21 Accelerator Modeling Community White Paper", arXiv:2203.08335, (2022).

[35] Budinski Ljubomir, "Quantum algorithm for the Navier-Stokes equations by using the streamfunction-vorticity formulation and the lattice Boltzmann method", International Journal of Quantum Information 20 2, 2150039-27 (2022).

[36] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, "Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance", arXiv:2012.06283, (2020).

[37] Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei, and Yongjian Gu, "A quantum Poisson solver implementable on NISQ devices", arXiv:2005.00256, (2020).

[38] Cheng Xue, Yuchun Wu, and Guoping Guo, "Quantum Newton’s Method for Solving the System of Nonlinear Equations", Spin 11 3, 2140004 (2021).

[39] Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low, and Jiasu Wang, "Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation", arXiv:2205.01141, (2022).

[40] Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki Usuda, "Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals", arXiv:2106.08076, (2021).

[41] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", arXiv:2007.10253, (2020).

[42] Cheng Xue, Yu-Chun Wu, and Guo-Ping Guo, "Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations", New Journal of Physics 23 12, 123035 (2021).

[43] Koichi Miyamoto and Kenji Kubo, "Pricing multi-asset derivatives by finite difference method on a quantum computer", arXiv:2109.12896, (2021).

[44] Guillermo González, Rahul Trivedi, and J. Ignacio Cirac, "Quantum algorithms for powering stable Hermitian matrices", Physical Review A 103 6, 062420 (2021).

[45] Xi-Ning Zhuang, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, "Quantum computational quantitative trading: high-frequency statistical arbitrage algorithm", New Journal of Physics 24 7, 073036 (2022).

[46] Changpeng Shao and Jin-Peng Liu, "Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer", arXiv:2010.15027, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2023-01-27 02:19:11) and SAO/NASA ADS (last updated successfully 2023-01-27 02:19:12). The list may be incomplete as not all publishers provide suitable and complete citation data.