Journal
NATURE PHYSICS
Volume 17, Issue 11, Pages 1221-+Publisher
NATURE PORTFOLIO
DOI: 10.1038/s41567-021-01356-3
Keywords
-
Categories
Funding
- VILLUM FONDEN via the QMATH Centre of Excellence [10059]
- Quantum Computing and Simulation Hub
- EPSRC
- UK National Quantum Technologies Programme
Ask authors/readers for more resources
The study compares classical and quantum algorithms running on noisy devices, finding that current quantum computers are unlikely to outperform classical devices in practical optimization tasks unless noise rates decrease substantially. Noise levels on current quantum devices are too high to produce a quantum advantage in optimization tasks.
Recent successes in producing intermediate-scale quantum devices have focused interest on establishing whether near-term devices could outperform classical computers for practical applications. A central question is whether noise can be overcome in the absence of quantum error correction or if it fundamentally restricts any potential quantum advantage. We present a transparent way of comparing classical and quantum algorithms running on noisy devices for a large family of tasks that includes optimization and variational eigenstate solving. Our approach is based on entropic inequalities that determine how fast the quantum state converges to the fixed point of the noise model, together with established classical methods of Gibbs state simulation. Our techniques are extremely versatile and so may be applied to a large variety of algorithms, noise models and quantum computing architectures. We use our result to provide estimates for problems within reach of current experiments, such as quantum annealers or variational quantum algorithms. The bounds we obtain indicate that substantial quantum advantages are unlikely for classical optimization unless noise rates are decreased by orders of magnitude or the topology of the problem matches that of the device. This is the case even if the number of available qubits increases substantially. Current quantum computers do not have error correction, which means noise may prevent them outperforming classical devices in useful tasks. An analysis of quantum optimization shows that current noise levels are too high to produce a quantum advantage.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available