Générer un circuit de 715 qubits et résoudre d'autres problèmes de SAT avec Classiq

Cette note décrit comment utiliser la plateforme Classiq pour résoudre des problèmes de satisfaction de contraintes, y compris Kakuro - un problème de notre récent concours de codage. Elle présente ensuite un exemple beaucoup plus complexe qui génère un circuit pour 715 qubits.

Nous vivons dans un monde contraint

Les problèmes de satisfiabilité des contraintes (SAT) sont omniprésents. Cette catégorie de problèmes difficiles est si vaste qu'il existe une conférence internationale visant à définir et à résoudre des cas spécifiques, avec des applications telles que "la vérification formelle, l'intelligence artificielle, la recherche opérationnelle, la biologie informatique, la cryptographie, l'exploration de données, l'apprentissage automatique, les mathématiques, etc. Dans chaque secteur d'activité, il existe des contraintes. Prenons l'exemple de la logistique, qui s'applique à toute industrie comportant des éléments mobiles complexes. L'emballage de produits dans un volume limité n'est qu'un exemple de problème de satisfiabilité de contraintes, et il est facile d'imaginer à quelle vitesse ces problèmes deviennent impossibles à résoudre. Un être humain peut configurer une voiture de bagages et une équipe peut ranger un placard de fournitures, mais quelle est la meilleure façon d'optimiser l'utilisation de conteneurs d'expédition transocéaniques ? L'informatique quantique offre une accélération quadratique par rapport à l'informatique classique lorsque ces problèmes de satisfiabilité sont définis et mis en œuvre à l'aide de l'algorithme de recherche de Grover.

L'énigme de Kakuro

Un exemple intéressant de problème SAT est le Kakuro, qui était l'un des problèmes du concours de codage Classiq. Kakuro est un casse-tête logique similaire au Sudoku ou aux mots croisés. Le but est de remplir les cellules vides avec des nombres tels que le contenu de chaque ligne et de chaque colonne s'additionne à une somme spécifiée et qu'il n'y ait pas deux numéros de cellule identiques dans une ligne ou une colonne. Pour le concours, le problème consistait à résoudre l'énigme suivante à l'aide d'une recherche de Grover en utilisant le moins de portes CX possible dans l'oracle après avoir décomposé le circuit en portes unitaires à qubit unique et en portes CX.

‍

Lorsque vous commencez à résoudre manuellement cette énigme, il apparaît clairement que les règles du jeu peuvent être écrites en logique booléenne pour être résolues par un oracle. La somme de X5 et X6 doit être égale à 1, la somme de X4 et X6 doit être égale à 1, et ainsi de suite. Après avoir constaté un certain chevauchement entre les règles, nous avons défini une liste de contraintes simplifiées les codant, toutes les variables étant des registres à qubit unique, à l'exception de X3, qui nécessite deux qubits. Une discussion sur la façon dont ces contraintes ont été réduites peut être trouvée ici. Voici les contraintes que nous devons satisfaire.

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

Comment résoudre Kakuro avec Classiq

Dans cette note, nous allons résoudre des problèmes avec le SDK Python de Classiq, bien que tous les résultats puissent également être obtenus en utilisant l'extension de Classiq dans Visual Studio Code. Afin de résoudre ce problème en utilisant le SDK Python de Classiq, il suffit de définir les contraintes comme une expression dans la fonction Arithmétique intégrée. Nous déclarons nos variables comme des registres à qubit unique, sauf X3 qui est un registre à double qubit (puisqu'il peut prendre la valeur 0, 1, 2 ou 3), et nous ajustons notre dernière contrainte en conséquence. 

from classiq import ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic
from classiq.interface.generator.model import Contraintes, Préférences
from classiq.interface.generator.model.preferences.preferences import (
    CustomHardwareSettings,
)

EXPRESSION = "(x0 != x1) et" + \
             (x2 + 2 != x3) et "(x2 + 2 != x3) et" + \
             (x3 != x4) et " + \N- " (x3 != x1) et " + \N- ".
             (x3 != x1) et " + \N- ".
             "(x5 != x6) et" + \N- "x5 != x6) et" + \
             "(x0 != x2) and" + \N- "x0 != x2) and" + \
             "(x1 != x5) and" + \N- "x1 != x5) and" + \
             "(x4 != x6) and" + \N- "x4 != x6) and" + \
             "(x3 == 2) and" + \
             "(((x2 + x4) + x3)%4 == 3)"


