Beispielfrage für 1-Wege-Quanten-endliche Automaten

8

Ich versuche mein Verständnis in dem Beispiel zu verdeutlichen, das in Abschnitt 2.2 von Einweg-Quantenautomaten: Stärken, Schwächen und Verallgemeinerungen vorgestellt wird (dieser alternative Link kann ebenfalls nützlich sein). Dieses Beispiel bietet ein sehr reduziertes Beispiel für eine 1-QFA mit den folgenden Übergangsregeln:

,Va|q0=12|q0+12|q1+12|qrej

,Va|q1=12|q0+12|q112|qrej

,V$|q0=|qrej

V$|q1=|qacc

Wenn ich zum Beispiel in bin und ein a als Eingabe verarbeite, wende ich die erste Regel an. Mein Verständnis ist, dass ich eine | haben würde | 1q0a Chance, im Staat zu bleiben| q0, a| | 1||12||2=14|q0 Chance auf Fortschritt| q1und ein| | 1||12||2=14|q1 Chance, die Berechnung zu beenden und die Zeichenfolge abzulehnen.||12||2=12

Ich würde mir vorstellen, dass die Automaten dafür wie das folgende Bild aussehen

Geben Sie hier die Bildbeschreibung ein

Ich bin mir jedoch nicht ganz sicher, ob das richtig ist. Die in der Arbeit genannten Wahrscheinlichkeiten für die Annahme der Zeichenfolge sind 1aa während die Wahrscheinlichkeit der Ablehnung3beträgt14 . Ich frage mich nur, ob jemand entweder auf einen Fehler hinweisen oder bestätigen könnte, was ich konzeptionell für das Beispiel im Sinn habe.34

Vielen Dank.

Überarbeitetes Automatenmodell, um die Wahrscheinlichkeiten genauer wiederzugeben: Geben Sie hier die Bildbeschreibung ein

Vincent Russo
quelle
1
Ich schlage vor, Sie suchen nach "Quantenüberlagerung". Es sieht so aus, als würden Sie es rein probabilistisch interpretieren, was die Möglichkeit von Interferenzen ignoriert, die im Quantencomputer von zentraler Bedeutung sind.
Funkstar
q0qrej||12||2
1
Beachten Sie, dass die Messung teilweise ist - es gibt Ihnen keinen genauen Zustand, es sei denn, es ist ein Endzustand. Auf diese Weise können Sie eine (Teil-) Messung durchführen, nachdem Sie eine einheitliche Transformation angewendet haben, die einem Symbol entspricht. Wenn sie nicht in einen endgültigen Zustand übergeht, befindet sie sich immer noch in einer richtigen Überlagerung, wodurch die Möglichkeit einer Interferenz offen bleibt.
Funkstar
a12q0q112|q0+12|q1a|q0|q1
(12q0|+12q1|)(12|q0+12|q1+12|qrej)((12|q0+12|q112|qrej)) =(14q0|q0+14q1|q1)(12|q0+12|q112|qrej) =18|q0+18|q1

Antworten:

5

Va|q0|q1|q0q0||q1q1|. Mit anderen Worten, diese Zahlen stellen keine Wahrscheinlichkeiten dar, sie entsprechen nicht den Ergebnissen der durchzuführenden Messung. Das Beschriften der Pfeile des Diagramms mit diesen Zahlen würde daher eine möglicherweise irreführende Darstellung der Funktionsweise des Messprozesses liefern.

aVa

{|q0,|q1,|qacc,|qrej}
  • Pacc=|qaccqacc|
  • Prej=|qrejqrej|
  • Pnon=|q0q0|+|q1q1|

Mit anderen Worten, die Messung hat drei mögliche Ergebnisse: ( acc ) die Automaten messen einen akzeptierenden Zustand und halten an; ( rej ) die Automaten messen einen Ablehnungszustand und halten an; ( nicht ) Das Automatisieren misst etwas anderes, hält nicht an und liest das nächste Symbol (Nichtzustände für Nicht-Anhalten).

(|q0+|q1)/2Pnon|q0|q1

Unter Berücksichtigung aller genannten Punkte ist es einfach, die in Ihrer Hauptreferenz angegebene Berechnung zu befolgen . Um alles zu veranschaulichen gesagt, und, der Vollständigkeit halber, werde ich es zitieren mit hier mit einigen kleineren Kommentare (obwohl ich einige Änderungen hinzugefügt, ich weiß nicht , ob diese Art des Zitierens akzeptabel ist, wenn sein ist nicht , bitte, lassen Sie mich die Antwort selbst kennen oder bearbeiten):

|q0

  1. Va12|q0+12|q1+12|qrej(1/2)2=1/2|qrej1/212|q0+12|q1

  2. 12|q0+12|q1Va

  3. V$$12|qrej+12|qacc(1/2)2=1/4qrej1/4qacc

1/41/2+1/4=3/4

