Source-linked AI summary
Reachability Deficits in Quantum Approximate Optimization
V. Akshay, H. Philathong, M. E. S. Morales, J. Biamonte
TL;DR
QAOA’s limitations are not fully characterized, particularly regarding how problem density constrains optimization. This paper studies QAOA on SAT-based optimization problems and finds density-dependent reachability deficits that persist with modified drivers and differ from barren plateaus.
Problem
Although QAOA has shown success on optimization problems, its ultimate limitations and its ability to achieve advantage over classical algorithms remain insufficiently understood.
Method
The paper numerically evaluates QAOA on MAX-2-SAT, MAX-3-SAT, and variational Grover search while varying circuit depth, problem density, and driver Hamiltonian.
Results
QAOA performance depends strongly on problem density: fixed-depth circuits develop reachability deficits above critical densities, while greater depth improves approximation and can restore ground-state recovery.
Takeaways & Limitations
Problem density is a fundamental limitation on the reachability of optimal solutions for a fixed QAOA ansatz, beyond circuit depth alone.
Takeaways & Limitations
Further investigation is necessary to establish a MAX-SAT phase transition for QAOA in Boolean satisfiability.
Abstract
from arXiv · showhide
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio$-$this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such $reachability~deficits$ persist even in the absence of barren plateaus [McClean et al., 2018] and are outside of the recently reported level-1 QAOA limitations [Hastings 2019]. These findings are among the first to determine strong limitations on variational quantum approximate optimization.