A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Abstract

Parameterized quantum circuits are widely studied approaches to tackling challenging optimization problems. A prominent example is the Quantum Alternating Operator Ansatz (QAOA), a generalized approach that builds on the alternating structure of the Quantum Approximate Optimization Algorithm. Finding high-quality parameters efficiently for QAOA remains a major chal-lenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for cases in which the number of distinct cost values grows only polynomially with the problem size, such as is common for constraint satisfaction problems. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a classical model that also has parameters which play an analogous role to the QAOA parameters, but can be efficiently evaluated classically. This model is based on empirical observations of QAOA, where variable configurations with the same cost have the same amplitudes from step to step, which we define as Perfect Homogeneity. Perfect Homogeneity is known to hold exactly for problems with particular symmetries. More generally, high overlaps between QAOA states and states with Perfect Homogeneity have been empirically observed in a number of settings. Building on this idea, we define a Classical Homogeneous Proxy for QAOA in which this property holds exactly, and which yields information describing both states and expectation values. We classically determine high-quality parameters for this proxy, and then use these parameters in QAOA, an approach we label the Homogeneous Heuristic for Parameter Setting. We numerically examine this heuristic for MaxCut on unweighted Erd˝os-R´enyi random graphs. For up to 3 QAOA levels we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously-found globally optimized approaches. For levels up to 20 we obtain parameters using our heuristic with approximation ratios monotonically increasing with depth, while a strategy that uses parameter transfer instead fails to converge with comparable classical resources. These results suggest that our heuristic may find good parameters in regimes that are intractable with noisy intermediate-scale quantum devices. Finally, we outline how our heuristic may be applied to wider classes of problems.