oracle_params = Arithmétique(
    expression=EXPRESSION,
    definitions=dict(
        x0=RegisterUserInput(size=1), x1=RegisterUserInput(size=1),
        x1=Enregistrement de l'entrée utilisateur(taille=1),
        x2=Enregistrement de l'entrée utilisateur(taille=1), x3=Enregistrement de l'entrée utilisateur(taille=1),
        x3=Enregistrement de l'entrée utilisateur (taille=2),
        x4=Enregistrement de l'entrée utilisateur (taille=1),
        x5=Enregistrement de l'entrée utilisateur (taille=1),
        x6=EnregistrerEntréeUtilisateur(taille=1)
    ),
    uncomputation_method="naïf",
)

‍

Nous spécifions maintenant les paramètres matériels, en déclarant notre ensemble de portes de base CX et U. Enfin, nous optimisons le nombre de portes CX et synthétisons notre circuit.

‍

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)

circuit = model_designer.synthesize()

circuit.show_interactive()
print(f"{circuit.transpiled_circuit.depth=}")
print(f"{circuit.transpiled_circuit.count_ops['cx']=}")

‍

Une fois que nous avons exécuté ce code, le moteur de synthèse Classiq explore - en quelques secondes - diverses techniques d'optimisation pour retourner un circuit qui répond à la fonctionnalité souhaitée. Le circuit interactif retourné illustré ci-dessous se trouve ici, et notre profondeur résultante et le nombre de portes CX suivent.

‍

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

‍

‍

‍

Pour découvrir d'autres solutions créées par les concurrents au cours du mois de compétition, cliquez ici.

Au-delà des puzzles

En utilisant la plateforme Classiq, vous pouvez également résoudre des problèmes SAT beaucoup plus sophistiqués. On prévoit que les ordinateurs quantiques produisant une valeur réelle auront besoin de centaines, voire de milliers de qubits, et Classiq est prêt pour les circuits massifs du futur. Prenons le bloc de code suivant dans lequel nous synthétisons un circuit de 715 qubits à partir d'un oracle de 10 variables et 100 clauses.

‍

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

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



oracle_params = Arithmétique(
    expression=EXPRESSION,
    definitions=dict(
        x0=RegisterUserInput(size=1), x1=RegisterUserInput(size=1),
        x1=Enregistrement de l'entrée utilisateur(taille=1),
        x2=Enregistrement de l'entrée utilisateur(taille=1), x3=Enregistrement de l'entrée utilisateur(taille=1),
        x3=Enregistrement de l'entrée de l'utilisateur (taille=1),
        x4=Enregistrement de l'entrée utilisateur (taille=1),
        x5=Enregistrement de l'entrée utilisateur (taille=1),
        x6=Enregistrement de l'entrée utilisateur (taille=1),
        x7=Enregistrement de l'entrée utilisateur (taille=1),
        x8=Enregistrement de l'entrée utilisateur (taille=1),
        x9=EnregistrerEntréeUtilisateur(taille=1),
    ),
    uncomputation_method="naïf",
)

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

circuit = model_designer.synthesize()

circuit.show_interactive()

‍

Le circuit interactif de 715 qubits généré avec ce code est disponible ici.

‍

Il n'est pas non plus difficile de déployer les circuits générés sur des services de cloud quantique. Par exemple, vous pouvez voir un exemple approfondi d'exécution d'un problème SAT résolu avec la plateforme Classiq sur Amazon Braket ici. 

En fin de compte, les ordinateurs quantiques ne seront pas utilisés uniquement pour jouer à des puzzles logiques ou effectuer de simples opérations arithmétiques. L'avantage offert par l'informatique quantique sera exploité par toute industrie disposant de grands ensembles de données en effectuant des recherches (résolution de problèmes SAT avec l'algorithme de Grover), en reconnaissant des modèles (apprentissage automatique quantique) et en optimisant ( QAOA hybride classique/quantique) beaucoup plus rapidement qu'auparavant. Avec le faible coût de l'exploration quantique et le coût potentiellement dévastateur de son ignorance, l'informatique quantique est l'une des meilleures polices d'assurance pour l'avenir de la technologie. Que vous soyez intéressé par l'exploration des cas d'utilisation quantiques ou que vous soyez prêt à amener votre code quantique à un niveau supérieur, la plateforme Classiq est remplie d'expertise intégrée, vous permettant de vous concentrer sur les problèmes que vous aimeriez résoudre, tandis que notre moteur de synthèse se concentre sur la façon dont ces problèmes seront résolus. 

Pour en savoir plus sur Classiq et notre logiciel révolutionnaire, contactez-nous ici, ou planifiez votre démonstration sans engagement de la plateforme ici.