Juan Bermejo Vega
quelle
1
Ah, tolle Antwort, vielen Dank, dass Sie sich die Zeit genommen haben, es expliziter zu schreiben. Nebenbei bemerkt, gibt es einen offensichtlichen Weg oder vielleicht eine frühere Referenz, die eine visuelle Darstellung genauer und nicht irreführend darstellt? Es scheint, dass die Darstellung der Entwicklung in einer Art baumartiger Struktur möglicherweise eine bessere Veranschaulichung der Verzweigung ermöglicht, die während der Ausführung der Automaten auftritt. Danke nochmal für deine Hilfe.
Vincent Russo
1
@ VincentRusso: Man kann es nicht wirklich baumbasiert beschreiben. Der eigentliche Punkt ist, dass es destruktive Interferenzen zwischen Amplituden in den verschiedenen endlichen Automatenzuständen geben kann; Dies ist der Hauptunterschied zwischen stochastischer und Quantenberechnung. Die grafische Darstellung des Automaten ist nicht wirklich irreführend, wenn Sie ernst nehmen, dass sie eher Amplituden für Vektoren als probabilistische Übergänge beschreibt. Natürlich handelt es sich bei dem Modell sowohl für quanten- als auch für stochastische Automaten tatsächlich um lineare Transformationen, sodass das Bild größtenteils nebensächlich ist.
Niel de Beaudrap
Zu Beginn von Kapitel 6 von Kaye, Laflamme, Mosca gibt es eine schöne Diskussion über die Unterschiede zwischen klassisch-probabilistischer und Quantenberechnung; Die Autoren veranschaulichen den Text mit Zustandsdiagrammen. Sie diskutieren tatsächlich, dass diese Diagramme nicht völlig ausreichen, um Quanteninterferenz zu beschreiben - wie Niel de Beaudrap hervorgehoben und gut erklärt hat -. Ich persönlich empfehle diese Referenz zur weiteren Lektüre.
Juan Bermejo Vega
5

Juan Bermejo Vega hat eine genaue Zusammenfassung dessen gegeben, was in der Originalarbeit gesagt wird. Ich werde Ihnen eine übergeordnete Beschreibung geben.

Ich werde in Ihrem Fall empfehlen, die Amplituden nicht als Wahrscheinlichkeiten zu betrachten. Sie beziehen sich auf Wahrscheinlichkeiten, aber dies ist für diese endlichen Automaten nicht besonders hilfreich. Ich vermute, dass die Dinge viel klarer werden, wenn Sie dies als ein leicht abstraktes Rezept für die Transformation komplexwertiger Vektoren betrachten.

Welche Vektoren transformieren wir? Nun: Angenommen, Sie haben einen endlichen Automaten mit n Zuständen. Der Automat stellt ein (ja, probabilistisches) Modell zum Transformieren von Vektoren dar, das zu jedem Zeitpunkt zu einer Annahme- oder Ablehnungsentscheidung führen kann.

  • HH
  • Vq:HHVqVq=IVcVc=IV$
  • Vce^1Vce^1q0

    1. aVa
    2. vuAuR|uA|2|uR|2
    3. (1|uA|2|uR|2)1/2
    4. Fahren Sie mit dem nächsten Buchstaben fort.
  • Wir führen diese Transformationen für jeden Buchstaben des Wortes und auch für ein Abschlusssymbol $ durch, das wir an das Ende anhängen.

Die einzigen Zeitwahrscheinlichkeiten, die ins Spiel kommen, sind die akzeptierende und die ablehnende Achse . Während dieses Berechnungsmodell offensichtlich von endlichen Automaten inspiriert ist, ist es einfach nicht sinnvoll, einen der anderen Koeffizienten des Vektors zu irgendeinem Zeitpunkt (sogar am Ende!) Als Wahrscheinlichkeiten zu interpretieren.

Beachten Sie, dass die Annahme- und Ablehnungswahrscheinlichkeiten bei jedem Zeitschritt bedingte Wahrscheinlichkeiten sind, dh  sie hängen davon ab, dass die Berechnung noch nicht angehalten wurde. Wenn Sie die Gesamtwahrscheinlichkeit der Annahme / Ablehnung berechnen möchten, können Sie dies am einfachsten tun, indem Sie auf den Schritt "Renormierung" in der Evolution verzichten (den Teil, in dem wir mit dem Wert der inversen Quadratwurzel multiplizieren, aber dennoch die Annahme festlegen / lehne Koeffizienten auf Null ab, wenn die Berechnung fortgesetzt wird) und summiere einfach alle probabilistischen Beiträge zum Akzeptieren / Ablehnen, die auf dem Weg entstehen.

Niel de Beaudrap
quelle
1
Niel, nochmals vielen Dank für deinen Kommentar. Es war sehr hilfreich, sich ein intuitiveres Bild davon zu machen, wie diese Berechnung stattfindet. Vielen Dank, dass Sie sich die Zeit genommen haben, es zu erklären. Es ist mir jetzt viel klarer.
Vincent Russo
3

Sie gehen fälschlicherweise davon aus, dass der Status nach dem Lesen jedes Symbols vollständig (auf einen rechnergestützten Basiszustand) zusammenbricht. Die Messung in jeder Stufe ist nur teilweise.

Shitikanth
quelle
Ich hatte den Eindruck, dass, da dies das "Measure Many" -Modell verwendet, eine Messung für jeden Schritt der Berechnung durchgeführt wird, wodurch die Überlagerung auf einen bestimmten Wahrscheinlichkeitswert reduziert wird.
Vincent Russo
@ Vincent Russo Sie haben Recht, dass der Zustand für jedes gelesene Symbol gemessen wird.
Funkstar
Ich denke, dass ein QFA, bei dem der Zustand des Automaten nach jedem Schritt gemessen wird, einer Markov-Kette vollständig entspricht. Was wäre also die Motivation, sie zu studieren?
Shitikanth
3
Ich wollte nur zeigen, warum sein "überarbeitetes Automatenmodell" das QFA-System nicht genau beschreibt. Dies liegt in der Tat daran, dass der Automat bei jedem Schritt in der Rechenbasis nicht vollständig zusammenbricht.
Shitikanth
2
Auf jeden Fall denke ich, dass die Frage bereits hinreichend klar beantwortet wurde. Lassen Sie uns nicht in technischen Details verlieren.
Shitikanth