Empirical performance bounds for quantum approximate optimization

Abstract

The quantum approximate optimization algorithm (QAOA) is a variational method for noisy, intermediate-scale quantum computers to solve combinatorial optimization problems. Quantifying performance bounds with respect to specific problem instances provides insight into when QAOA may be viable for solving real-world applications. Here, we solve every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices by numerically simulating the pure-state dynamics of QAOA. Testing up to three layers of QAOA depth, we find that distributions of the approximation ratio narrow with increasing depth while the probability of recovering the maximum cut generally broadens. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. We also identify consistent patterns within the ensemble of optimized variational circuit parameters that offer highly efficient heuristics for solving MaxCut with QAOA. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance that may be used to test on-going experimental realizations.

17 pages, 11 figures

References in corpus (5)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• A Quantum Approximate Optimization Algorithm
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• What do QAOA energies reveal about graphs?

Cited by in corpus (12)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Scaling Quantum Approximate Optimization on Near-term Hardware
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Reinforcement Learning Assisted Recursive QAOA
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization
• QuaSiMo: A Composable Library to Program Hybrid Workflows for Quantum Simulation