Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut

Abstract

Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single "typical" vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in $96.35\%$ of our cases.

References in corpus (16)

• Modularity and community structure in networks
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Counterdiabaticity and the quantum approximate optimization algorithm
• MAXCUT QAOA performance guarantees for p >1
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• 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
• Tensor Network Quantum Simulator With Step-Dependent Parallelization
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit
• The fixed angle conjecture for QAOA on regular MaxCut graphs

Cited by in corpus (43)

• Barren Plateaus in Variational Quantum Computing
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• A perspective on protein structure prediction using quantum computers
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Quantum approximate optimization via learning-based adaptive optimization
• Constrained Optimization via Quantum Zeno Dynamics
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Reinforcement Learning Assisted Recursive QAOA
• Approaches to Constrained Quantum Approximate Optimization
• Quantum Approximate Multi-Objective Optimization
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Qoncord: A Multi-Device Job Scheduling Framework for Variational Quantum Algorithms
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Trainability Barriers in Low-Depth QAOA Landscapes
• Low-depth Clifford circuits approximately solve MaxCut
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Universal Resources for QAOA and Quantum Annealing
• Optimization via Quantum Preconditioning
• Improving the efficiency of quantum annealing with controlled diagonal catalysts
• A Novel Noise-Aware Classical Optimizer for Variational Quantum Algorithms
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion