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?


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.

| improve this answer | |
  • $\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$ – Turbotanten Mar 30 '19 at 13:35
  • $\begingroup$ What is an intuitive or mathematical reason behind better result with increasing p? $\endgroup$ – Abdullah Ash- Saki Apr 20 '19 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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