Résolution d'un problème SAT de père Noël secret avec Classiq
Bienvenue sur le troisième blog de cette série consacrée à la résolution d'un problème de Père Noël secret à l'aide d'ordinateurs quantiques.
Cette année, je veux montrer à quel point il est facile de générer du code Q# pour résoudre le problème en utilisant la plateforme Classiq.
Ce blog fait partie du calendrier des vacances Q# 2022.
Voyons d'abord quel était le problème.
Trois personnes ou plus veulent jouer au Père Noël secret. Chacun inscrit son nom sur un papier, et tous les papiers sont mis dans un bol. Après avoir mélangé les papiers, chaque joueur choisit un papier et, comme personne n'a son propre nom, chaque joueur a un nom pour lequel il doit acheter un cadeau et/ou écrire un poème.
Ceci peut être facilement visualisé à l'aide de ce tableau, dans ce cas nous avons 3 joueurs.
Dans ce cas, si X1 = 1, Vincent doit acheter un cadeau à Shai.
Pour répondre à ce problème, vous devez avoir exactement une valeur dans chaque ligne et dans chaque colonne. Nous pouvons écrire ce problème sous la forme d'un problème SAT comme suit :
Pour une description plus détaillée, consultez mon premier article de blog ici.
Introduire Classiq
Classiq permet aux utilisateurs finaux de générer des circuits quantiques logiques efficaces à partir d'un langage de haut niveau. Nous pouvons utiliser la plateforme Classiq pour générer un circuit qui peut résoudre ce défi, sans penser aux qubits ou à la programmation à base de portes de bas niveau. Nous pouvons utiliser soit le SDK Python, que nous utiliserons ci-dessous, soit un modèle textuel pour créer ces circuits quantiques logiques.
Voyons comment nous pouvons le faire.
Commençons par créer la formule SAT sous la forme d'une chaîne Python :
Ensuite, créons un Oracle arithmétique pour résoudre le problème SAT :
Ce que nous voyons ici, c'est que nous avons d'abord fixé la taille du registre à 1, ce qui signifie que chaque variable ne peut prendre que la valeur 1 ou 0. Ensuite, nous chargeons la formule dans l'ArithmeticOracle.
Pour créer un circuit à partir de cela, nous allons passer cet oracle au moteur de synthèse de Classiq comme ceci :
Il se passe plusieurs choses ici, alors passons en revue chacune d'entre elles :
- Tout d'abord, nous définissons un paramètre d'optimisation. Ce paramètre indique au moteur de synthèse de créer le circuit qui utilise le moins de qubits.
- Deuxièmement, nous transmettons les spécifications du backend au moteur de synthèse. Cela permet de s'assurer que nous n'utilisons pas plus de qubits que le dispositif n'en possède. Le dispositif que nous avons choisi ici est le dispositif Ionq.qpu dans Azure Quantum. Nous allons également optimiser le circuit en prenant en compte le jeu de portes supporté en natif et la topologie du QPU. Ici, nous spécifions également le format de sortie, en disant que nous voulons obtenir du code Q# en sortie.
- Ensuite, nous ajoutons l'oracle à notre instance ModelDesiger.
- Enfin, nous créons le circuit en fonction de la fonctionnalité, de l'oracle et des contraintes/préférences.
Jetons un coup d'œil à l'Oracle après l'exécution du moteur de synthèse qui est généré ci-dessous ou ici.
Maintenant que nous avons l'oracle, nous voulons également jeter un coup d'œil au code Q# pour cet oracle.
Avec 'circuit.qsharp' nous pouvons obtenir le code Q# généré, disponible ici.
Maintenant que tout est en place, il est temps d'exécuter le programme, ce qui peut se faire de la manière suivante :
Maintenant vous êtes curieux de savoir qui doit offrir un cadeau à qui, alors voici le résultat que vous pouvez trouver avec 'res.result':
Ce qui signifie que Vincent offrira un cadeau à Simon, Shai offrira un cadeau à Vincent et enfin, Simon offrira un cadeau à Shai.
Cela montre à quel point il est facile de générer et d'exécuter du code Q# fonctionnel dans le monde réel en utilisant la plateforme Classiq.