Parameter Concentration in Quantum Approximate Optimization

Abstract

The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained -- by repeatedly adjusting circuit parameters -- to solve a problem. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system and not considering parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for variational state preparations at $p=1,2$ (corresponding to 2 and 4 tunable parameters respectively). The technique is also applicable for higher depths and the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction $w<n$ of qubits to assert that these parameters are nearly optimal on $n$ qubits. Clearly this effect has significant practical importance.

arXiv comment7 pages; 4 figures, REVTeX

References in corpus (36)

• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Probing many-body dynamics on a 51-atom quantum simulator
• A Quantum Approximate Optimization Algorithm
• Control of quantum phenomena: Past, present, and future
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Efficient variational simulation of non-trivial quantum states
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Quantum state engineering of a Hubbard system with ultracold fermions
• Heat-machine control by quantum-state preparation: from quantum engines to refrigerators
• On the Universality of the Quantum Approximate Optimization Algorithm
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Quantum approximate optimization is computationally universal
• Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States
• Quantum state preparation in circuit QED via Landau-Zener tunneling
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Abrupt Transitions in Variational Quantum Circuit Training
• Classical and Quantum Bounded Depth Approximation Algorithms
• Quantum state preparation and control of single molecular ions
• Comparison of QAOA with Quantum and Simulated Annealing
• Ultrafast Variational Simulation of Non-trivial Quantum States with Long Range Interactions
• Understanding Quantum Control Processor Capabilities and Limitations through Circuit Characterization
• Certified variational quantum algorithms for eigenstate preparation
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Variational quantum state preparation via quantum data buses
• Polynomial scaling of QAOA for ground-state preparation of the fully-connected p-spin ferromagnet

Cited by in corpus (55)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum computing for finance
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Graph neural network initialisation of quantum approximate optimisation
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Quantum optimization via four-body Rydberg gates
• Towards large-scale quantum optimization solvers with few qubits
• Challenges of variational quantum optimization with measurement shot noise
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Evaluation of QAOA based on the approximation ratio of individual samples
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Two-dimensional ${\mathbb{Z}}_2$ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Modular Parity Quantum Approximate Optimization
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Quantum Approximate Multi-Objective Optimization
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Parity Quantum Optimization: Benchmarks
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Variational Quantum Multi-Objective Optimization
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Progress towards analytically optimal angles in quantum approximate optimisation
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Ion native variational ansatz for quantum approximate optimization
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Constant Depth Code Deformations in the Parity Architecture
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Depth scaling of unstructured search via quantum approximate optimization
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Universal Resources for QAOA and Quantum Annealing
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Role of overparametrization in quantum approximate optimization
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization