Generierung einer 715-Qubit-Schaltung und Lösung anderer SAT-Probleme mit Classiq

In dieser Notiz wird beschrieben, wie die Classiq-Plattform zur Lösung von Constraint-Satisfaction-Problemen verwendet werden kann, darunter Kakuro - ein Problem aus unserem jüngsten Coding-Wettbewerb. Dann wird ein viel komplexeres Beispiel demonstriert, das einen Schaltkreis für 715 Qubits erzeugt.

Wir leben in einer eingeschränkten Welt

Probleme der Erfüllbarkeit von Bedingungen (SAT) sind allgegenwärtig. Diese schwierige Klasse von Problemen ist so weitreichend, dass es eine internationale Konferenz gibt, die darauf abzielt, spezifische Fälle zu definieren und zu lösen, mit Anwendungen wie "Formale Verifikation, künstliche Intelligenz, Operations Research, Computerbiologie, Kryptographie, Data Mining, maschinelles Lernen, Mathematik, usw.". In jeder Branche gibt es bestimmte Einschränkungen. Nehmen wir zum Beispiel die Logistik, die für jede Branche mit komplexen, beweglichen Teilen gilt. Das Verpacken von Produkten in einem begrenzten Volumen ist nur ein Beispiel für ein Problem der Erfüllbarkeit von Nebenbedingungen, und es ist leicht vorstellbar, wie schnell diese Probleme unlösbar werden. Ein Mensch kann ein Auto mit Gepäck konfigurieren, und ein Team kann einen Schrank mit Vorräten arrangieren, aber wie lässt sich die Auslastung von Überseecontainern am besten optimieren? Die Quanteninformatik bietet eine quadratische Beschleunigung gegenüber der klassischen Informatik, wenn diese Erfüllbarkeitsprobleme mit dem Grover-Suchalgorithmus definiert und implementiert werden.

Das Kakuro-Rätsel

Ein interessantes Beispiel für ein SAT-Problem ist Kakuro, das ein Problem des Classiq Coding Competition war. Kakuro ist ein Logikrätsel ähnlich wie Sudoku oder ein Kreuzworträtsel. Ziel ist es, die leeren Zellen mit Zahlen zu füllen, so dass der Inhalt jeder Zeile und Spalte eine bestimmte Summe ergibt und keine zwei Zellzahlen in einer Zeile oder Spalte gleich sind. Für den Wettbewerb bestand die Aufgabe darin, das folgende Rätsel mit Hilfe einer Grover-Suche mit den wenigsten CX-Gattern im Orakel zu lösen, nachdem die Schaltung in Ein-Qubit-Unitargatter und CX-Gatter zerlegt wurde.

‍

Wenn man anfängt, dieses Rätsel manuell zu lösen, ist es klar, dass die Spielregeln in boolescher Logik geschrieben werden können, damit ein Orakel sie lösen kann. X5 und X6 müssen sich zu 1 addieren, X4 und X6 müssen sich zu 1 addieren, und so weiter. Nachdem wir einige Überschneidungen zwischen den Regeln festgestellt hatten, definierten wir eine Liste vereinfachter Bedingungen, die diese kodieren, wobei alle Variablen Ein-Qubit-Register sind, außer X3, das zwei Qubits benötigt. Eine Diskussion darüber, wie diese reduziert wurden, ist hier zu finden. Hier sind die Bedingungen, die wir erfüllen müssen.

"(x0 != x1) und" 
"(x2 + 2 != x3) und" 
"(x3 != x4) und" 
"(x1 != x3) und"
"(x3 != x5) und"  
"(x5 != x6) und" 
"(x0 != x2) und"
"(x1 != x5) und" 
"(x4 != x6) und" 
"(x3 == 2) und" 
"(x2 + x4 + x3 == 3)"

Wie man Kakuro mit Classiq löst

In dieser Notiz werden wir die Probleme mit dem Python-SDK von Classiq lösen, obwohl alle Ergebnisse auch mit der Classiq-Erweiterung in Visual Studio Code erzielt werden können. Um dieses Problem mit dem Python-SDK von Classiq zu lösen, definieren Sie einfach die Einschränkungen als Ausdruck innerhalb der eingebauten Arithmetikfunktion. Wir deklarieren unsere Variablen als Einzel-Qubit-Register, mit Ausnahme von X3 als Doppel-Qubit-Register (da es den Wert 0, 1, 2 oder 3 annehmen kann), und wir passen unsere letzte Bedingung entsprechend an. 

from classiq importieren ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic
from classiq.interface.generator.model import Constraints, Voreinstellungen
from classiq.interface.generator.model.preferences.preferences import (
    CustomHardwareSettings,
)

AUSDRUCK = "(x0 != x1) und" + \
             "(x2 + 2 != x3) und" + \
             "(x3 != x4) und " + \
             "(x3 != x1) und " + \
             "(x5 != x6) und" + \
             "(x0 != x2) und" + \
             "(x1 != x5) und" + \
             "(x4 != x6) und" + \
             "(x3 == 2) und" + \
             "(((x2 + x4) + x3)%4 == 3)"


oracle_params = Arithmetic(
    ausdruck=EXPRESSION,
    definitionen=dict(
        x0=RegisterBenutzerEingabe(Größe=1),
        x1=RegisterBenutzereingabe(Größe=1),
        x2=RegisterBenutzereingabe(Größe=1),
        x3=RegisterBenutzereingabe(Größe=2),
        x4=RegisterBenutzereingabe(Größe=1),
        x5=RegisterBenutzereingabe(Größe=1),
        x6=BenutzereingabeRegistrieren(Größe=1)
    ),
    uncomputation_method="naive",
)

‍

Nun legen wir die Hardware-Einstellungen fest und deklarieren unsere Basisgattermenge aus CX- und U-Gattern. Zum Schluss optimieren wir die Anzahl der CX-Gatter und synthetisieren unsere Schaltung.

‍

custom_hardware_settings = CustomHardwareSettings(basis_gates=["cx", "u"])
preferences = Preferences(custom_hardware_settings=custom_hardware_settings)

model_designer = ModelDesigner(constraints=Constraints(optimization_parameter='cx'), preferences=preferences)
model_designer.Arithmetic(params=oracle_params)

Schaltung = model_designer.synthesize()

schaltung.show_interactive()
print(f"{Schaltung.transpilierte_Schaltung.Tiefe=}")
print(f"{Schaltung.transpilierte_Schaltung.count_ops['cx']=}")

‍

Sobald wir diesen Code ausführen, untersucht die Classiq-Synthese-Engine - innerhalb von Sekunden - verschiedene Optimierungstechniken, um eine Schaltung zu erstellen, die die gewünschte Funktionalität erfüllt. Die unten gezeigte interaktive Schaltung finden Sie hier, und unsere resultierende Tiefe und CX-Gatteranzahl folgt.

‍

circuit.transpiled_circuit.depth=197
circuit.transpiled_circuit.count_ops['cx']=190

‍

‍

‍

Um weitere Lösungen zu sehen, die von den Teilnehmern während des einmonatigen Wettbewerbs entwickelt wurden, klicken Sie hier.

Jenseits von Puzzles

Mit der Classiq-Plattform können Sie auch sehr viel anspruchsvollere SAT-Probleme lösen. Es wird vorhergesagt, dass Quantencomputer, die reale Werte erzeugen, Hunderte oder sogar Tausende von Qubits benötigen, und Classiq ist bereit für die massiven Schaltungen der Zukunft. Nehmen Sie den folgenden Codeblock, in dem wir eine 715-Qubit-Schaltung aus einem Orakel mit 10 Variablen und 100 Klauseln synthetisieren.

‍

from classiq importieren ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic

EXPRESSION = "(((x0 oder ~x1 oder ~x8) und (~x7 oder ~x5 oder x6)) und ((~x4 oder ~x3 oder ~x0) und (x0 oder x3 oder x7)) und ((~x5 oder x0 oder ~x2) und (x0 oder ~x7 oder ~x9)) und ((~x5 oder x4 oder x6) und (x4 oder ~x8 oder x9)) und ((x6 oder ~x5 oder ~x7) und (x8 oder ~x6 oder ~x4))) und" + \
             "(((x5 oder ~x3 oder ~x7) und (x7 oder x1 oder ~x4)) und ((~x5 oder ~x6 oder x2) und (~x8 oder ~x0 oder ~x4)) und ((x4 oder ~x8 oder ~x5) und (~x0 oder x6 oder ~x7)) und ((x4 oder x2 oder ~x8) und (~x6 oder ~x9 oder x0)) und ((x9 oder ~x0 oder x7) und (~x7 oder x5 oder ~x9))) und" + \
             "(((x6 oder ~x0 oder ~x9) und (x5 oder ~x8 oder x1)) und ((x3 oder ~x6 oder x2) und (x7 oder ~x5 oder x8)) und ((x8 oder ~x6 oder ~x3) und (x3 oder ~x1 oder x4)) und ((~x3 oder x9 oder ~x4) und (~x8 oder x1 oder ~x4)) und ((~x6 oder x3 oder x9) und (x4 oder x6 oder x3))) und" + \
             "(((~x0 oder x8 oder x5) und (~x6 oder x7 oder ~x4)) und ((x9 oder ~x8 oder ~x4) und (~x4 oder x2 oder ~x0)) und ((x7 oder x6 oder ~x5) und (x7 oder ~x2 oder x8)) und ((x5 oder ~x6 oder ~x7) und (~x2 oder x3 oder ~x0)) und ((x2 oder x3 oder x5) und (~x3 oder x8 oder x5))) und" + \
             "(((x6 oder ~x1 oder ~x9) und (~x0 oder ~x1 oder x4)) und ((x3 oder x7 oder ~x2) und (x4 oder x2 oder ~x0)) und ((~x0 oder ~x5 oder x4) und (~x3 oder ~x7 oder x1)) und ((~x0 oder x3 oder ~x7) und (x9 oder ~x5 oder ~x8)) und ((~x6 oder ~x7 oder x0) und (~x6 oder x1 oder x8))) und" + \
             "(((x8 oder ~x4 oder x1) und (x4 oder x2 oder ~x3)) und ((~x0 oder ~x2 oder ~x5) und (~x0 oder ~x8 oder ~x4)) und ((~x6 oder ~x9 oder ~x0) und (x4 oder x0 oder x9)) und ((x8 oder ~x7 oder x9) und (x0 oder ~x1 oder ~x2)) und ((~x7 oder x2 oder x5) und (x6 oder x8 oder x3))) und" + \
             "(((~x4 oder x6 oder x8) und (x9 oder ~x6 oder ~x4)) und ((~x9 oder ~x6 oder x2) und (~x2 oder x7 oder x6)) und ((x3 oder ~x9 oder x1) und (x8 oder ~x7 oder ~x9)) und ((x2 oder ~x1 oder x0) und (x2 oder x6 oder ~x4)) und ((~x3 oder ~x6 oder ~x8) und (~x0 oder ~x4 oder x2))) und" + \
             "(((x2 oder ~x0 oder x8) und (~x8 oder ~x5 oder ~x9)) und ((x5 oder ~x8 oder ~x9) und (x1 oder ~x3 oder ~x0)) und ((~x6 oder x9 oder x7) und (~x9 oder x1 oder x2)) und ((x0 oder ~x1 oder ~x8) und (x8 oder ~x6 oder x3)) und ((~x8 oder x1 oder ~x2) und (x4 oder ~x1 oder x0))) und" + \
             "(((x9 oder x3 oder ~x0) und (x5 oder ~x9 oder x2)) und ((~x0 oder x5 oder ~x9) und (x1 oder x8 oder ~x5)) und ((~x7 oder ~x0 oder x4) und (~x1 oder x7 oder ~x5)) und ((x8 oder ~x0 oder ~x6) und (~x7 oder x5 oder x9)) und ((x5 oder ~x6 oder ~x8) und (~x6 oder ~x9 oder x3))) und" + \
             "(((~x9 oder ~x1 oder x3) und (x2 oder ~x5 oder ~x6)) und ((~x2 oder x1 oder ~x4) und (x0 oder x8 oder ~x9)) und ((~x4 oder x1 oder x7) und (x8 oder ~x4 oder ~x0)) und ((x1 oder ~x0 oder ~x4) und (~x9 oder x8 oder ~x1)) und ((~x5 oder ~x1 oder x8) und (~x4 oder ~x3 oder x8)))"



