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.

arXiv comment19 pages, 7 figures

References in corpus (26)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Training variational quantum algorithms is NP-hard
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Layerwise learning for quantum neural networks
• Improving Variational Quantum Optimization using CVaR
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Clustering of solutions in the random satisfiability problem
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Counterdiabaticity and the quantum approximate optimization algorithm
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Using models to improve optimizers for variational quantum algorithms
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Surrogate-based optimization for variational quantum algorithms
• Analytical Framework for Quantum Alternating Operator Ansätze
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms

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