Quantenglühen

Quantenglühen. Quantum Annealing (QA) ist ein Optimierungsprozess zum Finden des globalen Minimums einer gegebenen Zielfunktion über einen gegebenen Satz von Kandidatenlösungen (Kandidatenzustände) durch einen Prozess, der Quantenfluktuationen nutzt. Quantenglühen wird hauptsächlich für Probleme verwendet, bei denen der Suchraum diskret ist (kombinatorische Optimierungsprobleme) mit vielen lokalen Minima, wie zum Beispiel das Finden des Grundzustands eines Spinglases oder das Lösen von QUBO-Problemen, die eine breite Palette von Problemen wie Max-Cut, Graphfärbung, SAT oder das Problem des Handlungsreisenden kodieren können. Der Begriff „Quantum Annealing“ wurde erstmals 1988 von B. Apolloni, N. Cesa Bianchi und D. De Falco als quanteninspirierter klassischer Algorithmus vorgeschlagen. In seiner jetzigen Form wurde es 1998 von T. Kadowaki und H. Nishimori (ja) formuliert, obwohl eine imaginäre Zeitvariante ohne Quantenkohärenz 1994 von A. B. Finnila, M. A. Gomez, C. Sebenik und J. D. Doll diskutiert wurde.

Theoretischer Kontext

Quantum Annealing geht von einer quantenmechanischen Überlagerung aller möglichen Zustände (Kandidatenzustände) mit gleichen Gewichten aus. Dann entwickelt sich das System nach der zeitabhängigen Schrödinger-Gleichung, einer natürlichen quantenmechanischen Entwicklung physikalischer Systeme. Die Amplituden aller Kandidatenzustände ändern sich ständig und realisieren eine Quantenparallelität entsprechend der zeitabhängigen Stärke des Transversalfelds, was zu Quantentunneln zwischen Zuständen oder im Wesentlichen zum Tunneln durch Spitzen führt. Wenn die Änderungsrate des transversalen Feldes langsam genug ist, bleibt das System nahe am Grundzustand des momentanen Hamilton-Operators (siehe auch adiabatische Quantenberechnung). Wenn die Änderungsrate des Querfelds beschleunigt wird, verlässt das System möglicherweise vorübergehend den Grundzustand, erzeugt jedoch eine höhere Wahrscheinlichkeit, im Grundzustand des endgültigen Hamilton-Problems, d. h. der diabatischen Quantenberechnung, zu landen. Das Transversalfeld wird schließlich ausgeschaltet und das System dürfte den Grundzustand des klassischen Ising-Modells erreicht haben, der der Lösung des ursprünglichen Optimierungsproblems entspricht. Unmittelbar nach dem ersten theoretischen Vorschlag wurde über eine experimentelle Demonstration des Erfolgs des Quantenglühens für Zufallsmagnete berichtet. Es hat sich auch gezeigt, dass Quantenglühen ein schnelles Grover-Orakel für die Quadratwurzelbeschleunigung bei der Lösung vieler NP-vollständiger Probleme darstellt.