Technical Summary: Quantum Computational Complexity of Classical Linear Dynamics with Geometrically Local Interactions

Problem Statement

The paper addresses the computational complexity of simulating classical linear dynamics governed by first-order linear differential equations on quantum computers, specifically focusing on systems with geometrically local interactions. While prior work (e.g., Babbush et al.) demonstrated that quantum algorithms could offer exponential speedups for classical systems with long-range interactions (such as coupled oscillators with arbitrary coupling), many real-world systems described by partial differential equations (PDEs)—like fluid dynamics, plasma dynamics, and wave equations—exhibit only geometrically local interactions.

The central question is whether quantum algorithms can still provide exponential advantages (in time or space) when simulating these local systems, or if the locality constraint allows for efficient classical simulation (dequantization). The authors analyze this problem by distinguishing between two regimes of evolution time $t$:

1. Short-time regime: $t = \text{polylog}(N) = \text{poly}(n)$, where $N=2^n$ is the system size.
2. Long-time regime: $t = \text{poly}(N) = \text{exp}(n)$.

The study assumes the initial state can be efficiently sampled classically, ensuring any potential advantage arises solely from the time evolution. The goal is to estimate quantities (inner products) or sample from the time-evolved state.

Methodology

1. Dequantization of Quantum Eigenvalue Transformation (QEVT)

The core technical contribution is the dequantization of the QEVT algorithm for geometrically local matrices.

• Geometrically Local Matrices: The authors define a matrix $A$ as $(r_0, N(r_0))$-geometrically local if non-zero entries $A_{ij}$ exist only when the distance $d(i,j) \le r_0$ on a specific lattice, and the number of sites within distance $r$ grows polynomially with $r$ (i.e., $N(r) = \text{poly}(r)$).
• Light Cone Property: A key lemma establishes that for such matrices, the power $A^k$ has non-zero entries only within a distance $k \cdot r_0$. This "light cone" restricts the propagation of information.
• Classical Simulation: The authors construct a classical algorithm to compute the $i$-th entry of $P(A)u$ (where $P$ is a polynomial of degree $d$) by iteratively querying non-zero entries. Due to the locality, the number of non-zero entries in $A^k u$ remains bounded by $N(kr_0) = \text{poly}(k)$.
• Complexity: The classical algorithm runs in time and space polynomial in $d$ and $n$ (specifically $\text{poly}(d, n)$), matching the complexity of the quantum algorithm up to polynomial overhead, provided $d = \text{poly}(n)$.

2. Sampling Simulation

The paper extends dequantization to the sampling problem (generating samples from the probability distribution defined by the evolved state).

• Rejection Sampling: The authors employ a robust rejection sampling technique. They utilize the light cone property to construct an "easy" distribution $p_{\text{over}}$ (sampling from the initial state and then uniformly within the light cone of radius $d \cdot r_0$) that oversamples the target distribution $P(A)|\psi\rangle$.
• Result: This allows for efficient classical sampling from the short-time evolved state with polynomial resources.

3. Hardness and Universality Proofs

To establish the lower bounds and the limits of dequantization, the authors embed computational models into the physical systems:

• Short-time Hardness: They embed a classical reversible circuit (of depth $\text{polylog}(N)$) into a 1D geometrically local Hamiltonian (using a Feynman-Kitaev construction adapted for coupled harmonic oscillators). This proves that simulating short-time dynamics is at least as hard as probabilistic classical computation with $\text{polylog}(N)$ time and $O(n)$ space.
• Long-time Universality: They demonstrate that simulating long-time dynamics ($t = \text{poly}(N)$) is equivalent to universal quantum computation. By embedding an $n$-qubit quantum circuit of depth $\text{poly}(N)$ into a 2D geometrically local system (using dilated Hamiltonians and decomposing non-local gates into local interactions), they show that the long-time dynamics can simulate any $\text{poly}(N)$-time, $O(n)$-space quantum computation.

Key Results

1. No Exponential Advantage in Short-Time Regime

For systems with geometrically local interactions evolving for short times ($t = \text{polylog}(N)$):

• Dequantization: The problem of estimating inner products or sampling from the evolved state can be solved classically with polynomial time and space complexity ($\text{poly}(n)$).
• Implication: There is no exponential quantum advantage in either time or space for these regimes. The classical algorithm achieves the same complexity as the quantum algorithm up to polynomial factors. This holds even when the initial state and observables are global, provided the interactions are local.

2. Hardness of Short-Time Dynamics

Simulating short-time dynamics is BPP-hard (specifically, at least as hard as $\text{polylog}(N)$-time and $O(n)$-space probabilistic classical computation). This establishes that while quantum computers offer no exponential speedup, the problem is not trivial; it captures the complexity of efficient classical probabilistic computation.

3. Exponential Advantage in Long-Time Regime

For long-time evolution ($t = \text{poly}(N)$):

• Universality: The computational complexity of simulating these dynamics is equivalent to BQP (specifically, $\text{poly}(N)$-time and $O(n)$-space quantum computation).
• Advantage:
  • Space: If classical resources are restricted to $\text{poly}(n)$ space, simulating the long-time dynamics requires exponential time ($\text{exp}(n)$), whereas quantum computers require only polynomial time. This yields an exponential space advantage for quantum computers.
  • Time: If classical resources are restricted to $\text{poly}(n)$ space, the best known classical algorithms require $\text{exp}(n^2)$ time (or similar super-polynomial time), suggesting a super-polynomial time advantage for quantum computers.
• Mechanism: The dequantization fails here because the "light cone" of information propagation expands to size $\text{poly}(N)$, effectively inducing long-range interactions that allow the encoding of universal quantum circuits.

Significance and Claims

The paper claims to provide the first complexity-theoretic characterization of simulating realistic classical systems (governed by PDEs with local interactions) on quantum computers.

1. Refutation of Universal Exponential Speedup: The work clarifies that the exponential quantum speedups previously proposed for classical dynamics (e.g., in Ref. [6]) rely crucially on long-range interactions. When interactions are geometrically local, these exponential advantages vanish for short-time simulations.
2. Clarification of Quantum Advantage: The paper delineates a sharp boundary:
   • Short-time: Classical computers are sufficient (up to polynomial overhead).
   • Long-time: Quantum computers offer a genuine advantage (exponential in space or super-polynomial in time) due to the ability of local dynamics to simulate universal quantum computation over long durations.
3. New Technical Tool: The dequantization technique for geometrically local matrices provides a method to efficiently simulate polynomial transformations of such matrices classically, which is applicable to various physical systems like coupled harmonic oscillators and discretized wave equations.

The authors conclude that while quantum computers do not offer exponential speedups for short-time local dynamics, they remain essential for long-time simulations where information propagation across the entire system induces effective non-locality, enabling the simulation of universal quantum computation.