[2210.12406] Deep-Circuit QAOA

[Submitted on 22 Oct 2022]

Download PDF

Abstract: Despite its popularity, several empirical and theoretical studies suggest
that the quantum approximate optimization algorithm (QAOA) has issues in
providing a substantial practical advantage. So far, those findings mostly
account for a regime of few qubits and shallow circuits. In this work we extend
on this by investigating the perspectives of QAOA in a regime of deep quantum
circuits.

Due to a rapidly growing range of classical control parameters, we consider
local search routines as the characteristic class of variation methods for this
regime. The behaviour of QAOA with local search routines can be best analyzed
by employing Lie theory. This gives a geometrically nice picture of
optimization landscapes in terms of vector and scalar fields on a
differentiable manifold. Our methods are clearly borrowed from the field of
optimal control theory.

In the limit of asymptotic circuits we find that a generic QAOA instance has
many favourable properties, like a unique local minimum. For deep but not close
to asymptotically deep circuits many of those nice properties vanish. Saddle
points turn into effective local minima, and we get a landscape with a
continuum of local attractors and potentially exponentially many local traps.
Our analysis reveals that statistical distribution properties of traps, like
amount, sizes, and depths, can be easily accessed by solely evaluating
properties of the classical objective function. As a result we introduce
performance indicators that allow us to asses if a particular combinatorial
optimization problem admits a landscape that is favourable for deep circuit
QAOA.

Even though we see that there is no free lunch on general instances, certain
problem classes like random QUBO, MAXCUT on 3-regular graphs, or a very
unbalanced MAX-$k$-SAT have a chance to perform not too bad in the deep circuit
regime.