Abstract
We propose a random circuit model that attempts to capture the behavior of noisy intermediate-scale quantum devices when used for variationally solving classical optimization problems. Our model accounts for the propagation of arbitrary single-qubit errors through the circuit. We find that, even with a small noise rate, the quality of the obtained optima implies that a single-qubit error rate of (where is the number of qubits and is the circuit depth) is needed for the possibility of a quantum advantage. We estimate that this translates to an error rate lower than using the quantum approximate optimization algorithm for classical optimization problems with two-dimensional circuits.
- Received 13 April 2022
- Accepted 13 October 2022
DOI:https://doi.org/10.1103/PRXQuantum.3.040326
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
Recent experimental advances in quantum hardware have given us access to small, noisy quantum computers. However, it remains unclear whether they can outperform classical computers in problems of practical interest since the noise levels in these devices place serious limitations on what they can achieve. One of the proposed applications for these small devices is to use the entanglement structure of possible quantum states to solve classical optimization problems. In this work, we theoretically analyze the impact of noise on the quality of the solution obtained by these devices.
An indispensable ingredient that makes quantum computers powerful is quantum entanglement. However, quantum entanglement might also be a double-edged sword: while it is necessary to unlock the power of quantum computers, any mechanism to create entanglement in a quantum circuit also propagates errors through the circuit. Our model, based on random circuits, shows that in the presence of entanglement, an error in one qubit can spread rapidly to the others and possibly to an extent that quantum circuits could lose their advantage over known classical algorithms. The analysis in our work suggests that the propagation of errors should be taken into account when designing quantum algorithms, as it might guide us to design better circuits even with current hardware constraints.