Die Classiq Engine II: Electric Boogaloo (oder: Wie man eine Nadel im Heuhaufen sucht)

In unserem letzten Blog-Beitrag über die Classiq-Engine haben wir erklärt, was die Engine tut, und einen kleinen Einblick in ihre Funktionsweise gegeben, nämlich den Backtracking-Algorithmus.
Diesmal tauchen wir tief in die Welt des Lösens von CSPs (Constraint Satisfaction Problems) ein. Der Backtracking-Algorithmus ist eine sehr einfache Methode zur Lösung von CSPs, aber er erfordert die Durchsuchung des gesamten Suchraums. Bei den meisten CSPs ist dies inakzeptabel - der Suchraum ist einfach zu groß (im besten Fall exponentiell). Gehen wir noch einmal auf das im vorigen Beitrag erwähnte Sudoku-Beispiel ein. Es gibt 9^81 Möglichkeiten, ein Sudoku-Feld auszufüllen. Das entspricht etwas weniger als 2e77 (das ist 2 gefolgt von 77 Nullen). Selbst wenn wir ein einfaches Beispiel betrachten, bei dem die Hälfte der Quadrate bereits ausgefüllt ist, haben wir etwa 1,5e38 mögliche Optionen. Sie alle zu durchsuchen, würde einfach zu lange dauern.
In diesem Beitrag werden wir erklären, wie wir den Backtracking-Algorithmus verbessern können, oder anders gesagt, wie Sie effizient nach einer Nadel im Heuhaufen suchen können.

Am Anfang

Das Wort "Backtracking" wird in diesem Beitrag noch oft erwähnt werden, aber wir haben noch nicht einmal gesagt, was es bedeutet.
CSPs sind definiert als eine Menge von Variablen, jede mit einer Domäne gültiger Werte, und eine Menge von Beschränkungen für die Zuweisungen zu diesen Variablen. Eine gültige Lösung ist eine Zuordnung von Werten zu allen Variablen, so dass alle Beschränkungen erfüllt sind.
Der Backtracking-Algorithmus versucht, eine gültige Lösung schrittweise aufzubauen, indem er jeder Variablen nacheinander einen Wert zuordnet. Nach jeder Zuweisung kann überprüft werden, ob die Nebenbedingungen erfüllt sind (zumindest für einige der Bedingungen). Wenn eine Bedingung nicht mehr erfüllt werden kann, ist die aktuelle Teillösung eine Sackgasse. Also gehen wir zurück - wir weisen der zuletzt zugewiesenen Variablen einen anderen Wert zu. Wenn es keine gültigen Werte mehr gibt, gehen wir weiter zurück (=backtrack), zur vorherigen Variablen, und weisen ihr erneut einen Wert zu.
Wenn wir einen Zustand erreichen, in dem alle Variablen zugewiesen und alle Randbedingungen erfüllt sind, haben wir eine gültige Lösung gefunden! Wenn wir hingegen alle Möglichkeiten ausschöpfen, bedeutet das, dass es überhaupt keine gültigen Lösungen gibt.
Wenn Sie gut aufgepasst haben, ist Ihnen vielleicht aufgefallen, dass der Algorithmus bereits etwas ziemlich Schlaues tut: Er hält in dem Moment an, in dem er erkennt, dass eine Bedingung nicht mehr erfüllbar ist.
Ich weiß, das klingt trivial. Wenn Sie ein Sudoku lösen und einen Fehler finden, versuchen Sie sofort, ihn zu beheben, anstatt weiter zu lösen. Aber schon diese einfache Sache reduziert die Größe des Suchraums erheblich - man braucht nicht weiter zu suchen, wenn man im Voraus sagen kann, dass die Suche vergeblich ist. Wir werden später auf diesen Gedanken zurückkommen.
Ich möchte auch darauf hinweisen, dass viele "intelligente" Dinge, die wir beim Backtracking tun, trivial klingen mögen. Das liegt daran, dass eine Möglichkeit, auf sie zu kommen, darin besteht, den Denkprozess im Kopf von jemandem nachzuvollziehen, der das gleiche Problem manuell löst. Unser Gehirn ist immer noch der beste Computer, den es ^gibt1.

Geordnete Suche

