On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
Kazuki Sakamoto, Keisuke Fujii · 2025
Read On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality by Kazuki Sakamoto, Keisuke Fujii (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10445.txt.
Introduction
Sakamoto and Fujii draw the exact border of quantum advantage for simulating ordinary physics with local rules. A prior result promised exponential quantum speedup for classical systems whose parts all touch each other. Real systems, like fluids, interact only with neighbors. The pair ask what survives of the speedup then.
For short runs of such local systems, they dequantize the quantum method: a classical trick matches it, so no exponential edge exists. Short-run simulation is also provably hard, matching a broad class of classical computing. For very long runs, the problem's difficulty jumps to a quantum class, hinting at space savings rather than time savings. The map tells builders where quantum hardware can truly help.
Catalog record
| CREATOR | Kazuki Sakamoto, Keisuke Fujii |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 126 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-10445
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality Kazuki Sakamoto, Keisuke Fujii Abstract The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in 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. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. 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. 1 Introduction The simulation of quantum systems is one of the key problems expected to demonstrate exponential quantum advantage. This advantage is natural because quantum computers inherently utilize the principles of quantum mechanics as Feynman pointed out [ 1 ] . Moreover, such speedups achieved in quantum simulation is guaranteed by rigorous analysis with computational complexity theory. That is, quantum simulation problem is \mathrm{BQP} -complete [ 2 , 3 , 4 ] , which implies that “any” classical algorithm cannot simulate those quantum systems efficiently under the widely-believed complexity-theoretic assumption \mathrm{BPP}\neq\mathrm{BQP} . As recent works investigated, quantum computers have potential applications to not only quantum systems but also classical systems. Many classical systems can be described by first-order linear ordinary differential equations. Even when higher-order derivatives are involved, these equations can be converted to first-order equations by introducing auxiliary variables [ 5 , 6 ] . Therefore, quantum algorithms for solving first-order linear ordinary differential equations have been actively studied. One major approach converts the differential equation into a linear system of equations by discretizing the time derivative and dilating the Hilbert space [ 7 , 8 , 9 , 10 , 11 ] and uses quantum linear system solvers [ 12 , 13 , 14 , 15 , 16 ] . Another approach converts the differential equation into a Schrödinger equation [ 5 , 17 , 18 ] and uses Hamiltonian simulation algorithm [ 3 , 19 , 20 , 21 ] . While many other algorithms use their unique approaches respectively [ 22 , 23 , 24 , 25 ] , in any case, we can interpret most of the algorithms as a polynomial transformation of some matrices using quantum eigenvalue transformation (QEVT) [ 11 ] . In the case of linear partial differential equations, quantum computers can also solve the problems since discretizing a partial differential equation leads to an ordinary differential equation. Then quantum algorithms and their circuit implementations for specific partial differential equations appeared in physics are proposed [ 5 , 26 , 17 , 18 , 27 , 28 , 29 , 30 , 31 , 32 , 33 ] . It should be noted that such quantum algorithms assume an efficient initial state preparation and provide efficient access to limited information extracted from the final quantum state, such as expectation values or samples, rather than unrestricted access to the full classical solution. In this setting, quantum computers are expected to solve certain tasks associated with classical systems with exponentially smaller resources of time and space than classical computers [ 5 , 30 , 31 , 34 , 35 ] . However, at present, such exponential quantum advantages are not guaranteed from complexity theoretic perspectives in most cases. Recent work by Babbush et al. partially solved this problem [ 6 ] . They proposed a quantum algorithm that can simulate the classical dynamics of exponentially many coupled oscillators, e.g., masses coupled by springs, in polynomial time. They introduced the reduction from Newton’s equation to Schrödinger equation and then showed that the Schrödinger equation can be solved efficiently using Hamiltonian simulation algorithm under appropriate conditions such as the sparsity of interactions. This algorithm also relies on efficient initial state preparation and provides access only to quantities that can be efficiently extracted from the final quantum state. They also showed that such classical dynamics can simulate universal quantum computation, that is, a certain problem obtained from that dynamics is BQP-complete. This means that the dynamics cannot be simulated efficiently on classical computers under the assumption of \mathrm{BQP}\neq\mathrm{BPP} . The essential part for showing BQP-completeness is that they allow long-range interactions between masses. However, many classical systems which appear in the real world have only geometrically local interactions. For example, the equations obtained by discretizing partial differential equations of fluid dynamics [ 36 ] or plasma dynamics [ 37 ] , e.g., the wave equation [ 5 ] , can be regarded as classical systems with spatially local interactions. Thus it is important to analyze the computational complexity of simulating the dynamics of such geometrically local classical systems on quantum computers. In this work, we provide a thorough characterization of the computational complexity of simulating classical linear dynamics with geometrically local interactions on quantum computers. Specifically, we consider classical systems of size N=2^{n} governed by first-order linear differential equations that can be solved by O(n) -qubit quantum algorithms. Note that we assume that the initial state can be efficiently sampled classically. This assumption ensures that quantum advantages arise solely from the time evolution, not from the description of the initial state. We then consider the problem of either estimating a quantity given by an inner product, or sampling from the time-evolved state. These problems are natural setups for quantum computers and corresponding quantum algorithms have an exponential space advantage over the conventional classical algorithms. In addition, we assume that the quantum algorithm runs in \mathrm{poly}(t,n) -time for an evolution time t , which restricts our focus to classical systems that can be efficiently simulated on quantum computers. This condition naturally holds when the original equation can be mapped to the Schrödinger equation [ 6 ] . In contrast, it does not generally hold for arbitrary linear dynamics, thereby excluding equations that cannot be solved efficiently on quantum computers. Throughout this work, we refer to the regime t=\mathrm{polylog}(N)=\mathrm{poly}(n) as short-time evolution, and t=\mathrm{poly}(N)=\exp{(n)} as long-time evolution. We distinguish these two regimes for both computational and physical reasons. The short-time regime corresponds to the parameter region where quantum algorithms run efficiently, that is, in \mathrm{poly}(n) -time. In contrast, the long-time regime is necessary for information to propagate across geometrically local systems and reach the boundaries, thereby enabling us to observe global and physically meaningful phenomena. We have three main results (see Fig. 1 ): (i) We dequantize the quantum algorithm for simulating the classical dynamics in the