For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

Abstract

The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.

16 pages, 1 figure

References in corpus (1)

• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

Cited by in corpus (35)

• Warm-starting quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Differentiable Quantum Architecture Search
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Hybrid quantum-classical algorithms for approximate graph coloring
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Variational preparation of finite-temperature states on a quantum computer
• Empirical performance bounds for quantum approximate optimization
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Training Optimization for Gate-Model Quantum Neural Networks
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Low depth mechanisms for quantum optimization
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Evaluation of QAOA based on the approximation ratio of individual samples
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Analytical Framework for Quantum Alternating Operator Ansätze
• FLIP: A flexible initializer for arbitrarily-sized parametrized quantum circuits
• What do QAOA energies reveal about graphs?
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Accelerating Variational Quantum Algorithms Using Circuit Concurrency
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Engineering the Cost Function of a Variational Quantum Algorithm for Implementation on Near-Term Devices
• ORQVIZ: Visualizing High-Dimensional Landscapes in Variational Quantum Algorithms
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles