Das adiabatische Modell
Dieses Modell der Quantenberechnung basiert auf Ideen der Quanten-Vielteilchentheorie und unterscheidet sich wesentlich sowohl vom Schaltungsmodell (das ein zeitkontinuierliches Modell ist) als auch von zeitkontinuierlichen Quantenläufen (das ein zeitkontinuierliches Modell hat). abhängige Entwicklung).
Die adiabatische Berechnung erfolgt normalerweise in der folgenden Form.
- Beginnen Sie mit einigen Qubits, die sich alle in einem einfachen Zustand wie . Rufen Sie den anfänglichen globalen Status .| ψ 0 ⟩|+⟩|ψ0⟩
- Unterwerfe diese Qubits einer Interaktion Hamiltonian für die der einzigartige Grundzustand ist (der Zustand mit der niedrigsten Energie). Wenn zum Beispiel , können wir wählen . | ψ 0 ⟩ | ψ 0 ⟩ = | + ⟩ ⊗ n H 0 = - ∑ k σ ( x ) kH0|ψ0⟩|ψ0⟩=|+⟩⊗nH0=−∑kσ(x)k
- Wählen Sie ein endgültiges Hamilton- mit einem eindeutigen Grundzustand, der die Antwort auf ein Problem codiert, an dem Sie interessiert sind. Wenn Sie beispielsweise ein Problem mit der Einschränkungszufriedenheit lösen möchten, können Sie ein Hamilton- wobei die Summe die Randbedingungen des klassischen Problems nimmt und wobei jedes ein Operator ist, der einen Energiebetrag (einen positiven Energiebeitrag) für jeden Standardbasiszustand auferlegt, der eine klassische Zuordnung darstellt, die die Randbedingung nicht erfüllt .H 1 = ∑ c h c c h c cH1H1=∑chcchcc
- Definieren Sie ein Zeitintervall und einen zeitvariablen Hamilton- so dass und . Eine übliche, aber nicht notwendige Wahl besteht darin, einfach eine lineare Interpolation .H ( t ) H ( 0 ) = H 0 H ( T ) = H 1 H ( t ) = tT⩾0H(t)H(0)=H0H(T)=H1H(t)=tTH1+(1−tT)H0
- Lassen Sie das System für die Zeiten bis unter dem sich kontinuierlich ändernden Hamilton- entwickeln und messen Sie die Qubits am Ausgang, um ein Ergebnis .t = T H ( t ) y ∈ { 0 , 1 } nt=0t=TH(t)y∈{0,1}n
Die Basis des adiabatischen Modells ist der adiabatische Satz , von dem es mehrere Versionen gibt. Die Version von Ambainis und Regev [ arXiv: quant-ph / 0411152 ] (ein strengeres Beispiel) impliziert, dass zwischen dem Grundzustand von und seinem Zustand immer eine "Energielücke" von mindestens erster angeregter Zustand für alle , und die Operatornormen der ersten und zweiten Ableitung von sind klein genug (das heißt,H ( t ) 0 ≤ t ≤ T H H ( t )λ>0H(t)0⩽t⩽THH(t)ändert sich nicht zu schnell oder abrupt), dann können Sie die Wahrscheinlichkeit, die gewünschte Ausgabe zu erhalten, so groß machen, wie Sie möchten, indem Sie die Berechnung nur langsam genug ausführen. Darüber hinaus können Sie die Fehlerwahrscheinlichkeit um einen beliebigen konstanten Faktor verringern, indem Sie die gesamte Berechnung um einen polynomialen Faktor verlangsamen.
Obwohl es sich in der Darstellung stark vom Einheitsschaltungsmodell unterscheidet, wurde gezeigt, dass dieses Modell dem Einheitsschaltungsmodell [ arXiv: quant-ph / 0405098 ] in Polynomzeit äquivalent ist . Der Vorteil des adiabatischen Algorithmus besteht darin, dass er einen anderen Ansatz für die Konstruktion von Quantenalgorithmen bietet, der sich besser für Optimierungsprobleme eignet. Ein Nachteil ist, dass es nicht klar ist, wie es vor Lärm geschützt werden soll oder wie sich seine Leistung unter unvollständiger Kontrolle verschlechtert. Ein weiteres Problem besteht darin, dass es selbst ohne Fehler im System schwierig ist, zu bestimmen, wie langsam der Algorithmus ausgeführt wird, um eine zuverlässige Antwort zu erhalten. Dies hängt von der Energielücke ab, und es ist im Allgemeinen nicht einfach, die Energie zu bestimmen Lücke ist für ein statisches HamiltonH ( t )Hgeschweige denn ein zeitlich veränderliches .H(t)
Dies ist jedoch ein Modell von sowohl theoretischem als auch praktischem Interesse und unterscheidet sich am stärksten von dem Einheitsschaltungsmodell, das im Wesentlichen existiert.
Das Unitary Circuit Model
Dies ist das bekannteste Modell der Quantenberechnung. In diesem Modell gibt es folgende Einschränkungen:
Kleinere Details können sich ändern (z. B. die Menge der Einheiten, die man ausführen kann; ob man die Vorbereitung in anderen reinen Zuständen wie , , ; ob Messungen in der müssen) Standardbasis oder kann auch auf einer anderen Basis sein), aber diese machen keinen wesentlichen Unterschied.|1⟩ |+⟩ |−⟩
quelle
Zeitdiskreter Quantenlauf
Eine "zeitdiskrete Quantenwanderung" ist eine Quantenvariation einer zufälligen Wanderung, bei der es einen "Walker" (oder mehrere "Walker") gibt, der kleine Schritte in einem Graphen ausführt (z. B. eine Knotenkette oder ein rechteckiges Gitter) ). Der Unterschied besteht darin, dass ein Quantenläufer, wenn er einen Schritt in eine zufällig festgelegte Richtung unternimmt, einen Schritt in eine Richtung unternimmt, die durch ein Quanten- "Münz" -Register bestimmt wird, das bei jedem Schritt durch eine einheitliche Transformation "umgedreht" wird, anstatt geändert zu werden durch erneutes Abtasten einer Zufallsvariablen. Siehe [ arXiv: quant-ph / 0012090 ] für eine frühe Referenz.
Der Einfachheit halber beschreibe ich einen Quantensprung auf einem Zyklus der Größe ; Allerdings muss man einige Details ändern, um Quantensprünge in allgemeineren Graphen zu berücksichtigen. In diesem Berechnungsmodell wird normalerweise Folgendes ausgeführt.2n
Der Hauptunterschied zwischen diesem und einem zufälligen Laufen besteht darin, dass die verschiedenen möglichen "Flugbahnen" des Läufers kohärent in Überlagerung ausgeführt werden, so dass sie destruktiv interferieren können. Dies führt zu einem Gehverhalten, das eher ballistischen Bewegungen als Diffusionen gleicht. Eine frühe Darstellung eines Modells wie dieses wurde von Feynmann gemacht, um die Dirac-Gleichung zu simulieren.
Dieses Modell wird auch häufig in Bezug auf das Suchen oder Auffinden von "markierten" Elementen in der Grafik beschrieben. In diesem Fall führt man einen weiteren Schritt durch (um zu berechnen, ob der Knoten, an dem sich der Wanderer befindet, markiert ist, und um dann das Ergebnis dieser Berechnung zu messen ), bevor Sie zu Schritt 2 zurückkehren. Andere Variationen dieser Art sind sinnvoll.
Um einen Quantensprung auf einem allgemeineren Graphen durchzuführen, muss man das "Positions" -Register durch eines ersetzen, das alle Knoten des Graphen ausdrücken kann, und das "Münz" -Register durch eines, das die Kanten ausdrücken kann, die auf einen Scheitelpunkt fallen. Der "Münzprüfer" muss dann auch durch einen ersetzt werden, der es dem Fußgänger ermöglicht, eine interessante Überlagerung verschiedener Flugbahnen durchzuführen. (Was als "interessant" gilt, hängt von Ihrer Motivation ab: Physiker überlegen sich häufig, wie sich durch das Ändern des Münzoperators die Entwicklung der Wahrscheinlichkeitsdichte ändert, und zwar nicht zu Berechnungszwecken, sondern als Methode zum Ermitteln der Grundphysik mithilfe von Quantenläufen vernünftiges Spielzeugmodell der Partikelbewegung. ] von zeitdiskreten Quantenläufen.
Dieses Berechnungsmodell ist streng genommen ein Sonderfall des Einheitsschaltungsmodells, ist jedoch mit sehr spezifischen physikalischen Intuitionen motiviert, was zu einigen algorithmischen Einsichten (siehe z. B. [ arXiv: 1302.3143 ]) für Polynom-Zeit-Beschleunigungen bei beschränktem Fehler geführt hat Quantenalgorithmen. Dieses Modell ist auch ein enger Verwandter des zeitkontinuierlichen Quantenlaufs als Berechnungsmodell.
quelle
Quantenschaltungen mit Zwischenmessungen
Dies ist eine geringfügige Abweichung von "Einheitsschaltungen", bei denen Messungen sowohl in der Mitte als auch am Ende des Algorithmus zulässig sind und bei denen künftige Operationen auch von den Ergebnissen dieser Messungen abhängen können. Es stellt ein realistisches Bild eines Quantenprozessors dar, der mit einem klassischen Steuergerät interagiert, das unter anderem die Schnittstelle zwischen dem Quantenprozessor und einem menschlichen Benutzer darstellt.
Eine Zwischenmessung ist praktisch erforderlich, um eine Fehlerkorrektur durchzuführen, und daher ist dies im Prinzip ein realistischeres Bild der Quantenberechnung als das Einheitsschaltungsmodell. Es ist jedoch nicht ungewöhnlich, dass Theoretiker eines bestimmten Typs es nachdrücklich vorziehen, Messungen bis zum Ende zu belassen (wobei das Prinzip der verzögerten Messung zur Simulation von Zwischenmessungen verwendet wird). So kann dies eine signifikante Unterscheidung zu machen , wenn im Gespräch über Quantenalgorithmen - aber dies führt nicht zu einer theoretischen Erhöhung der Rechenleistung eines Quantenalgorithmus.
quelle
Quantenglühen
Quantenglühen ist ein Modell der Quantenberechnung, das grob gesagt das adiabatische Modell der Berechnung verallgemeinert. Als Ergebnis der Arbeit von D-WAVE zu diesem Thema hat es die Aufmerksamkeit der Öffentlichkeit und der Wirtschaft auf sich gezogen.
Genau das, woraus Quantenglühen besteht, ist nicht so genau definiert wie andere Berechnungsmodelle, da es für Quantentechnologen von größerem Interesse ist als für Informatiker. Allgemein gesagt, kann man sagen, dass dies in der Regel eher von Ingenieuren als von Mathematikern in Betracht gezogen wird, so dass das Thema viele Intuitionen und Faustregeln zu haben scheint, aber nur wenige „formale“ Ergebnisse. In der Tat, in einer Antwort auf meine Frage zum Quantenglühen ,
Andrew O
geht man so weit zu sagen, dass " Quantenglühen kann nicht ohne Überlegungen von Algorithmen und Hardware definiert werden". Dennoch scheint "Quantenglühen" genau genug definiert zu sein, um als ein Ansatz zur Lösung von Problemen mit Quantentechnologien mit bestimmten Techniken beschrieben zu werden - und das trotzAndrew O
denke ich, dass es Einschätzung ein implizit definiertes Modell von Ich werde versuchen, dieses Modell hier zu beschreiben.Intuition hinter dem Modell
Quantenglühen hat seinen Namen von einer losen Analogie zum (klassischen) simulierten Glühen . Sie werden beide als Mittel zur Minimierung der Energie eines Systems dargestellt, ausgedrückt in der Form eines Hamilton-Operators: simulierten Tempern werden die möglichen Zuordnungen zu den 'lokalen' Variablen Wesentlichen zufällig ausgeführt , wobei jedoch die Wahrscheinlichkeit eines tatsächlichen Übergangs davon abhängt
Man beginnt mit dem System bei „unendlicher Temperatur“, was letztendlich eine ausgefallene Art zu sagen ist, dass Sie alle möglichen Übergänge zulassen, unabhängig von Energiezu- oder -abnahmen. Sie senken dann die Temperatur nach einem Zeitplan, so dass Zeit vergeht, Zustandsänderungen, die die Energie erhöhen, immer unwahrscheinlicher werden (obwohl immer noch möglich). Die Grenze ist die Temperatur Null, bei der jeder Übergang, der die Energie verringert, erlaubt ist, aber jeder Übergang, der die Energie erhöht, ist einfach verboten. Für jede TemperaturT>0 Es wird eine stabile Verteilung (ein "thermischer Zustand") von Zuordnungen geben, die die gleichmäßige Verteilung bei "unendlicher" Temperatur ist und die mit abnehmender Temperatur immer mehr auf die globalen Mindestenergiezustände gewichtet wird. Wenn Sie lange genug brauchen, um die Temperatur von unendlich auf nahe Null zu senken, sollten Sie im Prinzip ein globales Optimum für das Problem der Minimierung der Energie finden. Somit ist simuliertes Tempern ein Ansatz zur Lösung von Optimierungsproblemen.
Das Quantenglühen wird durch die Verallgemeinerung der Arbeit von Farhi et al. zur adiabatischen Quantenberechnung [ arXiv: quant-ph / 0001106 ] mit der Idee, zu überlegen, welche Evolution stattfindet, wenn man den Hamilton-Operator nicht unbedingt im adiabatischen Regime weiterentwickelt. Ähnlich wie beim klassischen Tempern beginnt man in einer Konfiguration, in der "klassische Zuordnungen" zu einem Problem in einer gleichmäßigen Verteilung vorliegen, diesmal jedoch in kohärenter Überlagerung anstelle einer Wahrscheinlichkeitsverteilung: Dies wird beispielsweise für die Zeit erreicht durch Setzen von in welchem Fall die einheitliche ÜberlagerungA ( t = 0 ) = 0 ,t=0
Ähnlich wie beim adiabatischen Quantenrechnen wird die Art und Weise, wie und definiert werden, häufig als lineare Interpolation von bis (ansteigend für und absteigend für ). und müssen jedoch nicht unbedingt linear oder sogar monoton sein , wie dies auch bei der adiabatischen Berechnung der Fall ist. Zum Beispiel hat D-Wave die Vorteile des Anhaltens des Glühplans und des "Rückwärtsglühens" in Betracht gezogen .A(t) B(t) 0 1 A(t) B(t) A(t) B(t)
"Richtiges" Quantenglühen (sozusagen) setzt voraus, dass die Evolution wahrscheinlich nicht im adiabatischen Regime stattfindet und die Möglichkeit diabatischer Übergänge zulässt, sondern nur nach einer hohen Chance fragt, ein Optimum zu erreichen - oder sogar noch pragmatischer. ein Ergebnis zu erzielen, das mit klassischen Techniken nur schwer zu finden ist. Es gibt keine formalen Ergebnisse darüber, wie schnell Sie Ihr Hamilton-Modell ändern können, um dies zu erreichen: Das Thema scheint hauptsächlich darin zu bestehen, mit einer Heuristik zu experimentieren, um zu sehen, was in der Praxis funktioniert.
Der Vergleich mit dem klassischen simulierten Glühen
Trotz der Terminologie ist nicht sofort klar, dass es viel gibt, was Quantenglühen mit klassischem Glühen gemeinsam hat. Die Hauptunterschiede zwischen dem Quantenglühen und dem klassischen simulierten Glühen scheinen zu sein:
Beim Quantenglühen ist der Zustand in gewisser Weise idealerweise eher ein reiner Zustand als ein gemischter Zustand (entsprechend der Wahrscheinlichkeitsverteilung beim klassischen Glühen);
Beim Quantenglühen wird die Evolution eher durch eine explizite Änderung des Hamilton-Werts als durch einen externen Parameter bestimmt.
Es ist möglich, dass eine Änderung der Darstellung die Analogie zwischen Quantenglühen und klassischem Glühen enger macht. Zum Beispiel könnte man den Temperaturparameter für das klassische Tempern in den Spin-Hamilton-Operator einbauen, indem man schreibt wobei wir für die Länge und des Anneal-Zeitplans. (Dies ist absichtlich so gewählt, dass und für
Es gibt immer noch Disanalogien zum Quantenglühen - zum Beispiel erreichen wir die starke Unterdrückung von Energiezuwächsen als indem wir die Potentialtöpfe unendlich tief machen (was nicht sehr physikalisch ist) - aber das tut es veranschaulichen etwas von einer Gemeinsamkeit zwischen den beiden Modellen, wobei der Hauptunterschied weniger die Entwicklung des Hamiltonian ist, als vielmehr der Unterschied zwischen Diffusions- und Schrödinger-Dynamik. Dies legt nahe, dass es einen schärferen Weg gibt, die beiden Modelle theoretisch zu vergleichen: indem der Unterschied zwischen klassischem und Quantenglühen als analog zum Unterschied zwischen Zufalls- und Quantenläufen beschrieben wirdt→tF . Eine gebräuchliche Redewendung bei der Beschreibung des Quantenglühens ist das "Tunneln" durch Energiebarrieren - dies ist sicherlich relevant für die Betrachtung von Quantenwanderungen: Betrachten Sie beispielsweise die Arbeit von Farhi et al. zu zeitkontinuierlichen Quantenbeschleunigungen für die Auswertung von NAND-Schaltkreisen und direkteren Grundlagenarbeiten von Wong zu Quantenläufen auf der Leitung, die durch potenzielle Barrieren tunneln . Die Kanzlerin [ arXiv: 1606.06800 ] hat einige Arbeiten durchgeführt, um das Quantenglühen in Form von Quantenläufen zu betrachten, obwohl offenbar Raum für eine formellere und vollständigere Darstellung besteht.
Auf rein operativer Ebene scheint das Quantenglühen einen Leistungsvorteil gegenüber dem klassischen Glühen zu bieten (siehe zum Beispiel diese Folien zum Leistungsunterschied zwischen Quantenglühen und klassischem Glühen von Troyers Gruppe an der ETH, ca. 2014).
Quantenglühen als Phänomen im Gegensatz zu einem Rechenmodell
Da Quantenglühen mehr von Technologen untersucht wird, konzentrieren sie sich auf das Konzept , Quantenglühen als Effekt zu realisieren, anstatt das Modell anhand allgemeiner Prinzipien zu definieren. (Eine grobe Analogie wäre, das Einheitsschaltungsmodell nur insofern zu untersuchen, als es ein Mittel darstellt, um die "Effekte" der Eigenwertschätzung oder Amplitudenverstärkung zu erzielen.)
Ob etwas als "Quantenglühen" gilt, wird daher zumindest von einigen als hardwareabhängig und sogar eingabeabhängig beschrieben: Zum Beispiel vom Layout der Qubits, den Geräuschpegeln der Maschine. Es scheint , dass auch die adiabatischen Regime zu nähern versuchen Sie verhindern , dass Quantenglühen zu erzielen, weil die Idee von dem, was Quantenglühen besteht sogar die Idee beinhaltet , dass Rauschen (wie Dekohärenz) Glühen davor realisiert verhindern wird: als rechnerischer Effekt , Im Gegensatz zu einem Rechenmodell erfordert das Quantentempern im Wesentlichen, dass der Temperschema kürzer ist als die Dekohärenzzeit des Quantensystems.
Einige Leute beschreiben gelegentlich Rauschen als wesentlich für den Prozess des Quantenglühens. Zum Beispiel haben Boixo et al. [ arXiv: 1304.4595 ] schreiben
Es könnte vielleicht zutreffend sein, es als ein unvermeidliches Merkmal von Systemen zu beschreiben, in denen man ein Tempern durchführen wird (nur weil Rauschen ein unvermeidliches Merkmal eines Systems ist, in dem Sie eine Quanteninformationsverarbeitung jeglicher Art durchführen werden): wie es " in Wirklichkeit nein "
Andrew O
schreibt Bäder helfen wirklich beim Quantenglühen ". Es ist möglich, dass ein dissipativer Prozess das Quantenglühen unterstützen kann, indem er dem System hilft, die Bevölkerung auf Zuständen mit niedrigerer Energie aufzubauen (wie von Amin et al. [ ArXiv: cond-mat / 0609332 ] vorgeschlagen). Dies scheint jedoch im Wesentlichen der Fall zu sein Dies ist ein klassischer Effekt und erfordert von Natur aus eher eine ruhige Umgebung mit niedrigen Temperaturen als das Vorhandensein von Lärm.Die Quintessenz
Insbesondere von jenen, die es studieren, könnte gesagt werden, dass Quantenglühen eher ein Effekt als ein Rechenmodell ist. Ein "Quanten-Annealer" würde dann am besten als "Maschine, die den Effekt des Quanten-Annealings realisiert" verstanden, und nicht als Maschine, die versucht, ein Rechenmodell zu verkörpern, das als " Quanten-Annealing " bekannt ist. Gleiches gilt jedoch für die adiabatische Quantenberechnung, die meines Erachtens als eigenständiges Rechenmodell bezeichnet wird.
Vielleicht wäre es fair, Quantenglühen als einen Ansatz zur Realisierung einer sehr allgemeinen Heuristik zu beschreiben , und dass es ein implizites Rechenmodell gibt, das als die Bedingungen charakterisiert werden könnte, unter denen wir erwarten könnten, dass diese Heuristik erfolgreich ist. Wenn wir Quantenglühen auf diese Weise betrachten, wäre es ein Modell, das das adiabatische Regime (mit Null-Rauschen) als Sonderfall einschließt, aber es kann im Prinzip allgemeiner sein.
quelle