Parameter setting strategies in multi-angle quantum approximate optimization algorithm

Abstract

Combinatorial optimization problems such as Max-Cut are difficult to solve exactly on classical computers, and variational quantum algorithms like Quantum Approximate Optimization Algorithm (QAOA) offer a promising avenue to solve these problems on near-term quantum computers. The QAOA prepares a parameterized quantum state by alternating two sets of unitaries, one encoding the problem cost and one mixing between candidate solutions, while a classical optimizer tunes the variational parameters associated with the unitaries to minimize a cost function. Standard QAOA shares one parameter per layer across each unitary, using only 2𝑝 parameters for a circuit of depth 𝑝. Its generalization, multi-angle QAOA (ma-QAOA), assigns an independent parameter to every quantum gate in every layer, increasing the number of variational parameters being optimized by the classical optimizer. This added freedom improves solution quality, but increases the dimensionality of the classical optimization problem. Moreover, the larger parameter space increases susceptibility to barren plateaus, where cost-function gradients vanish exponentially and impede convergence. As such, it is important to find good parameter setting strategies to leverage the added expressibility of ma-QAOA, while minimizing the added expensive classical computation. This thesis studies several strategies for setting ma-QAOA parameters efficiently for the Max-Cut problem on random 3-regular graphs. The first strategy builds on the fact that the QAOA cost function can be written as a sum of local terms. For Max-Cut, this means the total cost is a sum over local subgraphs whose size depends on the circuit depth 𝑝. We pre-optimize parameters on a library of all unique local subgraphs, then for each edge of a target host graph we look up the corresponding entry in the library and transfer those parameters directly into the full ma-QAOA circuit skipping the classical optimization step. We also consider variants of this idea, such as transferring only the cost-unitary parameters while optimizing the mixer-unitary parameters, or the reverse, and using the transferred angles as warm-starts for full classical optimization. Since the library size grows exponentially with 𝑝, we also study extrapolation of library parameters from depth 𝑝=2to𝑝=3. The second strategy uses a linear-ramp schedule, where each edge and node parameter increases linearly across layers, so that the parameter count becomes independent of depth. All methods are compared against fully optimized QAOA, fully optimized ma-QAOA, and fixed-angle QAOA, where a single pair of angles is shared across all gates and layers. The comparison is carried out in exact statevector simulations on graphs with up to 20 vertices, using approximation ratio and classical runtime as metrics. We find that none of these strategies recover the performance advantage of fully optimized ma-QAOA. Across all methods, the approximation ratio stays close to that of standard QAOA and previously studied QAOA transfer schemes, rather than approaching ma-QAOA. The transferred parameters do, however, serve well as a warm-start initialization for full optimization.