Source-linked AI summary
Multi-angle Quantum Approximate Optimization Algorithm
Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski, Travis S. Humble, George Siopsis
TL;DR
QAOA faces practical limitations from deep circuits and noise. The paper introduces multi-angle QAOA, which assigns separate parameters to operator terms while retaining QAOA as a special case, and reports higher performance with shallower circuits across analyzed MaxCut settings.
Problem
Practical QAOA implementations require large qubit counts and deep circuits, while noise increases with depth and reduces prepared-state fidelity.
Method
Multi-angle QAOA gives each cost and mixing-operator summand its own angle, with conventional QAOA recovered when those angles are equal.
Results
Multi-angle QAOA converges to the optimal solution, achieves higher approximation ratios than QAOA in reported MaxCut comparisons, and can require fewer layers.
Takeaways & Limitations
Reduced layers and fewer unitary operators per layer can decrease the expected measurements needed under noise, supporting shallower implementations than QAOA.
Abstract
from arXiv · showhide
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we introduce a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time. This new ansatz gives a 33\% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
I. INTRODUCTION
QAOA approximately solves combinatorial optimization problems but practical implementations face deep circuits and noise. Multi-angle QAOA increases classical parameters per layer to enable finer optimization while reducing circuit depth.
- QAOA uses optimized classical parameters with cost and mixing operators to prepare states for approximate combinatorial optimization.
- Deep circuits and noise undermine practical QAOA by increasing implementation demands and reducing prepared-state fidelity.
- Multi-angle QAOA assigns separate angles to individual cost and mixing-operator summands rather than using one angle for each operator.
- Increasing classical parameters provides finer-grained cost-function and approximation-ratio control while enabling reduced circuit depth.
Convergence of ma-QAOA
Multi-angle QAOA retains QAOA as a special case, so its optimized performance is at least as high at each depth. The paper establishes convergence to the optimal combinatorial-optimization solution as the iteration count grows.
- Multi-angle QAOA includes QAOA as the parameter-equality special case, implying M_ma_p ≥ M_p.
- The multi-angle expected cost converges to Cmax as p tends to infinity, establishing convergence to the optimal solution.
MaxCut on star graphs
For MaxCut on star graphs, one iteration of multi-angle QAOA reaches the optimal approximation ratio, whereas one-iteration QAOA approaches 0.75 for large stars.
- The approximation ratio is the expected cost divided by Cmax and measures performance relative to the optimal solution.
- Star graphs have one center connected to every other vertex, and their bipartite structure makes all edges part of an optimal MaxCut.
- 1.0 is the one-iteration multi-angle approximation ratio on star graphs, while QAOA approaches 0.75 as n tends to infinity.
Computational results
Computational tests compare ma-QAOA with QAOA across graph families and depths, finding higher approximation ratios and favorable circuit-fidelity implications for ma-QAOA.
- Graph families: ma-QAOA was evaluated on 3-regular and modified random graphs with 50 and 100 vertices against 1-QAOA.The collections included one-hundred triangle-free 3-regular graphs at each size and fifty modified random graphs for each size.
- Graph families: ma-QAOA has a higher average approximation ratio and a significant percent increase in approximation-ratio gap for every tested graph collection.The approximation-ratio gap compares one minus the 1-QAOA ratio with one minus the ma-QAOA ratio.
- Eight-vertex graphs: On all connected, non-isomorphic eight-vertex graphs, one iteration of ma-QAOA has a higher average approximation ratio than 1-QAOA, 2-QAOA, and 3-QAOA.The reported average performance is comparable to 3-QAOA, while the one-iteration ma-QAOA average is larger than the 3-QAOA average.
- Eight-vertex graphs: For eight-vertex graphs, significantly more graphs reach an approximation ratio of at least 0.95 with ma-QAOA than with up to three QAOA iterations.QAOA has higher fractions at thresholds 0.85 and 0.9, but ma-QAOA has the stronger result at 0.95.
- Circuit fidelity: A one-percent-per-unitary noise model estimates 1.25 measurements to sample the noiseless distribution for one iteration with n = 8 and m = 14.4.The estimate uses the fidelity model F = (1 − ϵn)^np(1 − ϵm)^mp and takes the expected measurement count as 1/F.
- Circuit fidelity: Zero optimized angles allow associated unitary operators to be removed, reducing circuit noise and the expected sampling burden relative to p-QAOA.The sampling comparison is reported as the expected-measurement ratio for p-QAOA relative to 1-ma-QAOA, using average gate reductions.
Computing Angles
ma-QAOA requires more classical optimization effort because it uses more variables, but numerical results indicate favorable optimization scaling with graph size.
- More variables make finding ma-QAOA angles more classically demanding, although exact optimal angles are unnecessary if angles outperform QAOA’s.
- After approximately ten BFGS iterations, ma-QAOA tends to reach a higher approximation ratio than QAOA at depths p = 1, 2, and 3.
- 0.10 seconds for n = 50 and 0.46 seconds for n = 100 were the reported single-optimization times for Erdős-Rényi graphs.
- The observed optimization-time scaling is approximately n^2 when graph degree remains roughly constant and m ∼ n.
III. DISCUSSION
The discussion emphasizes ma-QAOA’s performance and circuit-depth advantages while noting that its benefit is graph dependent and its parameter count is larger.
- ma-QAOA’s expected cost is at least QAOA’s because conventional QAOA is a special case of the multi-angle ansatz.
- One ma-QAOA iteration can use less circuit depth than one QAOA iteration, and numerical results show increased approximation ratios for several graph families.
- Some graphs do not show a significantly higher expected cost with ma-QAOA than with QAOA.
- ma-QAOA optimizes n + m classical parameters per layer, where n is the number of vertices and m is the number of edges.
Proof of convergence
The convergence proof uses QAOA’s known convergence and the fact that ma-QAOA contains QAOA as a restricted parameter choice.
- QAOA’s convergence means it suffices to lower-bound ma-QAOA’s optimal expected cost by QAOA’s value.
- Equalizing all edge angles and all vertex angles reduces ma-QAOA to QAOA, so ma-QAOA cannot have a lower optimal expected cost.
⟨C⟩for solving MaxCut on triangle-free graphs using
For triangle-free graphs, the one-iteration ma-QAOA MaxCut expectation is derived by conjugating cost terms through the mixing and phase operators; higher-order triangle terms vanish.
- The triangle-free MaxCut expectation after one ma-QAOA iteration is obtained by analyzing each edge cost term under operator conjugation.
- The neighborhood Nbhd(x) contains vertices adjacent to x, providing the graph structure used in the expectation formula.
- The first cost term commutes with the phase operator and therefore does not contribute to the expected value.
- The remaining conjugated terms produce cosine and sine factors involving edge angles, mixing angles, and neighboring vertices.
- For triangle-free graphs, the final conjugated term contributes nothing because higher-order contributions require triangles.
Star graphs
For star graphs, one iteration of QAOA approaches an approximation ratio of 0.75 as the graph grows, whereas one iteration of ma-QAOA achieves the optimal cut.
- QAOA baseline: QAOA's approximation ratio approaches 0.75 as the number of star-graph vertices tends to infinity.The expected cut approaches 0.75(n−1), while the optimal cut has size n−1.
- ma-QAOA construction: The ma-QAOA construction sets parameters so each star edge contributes one to the expected objective.The edge contribution is bounded by one, and equality follows by choosing γ1,uv = π/2 and suitable β′ parameters.
- ma-QAOA result: ma-QAOA achieves an approximation ratio of 1 after one iteration on every star graph.Its expected cut equals n−1, the optimal star-graph cut size.
Setup for Computational Results
The computational study optimizes QAOA and ma-QAOA angles with numerical methods across small, medium, and larger MaxCut graph collections, using multiple random initializations.
- Eight-vertex graphs: BFGS optimizes eight-vertex QAOA and ma-QAOA angles using numerical gradients and an approximate second-order Hessian.The optimization seeks local maxima of the expected objective from initial angle collections.
- Eight-vertex graphs: 100 random seeds are used to optimize ma-QAOA on the eight-vertex graphs.
- Larger graphs: The study uses MMA for 50- and 100-node graphs, while BFGS gives similar results.Reported values use the best optimized results from the specified initial-seed sets.