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

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:

,$V_a|q_0\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle$

,$V_a|q_1\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle$

,$V_{\$}|q_0\rangle = |q_{rej}\rangle$

$V_{\$}|q_1\rangle = |q_{acc}\rangle$

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 | $q_0$$a$ Chance, im Staat zu bleiben| q0⟩, a| | $||\frac{1}{2}||^2 = \frac{1}{4}$$|q_0\rangle$ Chance auf Fortschritt| q1⟩und ein| | $||\frac{1}{2}||^2 = \frac{1}{4}$$|q_1\rangle$ Chance, die Berechnung zu beenden und die Zeichenfolge abzulehnen.$||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$

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

Ich bin mir jedoch nicht ganz sicher, ob das richtig ist. Die in der Arbeit genannten Wahrscheinlichkeiten für die Annahme der Zeichenfolge sind $aa$ während die Wahrscheinlichkeit der Ablehnung3beträgt$\frac{1}{4}$ . 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.$\frac{3}{4}$

Vielen Dank.

Überarbeitetes Automatenmodell, um die Wahrscheinlichkeiten genauer wiederzugeben:

$V_a$$|q_{0}⟩$$|q_{1}⟩$$|q_{0}⟩\langle q_{0}|$$|q_{1}⟩\langle q_{1}|$. 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.

$a$$V_a$

• $P_{acc}=|q_{acc}⟩\langle q_{acc}|$
• $P_{rej}=|q_{rej}⟩\langle q_{rej}|$
• $P_{non}= |q_{0}⟩\langle q_{0}|+|q_{1}⟩\langle q_{1}|$

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

$(|q_{0}⟩+|q_{1}⟩)/2$$P_{non}$$|q_{0}⟩$$|q_{1}⟩$

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):

$|q_0\rangle$

1. $V_a$$\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle+ \frac{1}{\sqrt{2}} |q_{rej}\rangle$$(1/\sqrt{2})^2=1/2$$|q_{rej}\rangle$$1/2$$\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$

2. $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$$V_a$

3. $V_{\$}$$\$$$\frac{1}{2} |q_{rej}\rangle+\frac{1}{2} |q_{acc}\rangle$$(1/2)^2=1/4$$q_{rej}$$1/4$$q_{acc}$

$1/4$$1/2+1/4=3/4$

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.

• $\mathcal H$$\mathcal H$
• $V_q : \mathcal H \to \mathcal H$$V_q^\dagger V_q = I$$V_c$$V_c = I$$V_\$$
• $V_c\,\mathbf{\hat e}_1$$V_c$$\mathbf{\hat e}_1$$q_0$
  
  
  1. $a$$V_a$
  2. $\mathbf v$$u_A$$u_R$$|u_A|^2$$|u_R|^2$
  3. $(1 - |u_A|^2 - |u_R|^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.

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.