What is the relationship between the mixing operators and initial states found in QAOA and Quantum Annealing?

Question

In many papers, the QAOA is shown to be intimately related to Quantum Annealing/Quantum Adiabatic Algorithm/Adiabatic Quantum Optimization.

The mixing operator in the QAOA is described by Hadfield as one that transfers probability amplitudes between states. Another post shows it also helps change the probability distribution, as evolving only under the cost Hamiltonian has no effect on the probabilities. It also prevents the possibility of being stuck in an eigenstate of the problem Hamiltonian. In Quantum Annealing, the driver is chosen such that it doesn't commute with the problem Hamiltonian and that it has an easy to construct ground state, after which the system is evolved adiabatically to find the ground state of the problem Hamiltonian. I also see how the QAOA is a discrete trotterization of Quantum Annealing.

I used Qiskit to implement the QAOA and tested them on a simple 3 node graph with 2 edges, a 4-regular 6 node graph and an 8 node 4-regular graph. In each case, I tried a variety of depths (p=3,6,12,24), the standard equal superposition initial state as well as random states. In all initial states I tried, I was able to find the MAXCUT solution. This to me seems strange, since the initial state is crucial to Quantum Annealing. In which case, how is the driver and the mixer related?

I also inspected the relationships between the optimized $\beta$s and $\gamma$s. Given that the QAOA is a trotterization of Quantum Annealing, and that we can think of these angles as the length of time the system is evolving under the operator, I expected to find an inverse relationship such that the values of the angles used for the Mixer unitary decrease in magnitude and the values of the angles used for the Phase unitary increase in magnitude as we move from the leftmost part of the circuit to the right. But this was not the case and no discernible pattern could be seen. Shouldn't there be a correlation to a progression in time? Or perhaps the progression is not linear?

Answer 1

You shouldn't take the analogy with quantum annealing too seriously.

The derivation of QAOA starting from quantum annealing proves that if you allow yourself as many layers as you want, then there exists some angles that get you close to the ground state, just by Trotterizing an adiabatic evolution path starting from a product state. But if you take this derivation seriously for actually choosing angles, you'll run into some problems:

• What is the best adiabatic path? Is it linear or quadratic or smooth or what? We'll get different angles depending on what adiabatic schedule we decide to Trotterize!
• Are the Trotterized angles really the best possible angles? If I take these angles seriously, it seems to say that at the beginning I should be applying the mixing Hamiltonian $B=\sum_i X_i$ for large angles, and the cost Hamiltonian $C=\sum_{i,j}C_{i,j}Z_iZ_j$ for short times. But when I start in the $|+\cdots +\rangle$ state, the first few applications of $e^{-i\beta B}$ don't really do anything, since I'm in an eigenstate of $B$.
• If I don't have large enough $p$ to imitate Trotterization, am I stuck?

In practice, QAOA is run at depths $p$ far too small to be able to actually realize the Trotterized evolution. You have to hope that the mistake you're making by limiting to small $p$ is counteracted by the fact that you're allowing the algorithm to optimize over the angles. There's no guarantee you'll get anything like the Trotterization of some adiabatic path. And there's no guarantee that starting in the "wrong" state will stop the algorithm from being able to steer you to the correct answer, if you give it enough layers $p$ to make up for the wrong initial state.

That said, in general for MAXCUT and similar problems, people do seem to see a general pattern of $\beta$ decreasing with each layer and $\gamma$ increasing, which roughly matches the Trotterization expectation. See Fig. 2 here or Tables 1 and 2 here.