Parameter-Dependent Noise Resilience in the Quantum Approximate Optimization Algorithm

The gist The stability of QAOA in noisy environments depends on its variational parameters, and new methods are introduced to manufacture error resilience

Parameter-Dependent Noise Resilience

The study explores how the choice of variational parameters impacts the resilience of the QAOA circuit to errors. The authors derive an upper bound on the total variation distance between noisy and noiseless circuit outputs as a function of these parameters. Results from noisy simulations support this bound and give insight into the best methods to use for parameter generation in the presence of noise. They find that smaller valued and smoother varying parameters are more stable in the presence of noise than larger valued, more erratic parameters.

Error Propagation Modeling

The paper models noise using a Pauli noise model where arbitrary noise channels can be transformed into effective Pauli channels. The propagation of errors is analyzed by considering the effect of a single Pauli error K in a specific layer s, denoted as U˜ K j,s(γ, β). For instance, propagating a Z error to the end of the circuit results in an operator that changes the signs of parameters on the mixer terms.

Bounding Error Distance

Theorem III.1 provides an upper bound on the total variation distance D(U˜ K j,s, U) between noisy and noiseless circuits based on variational parameters. The bound is given by a complex expression involving terms related to the Pauli error type K. For example, for a Z error, the bound involves the angles associated with the mixer terms that come after it.

Noise-Informed Parameter Selection

The authors investigate methods for generating parameters to increase noise resilience. They compare different parameter generation methods, finding that predetermined parameters can be more stable to noise than methods which require optimization. They also introduce a method of noise-informed parameter optimization by adding a penalty term to the objective function based on the expected value of the upper bound on the distance.

Adiabatic Limit and Schedules

The analysis is extended to the quantum adiabatic algorithm (QAA) by taking the continuous limit of QAOA. In this limit, the error resilience of a single schedule is bounded by E(s). They derive a lower bound on E(s) using unphysical schedules, showing that a fixed floor on how error resilient it can be based on our bound. Furthermore, they investigate a two-schedule approach but find that measures made to attempt to decrease this lower bound increase the runtime of the algorithm such that the bound cannot be improved.

Conclusion on Parameter Choice

The paper concludes that optimizing without consideration of noise (which can be done to avoid costly noisy optimization on device [60–62]) can perform worse in the noisy case than unoptimized parameters. The stability of non-optimized parameters comes primarily from their shape as adiabatic-looking schedules – monotonically increasing γ and decreasing β – tend to minimize the bound and exhibit more resilience to errors. They suggest that correcting Z errors in early layers, X in later layers and on high degree qubits helps to mitigate the effect of errors.

Appendix Details

The analysis of error propagation shows that for a Pauli Z error, the final measurement is in the computational basis and therefore immune to Z errors. For an X error propagated to the beginning of the circuit, it has the same effect on the layers it moves through. The light cone of errors shows that for Kj = Z this acts on qubits in Np−s−1(j) and depends on 2(p − s) − 1 parameters. For Kj = X, the error acts on qubits in Np−s(j) and depends on 2(p − s) + 1 parameters. The bound E(U˜ K j,s, U) is defined as a quantity to measure the resilience of a circuit with parameters (γ, β) to Pauli noise.

Numerical Insights

Numerical results show that not all parameters are equally error resilient. The predicted parameters perform worst in the noiseless case but perform similarly to optimized parameters in the noisy regime. The bound is loose, but its qualitative agreement with D(U, U˜) and ∆E makes it a good qualitative indicator of relative noise resilience across the methods. The results are shown for Max-Cut on 5 graphs with 6 nodes.

Parameter Truncation

A simpler way to restrict the optimizer to smaller parameters is truncating the search space by adding constraints such as 0 ≤ γi ≤ π/2 and −π/2 ≤ βi ≤ 0 for all i. This constraint bounds E(γ, β) by E(γ, β) ≤ npπ/2 (p + 1)(ϵzy + davgϵxy). The periodicity of QAOA parameters for unweighted Max-Cut is stated as 2π in γ and π/2 in β.

Two-Schedule Approach

The authors attempt to beat the lower bound on E(s) by deriving a two-schedule adiabatic algorithm. They find that when we build in physically realistic constraints on the schedules and runtime, it is not possible to get significantly better error behaviour. The total runtime T is lower bounded by Tcross ≳ √N / (2ηδ). This leads to the bound Econt = Ω nN / η 2δ (ϵzy + ϵxy).

Unstructured Quantum Search

For unstructured quantum search with two schedules, the gap g(t) is given by g(t) = r(β(t) − γ(t)) squared + 4β(t)γ(t)/N. The time spent in the crossing region Tcross is lower bounded by Tcross ≈ √N / (2ηδ). This results in a bound Econt ≳ nδ / (ϵzy + ϵxydavg) T 2cross. The analysis of the two schedule approach shows that physical constraints limit the speed at which the schedules can change and hence determine the total runtime of the algorithm.

Final Findings

The paper finds that optimizing without consideration of noise (which can be done to avoid costly noisy optimization on device [60–62]) can perform worse in the noisy case than unoptimized parameters. The stability of non-optimized parameters comes primarily from their shape as adiabatic-looking schedules – monotonically increasing γ and decreasing β – tend to minimize the bound and exhibit more resilience to errors. The authors suggest that MA-QAOA style parameter shrinking on these qubits to counteract errors on them may improve error resilience.

Acknowledgments

The authors thank Ieva Cepait˙e and Ra´ul Garc´ıa- ˇ Patron for helpful discussions on the topic of this paper.

1. textbfConcentration of Parameter Generation Methods in Noisy Regimes: The improved AI system can perform better than standard optimization by using precomputed parameters when noise rates are beyond a certain threshold, as beyond a certain noise rate precomputed parameters can perform better than optimization methods. This allows the system to achieve not all parameters are equally error resilient and potentially save computational cost by avoiding costly noisy emulation when optimization offers no advantage over precomputed values.

2. textbfNoise-Informed Parameter Optimization: The improved AI system can be trained using a penalty function based on the expected upper bound on the distance between noisy and noiseless circuits, specifically minimizing F(γ, β) + λ E(γ, β), where E(γ, β) is defined in Equation (30). This directly leverages Theorem III.1 to encourage robustness by introducing penalties that give preference to smaller parameters, potentially leading to a better balance between solution quality and noise resilience.

3. textbfTruncated Search Space Optimization: The improved AI system can restrict its search space for variational parameters, such as adding constraints like 0 ≤ γi ≤ π/2 and −π/2 ≤ βi ≤ 0 for all i, to bound the expected distance by E(γ, β) ≤ npπ/2 (p + 1)(ϵzy + davgϵxy). This technique is explicitly tested to see if it can improve results, though preliminary tests showed the results on the effectiveness of these techniques are inconclusive for general scaling.

4. textbfAdiabatic Schedule Insight: The improved AI system can be guided to adopt parameter schedules that resemble adiabatic evolution, specifically by ramping schedules where γi start small and increase and βi begin large in magnitude and decrease, which is suggested as a way to inherently suppress the bound E(γ, β)." This mimics physical constraints observed in the QAA limit.

5. textbfModel for Error Propagation: The improved AI system can utilize the derived light cone of errors to prioritize error correction strategies; specifically, Correcting Z errors in early layers, X in later layers and on high degree qubits helps to mitigate the effect of errors. This allows the system to adapt its parameter generation based on where it anticipates noise will propagate most damagingly.