Exponential Quantum Speedup in Simulating Coupled Classical Oscillators

We present a quantum algorithm for simulating the classical dynamics of $2^n$ coupled oscillators (e.g., $2^n$ masses coupled by springs). Our approach leverages a mapping between the Schrödinger equation and Newton’s equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in $n$, almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time. We show that any classical algorithm solving this same problem is inefficient and must make $2^{\mathrm{\Omega }(n)}$ queries to the oracle, and when the oracles are instantiated by efficient quantum circuits, the problem is bounded-error quantum polynomial time complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with $2^n$ modes.

Popular Summary

Quantum computing offers the potential to solve certain problems far more efficiently than can be done on a classical computer. While certain use cases are known, the discovery of even more remains critical for understanding and motivating the value proposition of quantum computers. Here, we introduce a new such class of problems: simulating the dynamics of many coupled, classical oscillators. Simulations of such systems could prove relevant to many real-world applications such as the modeling of electrical grids, molecular vibrations, and structural engineering, all of which are described by coupled classical oscillators.

In particular, we show that one can simulate the dynamics of exponentially coupled classical oscillators on a quantum computer using resources that grow only polynomially. Our algorithm works by showing that one can map the phase space of coupled classical oscillators to that of a quantum system of exponentially smaller size, which can be simulated efficiently using state-of-the-art techniques. We prove it is impossible to efficiently solve the same problem on a classical computer unless all quantum circuits can be efficiently simulated on a classical computer. We also prove that if details of the system we are simulating are provided by a black-box circuit, then our algorithm must query that black-box circuit exponentially fewer times than any classical algorithm.

The impact of this work is twofold: First, it potentially unlocks several new, practical applications of quantum computers with a large quantum advantage that go beyond quantum simulation. Second, it provides a new way of reasoning about the mechanisms of certain quantum algorithms in terms of a type of classical mechanical wave interference in a larger classical system.

Figure 1

An example system of $N/2$ oscillators in $D=2$ dimensions. We use $x_1(t)$ for the first coordinate of the first mass and $x_2(t)$ for the second coordinate of the first mass, and so on. Since the first and second mass now correspond to the same original mass, $m_1=m_2$.

Figure 2

A network of $N=2^{n+1}-2$ coupled oscillators obtained by randomly gluing two binary trees. Each mass is $m_j=1$ for all $j\in [N]$ and is labeled by a random bit string of size $2n$. Edges denote springs of constant ${\kappa }_{jk}=1$. The goal is to find the label of the EXIT mass given the label of the ENTRANCE mass and given oracle access to the network.

Figure 3

The $2n\times 2n$ matrix $\tilde{A}=3{\mathbb{1}}_{2n}-\tilde{\mathbf{A}}$ viewed as the adjacency matrix of a weighted graph.

Figure 4

Numerical simulation of the network in Fig. 2 for $n=20$ ($N=2^{21}-2$). Initially $\overrightarrow{x}(0)=(0,0,\dots ,0{)}^T$ and $\dot{\overrightarrow{x}}(0)=(1,0,\dots ,0{)}^T$. At time $t\approx 2n$, $|{\dot{x}}_N(t)|$ becomes significant. Similar behavior is observed for larger values of $n$.