Welches Maß an "Vertrauen" des Ergebnisses von einem Quantencomputer ist möglich?

Auf einer sehr einfachen Ebene zwingt das Lesen oder Messen eines Qubits dazu, sich in dem einen oder anderen Zustand zu befinden, so dass der Betrieb eines Quantencomputers, um ein Ergebnis zu erhalten, den Zustand in eine von vielen Möglichkeiten einbricht.

Da der Zustand jedes Qubits jedoch probabilistisch ist, bedeutet dies sicherlich, dass das Ergebnis tatsächlich eine dieser Möglichkeiten mit unterschiedlicher Wahrscheinlichkeit sein kann. Wenn ich das Programm erneut ausführe - sollte ich mit unterschiedlichen Ergebnissen rechnen?

Wie kann ich sicher sein, dass ich das "beste" Ergebnis habe? Was gibt dieses Vertrauen? Ich gehe davon aus, dass es nicht die Zwischenmessungen sein können, wie in dieser Frage beschrieben, da sie die Ausgabe nicht kollabieren.

Die Mehrzahl der nützlichen / relativ effizienten Algorithmen ¹ für Quantencomputer gehört zur Komplexitätsklasse der BQP (Bounded Error Quantum Polynomial Time) . Nach dieser Definition soll die Ausfallrate eines Quantenalgorithmus oderP(Erfolg)≥$\leq\frac{1}{3}$ , obwohl das Ergebnis immer noch innerhalb eines kleinen Fehlers liegen kann. Ein nicht-probabilistischer Algorithmus (der in Polynomialzeit ausgeführt werden kann) befindet sich weiterhin in dieser Komplexitätsklasse, mit dem einzigen Unterschied, dass erimmerdas richtige Ergebnis²zurückgibt.$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$

Da Sie einen Algorithmus jedoch beliebig oft ausführen können, entspricht dies einer Erfolgswahrscheinlichkeit von mindestens für eine Eingabe der Längenund einer beliebigen positiven Konstantec.$\frac{1}{2} + n^{-c}$$n$$c$

Das "richtige" Ergebnis ist also das, das in mindestens zwei Dritteln der Fälle angezeigt wird, es sei denn, Sie möchten eine "One-Shot" -Berechnung durchführen, z der Quantenchip, bei dem die Statistiken eine Rolle spielen und Teil des „Ergebnisses“ sind.

Abgesehen von diesen (oder anderen Algorithmen, die kein einziges "korrektes Ergebnis" haben), ist ein Algorithmus mit einer Erfolgsrate von weniger als der Hälfte kein "begrenzter Fehler" mehr und für den Benutzer möglicherweise nicht möglich um das richtige ergebnis zu kennen - es kann einfach eine falsche antwort geben, bei der die wahrscheinlichkeit höher ist als bei der richtigen.

Ja, bei jeder Berechnung wird möglicherweise ein anderes Ergebnis angezeigt. Das Vertrauen in das Ergebnis ist gegeben durch:

1. Der Quantenalgorithmus selbst sorgt dafür, dass das richtige Ergebnis mit hoher Wahrscheinlichkeit eintritt und;
2. Wiederholen Sie den Algorithmus einige Male, um das wahrscheinlichste Ergebnis zu finden.

^{1 Hier Algorithmen, die in Polynomialzeit berechnet werden können, um eine Lösung mit 'hoher Wahrscheinlichkeit' zu erhalten, obwohl für die Zwecke dieser Antwort die Zeitkomplexität von geringerer Bedeutung ist}

^{2 Nun, zumindest idealistisch}

Auf Mithrandir24601die Antwort von etwas näher eingehen -

Die Funktion, die Sie befürchten, dass ein Quantencomputer beim nächsten Berechnungslauf eine andere Antwort liefert, ist auch eine Funktion der zufälligen Berechnung. In mancher Hinsicht ist es gut, eine einzige Antwort wiederholt zu erhalten, aber am Ende ist es ausreichend, eine korrekte Antwort mit ausreichend hoher Sicherheit zu erhalten. Genau wie bei einem zufälligen Algorithmus ist es wichtig, dass Sie sicher sein können, dass Sie bei jedem Durchlauf der Berechnung die richtige Antwort erhalten.

Zum Beispiel könnte Ihr Quantencomputer Ihnen zwei Mal von drei die richtige Antwort auf eine JA / NEIN-Frage geben. Dies scheint eine schlechte Leistung zu sein, aber dies bedeutet, dass Sie, wenn Sie es viele Male ausführen, einfach die Mehrheitsantwort nehmen und sehr zuversichtlich sein können, dass die Mehrheitsregel Ihnen die richtige Antwort gibt. (Gleiches gilt auch für normale zufällige Berechnungen.) Die Art und Weise, wie das Vertrauen mit der Anzahl der Runen steigt, bedeutet, dass, solange ein Lauf eine Antwort liefert, die deutlich mehr als nur eine 50% ige Chance auf Richtigkeit hat, Sie können Ihr Selbstvertrauen so hoch machen, wie Sie möchten, indem Sie nur eine bescheidene Anzahl von wiederholten Läufen durchführen (obwohl mehr Läufe erforderlich sind, liegt die Wahrscheinlichkeit einer korrekten Antwort in einem Lauf bei 50%).

$\mathrm{poly}(n)$$n$

Bei Problemen, die ausführlichere Antworten als JA / NEIN-Fragen enthalten, können wir nicht unbedingt davon ausgehen, dass dieselbe Antwort mehrmals gegeben wird, damit wir mehrheitlich abstimmen können. (Wenn Sie einen Quantencomputer zum Abtasten einer exponentiellen Anzahl von Ergebnissen verwenden, gibt es möglicherweise einige kleinere, aber immer noch exponentiell viele Antworten, die korrekt und nützlich sind!) Angenommen, Sie versuchen, ein Optimierungsproblem zu lösen: Es ist möglicherweise nicht einfach zu überprüfen, ob Sie die optimale Lösung oder eine nahezu optimale Lösung gefunden haben - oder ob die Antwort, die Sie erhalten haben, die beste ist, die der Quantencomputer leisten kann (was ist, wenn Sie beim nächsten Durchlauf eine Antwort erhalten?) bessere Antwort durch Zufall?). In diesem Fall ist es wichtig festzustellen, was Sie über das Problem wissen.NP , was bedeutet, dass Sie im Prinzip jede Antwort, die Sie erhalten, effizient überprüfen können?) Und mit welcher Qualität der Lösung Sie zufrieden wären.

Dies gilt auch für randomisierte Algorithmen. Der Unterschied besteht darin, dass wir davon ausgehen, dass Quantencomputer Probleme lösen können, die ein randomisierter Computer allein nicht leicht lösen kann.

$15$$3\times5$

Das passt gut zu Aaronsons gut getimtem Beat, und das Publikum schien immer ein wenig zu kichern, aber natürlich wissen wir alle, dass dies eine kleine Vereinfachung der Wahrscheinlichkeitscharakteristik von Shors Algorithmus ist.

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$

$\mathrm{BQP}$$\mathrm{NP}$

(Ich weiß, dass es bereits zwei großartige Antworten gibt. Die Frage ermöglicht jedoch eine Erläuterung / Klärung von Aaronsons Zitat / Anektdote.)