Edward Farhi's paper on the Quantum Approximate Optimization Algorithm introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum annealers have focused on combinatorial optimization algorithms for some time now. What is gained by using QAOA on a gate model quantum computer instead of using a Quantum Annealer?


1 Answer 1


One of the advantages, as stated in the paper you linked, is that with QAOA you can increase the precision arbitrarily, whereas QA will only find the solution with probability 1 as $T \to \infty$ which is impractical. In addition if $T$ is too long you're likely to not find the solution as the probability is not monotonic. I believe an example of this can be found in a fair-sampling paper by Matsuda et al. Figure 4 shows that for large $\tau$, using quantum annealing on a 5-qubit system, you only likely to find 2 of the 3 possible states.

[arXiv:0808.0365v3] Ground-state statistics from annealing algorithms: Quantum vs classical approaches - Matsuda et al.

  • 1
    $\begingroup$ Yes, you can increase the precision arbitrarily with QAOA, but you do that by increasing the integer $p$. When $p\rightarrow \infty$ then you find the solution with probability $1$. $\endgroup$ Commented Mar 30, 2019 at 13:35
  • $\begingroup$ What is an intuitive or mathematical reason behind better result with increasing p? $\endgroup$
    – Edifice
    Commented Apr 20, 2019 at 3:22

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.