Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Limitations of Variational Quantum Algorithms : A Quantum Optimal Transport Approach. / De Palma, Giacomo; Marvian, Milad; Rouzé, Cambyse; França, Daniel Stilck.
In: PRX Quantum, Vol. 4, No. 1, 010309, 2023.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Limitations of Variational Quantum Algorithms
T2 - A Quantum Optimal Transport Approach
AU - De Palma, Giacomo
AU - Marvian, Milad
AU - Rouzé, Cambyse
AU - França, Daniel Stilck
N1 - Publisher Copyright: © 2023 authors. Published by the American Physical Society.
PY - 2023
Y1 - 2023
N2 - The impressive progress in quantum hardware of the last years has raised the interest of the quantum computing community in harvesting the computational power of such devices. However, in the absence of error correction, these devices can only reliably implement very shallow circuits or comparatively deeper circuits at the expense of a nontrivial density of errors. In this work, we obtain extremely tight limitation bounds for standard noisy intermediate-scale quantum proposals in both the noisy and noiseless regimes, with or without error-mitigation tools. The bounds limit the performance of both circuit model algorithms, such as the quantum approximate optimization algorithm, and also continuous-time algorithms, such as quantum annealing. In the noisy regime with local depolarizing noise p, we prove that at depths L=O(p-1) it is exponentially unlikely that the outcome of a noisy quantum circuit outperforms efficient classical algorithms for combinatorial optimization problems like max-cut. Although previous results already showed that classical algorithms outperform noisy quantum circuits at constant depth, these results only held for the expectation value of the output. Our results are based on newly developed quantum entropic and concentration inequalities, which constitute a homogeneous toolkit of theoretical methods from the quantum theory of optimal mass transport whose potential usefulness goes beyond the study of variational quantum algorithms.
AB - The impressive progress in quantum hardware of the last years has raised the interest of the quantum computing community in harvesting the computational power of such devices. However, in the absence of error correction, these devices can only reliably implement very shallow circuits or comparatively deeper circuits at the expense of a nontrivial density of errors. In this work, we obtain extremely tight limitation bounds for standard noisy intermediate-scale quantum proposals in both the noisy and noiseless regimes, with or without error-mitigation tools. The bounds limit the performance of both circuit model algorithms, such as the quantum approximate optimization algorithm, and also continuous-time algorithms, such as quantum annealing. In the noisy regime with local depolarizing noise p, we prove that at depths L=O(p-1) it is exponentially unlikely that the outcome of a noisy quantum circuit outperforms efficient classical algorithms for combinatorial optimization problems like max-cut. Although previous results already showed that classical algorithms outperform noisy quantum circuits at constant depth, these results only held for the expectation value of the output. Our results are based on newly developed quantum entropic and concentration inequalities, which constitute a homogeneous toolkit of theoretical methods from the quantum theory of optimal mass transport whose potential usefulness goes beyond the study of variational quantum algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85147531260&partnerID=8YFLogxK
U2 - 10.1103/PRXQuantum.4.010309
DO - 10.1103/PRXQuantum.4.010309
M3 - Journal article
AN - SCOPUS:85147531260
VL - 4
JO - PRX Quantum
JF - PRX Quantum
SN - 2691-3399
IS - 1
M1 - 010309
ER -
ID: 336076352