Quantum computational complexity of classical linear dynamics with geometrically local interactions
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. Prior work demonstrated exponential quantum speedups for simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. In this work, we study whether quantum advantage can persist under such locality constraints. We show that quantum algorithms for simulating short-time dynamics of geometrically local systems can be dequantized, ruling out exponential quantum advantage in this regime. In contrast, we show that the computational complexity of simulating long-time dynamics is captured by exponential-time and polynomial-space quantum computation. This implies an exponential space advantage over classical simulation, or a super-polynomial time advantage when classical computation is restricted to polynomial space. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.

