  The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a
gate model quantum computer and has shallow depth. It takes as input a
combinatorial optimization problem and outputs a string that satisfies a high
fraction of the maximum number of clauses that can be satisfied. For certain
problems the lowest depth version of the QAOA has provable performance
guarantees although there exist classical algorithms that have better
guarantees. Here we argue that beyond its possible computational value the QAOA
can exhibit a form of Quantum Supremacy in that, based on reasonable complexity
theoretic assumptions, the output distribution of even the lowest depth version
cannot be efficiently simulated on any classical device. We contrast this with
the case of sampling from the output of a quantum computer running the Quantum
Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that
governs the evolution is gapped and stoquastic. Here we show that there is an
oracle that would allow sampling from the QADI but even with this oracle, if
one could efficiently classically sample from the output of the QAOA, the
Polynomial Hierarchy would collapse. This suggests that the QAOA is an
excellent candidate to run on near term quantum computers not only because it
may be of use for optimization but also because of its potential as a route to
establishing quantum supremacy.
