A new quantum algorithm has been discovered that offers an exponential advantage for simulating coupled classical harmonic oscillators, according to a study published in Physical Review X and presented at the Symposium on Foundations of Computer Science. The research was conducted in collaboration with Dominic Berry of Macquarie University and Nathan Wiebe of the University of Toronto. The algorithm can transform any system involving coupled oscillators into a problem describing the time evolution of a quantum system. This could be solved exponentially faster with a quantum computer than with a classical computer, unlocking previously unknown applications of quantum computers.
Quantum Computing and Classical Oscillators
Quantum computers can potentially solve certain problems exponentially faster than classical computers. However, this speedup is typically seen in the simulation of physical systems that are inherently quantum mechanical. A recent study published in Physical Review X and presented at the Symposium on Foundations of Computer Science (FOCS 2023) explores whether quantum computers can offer an exponential advantage for simulating systems that are not inherently quantum, such as coupled classical harmonic oscillators.
Coupled classical harmonic oscillators are fundamental systems in nature, describing the physics of numerous natural systems, from electrical circuits to molecular vibrations to the mechanics of bridges. The researchers, in collaboration with Dominic Berry of Macquarie University and Nathan Wiebe of the University of Toronto, discovered a mapping that can transform any system involving coupled oscillators into a problem describing the time evolution of a quantum system. Given certain constraints, this problem can be solved with a quantum computer exponentially faster than it can with a classical computer.
“Coupled harmonic oscillators are ubiquitous in nature, describing a broad range of systems from electrical circuits to chains of molecules to structures such as bridges. While our work here focuses on the fundamental complexity of this broad class of problems, we expect that it will guide us in searching for real-world examples of harmonic oscillator problems in which a quantum computer could offer an exponential advantage.”
Authors of the study
Simulating Coupled Oscillators with Quantum Computers
The systems under consideration consist of classical harmonic oscillators. An example of a single harmonic oscillator is a mass (such as a ball) attached to a spring. If you displace the mass from its rest position, then the spring will induce a restoring force, pushing or pulling the mass in the opposite direction. This restoring force causes the mass to oscillate back and forth.
When multiple masses are attached to one another through springs, they form coupled harmonic oscillators. Displacing one mass will induce a wave of oscillations to pulse through the system. Simulating the oscillations of a large number of masses on a classical computer becomes increasingly difficult. However, the researchers developed a mapping that encodes the positions and velocities of all masses and springs into the quantum wavefunction of a system of qubits. This allows the simulation of a large number of coupled harmonic oscillators.
Quantum Algorithm and the Glued-Trees Problem
The researchers provided evidence that their quantum algorithm achieves an exponential speedup over any possible classical algorithm. The first piece of evidence involves the glued-trees problem, a famous problem about graphs known to be difficult to solve classically. The problem involves two branching trees whose branches are glued together through a random set of edges. The goal is to find the exit node as efficiently as possible.
By recasting this as a problem with balls and springs, the researchers showed that the quantum algorithm can solve the glued-trees problem exponentially faster than a classical computer.
BQP-Completeness and Quantum Computing
The second piece of evidence that the quantum algorithm is exponentially more efficient than any possible classical algorithm involves the set of problems a quantum computer can solve efficiently, referred to as bounded-error quantum polynomial time or BQP. The hardest problems in BQP are called “BQP-complete”.
The researchers showed that their problem of simulating balls and springs is BQP-complete. This means that if someone were to find an efficient classical algorithm for solving this problem, then every problem solved by a quantum computer efficiently would be classically solvable.
Implications and Future Work
This research reveals potential applications for quantum computers and provides a new method of designing quantum algorithms. The researchers showed that the dynamics of any classical system of harmonic oscillators can be equivalently understood as the dynamics of a corresponding quantum system of exponentially smaller size.
While the research focuses on the fundamental complexity of this broad class of problems, it is expected to guide future searches for real-world examples of harmonic oscillator problems in which a quantum computer could offer an exponential advantage.
“Our results make that connection precise. We showed that the dynamics of any classical system of harmonic oscillators can indeed be equivalently understood as the dynamics of a corresponding quantum system of exponentially smaller size.”
Authors of the study
Summary
A new quantum algorithm has been discovered that can exponentially speed up the simulation of coupled classical harmonic oscillators, systems that describe the physics of numerous natural phenomena, from electrical circuits to molecular vibrations. This breakthrough not only unlocks previously unknown applications for quantum computers, but also provides a new method for designing quantum algorithms by reasoning about classical systems.
“Our work also reveals that every quantum algorithm can be equivalently understood as the propagation of a classical wave in a system of coupled oscillators.”
Authors of the study
- A new quantum algorithm has been discovered that offers an exponential advantage for simulating coupled classical harmonic oscillators, which are fundamental systems in nature.
- The research was conducted in collaboration with Dominic Berry of Macquarie University and Nathan Wiebe of the University of Toronto.
- The algorithm can transform any system involving coupled oscillators into a problem describing the time evolution of a quantum system.
- This problem can be solved with a quantum computer exponentially faster than with a classical computer, given certain constraints.
- The researchers also used this mapping to prove that any problem efficiently solvable by a quantum algorithm can be recast as a problem involving a network of coupled oscillators.
- This discovery could unlock previously unknown applications of quantum computers and provide a new method of designing new quantum algorithms.
- The researchers also provided evidence that their quantum algorithm achieves an exponential speedup over any possible classical algorithm.
- The research also sheds light on work from 2002 by Lov K. Grover and Anirvan M. Sengupta, which used an analogy to coupled pendulums to illustrate how Grover’s famous quantum search algorithm could find the correct element in an unsorted database quadratically faster than could be done classically.
- The researchers showed that the dynamics of any classical system of harmonic oscillators can be equivalently understood as the dynamics of a corresponding quantum system of exponentially smaller size.