Versuchen wir also, den Denkprozess einer Person nachzuahmen, die ein Sudoku löst, und sehen wir, wohin er uns führt. Nehmen wir ein teilweise gefülltes Sudoku-Brett. Wo werden Sie nach dem nächsten zu füllenden Feld suchen? Schauen Sie auf die leere Spalte oder auf eine Spalte mit 5 Zahlen, die eine Reihe mit 4 Zahlen kreuzt? Natürlich ist es letzteres. Wenn Sie ein Sudoku lösen, suchen Sie natürlich nach Bereichen mit vielen Hinweisen (d. h. ausgefüllten Feldern). Sagen wir also unserem Computer, dass er das auch tun soll!
Beim Lösen von CSPs nennt man dies Ordnungsheuristik. Bei der Beschreibung des Backtracking-Algorithmus habe ich (implizit) zwei Fälle erwähnt, in denen der Algorithmus Entscheidungen trifft: die Entscheidung, welche Variable als nächstes zugewiesen werden soll, und die Entscheidung, welcher Wert ihr zugewiesen werden soll. Wie trifft er diese Entscheidungen? Nun, das liegt an uns. Wir können Heuristiken implementieren, die ihm helfen, die richtige Entscheidung zu treffen. Beachten Sie, dass die Heuristiken nicht garantieren, dass wir sofort eine gültige Lösung finden werden. Sie implementieren normalerweise einen gierigen Ansatz zur Lösung des Problems, der es wahrscheinlicher macht, dass wir früher eine gültige Lösung finden, während der Backtracking-Algorithmus sicherstellt, dass wir immer noch alle Möglichkeiten durchgehen.
Unser Sudoku-Beispiel kann als eine Variation der Heuristik der am wenigsten verbleibenden Werte (LRV) betrachtet werden, die besagt, dass wir versuchen, der Variablen mit der geringsten Anzahl verbleibender gültiger Werte einen Wert zuzuweisen. Diese Variablen werden wahrscheinlich eine Herausforderung darstellen, daher ist es gut, sich frühzeitig mit ihnen zu befassen.
Wir haben heute noch nicht über Quantenschaltungen gesprochen. Wie im vorherigen Beitrag erwähnt, weist die Classiq-Engine den verschiedenen Funktionen im Schaltkreis Ressourcen zu. In welcher Reihenfolge sollte sie die Ressourcen zuweisen? Eine natürliche Antwort ist die topologische Ordnung des Schaltkreises, d. h., wenn eine Funktion vor einer anderen ausgeführt werden muss, dann sollten wir ihre Ressourcen früher zuweisen. Es ist zwar nicht notwendig, die Ressourcen in dieser Reihenfolge zuzuweisen, aber es macht es für die Maschine einfacher, Situationen zu erkennen, in denen die Einschränkungen nicht mehr erfüllt werden können, und ist daher eine gute Heuristik.
Was passiert, wenn zwei Funktionen in beliebiger Reihenfolge angewendet werden können? Hier gibt es nicht unbedingt eine natürliche Antwort. Wir können jedoch auf eine andere beliebte Heuristik zurückgreifen: die Heuristik der einschränkendsten Variablen (MCV), die besagt, dass wir die Variable wählen, die die meisten Einschränkungen für die übrigen Variablen mit sich bringt. In diesem Fall wäre das die Funktion, die die meisten Ressourcen erfordert.
Wie sieht es mit der Bestimmung der Werteordnung aus? Eine gängige Heuristik dafür ist die Heuristik des am wenigsten einschränkenden Wertes (Least Constraining Value, ^LCV2): Wählen Sie den Wert, der, wenn er der Variablen zugewiesen wird, die wenigsten Werte für andere Variablen ausschließt. Wenn wir zum Beispiel versuchen, einen Schaltkreis mit einer begrenzten Anzahl von Qubits zu synthetisieren, werden wir zuerst versuchen, den Funktionen weniger Qubits zuzuweisen (so dass die nächsten Funktionen mehr Qubits für sie haben). Auch dies mag sich für uns trivial anhören, aber der Algorithmus wüsste nicht, wie er das machen soll, wenn wir ihm nicht ausdrücklich sagen, dass er das tun soll.

Der frühe Vogel fängt den Wurm

