4
$\begingroup$

QAOA is a well-known heuristic for solving optimization problems, and it has the desirable property that as p -> infinity, the true minimum objective function value is reached.

There is a generalization of QAOA cleverly named with the same acronym, but for the purpose of avoiding confusion in this question I'll call it QAO Ansatz (https://arxiv.org/pdf/1709.03489.pdf)

Nowhere in this paper, or any other paper have I ever found any formal performance guarantees for QAO Ansatz. Is there any reason to expect it to perform better, aside from an informal argument that it only explores feasible states?

$\endgroup$

1 Answer 1

6
$\begingroup$

The statement that "as $p \rightarrow \infty$, the minimum of the objective function is reached" is not correct. In fact, it is a pretty meaningless statement.

Commonly, a QAOA circuit has $p$ layers and $2p$ parameters. For a QAOA circuit to sample a low energy state with high probability, we need to find $2p$ parameters which are optimal or close to being optimal. For an arbitrary problem and a finite $p$, finding the optimal $2p$ parameters is already really hard. Non-convex optimization is hard.

This is to say that if we have infinitely many layers and all infinitely many parameters are suboptimal, then there is no reason to expect any sort of convergence to the ground eigenstate. A simple example would be a $p$-layered circuit with all parameters set to zero. Then we can set $p$ to any number, but we'll never reach the ground eigenstate. This is because the unitary matrix representing QAOA would be simply an identity matrix. So $p \rightarrow \infty$ does not imply an optimal solution will be found.

Having cleared this up, the correct statement is a quote from Farhi and Goldstone paper:

The algorithm depends on an integer p ≥ 1 and the quality of the approximation improves as p is increased.

The statement is a bit vague, but if you are familiar with Farhi's work, it is straightforward to see that the statement has to do with an approximation of the adiabatic evolution given by a time-dependent Hamiltonian. You can read Section 6 of the original paper for more details.

Roughly speaking, QAOA is viewed as a discretized version of an adiabatic evolution where we transition from the "simple" Hamiltonian, whose ground state is known, to a more "difficult" Hamiltonian, whose ground state we would like to find.

Putting this in the context of combinatorial optimization means that the simple Hamiltonian is the "mixer" and the "difficult" Hamiltonian is the Hamiltonian encoding a combinatorial problem. To implement the adiabatic process, we discretize it (finite time intervals + Trotterization) and represent it as a quantum circuit. Specifically, splitting the evolution time into $p$ subintervals and performing the first-order Trotterization produces a circuit with $p$ layers. As $p$ increases the "quality" of the approximation improves.

The paper that you referenced is nothing more than discretizing an adiabatic evolution given by different time-dependent Hamiltonians. In the QAOA case, we discretize the adiabatic evolution given by the transverse-field Ising Hamiltonian. In the QAO paper case, we discretize some other suitable Hamiltonians which we think can do a better job on some specific problem class.

So if you look one level up to where it all stems from (adiabatic algorithms), the QAOA and QAO are essentially two cases of a more general single theoretical paradigm. Hence, all convergence guarantees stem from the adiabatic theorem and not particular circuit implementation.

$\endgroup$
6
  • $\begingroup$ Right, so there's no reason to think that QAO Ansatz would perform any better than QAOA, since they both have their roots in the (same) adiabatic theorem. $\endgroup$ Commented Apr 16, 2023 at 15:19
  • 2
    $\begingroup$ QAO might perform better as it explores a different feasible space. Moreover choosing a different mixing Hamiltonian may improve the minimum eigengap situation. But overall, the asymptomatic behavior shouldn't be significantly different. $\endgroup$
    – MonteNero
    Commented Apr 16, 2023 at 16:38
  • 2
    $\begingroup$ There is some interesting evidence that QAO Ansatz, to use your naming scheme, (specifically, using different mixers such as Grover, Clique, or Ring) may have advantages over the transverse field Ising QAOA implementation: arxiv.org/abs/2202.00648 $\endgroup$ Commented Apr 16, 2023 at 20:19
  • $\begingroup$ Interesting paper. The adiabatic theorem requires that we start in the ground state of the Ising Hamiltonian. For QAOA it's obvious that starting in the ground state |0> of the mixer Hamiltonian. However, in QAO Ansatz I fail to see how we "start" in the ground state of these more advanced mixers by starting in a feasible state. In what way are we starting in the ground state of these complex Hamiltonians? $\endgroup$ Commented Apr 18, 2023 at 3:37
  • 2
    $\begingroup$ @IsalanOnkar, the QAOA has the initial ground state $|+...+\rangle$ not $|0...0\rangle$. $\endgroup$
    – MonteNero
    Commented Apr 18, 2023 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.