From A Quantum Approximate Optimization Algorithm - Farhi et al.
The Quantum Approximate Optimization Algorithm has the key feature that as p increases the approximation improves. We contrast this to the performance of the QAA. For realizations of the QAA there is a total run time T that also appears in the instantaneous Hamiltonian, H ( t ) = ˜ H ( t / T ) . We start in the ground state of ˜ H ( 0 ) seeking the ground state of ˜ H ( 1 ) . As T goes to infinity the overlap of the evolved state with the desired state goes to 1. However the success probability is generally not a monotonic function of T . See figure 2 of reference crosson-2014 for an extreme example where the success probability is plotted as a function of T for a particular 20 qubit instance of Max2Sat. The probability rises and then drops dramatically, and the ultimate rise for large T is not seen for times that can be reasonably simulated. It may well be advantageous in designing strategies for the QAOA to use the fact that the approximation improves as p increases.
It sounds like he is suggesting that QAOA will always give a better approximation to the optimization function monotonically as p increases. (unlike the Quantum Adiabatic Algorithm)
- Is my interpretation correct from his statement?
- Why is this the case? Couldn't the classical optimizer (e.g a gradient descent one) get stuck at a local optima?