Ich habe bereits erwähnt, dass wir die Suche stoppen wollen, sobald auch nur eine einzige Bedingung nicht mehr erfüllbar ist. Wir können diese Idee noch viel weiter ausbauen. Manchmal ist es einfach zu erkennen, dass eine Bedingung nicht erfüllbar ist, z. B. wenn man eine Spalte mit allen Zahlen von 1 bis 8 ausgefüllt hat, aber die Zeile des letzten verbleibenden Quadrats bereits eine 9 enthält. Aber manchmal muss man etwas tiefer schauen. Vielleicht gibt es noch 3 verbleibende Quadrate in einer Spalte, aber zwei der fehlenden Zahlen müssen im selben Quadrat stehen. Das springt nicht sofort ins Auge, aber mit etwas Nachdenken kann man herausfinden, dass diese Bedingung nicht erfüllbar ist.
Es gibt verschiedene Möglichkeiten, solche Ideen beim Lösen von CSPs umzusetzen. Die erste, die wir besprechen werden, ist die Vorwärtsprüfung. Bei der Vorwärtsprüfung werden wir die verbleibenden gültigen Werte für jede Variable verfolgen (beachten Sie, dass dies auch für die Implementierung der zuvor erwähnten Ordnungsheuristiken verwendet werden kann). Wenn Sie jemals ein Sudoku lösen mussten und alle möglichen Werte in die Ecken der Quadrate geschrieben haben, dann ist das genau das.
Nach jeder Zuweisung gehen wir die verbleibenden gültigen Werte durch und entfernen jeden Wert, der nicht mehr gültig ist (indem wir die entsprechenden Einschränkungen überprüfen). Wenn kein gültiger Wert mehr übrig ist, können wir sofort zurückgehen - diese Zuweisung kann uns nicht zu einer gültigen Lösung führen.
Aber diese Methode reicht für das obige Beispiel nicht ganz aus - alle Quadrate werden mindestens einen gültigen Wert haben. Wir müssen etwas Anspruchsvolleres tun. Wir brauchen Bogenkonsistenz.
Bogenkonsistenz betrachtet Paare von Variablen, die Teil der gleichen Bedingung sind, und nicht einzelne Variablen. Um sicherzugehen, dass ein Wert gültig ist, prüfen wir, ob es einen gültigen Wert der anderen Variablen gibt, der mit ihr gepaart werden kann, um ihre gemeinsame Bedingung zu erfüllen. Wenn wir keinen finden können, dann ist dieser Wert sicher ungültig: Wenn wir ihn wählen, erfüllen wir die gemeinsame Bedingung nicht.
Das wird langsam verwirrend, nicht wahr? Manchmal erfordern die trivialen Dinge, die wir in unserem Kopf tun, einige Arbeit, um sie in einen Algorithmus zu übertragen. Und das ist noch nicht einmal das Ende: Pfadkonsistenz betrachtet Triplets von Variablen, während k-Konsistenz k-Tupel von Variablen betrachtet! Diese sind ziemlich kompliziert, aber die Prämisse bleibt dieselbe: Je früher wir feststellen, dass diese Teillösung eine Sackgasse ist, desto besser.

Wann ist es das wert?

Alle bisher diskutierten Methoden erfordern nicht-triviale Berechnungen. Kann deren wiederholte Durchführung in der Mitte einer bereits sehr langen Suche zu Laufzeiteinbußen führen? Im schlimmsten Fall lautet die Antwort: Ja. Man könnte wahrscheinlich einen Grenzfall konstruieren, in dem alle Berechnungen nutzlos sind, und der Algorithmus könnte genauso gut alle möglichen Lösungen in einer zufälligen Reihenfolge ausprobiert haben. Aber in der Praxis ist es fast immer von Vorteil, diese zusätzlichen Berechnungen durchzuführen. Die Probleme, mit denen wir es beim Lösen von CSPs zu tun haben, sind bestenfalls exponentiell groß, und daher ist jeder Unterraum, den wir nicht durchsuchen müssen, ein großer Vorteil. Wenn unsere Berechnungen polynomiell sind, ist es immer besser, sie über eine umfangreichere Suche durchzuführen.

Ist es das?

Nein.

Bei CSP-Lösern gibt es nie ein Ende. Sie können immer neue Heuristiken finden oder Ihre Implementierung verbessern, um die Laufzeit um ein paar Prozent zu verkürzen. Es gibt auch noch komplexere Techniken, wie Backjumping oder Constraint Learning.
Es ist ein ständiger Wettlauf um Verbesserungen, damit die Classiq-Engine komplexere Schaltungen noch schneller synthetisieren kann.

‍

1 Das ist eigentlich etwas, was ich Leuten, die neu im Programmieren sind, immer sage: Computer sind ziemlich dumm, sie machen einfach genau das, was man ihnen sagt. Der einzige Grund, warum wir sie benutzen, ist, dass sie es viel schneller machen als Menschen. Backtracking ist ein gutes Beispiel dafür.

² LRV, MCV und LCV. Ja, Akronyme in der Informatik können verdammt verwirrend sein.