Quantenalgorithmus für lineare Gleichungssysteme (HHL09): Schritt 2 - Was ist

9

Dies ist eine Fortsetzung des Quantenalgorithmus für lineare Gleichungssysteme (HHL09): Schritt 1 - Verwirrung hinsichtlich der Verwendung des Phasenschätzungsalgorithmus und des Quantenalgorithmus für lineare Gleichungssysteme (HHL09): Schritt 1 - Anzahl der benötigten Qubits .


In der Arbeit: Quantenalgorithmus für lineare Gleichungssysteme (Harrow, Hassidim & Lloyd, 2009) , was zu dem Teil geschrieben wurde

Der nächste Schritt ist die Zersetzung von |b in der Eigenvektorbasis, unter Verwendung von Phasenschätzung [5-7]. Bezeichnen mit |uj die Eigenvektoren von A (oder äquivalent, von eiAt ) und durch λj die entsprechenden Eigenwerte.

auf Seite 2 macht etwas Sinn für mich (die Verwirrungen bis es in den früheren Veröffentlichungen oben verlinkten angesprochen wurde). Der nächste Teil, dh die R(λ1) -Rotation, scheint jedoch etwas kryptisch.

Lassen Sie

|Ψ0:=2Tτ=0T1sinπ(τ+12)T|τ

für einige große . Die Koeffizienten von | Ψ 0 gewählt wird (nach [5-7]) einer gewissen quadratischen Verlustfunktion zu minimieren , die in unserer Fehleranalyse wird angezeigt (siehe [13] für weitere Details).T|Ψ0

Als nächstes wenden wir die bedingte Hamiltonsche Evolution on | Ψ 0 C & xotime ; | b , wobei t 0 = O ( κ / ε ) .τ=0T1|ττ|CeiAτt0/T|Ψ0C|bt0=O(κ/ϵ)

Fragen:

1. Was genau ist ? Wofür stehen T und τ ? Ich habe keine Ahnung , von wo aus diesem gigantischen Ausdruck |Ψ0Tτkommt plötzlich aus und was seine Verwendung ist.

2Tτ=0T1sinπ(τ+12)T|τ

2. Nach dem Phasenschätzungsschritt ist der Zustand unseres Systems anscheinend :

(j=1j=Nβj|uj|λ~j)|0ancilla

Dies ist sicherlich nicht geschrieben werden dh

(j=1j=Nβj|uj)(j=1j=N|λ~j)|0ancilla

|b(j=1j=N|λ~j)|0ancilla

Es ist also klar, dass nicht verfügbar ist separat in dem zweiten Register. Ich habe also keine Ahnung, wie sie einen Staat wie | vorbereiten Ψ 0 C & xotime ; | b an erster Stelle! Auch was macht das C im hochgestellten von | Ψ 0 C bezeichnen?|b|Ψ0C|bC|Ψ0C

3. Woher kommt dieser Ausdruck erscheinen plötzlich von? Was nützt es, es zu simulieren? Und was ist κ in O ( κ / ϵ ) ?τ=0T1|ττ|CeiAτt0/TκO(κ/ϵ)

Sanchayan Dutta
quelle

Antworten:

5

1. Definitionen

Die in dieser Antwort verwendeten Namen und Symbole folgen denen, die in Algorithmen für lineare Quantensysteme definiert sind: ein Primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) . Ein Rückruf erfolgt unten.

1.1 Registernamen

Registernamen sind in Abbildung 5 der Algorithmen für quantenlineare Systeme definiert: ein Primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (unten wiedergegeben):

  • (1 Qubit) ist das Ancilla-Register, mit dem überprüft wird, ob die Ausgabe gültig ist oder nicht.S
  • ( n Qubits) ist das Taktregister, dh das Register, das zum Schätzen der Eigenwerte des Hamilton-Operators mit Quantenphasenschätzung (QPE) verwendet wird.Cn
  • ( m Qubits) ist das Register, in dem die rechte Seite der Gleichung A x = b gespeichert ist. Es speichert x , das Ergebnis der Gleichung, wenn S als | gemessen wird 1 am Ende des Algorithmus.ImAx=bxS|1

HHL-Algorithmus

