Hub researchers' paper amongst top 10 downloaded from prestigious journal
A paper published by Hub researchers Noah Linden, Ashley Montanaro, and Changpeng Shao was in the top ten papers downloaded in 2022 from the journal Communications in Mathematical Physics, the premier journal in Mathematical Physics.
Their paper, “Quantum vs. Classical Algorithms for Solving the Heat Equation”, provides an important benchmark for understanding how quantum computers might impact scientific computing and engineering. Focussing on comparing classical and quantum algorithms for solving the heat equation, their work made some very important discoveries.
So what exactly is the heat equation? In essence, it describes how heat diffuses over time through a material. Picture a warming cup of coffee. The way the heat spreads through the liquid can be modelled using this equation. But real-world problems get far more complex, involving heat flow in 3D spaces like aeroplane engines. But this pivotal equation contains intricacies that can overwhelm even the most powerful supercomputers. In their paper, the authors demonstrated that quantum computers could provide a long-sought speedup – potentially accelerating solutions to the heat equation by orders of magnitude, but not by as wide a margin as might have been hoped.
Linden, Montanaro, and Shao compared several classical algorithms and quantum algorithms for approximately solving the heat equation in order to probe where quantum advantages may lie. The heat equation can be extended to model diffusion in multiple spatial dimensions – for example, in a 2D or 3D object. By studying the performance of the algorithms on higher dimensional versions of the problem, the researchers could test where quantum speedups appear for settings more relevant to practical use cases
Their key findings? For the 1-dimensional heat equation, none of the quantum algorithms were faster than the best classical one based on the Fast Fourier Transform. But for 2 or more spatial dimensions, the best quantum algorithm achieved a quadratic speedup over classical methods by using a technique called amplitude estimation to the fast classical random walk algorithm. Surprisingly, a quantum algorithm, expected to yield exponential speedups via linear equation solving did not outperform classical approaches as might have been hoped.
The results show that while polynomial quantum speedups are achievable for this foundational problem, exponential gains may be out of reach. By benchmarking performance on specific cases, Linden, Montanaro, and Shao's work helps map where quantum computers can truly accelerate scientific computing tasks like simulation. Their findings suggest that quantum advantages may be more nuanced than originally thought across different problem settings and dimensions. More comparative studies between quantum and classical algorithms will be key for pinpointing where quantum computing can impact both science and engineering.