Adiabatisches Quantencomputing: Warum nicht gleich das System in sein Problem Hamiltonian HPHPH_{P} versetzen?

Hintergrund: In jedem adiabatischen Quantencomputer (AQC)-Algorithmus lösen wir Probleme auf folgende Weise: Wir haben einen anfänglichen Hamilton-Operator, H 0 , dessen Grundzustand leicht zu finden ist, und ein Problem-Hamiltonoperator H P , dessen Grundzustand die Lösung unseres Problems kodiert. Wenn wir dann unser AQC für eine Zeit weiterentwickeln T so dass seine Energie durch den Hamiltonoperator beschrieben wird

H ( T ) = ( 1 − T / T ) H 0 + ( T / T ) H P
dann befindet sich das System, sofern einige Bedingungen zutreffen, im Grundzustand von H P zum Zeitpunkt T (und voila, wir hätten eine Lösung für unser Problem)

Frage: Wenn wir den AQC einfach so aufstellen, dass seine Energie zunächst durch den Hamilton-Operator beschrieben wird H P , warum würde das System nicht einfach in seinen Grundzustand "fallen" (und sofort eine Lösung für unser Problem codieren)? Warum müssen wir den AQC aus dem anfänglichen Hamilton-Operator weiterentwickeln? H 0 hinein H P ?

Antworten (3)

Die meisten NP-vollständigen Probleme können so formuliert werden, dass man den Grundzustand eines Hamiltonoperators findet. Wenn Sie ein physikalisches System erstellen, das einen solchen Hamilton-Operator hat, wird es ein "frustriertes System". Es wird sich in einen Zustand einpendeln, der ein lokales Minimum der Energie ist, und während die Quantenmechanik sagt, dass es schließlich in den Grundzustand zerfallen wird (vorausgesetzt, es ist nicht isoliert; das heißt, es gibt einen Mechanismus, durch den es Energie verliert). die dafür benötigte Zeit kann leicht um viele Größenordnungen größer sein als die Lebensdauer des Universums.

Wenn Sie den Grundzustand eines beliebigen Problem-Hamiltonoperators berechnen möchten, müssen Sie 1/2^N Zustände durchsuchen. Für N=100 ist das selbst bei massiver Parallelisierung praktisch unmöglich, und selbst das liegt noch Größenordnungen unter industriell anwendbaren Problemgrößen. Natürlich verwenden die besten klassischen Algorithmen Heuristik und Problemstruktur, um die Nachvollziehbarkeit zu verbessern, aber die Hoffnung ist, dass AQC bei einigen Algorithmen zumindest eine polynomiale Beschleunigung bietet und die besten klassischen Algorithmen auf den größten Supercomputern aus dem Wasser bläst ( muss noch nachgewiesen werden).

Ich habe einmal genau die gleiche Frage während eines Kurses über Quantencomputing gestellt. Systeme „fallen“ erst dann in ihren Grundzustand, wenn sie sich bei Nulltemperatur im thermischen Gleichgewicht befinden . Beide Teile sind problematisch: (a) Viele Systeme, die für die Quantenberechnung vorgeschlagen wurden, haben Energieskalen, die niedrig genug sind, dass es äußerst schwierig ist, sie auf ausreichend niedrige Temperaturen zu bringen, und (b) wie Peter Shor betonte, Sie haben keine Ahnung wie lange es dauert, bis das System tatsächlich ein thermisches Gleichgewicht erreicht - Sie könnten ein physikalisches Äquivalent zu einem Monte-Carlo-Vorzeichenproblem haben, bei dem es in der Systemgröße exponentiell lange dauert, bis lokale Störungen Sie in das thermische Gleichgewicht bringen.

Aber wenn Sie den anfänglichen Hamiltonian kontrollieren können H 0 , können Sie das System viel schneller in seinen Grundzustand "zwingen" - im Prinzip durch Messfilterung, aber realistischer durch das Herstellen H 0 unfrustriert und mit einer sehr großen charakteristischen Energieskala. Wenn Sie beispielsweise ein System von Quantenspins haben und ein riesiges einheitliches Feld auf das gesamte System anwenden ("riesig" bedeutet viel größer als die Temperatur und die relevante Spin-Wechselwirkungsskala), dann wird sich das gesamte System sehr an dem Feld ausrichten schnell und Sie können sicher sein, dass Sie sich im Grundzustand befinden.

Es ist eigentlich ziemlich einfach (zumindest theoretisch), Systeme so zu konstruieren, dass (a) kein Problem darstellt. Das große Problem ist (b).
@PeterShor Stimmt, aber ich denke, es gibt auch Systeme, bei denen (a) schwer ist. D-Wave funktioniert ("funktioniert") bei 15 mK, was nicht allzu schwer zu erreichen ist, aber gibt es nicht auch Vorschläge für AQC in kalten Atomsystemen (z. B. arxiv.org/abs/quant-ph/0406144 )? Das müsste auf der Nanokelvin-Skala durchgeführt werden, was viel, viel schwieriger ist als Millikelvin.
@tparker Danke, tolle Antwort. Ist dieses einheitliche Feld (das man auf das System anwendet, um es schneller in den Grundzustand zu bringen) das, was in Quantenglühalgorithmen verwendet wird (z. B. auf den D-Wave-Maschinen)? Und ermöglicht dies das „Tunneln“ zwischen Barrieren, die lokale Minima in Quantenglühalgorithmen trennen?
@AlexMichael Ich kenne die Antwort auf Ihre erste Frage nicht. Ich bin mir nicht sicher, ob ich Ihre zweite Frage verstehe, aber das adiabatische Theorem garantiert, dass sich der Grundzustand des anfänglichen Hamilton-Operators zum Grundzustand des endgültigen Hamilton-Operators entwickelt, solange der Hamilton-Operator viel langsamer variiert wird als die festgelegte Zeitskala durch die Energielücke in den ersten angeregten Zustand, weil das System Energiebarrieren quantentunneln kann, solange es genug Zeit dafür hat. Im Prinzip sind die Details des anfänglichen Hamilton-Operators unwichtig, nur die Größe seiner Energielücke.
Warum kann ich den anfänglichen Hamiltonian H0 zwingen, sich im Grundzustand zu befinden, aber nicht den endgültigen Hamiltonian, sich im Grundzustand zu befinden?
@hii: Der anfängliche Hamiltonian ist einer, der speziell ausgewählt wurde, damit Sie ihn in den Grundzustand zwingen können.
@hii Ja, wie ich oben sagte, die wichtigsten Zutaten, die machen H 0 viel einfacher zu handhaben sind (a) ein nicht frustrierter Grundzustand und (b) eine sehr große Lücke zum ersten angeregten Zustand. Solche Hamiltonoperatoren sind ziemlich einfach zu konstruieren und fallen viel schneller in ihre Grundzustände als der endgültige "Problem"-Hamiltonoperator H P (was normalerweise frustriert und kompliziert zu entwickeln ist).

Sie beginnen in einem Zustand, der dann ein kompliziertes Durcheinander von Eigenzuständen ist. Und Sie haben dem Zerfall keinen Mechanismus gegeben. Eben Evolution mit einem einzigen PS. Sie wissen nur, wie man im Grundzustand von H0 beginnt und sich von dort aus bewegt.

Adiabatisches Quantencomputing: Warum nicht gleich das System in sein Problem Hamiltonian HPHPH_{P} versetzen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v