Die CLASSIQ Engine: Ich KANN eine gewisse Befriedigung erlangen

Haben Sie schon einmal ein Sudoku-Rätsel gelöst? Irgendwann in den frühen 2000er Jahren war es ziemlich beliebt. Aus irgendeinem Grund löste es jeder ständig. Wohlgemerkt, das war eine Zeit lange vor Smartphones. Die Leute hatten einfach nichts Besseres zu tun. Falls Sie noch nie davon gehört haben: Bei einem Sudoku besteht das Ziel darin, ein 9X9-Gitter so mit Ziffern zu füllen, dass in jeder Zeile und jeder Spalte jede Ziffer nur einmal vorkommt. Diese Art von Rätsel ist ein Beispiel für ein Constraint Satisfaction Problem (CSP). Dabei handelt es sich um Probleme, bei denen man die Lücken mit einem Element (z. B. einer Ziffer) aus einer Reihe von Möglichkeiten (z. B. den Ziffern 1 bis 9) füllen muss, dabei aber nicht gegen eine Reihe von Regeln verstoßen darf (z. B. keine Wiederholung einer Ziffer).
Die Klasse der CSP hat andere, wohl interessantere Beispiele in Form von Spielen (jedes Kreuzworträtsel), Mathematik (Kartenfärbung[https://en.wikipedia.org/wiki/Four_color_theorem]) und so weiter. Es gibt jedoch einen Grund, warum diese ganze Sache für uns wichtig ist, und zwar nicht, weil wir ein mathematisches Theorem beweisen wollen. Es ist viel praktischer als das. Zumindest wenn man sich mit der Entwicklung von Quantenalgorithmen beschäftigt.

Optimierung von Quantenschaltungen

Es gibt nichts umsonst, aber es ist schön, das beste Ergebnis für sein Geld zu bekommen. Das ist der Sinn von Optimierungstechniken: herauszufinden, wie man eine bestimmte Problemmetrik maximieren (oder minimieren) kann. Es gibt viele Arten von Problemen dieser Art. Manchmal nimmt das, was Sie zu optimieren versuchen, kontinuierliche Werte an, während diese Werte in anderen Fällen diskret sind. Ihr Optimierungsraum kann entweder endlich oder unendlich sein, und er kann auch auf verschiedene Weise variieren. In CSPs gibt es eine Reihe von Beschränkungen, die alle so gut wie möglich erfüllt werden sollen. Diese Unterklasse von CSPs kann als CSOP bezeichnet werden, wobei "O" für "Optimization" steht.
Wir wollen einen Quantenalgorithmus entwerfen und unsere Bausteine "high-level" machen. Wir wollen also mit etwas anderem arbeiten als mit einzelnen Quantengattern. Stattdessen möchten wir einen Funktionsaufruf verwenden, der dann in die richtige Gatterfolge umgewandelt wird. Dieser Schritt, bei dem Funktionsaufrufe auf hoher Ebene durch Gattersequenzen ersetzt werden, wird als Synthese bezeichnet. Das ist nicht das Einzige, was hier passiert, aber der Einfachheit halber wollen wir nur einen Aspekt betrachten. Bei der Synthese sind wir hauptsächlich durch die Quantenhardware eingeschränkt. Wir haben eine endliche Anzahl von Qubits zur Verfügung, eine Obergrenze für die Schaltungstiefe, die wir ausführen können, bevor uns das Rauschen überwältigt, und so weiter.
Das Spiel, das uns bleibt, ist das folgende: Weisen Sie den Funktionen die Ressourcen (Anzahl der Qubits, Schaltungstiefe usw.) so zu, dass sie die vorgegebenen Beschränkungen optimal erfüllen.

Ziele erreichen, aber der Boden ist in Bewegung

In einem einfachen Fall ist jeder Funktionsaufruf eine "Maske", die durch eine feste Gatterfolge ersetzt werden kann. Man setzt diese Sequenzen hintereinander und erhält eine Schaltung. Das wäre langweilig und böte wenig Spielraum für die Synthese. In diesem Fall bestimmt die Abfolge der Funktionsaufrufe eindeutig die resultierende Schaltung. Glücklicherweise geschieht hier etwas viel Interessanteres und Schwierigeres.
Dieses Problem ist interessanter, als Sie vielleicht annehmen, weil es für einige Funktionen mehr als eine korrekte Implementierung gibt. Unterschiedliche Implementierungen kommen aus verschiedenen Gründen zustande. Ein Beispiel sind hardwareabhängige Implementierungen. Diese entstehen aufgrund unterschiedlicher nativer Gattersätze in Quantenprozessoren mit eingeschlossenen Ionen im Vergleich zu denen von Quantenprozessoren mit neutralen Atomen (oder anderen Qubit-Typen). Ein weiterer Grund ist die Konnektivitätskarte von Qubits. Diese Karten legen fest, auf welchen Qubit-Paaren bedingte Operationen ausgeführt werden können, und sie variieren zwischen den Qubit-Chip-Architekturen (sogar für einen bestimmten Qubit-Typ).
Mehrere Implementierungen sind jedoch nicht nur auf Unterschiede in der Hardware zurückzuführen. Ein Beispiel ist die Addierschaltung. Dieses Schaltungselement ermöglicht die Addition von Zahlen, die durch verschiedene Register (Sätze von Qubits) dargestellt werden. Dies ist ein grundlegender Bestandteil eines jeden Computers, auch eines klassischen Computers. Er ist für Quantenberechnungen ebenso wertvoll. Für die Implementierung dieses Elements gibt es mehr als eine Darstellung als Quantenlogikgatter. Der Zweck des Addierers kann durch eine Ripple-Carry-Schaltung(https://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-Carry_adder) oder durch die Verwendung der Quanten-Fourier-Transformation (siehe dieses Papier: https://arxiv.org/pdf/1411.5949.pdf) erreicht werden. Die verschiedenen Implementierungen haben unterschiedliche Eigenschaften in Bezug auf die Anzahl der verwendeten Qubits, die Schaltungstiefe, die Anzahl der durchgeführten Zwei-Qubit-Operationen und so weiter.

Reduzieren, Wiederverwenden, Recyceln

Ressourcen sind in der Datenverarbeitung knapp, egal ob es sich um Quantencomputer oder andere handelt. Wenn man keine wirklich einfachen Probleme löst, stößt man in der Regel an eine von zwei Grenzen. Man hat entweder nicht genug Geschwindigkeit oder nicht genug Platz. Oft kann man eines dieser Probleme in das andere umwandeln, aber nur manchmal, und das hilft auch nur manchmal.
Aus diesem Grund ist die Entwicklung von Methoden zur sparsamen Nutzung von Ressourcen eine alte (und notwendige) Tradition in der Informatik. Eine effiziente Speicherverwaltung oder Garbage Collection ist unerlässlich und ermöglicht es Programmen, immer wieder dieselben Teile des physischen Speicherplatzes in einem Programm wiederzuverwenden. Die Automatisierung dieser Aufgaben ist die Domäne der Software für die Automatisierung des elektronischen Designs (EDA), die eine Inspirationsquelle für die CLASSIQ-Engine war.

Bei der Synthese von Quantenprogrammen ist ein besonders kniffliges Puzzleteil die Frage, was mit den Hilfs-Qubits geschehen soll. Konzentrieren wir uns wieder darauf, was die Synthese-Engine zu tun hat.
Die Engine wählt eine Implementierung der High-Level-Funktion aus und "verbindet" sie dann mit der folgenden Funktionsimplementierung. Wenn diese Funktion ein Hilfs-Qubit (oder Qubits) hat, d. h. ein Qubit, das verwendet wurde und jetzt irrelevant ist, kann es von einer anderen Funktion wiederverwendet werden. Wenn es nicht wiederverwendet werden kann und die nachfolgende Funktion ebenfalls ein Hilfs-Qubit benötigt, müssen wir dieser Funktion ein neues Qubit zuweisen (das wir möglicherweise nicht zur Hand haben!).
Diese Wiederverwendung von Hilfs-Qubits macht das Problem der Befriedigung von Nebenbedingungen (und der Optimierung), das wir zu lösen versuchen, in gewissem Sinne "nicht-lokal". Was wäre, wenn ich durch die Wahl einer Implementierung (und der Verdrahtung der Hilfsqubits) zu Beginn der Schaltung, die mir zu diesem Zeitpunkt als eine gute Idee erschien, gezwungen wäre, später eine weniger geeignete Implementierung zu wählen? Eine, die insgesamt schlechter für die Optimierung meines Ziels ist? Man trifft eine Entscheidung, und das Endziel bewegt sich in die eine oder andere Richtung, so dass man seine Entscheidungen neu bewerten und im Nachhinein ändern muss. Wenn man im wirklichen Leben nur solche Freiheiten hätte.

Einfache Strategien für den Erfolg

Es gibt viele Möglichkeiten, Funktionen anzuordnen und den einzelnen Funktionen Ressourcen zuzuweisen. Die Anzahl skaliert exponentiell mit der Anzahl der Funktionen, wie es bei Quantensachen üblich ist. Das bedeutet, dass Sie das Problem mit einem Brute-Force-Ansatz nicht lösen können, wenn Sie viele Funktionsaufrufe haben, es sei denn, Sie haben (vielleicht) bereits einen funktionierenden Quantencomputer, der die Suche durch die Möglichkeiten effizient beschleunigt. Man müsste sie immer noch irgendwie speichern, so dass selbst ein Quantencomputer möglicherweise nicht ausreicht!

Es gibt viele Möglichkeiten, dieses schwierige Problem zu lösen. Der erste Ansatz, der zwar langsam, aber zumindest methodisch ist, besteht in Backtracking-Algorithmen(https://en.wikipedia.org/wiki/Backtracking). Dies ist eine inkrementelle (rekursive) Methode, um den Schaltkreis Schicht für Schicht aufzubauen. Um dies zu verbessern, gibt es bessere Algorithmen, die teilweise auf cleveren Heuristiken beruhen. Wir werden in zukünftigen Blogbeiträgen mehr über solche Techniken berichten.

Wie geht es weiter?

Heute haben wir einen kleinen Einblick in die Welt der CSP bekommen und wie sie auf das Problem der Quantenalgorithmus-Schaltungssynthese angewendet wird. Oder, wie wir es bei CLASSIQ nennen: Brot und Butter.
Wir haben gelernt, wie das Problem aufgebaut ist und was man naiverweise tun könnte, um es in Angriff zu nehmen. Aber die CLASSIQ-Engine geht mit diesen Ideen noch viel weiter. Neben der Anwendung komplizierterer und cleverer Methoden zur schnellen und effizienten Auswahl von Blockimplementierungen gibt es Erweiterungen des Problems aufgrund der besonderen Herausforderungen, die sich aus der Quantennatur der Schaltungen ergeben, die wir aufbauen müssen.
Wie würde man einen CSOP lösen, wenn man Messungen in der Mitte der Schaltung durchführen kann? Wie sollten Überlegungen wie kohärentes und inkohärentes Rauschen in eine Synthese-Engine integriert werden? Wie kann die Informationsverarbeitung in einem hybriden klassisch-quantischen Berechnungsablauf zur Ausführungszeit in die Schaltungssynthese oder Re-Synthese einfließen? Dies sind alles schwierige und faszinierende Fragen. In künftigen Beiträgen werden wir tiefer in die Welt der Schaltungssynthese und die damit verbundenen algorithmischen Herausforderungen eintauchen.