Properties of QAOA

Question

The QAOA algorithm consists of two elements:

1. The outer loop, basically a classical optimization algorithm
2. 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:

1. It can find better solutions (approximation ratio)
2. It requires less iterations to find acceptable solutions
3. 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.

Answer 1

QAOA is used for NP-Hard problems because it is a heuristic algorithm. You rarely (or almost never) use heuristic algorithms for problems that are simple.

Ad 1.) I am not sure if there is a problem in which QAOA is clearly better than its classical counterparts. However, it was "proved" that it is hard to simulate even a single layer of QAOA [1]. So we may hope (I don't think I can use a stronger word) to get new candidates different than from classical optimization (hopefully which are better)

Ad 2.) Time and quality of the answer are correlated, I hardly see a difference of this point compared to 1)

Ad 3.) All NP problems can be written efficiently in QUBO (because QUBO is NP-complete). Transformation to 2-local Ising model is efficient, and finally, 2-local Ising model can be efficiently implemented. So in this case you're right. However, it is also true that any problem can be written as QUBO, but not necessarily efficiently. The proof is as follows:

• suppose you're given a function $f:A\to R$ ($A$ is finite)
• you can enumerate $A$, so you have new function $g:\{1,\dots,|A|\} \to R$
• all integer $1\leq i \leq |A|$ can be written as a binary string so you have function $g':\{0,1\}^{\lceil \log n\rceil +1} \to R$
• $g'$ is a pseudo-Boolean function which can be always (even uniquely, but it is not important) written as a pseudo-Boolean polynomial.
• you can always change pseudo-Boolean polynomial to sum of Pauli tensor products by $b_i \leftarrow \frac{1}{2} (1-Z_i)$

But you're right that we should not compare QAOA to algorithms providing global optimum, rather we should compare it to heuristic optimization methods. In this case, I can hardly imagine any best way than to just compare these methods "through testing" and for this, we need a quantum computers.

[1] https://arxiv.org/pdf/1602.07674.pdf