Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach

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=\mathcal{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.

Popular Summary

Since the advent of quantum devices consisting of hundreds of noisy qubits, one of the central questions in quantum computing is how to harvest such devices' computational power. Variational quantum algorithms (VQAs) are one of the main proposals to use near-term devices to solve complex optimization problems. This is because these algorithms only require the implementation of simple quantum circuits.

Unfortunately, noise plagues near-term devices: operations performed on the qubits fail with a non-negligible probability. Thus, it is only possible to reliably run circuits with a few operations (the shallow circuit regime) or to have outputs with a significant fraction of the operations having failed. Therefore, it is natural to ask how these limitations constrain the performance of such algorithms.

In this paper, we develop a unified framework to analyze these two regimes through the lens of quantum optimal transport and concentration inequalities. First, we use these tools to strengthen results that show for certain optimization problems, circuits of depth that are at least logarithmic in system size are required to outperform known classical algorithms. This means that for these problems, we cannot expect quantum advantage in the shallow regime.

On the other hand, we show concentration inequalities for outputs of noisy circuits. These show that as long as we have a non-negligible density of errors, the probability that the output of a noisy quantum algorithm outperforms a classical algorithm is exponentially small. Taken together, our results show that the performance of VQAs is constrained strongly in the presence of noise.

Figure 1

Schematic of an error-mitigation protocol.

Figure 2

Relative entropy density of the output of a QAOA circuit of $P=17$ layers for various fixed points ${\tau }_q^{\otimes n}$ as a function of the contraction coefficient and $D=50$. We use the optimal parameters found in Ref. [76] for our circuit. The threshold we use is that in Eq. (68) and we use Corollary C.1 to estimate the relative entropy decay. Although we see that our bounds have a worse performance as $q\to 1$, the amount of noise we can tolerate is still independent of the system’s size.