A Quantum Leap in Classical Mechanics: Exponential Speedup Unveiled by Google

By Robin Kothari and Rolando Somma, Research Scientists, Google Research, Quantum AI Team

Quantum computers are renowned for their potential to solve certain problems exponentially faster than classical computers. However, such dramatic speedups have been limited to a handful of examples, notably Shor’s factoring algorithm and quantum simulation, primarily focusing on inherently quantum mechanical systems. But what about systems rooted in classical mechanics? Can quantum computers revolutionize their simulation as well?

In a groundbreaking study titled "Exponential quantum speedup in simulating coupled classical oscillators," published in Physical Review X (PRX) and presented at the Symposium on Foundations of Computer Science (FOCS 2023), we unveil a new quantum algorithm offering exponential advantages in simulating coupled classical harmonic oscillators. These oscillators, fundamental in nature, pervade various domains, from electrical circuits to molecular vibrations to structural mechanics. Collaborating with Dominic Berry of Macquarie University and Nathan Wiebe of the University of Toronto, we devised a transformative mapping that translates systems of coupled oscillators into quantum mechanical problems, solvable exponentially faster on a quantum computer under certain constraints.

Simulation of Coupled Oscillators: We start with classical harmonic oscillators, exemplified by a mass attached to a spring. Extending this to coupled oscillators, where multiple masses are interconnected via springs, yields complex dynamics. Simulating such systems classically becomes increasingly arduous with growing complexity.

Our innovation lies in encoding the positions and velocities of masses and springs into the quantum wavefunction of qubit systems. Leveraging the exponential growth of qubit parameters, we encode N masses into a logarithmic number of qubits, facilitating efficient evolution of the wavefunction. This approach enables the simulation of large-scale coupled oscillators with significantly fewer resources compared to classical methods, provided the system possesses a concise description.

Evidence of Exponential Speedup: To demonstrate the exponential superiority of our quantum algorithm, we provide compelling evidence:

1. The Glued-Trees Problem and the Quantum Oracle: We showcase the quantum algorithm's efficiency in solving the glued-trees problem, a graph-theoretic challenge notoriously hard for classical computation. By mapping this problem to a ball-and-spring system, we exploit the efficiency of quantum evolution to detect the exit node exponentially faster than classical methods.
2. BQP-Completeness: We establish the BQP-completeness of our problem domain, indicating its position among the most challenging problems solvable efficiently on a quantum computer. This assertion reinforces the exponential advantage of our quantum algorithm over any classical counterpart.

Implications and Future Directions: Our findings illuminate a deeper connection between classical oscillating systems and quantum algorithms, bridging the gap between classical and quantum computation. By unveiling the equivalence between classical oscillator dynamics and quantum wave propagation, we pave the way for the design of novel quantum algorithms with exponential speedups.

Moreover, our work hints at the potential for real-world applications, where quantum computers could revolutionize the simulation of systems governed by coupled oscillators, spanning diverse fields such as engineering, chemistry, and physics.

Acknowledgments: We extend our gratitude to Katie McCormick, our Quantum Computing Science Communicator, for her invaluable assistance in crafting this article.

In conclusion, our discovery not only unlocks new frontiers in quantum computation but also underscores the transformative potential of quantum algorithms in classical mechanics, promising unparalleled insights into the dynamics of complex systems.