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

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

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.

► BibTeX data

► 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.
https:/​/​doi.org/​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] 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, WIREs Computational Molecular Science 11 1(2021).

[2] 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", arXiv:2011.03185.

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

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

[5] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Pricing Financial Derivatives with Exponential Quantum Speedup", arXiv:2101.04023.

[6] 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).

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

[8] Paula García-Molina, Javier Rodríguez-Mediavilla, and Juan José García-Ripoll, "Solving partial differential equations in quantum computers", arXiv:2104.02668.

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

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

[11] Ljubomir Budinski, "Quantum algorithm for the Navier-Stokes equations", arXiv:2103.03804.

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

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

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

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

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

[17] 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", arXiv:2110.05708.

[18] Cheng Xue, Yu-Chun Wu, and Guo-Ping Guo, "Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations", arXiv:2111.07486.

[19] Xi-Ning Zhuang, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, "Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm", arXiv:2104.14214.

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-12-08 01:38:50) and SAO/NASA ADS (last updated successfully 2021-12-08 01:38:51). The list may be incomplete as not all publishers provide suitable and complete citation data.