2. Über :|Ψ0

  1. Was genau ist ?|Ψ0

    |Ψ0C

  2. Tτ

    TT|Ψ0T|Ψ0T2nC

    τ

  3. |Ψ0

    Eine ausführliche Erklärung finden Sie in DaftWullies Beitrag .

    Nach den Zitaten im Quantenalgorithmus für lineare Gleichungssysteme (Harrow, Hassidim & Lloyd, 2009 v3) erhalten wir:

    1. Die vorherige Version des gleichen Papiers Quantenalgorithmus für lineare Gleichungssysteme (Harrow, Hassidim & Lloyd, 2009 v2) . Die Autoren haben das Papier zweimal überarbeitet (es gibt 3 Versionen des ursprünglichen HHL-Papiers) und Version Nr. 3 enthält nicht alle Informationen, die in den vorherigen Versionen bereitgestellt wurden. In der V2 (Abschnitt A.3. Ab Seite 17) bieten die Autoren eine detaillierte Analyse des Fehlers mit diesem speziellen Ausgangszustand.
    2. |Ψ0|Ψopt

|Ψ0

|Ψ0|Ψ0

Ihr Phasenschätzungsalgorithmus ist:

  1. |Ψ0C
  2. CI|Ψ0|b
  3. Wenden Sie die Quanten-Fourier-Transformation auf den resultierenden Zustand an.

C|Ψ0C|Ψ0C

4. Hamiltonsche Simulation:

κA

τ=0T1|ττ|CeiAτt0/T

|ττ|CC

eiAτt0/TI|b

U=eiAτt0/T

Nelimee
quelle
3

Als Antwort auf Ihre erste Frage habe ich mir vor einiger Zeit einige Notizen über mein Verständnis der Funktionsweise geschrieben. Die Notation ist wahrscheinlich etwas anders (ich habe versucht, sie besser in Einklang zu bringen, aber es ist leicht, Bits zu übersehen), versucht aber, diese Wahl des Zustands zu erklären . Es scheint auch einige Faktoren zu geben, in denen stellenweise .|Ψ012

Wenn wir die Phasenschätzung zum ersten Mal untersuchen, denken wir normalerweise darüber nach, ob sie in einem bestimmten Algorithmus wie dem Shor-Algorithmus verwendet werden soll. Dies hat ein spezifisches Ziel: die beste Bit-Annäherung an den Eigenwert zu erhalten. Entweder Sie tun es oder Sie tun es nicht, und die Beschreibung der Phasenschätzung ist speziell darauf abgestimmt, eine möglichst hohe Erfolgswahrscheinlichkeit zu erzielen.t

In HHL versuchen wir, einen Zustand zu erzeugen wobei unter Verwendung der Phasenschätzung. Die Genauigkeit der Approximation davon hängt wesentlich kritischer von einer genauen Schätzung der Eigenwerte ab, die nahe bei 0 liegen, als von denen, die weit von 0 entfernt sind. Ein naheliegender Schritt besteht daher darin, zu versuchen, das Phasenschätzungsprotokoll so zu modifizieren, dass eher "Bins" mit fester Breite zur Approximation der Phasen von ( und ist die Anzahl der Qubits im Phasenschätzungsregister), könnten wir eher einen Satz von spezifizieren für

|ϕ=jβjλj|λj,
|b=jβj|λj2π/TeiAtT=2ttϕyy{0,1}t soll als Zentrum jedes Behälters fungieren, so dass wir die Genauigkeit nahe der 0-Phase erheblich erhöhen können. Im Allgemeinen können Sie eine Kompromissfunktion angeben, wie tolerant Sie gegenüber Fehlern in Abhängigkeit von der Phase . Die genaue Art dieser Funktion kann dann auf eine bestimmte Anwendung und die bestimmte Gütezahl abgestimmt werden, anhand derer Sie den Erfolg bestimmen. Im Fall von Shors Algorithmus war unsere Gütezahl einfach dieses Binning-Protokoll - wir waren erfolgreich, wenn sich die Antwort im richtigen Bin befand und außerhalb davon erfolglos war. Dies wird bei HHL nicht der Fall sein, dessen Erfolg durch ein kontinuierliches Maß wie die Wiedergabetreue vernünftiger erfasst wird. Für den allgemeinen Fall werden wir also eine KostenfunktionϕC(ϕ,ϕ)Dies gibt eine Strafe für Antworten wenn die wahre Phase .ϕϕ