oracle_params = Arithmetic(
    ausdruck=EXPRESSION,
    definitionen=dict(
        x0=RegisterBenutzerEingabe(Größe=1),
        x1=RegisterBenutzereingabe(Größe=1),
        x2=RegisterBenutzereingabe(Größe=1),
        x3=RegisterBenutzereingabe(Größe=1),
        x4=RegisterBenutzereingabe(Größe=1),
        x5=BenutzereingabeRegistrieren(Größe=1),
        x6=BenutzereingabeRegistrieren(Größe=1),
        x7=RegisterBenutzereingabe(Größe=1),
        x8=RegisterBenutzereingabe(Größe=1),
        x9=RegisterBenutzereingabe(Größe=1),
    ),
    uncomputation_method="naive",
)

model_designer = ModelDesigner()
model_designer.Arithmetic(params=oracle_params)

Schaltkreis = model_designer.synthesize()

schaltung.show_interactive()

‍

Die mit diesem Code erzeugte interaktive 715-Qubit-Schaltung ist hier zu finden.

‍

Es ist auch nicht schwierig, generierte Schaltungen auf Quanten-Cloud-Diensten einzusetzen. Ein ausführliches Beispiel für die Ausführung eines SAT-Problems, das mit der Classiq-Plattform auf Amazon Braket gelöst wurde, finden Sie zum Beispiel hier. 

Letztendlich werden Quantencomputer nicht nur zum Spielen von Logikrätseln oder zum Ausführen einfacher arithmetischer Berechnungen verwendet werden. Der Vorteil der Quanteninformatik wird von jeder Branche mit großen Datensätzen genutzt werden, indem sie viel schneller als je zuvor sucht (Lösung von SAT-Problemen mit Grovers Algorithmus), Muster erkennt (maschinelles Lernen mit Quanten) und optimiert (hybride klassisch/quantische QAOA). Angesichts der geringen Kosten für die Erforschung der Quantenphysik und der potenziell verheerenden Kosten, wenn man sie ignoriert, ist die Quanteninformatik eine der besten Versicherungspolicen für die Zukunft der Technologie. Ganz gleich, ob Sie an der Erforschung von Quantenanwendungsfällen interessiert sind oder Ihren Quantencode auf ein höheres Niveau bringen wollen, die Classiq-Plattform ist vollgepackt mit integriertem Fachwissen, so dass Sie sich auf die Probleme konzentrieren können, die Sie lösen möchten, während sich unsere Synthese-Engine darauf konzentriert, wie diese Probleme gelöst werden. 

Wenn Sie mehr über Classiq und unsere revolutionäre Software erfahren möchten, kontaktieren Sie uns hier, oder vereinbaren Sie hier einen Termin für eine unverbindliche Demonstration der Plattform.