4
$\begingroup$

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)

Questions

  • 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?
Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ When you add a layer, you can always just set the last two angles to zero and get the same performance as before. If you optimize from there, you won’t get any worse! Of course, there might be a better strategy to find a global optimum, but this at least always lets you beat the value you found at p-1 when increasing to p $\endgroup$
    – Jahan Claes
    Mar 7, 2022 at 4:53
  • $\begingroup$ But if I'm stuck at a local optimum increasing p wouldn't help me is this correct? Unless I try starting from a different starting point? I want to confirm my understanding of this since he says in the paper that we always find the max value of the cost function as p goes to infinity. But I can see a sitiuation where arbitrarily increasing p wouldn't help us. $\endgroup$
    – bubakazouba
    Mar 7, 2022 at 17:42
  • $\begingroup$ The performance should monotonically increase either way, but to actually get the optimal value of the cost function requires you to be able to do the optimization over angles; you could get stuck and never quite reach the max value. $\endgroup$
    – Jahan Claes
    Mar 7, 2022 at 20:20
  • $\begingroup$ On the other hand, you can always fall back on choosing the angles by Trotterizing an adiabatic path, instead of trying to optimize them. In this case, you don't need to worry about local minima, and you will EVENTUALLY get to the optimal value. $\endgroup$
    – Jahan Claes
    Mar 7, 2022 at 20:21
  • $\begingroup$ this makes sense, I guess the correct way of intepreting this is that it "can" monotonically increase. But we can make bad decisions with the classical optimizer and get stuck in a loca optimum or even do worse. Thanks for clarifying! $\endgroup$
    – bubakazouba
    Mar 7, 2022 at 23:32

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.