Parameter Setting in Quantum Approximate Optimization of Weighted Problems

Abstract

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for $p\ge 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for $p=1$ the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only $1.1$ percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.

arXiv commentAccepted to Quantum Journal

References in corpus (30)

• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Extremal Cuts of Sparse Random Graphs
• Benchmarking the performance of portfolio optimization with QAOA
• A Survey of Quantum Computing for Finance
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Reinforcement Learning for Many-Body Ground-State Preparation Inspired by Counterdiabatic Driving
• Reinforcement Learning assisted Quantum Optimization
• On the method of typical bounded differences
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Constrained Optimization via Quantum Zeno Dynamics
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Exploiting Symmetry Reduces the Cost of Training QAOA
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Bandwidth Enables Generalization in Quantum Kernel Models
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Iterative-Free Quantum Approximate Optimization Algorithm Using Neural Networks
• A Classical Algorithm Which Also Beats $\frac{1}{2}+\frac{2}{\pi }\frac{1}{\sqrt{D}}$ For High Girth MAX-CUT

Cited by in corpus (19)

• Quantum computing for finance
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Quantum Approximate Multi-Objective Optimization
• Performance Analysis of Multi-Angle QAOA for p > 1
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Trainability Barriers in Low-Depth QAOA Landscapes
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Optimization via Quantum Preconditioning
• Universal resources for quantum approximate optimization algorithm and quantum annealing
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Direct entanglement ansatz learning (DEAL) with ZNE on error-prone superconducting qubits
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization