Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2021-12, Vol.20 (12), Article 403
Main Authors: Lotshaw, Phillip C., Humble, Travis S., Herrman, Rebekah, Ostrowski, James, Siopsis, George
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Approximation
ASTRONOMY AND ASTROPHYSICS
Benchmarks
Circuits
Data Structures and Information Theory
Empirical analysis
Graphs
Mathematical Physics
Optimization
Parameters
Physics
Physics and Astronomy
QAOA
Quantum algorithms
Quantum approximate optimization
Quantum computers
Quantum Computing
Quantum Information Technology
Quantum Physics
Spintronics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3 . We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. The resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.
ISSN:1570-0755
1573-1332
DOI:10.1007/s11128-021-03342-3