Reachability Deficits in Quantum Approximate Optimization of Graph Problems

Abstract

The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.

(feedback welcome) 11 pages; 5 composite figures

References in corpus (3)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Simulated Quantum Computation of Molecular Energies
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Cited by in corpus (14)

• Quantum optimization via four-body Rydberg gates
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• An entanglement perspective on the quantum approximate optimization algorithm
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• An evolving objective function for improved variational quantum optimisation
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Progress towards analytically optimal angles in quantum approximate optimisation
• Ion native variational ansatz for quantum approximate optimization
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• A Quantum Constraint Generation Framework for Binary Linear Programs