Circuit depth scaling for quantum approximate optimization

Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density—a problem constraint to a variable ratio—induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\sigma$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5–15 qubits.

Figure 1

Average energy error in approximation, $f$ in Eq. (10), vs clause density for MAX-2-SAT instances on 15 variables. Data points represent the average value obtained over statistics of 300 random instances with error bars representing $3\sigma$ for the estimated mean. Colors indicate varying QAOA depths $p=\{5,10,15\}$, illustrating improved performance at higher depths.

Figure 2

Ground state overlap vs clause density for depth $p=10$ QAOA on MAX-2-SAT instances with 15 variables. Stability lower bound is calculated by considering average energy error in approximation obtained over statistics of 300 random instances. Points in orange indicate the corresponding average ground state overlap.

Figure 3

Average critical depth $p^{*}$ vs clause density. Data points represent the average $p^{*}$ calculated according to Eq. (11) across the problem density for MAX-2-SAT with tolerance $\epsilon =0.3$. Colors correspond to different problem sizes $n=\{5,10,15\}$ with error bars representing $3\sigma$ for the estimated mean. Solid curves represent the least-squares fit of the data to the predictive model as described in Eq. (12).

Figure 4

Fitting parameters vs number of qubits for QAOA on MAX-2-SAT with tolerance $\epsilon =0.3$. Note that the recovered critical density ${\alpha }_c\approx 1$, and growth rate $\kappa$, show very little variability with respect to the number of qubits. In contrast, the saturation value $p_{\text{max}}$ illustrates a linear trend in the considered range of 5–15 qubits.