A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Abstract

Parameterized quantum circuits are widely studied approaches for tackling optimization problems. A prominent example is the Quantum Alternating Operator Ansatz (QAOA), an approach that builds off the structure of the Quantum Approximate Optimization Algorithm. Finding high-quality parameters efficiently for QAOA remains a major challenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for common cases in which the number of distinct cost values grows only polynomially with the problem size. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a parameterized model that can be efficiently evaluated classically. This model is based on empirical observations that QAOA states have large overlaps with states where variable configurations with the same cost have the same amplitude, which we define as Perfect Homogeneity. We thus define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity holds exactly, and which yields information describing both states and expectation values. We classically determine high-quality parameters for this proxy, and use these parameters in QAOA, an approach we label the Homogeneous Heuristic for Parameter Setting. We numerically examine this heuristic for MaxCut on random graphs. For up to $3$ QAOA levels we are easily able to find parameters that match approximation ratios returned by previous globally optimized approaches. For levels up to $20$ we obtain parameters 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.

19 pages, 7 figures

References in corpus (2)

• Clustering of solutions in the random satisfiability problem
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs

Cited by in corpus (9)

• Artificial Intelligence for Quantum Computing
• Performance Analysis of Multi-Angle QAOA for p > 1
• Approximating under the Influence of Quantum Noise and Compute Power
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Role of overparametrization in quantum approximate optimization