Posted by Robin Kothari and Rolando Somma, Research Scientists, Google Research, Quantum AI Team
Quantum computers have the potential to solve certain problems much faster than classical computers. However, most examples of this exponential speedup involve simulating quantum mechanical systems. In a recent study published in Physical Review X (PRX) and presented at the Symposium on Foundations of Computer Science (FOCS) 2023, we introduce a new quantum algorithm that offers an exponential advantage for simulating coupled classical harmonic oscillators. These oscillators are fundamental systems found in various natural phenomena, from electrical circuits to molecular vibrations to bridge mechanics.
In collaboration with Dominic Berry of Macquarie University and Nathan Wiebe of the University of Toronto, we discovered a mapping that transforms systems with coupled oscillators into a problem describing the time evolution of a quantum system. Under certain constraints, this problem can be solved exponentially faster with a quantum computer compared to a classical computer. Additionally, we use this mapping to demonstrate that any problem solvable with a quantum algorithm can be reformulated as a problem involving a network of coupled oscillators, even if there are exponentially many of them.
To enable the simulation of a large number of coupled harmonic oscillators, we developed a mapping that encodes the positions and velocities of the oscillators into the quantum wavefunction of a system of qubits. By utilizing the exponential growth of parameters in a quantum wavefunction, we can encode the information of N oscillators into a system of only log(N) qubits. This allows us to simulate the system more efficiently compared to a classical approach.
We provide two pieces of evidence to demonstrate the exponential advantage of our quantum algorithm. First, we show that our algorithm can efficiently solve the glued-trees problem, a graph problem known to be difficult to solve classically. By recasting the problem as a system of balls and springs, we can leverage the oscillations of the system to find the solution exponentially faster.
Second, we argue that our algorithm is BQP-complete, meaning it belongs to the class of problems that a quantum computer can solve efficiently. If an efficient classical algorithm were to be found for our problem, it would imply that all problems solvable by a quantum computer can also be solved classically. This includes problems like factoring large numbers, which are currently the basis of modern encryption.
This research not only uncovers new applications for quantum computers but also provides insights into the relationship between classical oscillating systems and quantum algorithms. It also opens up possibilities for designing new quantum algorithms based on classical systems. Our work contributes to a deeper understanding of the potential of quantum computing and paves the way for future advancements in the field.
