2022/08/24 by Noah Linden, Ashley Montanaro, Changpeng Shao · 16 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.1007/s00220-022-04442-6
Abstract 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 ≥ 2 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> , there is an at most quadratic quantum speedup in terms of the allowable error ε <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math> 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.