The QAOA algorithm consists of two elements:
- The outer loop, basically a classical optimization algorithm
- The quantum circuit, taking $2p$ parameters (where $p$ is the number of layers, where each layer is a gate representation of the cost and mixer Hamiltonian)
In each iteration of the outer loop, the quantum circuit is sampled with candidate variational parameters which yields a classical bit string (after a measurement, then the bit string's cost is classicaly evaluated and finally the parameters are accordingly updated through some optimization approach.
Usually, QAOA is presented as a potential candidate for quantum advantage, esp. for NP-hard problems. Why?
There are only three ways how an approximation algorithm can improve the state-of-the-art:
- It can find better solutions (approximation ratio)
- It requires less iterations to find acceptable solutions
- Per iteration, less time is required (or any other important resources, e.g. space, ...)
ad 1) As far as I know, currently no problem is known for which QAOA performs better than classical algorithms (but of course, such problems can exist)
ad 2) I assume that this entirely depends on the optimization algorithm in the outer loop
ad 3) The quantum circuit does two things: it computes part of the cost function (in the form of the cost Hamiltonian $H_C$) and stochastically maps the $2p$ parameters to a bit string (via qubit rotation and measurement). If $H_C$ can be classicaly evaluated in an efficient way (and this should almost always be the case, maybe even always as cost Hamiltonians that are not efficiently computable are probably not constructuable with sums of Pauli tensor products, I guess), I don't see a chance of structural improvement (as the mapping from parameters to a candidate solution bit string is also done efficiently by many classical optimization algorithms)
So, QAOA can not be faster per iteration (in terms of time complexity) than a classical algorithm and it can not require less iterations than a classical algorithm. It only may have better approximation ratios for certain problems. Is my thought process correct?
PS. Yes, there are papers stating a QAOA advantage once a certain amount of qubits are available, but those compare deterministic solver algorithms (always correct/optimal solutions) with the stochastic approximations algorithm QAOA.