Was ist der Unterschied zwischen QAOA und Quantum Annealing?

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?

algorithm speedup annealing optimization qaoa hoffentlich kohärent
quelle

Antworten:

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 \to \infty$ $T$ $\tau$

[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 .

p

$p$

p \to \infty

$p\rightarrow \infty$

1

$1$

Turbotanten

Was ist ein intuitiver oder mathematischer Grund für ein besseres Ergebnis mit zunehmendem p?

Abdullah Ash-Saki