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.


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.

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

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

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

[6] Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numerica 13 (2004), 147–269, doi: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.

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

[9] Andrew M. Childs and Jin-Peng Liu, Quantum spectral methods for differential equations, doi: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.

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

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

[13] Lawrence C. Evans, Partial differential equations (2nd ed.), American Mathematical Society, 2010, doi: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.

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

[17] Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, 2012, doi: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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by

[1] Ismail Yunus Akhalwaya, Adam Connolly, Roland Guichard, Steven Herbert, Cahit Kargi, Alexandre Krajenbrink, Michael Lubasch, Conor Mc Keever, Julien Sorci, Michael Spranger, and Ifan Williams, "A Modular Engine for Quantum Monte Carlo Integration", arXiv:2308.06081, (2023).

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

[3] Fatima Ezahra Chrit, Sriharsha Kocherla, Bryan Gard, Eugene F. Dumitrescu, Alexander Alexeev, and Spencer H. Bryngelson, "Fully quantum algorithm for lattice Boltzmann methods with application to partial differential equations", arXiv:2305.07148, (2023).

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

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

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

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

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

[9] I. Joseph, Y. Shi, M. D. Porter, A. R. Castelli, V. I. Geyko, F. R. Graziani, S. B. Libby, and J. L. DuBois, "Quantum computing for fusion energy science applications", Physics of Plasmas 30 1, 010501 (2023).

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

[11] Zhaoyuan Meng and Yue Yang, "Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation", Physical Review Research 5 3, 033182 (2023).

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

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

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

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

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

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

[18] Yizhou Liu, Weijie J. Su, and Tongyang Li, "On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks", Quantum 7, 1030 (2023).

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

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

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

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

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

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

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

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

[27] Juan Castaneda and Nathan Wiebe, "Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States", arXiv:2308.13020, (2023).

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

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

[30] Soronzonbold Otgonbaatar and Dieter Kranzlmüller, "Exploiting the Quantum Advantage for Satellite Image Processing: Quantum Resource Estimation", arXiv:2308.09453, (2023).

[31] Alexander Engel and Scott E. Parker, "Correspondence between open bosonic systems and stochastic differential equations", European Physical Journal Plus 138 6, 578 (2023).

[32] D. V. Babukhin, "Harrow-Hassidim-Lloyd algorithm without ancilla postselection", Physical Review A 107 4, 042408 (2023).

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

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

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

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

[37] Koichi Miyamoto and Hiroshi Ueda, "Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion", Quantum Information Processing 22 6, 239 (2023).

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

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

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

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

[42] Paula García-Molina, Luca Tagliacozzo, and Juan José García-Ripoll, "Global optimization of MPS in quantum-inspired numerical analysis", arXiv:2303.09430, (2023).

[43] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).

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

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

[46] Dylan Lewis, Stephan Eidenbenz, Balasubramanya Nadiga, and Yiğit Subaşı, "Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems", arXiv:2307.09593, (2023).

[47] Shi-Jie Wei, Chao Wei, Peng Lv, Changpeng Shao, Pan Gao, Zengrong Zhou, Keren Li, Tao Xin, and Gui-Lu Long, "A quantum algorithm for heat conduction with symmetrization", Science Bulletin 68 5, 494 (2023).

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

[49] Shi Jin, Nana Liu, and Yue Yu, "Quantum simulation of partial differential equations: Applications and detailed analysis", Physical Review A 108 3, 032603 (2023).

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-10-01 02:51:33). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-10-01 02:51:29: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2021-11-10-574.