Built on

A. Childs and J.-P. Liu, Quantum spectral methods for differential equations, Comm. Math. Phys. (2020), arXiv:1901.00961
Original
1901
Earlier work this paper cites.
M. Lubasch, J. Joo, P. Moinier, M. Kiffner, and D. Jaksch, Variational quantum algorithms for nonlinear problems (2019), arXiv:1907.09032
Original
1907
Earlier work this paper cites.
S. Wang, Z. Wang, W. Li, L. Fan, Z. Wei, and Y. Gu, Quantum fast Poisson solver: the algorithm and modular circuit design (2019), arXiv:1910.09756
Original
1910
Earlier work this paper cites.
N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning (2019), arXiv:1910.06151
Original
1910
Earlier work this paper cites.
O. Ore, On functions with bounded derivatives, Transactions of the American Mathematical Society 43
1938
Earlier work this paper cites.
M. Kac, Random walk and the theory of Brownian motion, American Mathematical Monthly 54
1947
Earlier work this paper cites.
G. King, Monte-Carlo method for solving diffusion problems, Industrial and Engineering Chemistry 43
1951
Earlier work this paper cites.
W. Bauer, The Monte Carlo method, J. Soc. Indust. Appl. Math. 6
1958
Earlier work this paper cites.
R. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, in Analytic computational complexity (Elsevier, 1976) pp. 151–176, arXiv:1004.3412
Original
1976
Earlier work this paper cites.
L. Devroye, Non-uniform random variate generation (Springer-Verlag, New York, 1986)
1986
Earlier work this paper cites.
V. Kachitvichyanukul and B. Schmeiser, Binomial random variate generation, C. ACM 31
1988
Earlier work this paper cites.
N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica 12
1992
Earlier work this paper cites.
J. Shewchuk, An introduction to the conjugate gradient method without the agonizing pain , Tech. Rep. CMU-CS-TR-94-125 (Carnegie Mellon University, 1994) http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.ps
1994
Earlier work this paper cites.
L. Trefethen, Finite difference and spectral methods for ordinary and partial differential equations (1996), http://people.maths.ox.ac.uk/trefethen/pdetext.html
1996
Earlier work this paper cites.
C. Zalka, Simulating quantum systems on a quantum computer, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 454
1998
Earlier work this paper cites.

Similar

G.-L. Long and Y. Sun, Efficient scheme for initializing a quantum register with an arbitrary superposed state, Phys. Rev. A 64
2001
Cited alongside, same era.
J. Watrous, Quantum simulations of classical random walks and undirected graph connectivity, J. Comput. Syst. Sci. 62
2001
Cited alongside, same era.
A. Childs, J.-P. Liu, and A. Ostrander, High-precision quantum algorithms for partial differential equations (2020), arXiv:2002.07868
Original
2002
Cited alongside, same era.
G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information: A Millennium Volume 305
2002
Cited alongside, same era.
L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002), quant-ph/0208112
2002

Then

Y. Cao, A. Papageorgiou, I. Petras, J. Traub, and S. Kais, Quantum algorithm and circuit design solving the Poisson equation, New J. Phys. 15
Original
2013
Later among the works it cites.
D. Berry, High-order quantum algorithm for solving linear differential equations, J. Phys. A: Math. Gen. 47
Original
2014
Later among the works it cites.
K. Bringmann, F. Kuhn, K. Panagiotou, U. Peter, and H. Thomas, Internal DLA: Efficient simulation of a physical growth model, in Proc. 41 st International Conference on Automata, Languages and Programming (ICALP’14) (2014) pp. 247–258
2014
Later among the works it cites.
M. Farach-Colton and M.-T. Tsai, Exact sublinear binomial sampling, Algorithmica 73
2015
Later among the works it cites.
A. Montanaro and S. Pallister, Quantum algorithms and the finite element method, Phys. Rev. A 93

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2020

Quantum vs. classical algorithms for solving the heat equation

Linden, Noah, Montanaro, Ashley, Shao, Changpeng

Understand

Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially.

Here we consider a prototypical PDE - the heat equation in a rectangular region - and compare in detail the complexities of ten classical and quantum algorithms for solving it, in the sense of approximately computing the amount of heat in a given region.
We find that, for spatial dimension $d \ge 2$, there is an at most quadratic quantum speedup using an approach based on applying amplitude estimation to an accelerated classical random walk.
However, an alternative approach based on a quantum algorithm for linear equations is never faster than the best classical algorithms.

Built on

A. Childs and J.-P. Liu, Quantum spectral methods for differential equations, Comm. Math. Phys. (2020), arXiv:1901.00961
Original
1901
Earlier work this paper cites.
M. Lubasch, J. Joo, P. Moinier, M. Kiffner, and D. Jaksch, Variational quantum algorithms for nonlinear problems (2019), arXiv:1907.09032
Original
1907
Earlier work this paper cites.
S. Wang, Z. Wang, W. Li, L. Fan, Z. Wei, and Y. Gu, Quantum fast Poisson solver: the algorithm and modular circuit design (2019), arXiv:1910.09756
Original
1910
Earlier work this paper cites.
N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning (2019), arXiv:1910.06151
Original
1910
Earlier work this paper cites.
O. Ore, On functions with bounded derivatives, Transactions of the American Mathematical Society 43
1938
Earlier work this paper cites.
M. Kac, Random walk and the theory of Brownian motion, American Mathematical Monthly 54
1947
Earlier work this paper cites.
G. King, Monte-Carlo method for solving diffusion problems, Industrial and Engineering Chemistry 43
1951
Earlier work this paper cites.
W. Bauer, The Monte Carlo method, J. Soc. Indust. Appl. Math. 6
1958
Earlier work this paper cites.
R. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, in Analytic computational complexity (Elsevier, 1976) pp. 151–176, arXiv:1004.3412
Original
1976
Earlier work this paper cites.
L. Devroye, Non-uniform random variate generation (Springer-Verlag, New York, 1986)
1986
Earlier work this paper cites.
V. Kachitvichyanukul and B. Schmeiser, Binomial random variate generation, C. ACM 31
1988
Earlier work this paper cites.
N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica 12
1992
Earlier work this paper cites.
J. Shewchuk, An introduction to the conjugate gradient method without the agonizing pain , Tech. Rep. CMU-CS-TR-94-125 (Carnegie Mellon University, 1994) http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.ps
1994
Earlier work this paper cites.
L. Trefethen, Finite difference and spectral methods for ordinary and partial differential equations (1996), http://people.maths.ox.ac.uk/trefethen/pdetext.html
1996
Earlier work this paper cites.
C. Zalka, Simulating quantum systems on a quantum computer, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 454
1998
Earlier work this paper cites.

Similar

G.-L. Long and Y. Sun, Efficient scheme for initializing a quantum register with an arbitrary superposed state, Phys. Rev. A 64
2001
Cited alongside, same era.
J. Watrous, Quantum simulations of classical random walks and undirected graph connectivity, J. Comput. Syst. Sci. 62
2001
Cited alongside, same era.
A. Childs, J.-P. Liu, and A. Ostrander, High-precision quantum algorithms for partial differential equations (2020), arXiv:2002.07868
Original
2002
Cited alongside, same era.
G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information: A Millennium Volume 305
2002
Cited alongside, same era.
L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002), quant-ph/0208112
2002