Quantum computers could solve computational problems faster than classical computers but are currently limited by size and error rates. A new quantum algorithm has been introduced that samples from complex distributions, performing Markov chain Monte Carlo to sample from the Boltzmann distribution of classical Ising models. Recently published in Nature (first author: David Layden), this algorithm converges to the correct distribution and has shown robustness to noise and speed in experiments and simulations. This could ease computational bottlenecks in machine learning, statistical physics and optimisation, providing a new path for quantum computers to solve useful sampling problems.
A New Quantum Algorithm
A new quantum algorithm has been introduced that is well-suited to current hardware—this algorithm samples from complex distributions that arise in several applications. The algorithm utilises Markov chain Monte Carlo (MCMC), a well-known iterative technique, to sample from the Boltzmann distribution of classical Ising models. This is a significant departure from most near-term quantum algorithms, as it can be proven to converge to the correct distribution, even though it is challenging to simulate using classical methods.
The convergence rate of the new quantum algorithm, like most MCMC algorithms, is challenging to establish theoretically. Therefore, it has been analysed through both experiments and simulations. In experiments, the quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting unusual robustness to noise.
A speedup was observed between cubic and quartic over classical alternatives in simulations. If this empirical speedup persists at larger scales, it could alleviate computational bottlenecks posed by this sampling problem in various fields. These fields include machine learning, statistical physics, and optimisation.
This new algorithm opens a new path for quantum computers to solve not just difficult but also useful sampling problems. This development is significant as it moves quantum computing from a theoretical and experimental field into one with practical applications. It also suggests that as quantum hardware continues to improve, the range and complexity of problems that quantum computers can solve will also increase.
Quick Summary
Quantum computers have been shown to solve certain computational problems faster than traditional computers, but their potential has been limited by their size and error rates. A new quantum algorithm has been introduced and tested, which samples from complex distributions. It has shown promising results in machine learning, statistical physics and optimisation, potentially paving the way for quantum computers to solve not just difficult but also useful sampling problems.
- Quantum computers have the potential to solve computational problems much faster than classical computers.
- Current quantum processors are limited by their small size and high error rates.
- Recent efforts have focused on problems that are difficult for classical computers but suitable for current quantum hardware.
- A new quantum algorithm has been introduced and demonstrated, which samples from complex distributions found in several applications.
- The algorithm uses Markov chain Monte Carlo (MCMC), a well-known iterative technique, to sample from the Boltzmann distribution of classical Ising models.
- Unlike most near-term quantum algorithms, this one converges to the correct distribution, even though it’s hard to simulate classically.
- The convergence rate of this algorithm is difficult to establish theoretically, so it was analysed through experiments and simulations.
- In experiments, the quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting it is unusually robust to noise.
- A polynomial speedup was observed between cubic and quartic over such alternatives in simulations.
- If this empirical speedup persists to larger scales, it could ease computational bottlenecks in machine learning, statistical physics and optimization.
- This algorithm opens a new path for quantum computers to solve useful, not just difficult, sampling problems.
