Was ist der Unterschied zwischen QAOA und Quantum Annealing?

8

Edward Farhis Artikel über den Quantum Approximate Optimization Algorithm stellt eine Möglichkeit für Gate-Modell-Quantencomputer vor, kombinatorische Optimierungsalgorithmen zu lösen. Quanten-Annealer im D-Wave-Stil konzentrieren sich jedoch seit einiger Zeit auf kombinatorische Optimierungsalgorithmen. Was bringt die Verwendung von QAOA auf einem Quantencomputer mit Gate-Modell anstelle eines Quanten-Annealers?

hoffentlich kohärent
quelle

Antworten:

3

Einer der Vorteile, wie in dem von Ihnen verlinkten Artikel angegeben, besteht darin, dass Sie mit QAOA die Genauigkeit beliebig erhöhen können, während QA die Lösung nur mit der Wahrscheinlichkeit 1 als was unpraktisch ist. Wenn zu lang ist, werden Sie wahrscheinlich keine Lösung finden, da die Wahrscheinlichkeit nicht monoton ist. Ich glaube, ein Beispiel dafür findet sich in einem Fair-Sampling-Paper von Matsuda et al. Abbildung 4 zeigt, dass Sie für großes Quantenglühen in einem 5-Qubit-System wahrscheinlich nur 2 der 3 möglichen Zustände finden.T.T.τ

[arXiv: 0808.0365v3] Grundzustandsstatistik von Annealing-Algorithmen: Quantum vs klassische Ansätze - Matsuda et al.

Andrew O.
quelle
Ja, Sie können die Genauigkeit mit QAOA beliebig erhöhen, aber Sie tun dies, indem Sie die Ganzzahl erhöhen . Wenn ist, finden Sie die Lösung mit der Wahrscheinlichkeit . pp1
Turbotanten
Was ist ein intuitiver oder mathematischer Grund für ein besseres Ergebnis mit zunehmendem p?
Abdullah Ash-Saki