Limitations of optimization algorithms on noisy quantum devices
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Limitations of optimization algorithms on noisy quantum devices. / Stilck França, Daniel; García-Patrón, Raul.
In: Nature Physics, Vol. 17, 2021, p. 1221–1227.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Limitations of optimization algorithms on noisy quantum devices
AU - Stilck França, Daniel
AU - García-Patrón, Raul
N1 - Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer Nature Limited.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85117476780&partnerID=8YFLogxK
U2 - 10.1038/s41567-021-01356-3
DO - 10.1038/s41567-021-01356-3
M3 - Journal article
AN - SCOPUS:85117476780
VL - 17
SP - 1221
EP - 1227
JO - Nature Physics
JF - Nature Physics
SN - 1745-2473
ER -
ID: 284295860