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?

up vote 3 down vote accepted

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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