Error Propagation in NISQ Devices for Solving Classical Optimization Problems

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 $1/(nD)$ (where $n$ is the number of qubits and $D$ is the circuit depth) is needed for the possibility of a quantum advantage. We estimate that this translates to an error rate lower than ${10}^{-6}$ using the quantum approximate optimization algorithm for classical optimization problems with two-dimensional circuits.

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.

Figure 1

(a) Schematic depiction of the ensemble of unitary circuits considered in this paper. The circuits consist of an entangling and uncomputing unitary that maps a product state to another product state in the absence of noise. (b) Different circuit architectures (1D, 2D, and nonlocal circuits) studied in this paper. All the circuit architectures are assumed to be translationally invariant—in particular, for the 1D and 2D architectures we assume periodic boundary conditions).

Figure 2

(a) Averaging over Haar-random unitary $U$ yields a two-qubit depolarizing channel ${\mathcal{E}}_{\mathrm{dep}}$. (b) Schematic depiction of averaging over the circuit ensemble shown in Fig. 1—we average from the center of the circuit outwards, and derive an effective Markov chain that describes the channels obtained.

Figure 3

We represent the expectation value of the fraction of depolarized qubits, $⟨q⟩/n$, as a function of the circuit depth for the different architectures: 1D, 2D, and nonlocal. We use a system size $n=900$ and an error rate $p={10}^{-3}$. Additionally, we represent $⟨q⟩/n=1-(1-p{)}^D$, which is the number of depolarized qubits that one would get when applying only local depolarizing noise to all the qubits, without any unitaries (and therefore without entanglement). We see that the convergence to uniform is very fast with our model. The horizontal lines represent thresholds for classical superiority for unweighted max-cut problems on arbitrary bounded degree-3 graphs and bipartite bounded degree-3 graphs: for values of $⟨q⟩/n$ greater than the threshold, there is a classical efficient algorithm that outputs a better solution than the averaged quantum channel (see Sec. 3b). The number of samples taken is $2000$, which reduces the error in the estimated mean to 2%.

Figure 4

In (a) we represent the relation between the system size and the error rate when the average number of depolarized qubits at the end of the computation is fixed to $⟨q⟩/n=0.5$ for bounded degree-($\mathrm{\Delta }=3$) graphs. In the 1D case the depth is $D_{1\mathrm{D}}=30n$, and in the 2D case $D_{2\mathrm{D}}=10\sqrt{7n}$. The horizontal dashed line corresponds to system sizes of $n=1000$, which is when a potential quantum advantage could begin to be practically useful [26]. In (b) we represent the upper bound for the approximation ratio of bounded degree-($\mathrm{\Delta }=3$) graphs, given by Eq. (17), as a function of the circuit depth for the different architectures: 1D, 2D, and nonlocal. We use a system size $n=900$ and an error rate $p={10}^{-3}$. The horizontal line represents the approximation ratio that is reachable by an efficient classical algorithm. The number of samples taken is $2000$, which reduces the error in the estimated mean to 2%.

Figure 5

The heuristic formula in Eq. (12) is plotted along with the results from sampling from the Markov chain for the 1D architecture. This is done for an error rate $p={10}^{-3}$ and with two different system sizes, $n=100$ and $n=1000$. The heuristic formula shows good agreement with the result from sampling from the Markov chain. The number of samples taken is $50000$, and the error is upper bounded by 0.4%.