Springing simulations forward with quantum computing
A new quantum algorithm speeds up simulations of coupled oscillators dynamics
image: The dynamics of coupled oscillators, such as those shown here, can be simulated faster with a new quantum algorithm.
Credit: Image courtesy of Nathan Johnson | Pacific Northwest National Laboratory
The Science
Quantum computers have the potential to solve some problems much more efficiently than conventional computers. In a new example, researchers have created a quantum computer algorithm for simulating systems of coupled masses and springs. These systems, called coupled oscillators, are important for describing many real-world physical systems—even bridges. The researchers first mapped the dynamics of the coupled oscillators to a Schrödinger equation. These equations describe the wave function of a quantum mechanical system. From there, they simulated the system using new Hamiltonian simulation methods. Hamiltonian methods describe how objects move in a way that bridges between classical physics and quantum mechanics. This approach allowed the researchers to express the dynamics of a given number of coupled oscillators (N) using a smaller number [log(N)] of quantum bits. The number of quantum bits required is dramatically smaller than would be needed with a conventional computer.
The Impact
Researchers have developed very few new classes of provable exponential speedups such as the one described here. This new research shows that a quantum computer acting on a number n of quantum bits can be simulated using 2n coupled harmonic oscillators. This algorithm results in exponentially faster simulation of coupled oscillators compared to ordinary algorithms. The approach also demonstrates a novel and subtle link between quantum dynamics and harmonic oscillators. This work could prove useful to a wide range of real-world problems involving coupled oscillators. These applications range from engineering to neuroscience to chemistry.
Summary
Researchers provide two quantum algorithms for simulating coupled harmonic oscillators that provide exponential speedup. Using energy conservation and the fact that the Hamiltonian is quadratic, they represented the dynamics of the displacements and the momenta as a unitary evolution. They then simulated the unitary dynamics using Hamiltonian simulation methods including a novel approach for computing fractional queries. This quantum algorithm provides an exponential advantage over classical algorithms by finding a set of coupling constants such that the classical coupled Harmonic oscillators can simulate an arbitrary quantum computation.
Additionally, the researchers found further query lower bounds and demonstrated that if a classical algorithm existed for simulating oscillators that matched the performance of the researchers’ new algorithm, then the classical algorithm would violate query lower bounds on the number of times that the labels of the vertices on a graph need to be accessed for a walker to move from the entrance to exit of a maze described by that graph. This means that the algorithm provably provides an exponential advantage for a very important set of problems and reveals that quantum computing has even more potential impact than previously thought.
Funding
This work was supported by the Department of Energy Office of Science, National Quantum Information Science Research Center, Co-design Center for Quantum Advantage (C2QA). This work was also supported by grants from Google Quantum AI and the Australian Research Council.