Es sei daran erinnert, dass das Standard-Phasenschätzungsprotokoll einen Eingangszustand erzeugte, der die einheitliche Überlagerung aller Basiszustände für . Dieser Zustand wurde verwendet, um die sequentielle Anwendung mehrerer gesteuerter Gatter zu steuern , auf die eine inverse Fourier-Transformation folgt. Stellen Sie sich vor, wir könnten den Eingabestatus durch einen anderen Status ersetzen und dann könnte der Rest des Protokolls arbeite wie zuvor. Im wir die Frage ignorieren, wie schwierig es ist, den neuen Zustand zu erzeugen , da wir nur versuchen, das Grundkonzept zu vermitteln. Ausgehend von diesem Zustand erfolgt die Verwendung des gesteuerten|xx{0,1}tU

|Ψ0=x{0,1}tαx|x,
|Ψ0UGates (die auf einen Eigenvektor von mit dem Eigenwert abzielen ) erzeugen den Zustand Das Anwenden der inversen Fourier-Transformation ergibt Die Wahrscheinlichkeit, eine Antwort (dh ), ist sodass der erwartete Wert der Kostenfunktion unter der Annahme einer zufälligen Verteilung des ist Uϕ
x{0,1}tαxeiϕx|x.
1Tx,y{0,1}teix(ϕ2πyM)αx|y.
yϕ=2πy/T
1T|x{0,1}teix(ϕ2πyT)αx|2
ϕ
C¯=12πT02πdϕy{0,1}t|x{0,1}teix(ϕ2πyT)αx|2C(ϕ,2πy/T),
und unsere Aufgabe ist es, die Amplituden , die dies für jede spezifische Realisierung von minimieren . Wenn wir die vereinfachende Annahme treffen, dass nur eine Funktion von , können wir eine Änderung der Variablen in der Integration vornehmen, um Wie wir festgestellt haben, ist das nützlichste Maß wahrscheinlich ein Treue-Maß. Stellen Sie sich vor, wir haben einen ZustandαxC(ϕ,ϕ)C(ϕ,ϕ)ϕϕ
C¯=12π02πdϕ|x{0,1}teixϕαx|2C(ϕ),
|+und wir möchten das einheitliche implementieren, aber stattdessen implementieren wir . Die Wiedergabetreue misst, wie gut dies die gewünschte Aufgabe erfüllt, also nehmen wir da im Idealfall , kann der Fehler, den wir minimieren wollen, als . Dies wird sicherlich die richtige Funktion für die Bewertung einesUϕ=|00|+eiϕ|11|Uϕ=|00|+eiϕ|11|
F=|+|UϕU|+|2=cos2(ϕϕ2),
C(ϕϕ)=sin2(ϕϕ2),
F=11FUtFür die allgemeinere Aufgabe, die Amplituden und nicht nur die Phasen zu modifizieren, breiten sich die Auswirkungen von Ungenauigkeiten weniger trivial durch das Protokoll aus, so dass es schwierig ist, die Optimalität zu beweisen, obwohl die Funktion wird bereits eine gewisse Verbesserung gegenüber der einheitlichen Überlagerung von Zuständen liefern. Wenn wir mit diesem Formular fortfahren, haben wir Das Integral over kann jetzt ausgeführt werden, daher möchten wir die Funktion minimieren Dies kann kurz ausgedrückt werden als C(ϕϕ)
C¯=12π02πdϕ|x{0,1}teixϕαx|2sin2(12ϕ),
ϕ
12x,y=0T1αxαy(δx,y12δx,y112δx,y+1).
minΨ0|H|Ψ0
wobei Die optimale Wahl von ist der minimale Eigenvektor der Matrix , und ist der minimale Eigenwert Entscheidend ist , dass für große , Skalen als eher als die , die wir von den einheitlichen bekommen haben würde Kopplung Wahl
H=12x,y=0T1(δx,y12δx,y112δx,y+1)|xy|.
|Ψ0H
αx=2T+1sin((x+1)πT+1),
C¯
C¯=1212cos(πT+1).
TC¯1/T21/Tαx=1/T. Dies ergibt einen signifikanten Vorteil für die Fehleranalyse.

Wenn Sie das gleiche wie im HHL-Papier erhalten möchten, müssen Sie die Begriffe hinzufügen zum Hamiltonianer. Ich habe jedoch keine Rechtfertigung dafür, aber dies ist wahrscheinlich mein Versagen.|Ψ014(|0T1|+|T10|)

DaftWullie
quelle