Kubernetes mac os x, voici des explications pour installer facilement kubernetes sur son mac.
Kubernetes, ou k8s, est une plate-forme open source, lancée par Google, qui a commencé comme un simple outil d’orchestration de conteneurs mais est devenue une plate-forme native pour le cloud.
Introduction – installer kubernetes mac
Sur mac os x une des méthodes les plus rapide pour installer Kubernetes est d’utiliser HoweBrew (voir le lien : Homebrew). Homebrew est un système de gestion de progiciels gratuit et open source qui simplifie l’installation de logiciels sur le système d’exploitation mac OS x Apple.
J’ai démarrer une console et executé la commande :
brew install kubectl
Vous devriez obtenir une sortie du type :
==> Pouring kubernetes-cli-1.20.2.catalina.bottle.tar.gz
==> Caveats
zsh completions have been installed to:
/usr/local/share/zsh/site-functions
==> Summary
🍺 /usr/local/Cellar/kubernetes-cli/1.20.2: 246 files, 46.1MB
A la fin de l’installation vous pouvez vérifier que kubernetees est bien installer :
Je rappelle ici quelques concepts que nous allons utiliser dans notre algorithme de tri quantique, aussi je vous conseille de consulter le site IBM Qiskit pour en savoir plus sur le qiskit textbook https://qiskit.org.
Circuits dans Qiskit :
Le principe en algorithme quantique est de manipuler des qubits, le processus peut être représenté sous forme de circuit (entrées à gauche, sortie à droite). Nous pouvons effectuer différentes opérations au moyen de portes quantiques (qui agissent sur les qubits de manière similaire en algorithme classique aux portes logiques comme ET, OU, OU Exclusif …).
Dans cet article je vais m’appuyer sur Qiskit qui est le framework IBM pour l’informatique quantique.
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(2, 'qubit')
creg_classic = ClassicalRegister(2, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.x(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
circuit.measure(qreg_qubit[1], creg_classic[1])
Dans ce premier algorithme on initialise un registre quantique à l’état |01> . On mesure dans un registre classique à 2 bits l’état quantique d’un registre quantique de 2 qubits. Le circuit peut être dessiné au moyen de l’instruction circuit.draw() ou via Circuit Composer de IBM Quantum Experience : https://quantum-computing.ibm.com/
Etat quantique d’un qubit seul :
L’état d’un qubit peut s’exprimer sous la forme d’un vecteur d’état si on passe en forme trigonométrique et exponentielle on a avec θ and ϕ qui sont des nombres réels :
C’est à dire qu’il existe une probabilité de mesurer le qubit dans l’état |0> et une probabilité de mesurer le qubit dans l’état |1>. La mesure d’un qubit révèle si celui-ci est dans l’état 1 ou dans l’état 0, en général la mesure est placée en fin de circuit car elle affecte l’état du qubit en conséquence.
Qiskit tutorial et Qiskit textbook – Liens internes :
COBOL UPON ET COBOL DISPLAY UPON, DISPLAY provoque l’affichage et l’instruction UPON entraîne l’affichage des données sur le périphérique demandé.
Fonctionnement de DISPLAY … UPON
La présence de la phrase UPON peut affecter le périphérique de sortie utilisé.
DISPLAY "HELLO WORLD" UPON SYSTEM-OUTPUT
DISPLAY "ERROR" UPON SYSTEM-OUTPUT
DISPLAY . . . UPON SYSOUT est traité comme si SYSOUT IS SYSOUT était précisé dans un paragraphe SPECIAL-NAMES sauf si SYSOUT a été déclaré autrement.
Sur le système COBOL 16 bits, la taille maximale COBOL d’un programme est de 256 Mo pour les données et de 4096 Mo pour le code.
Aussi, lorsque DISPLAY contient plus de un opérande, la taille totale de l’élément qui va être affiché corresponds à la somme de toutes les tailles des opérandes, et les valeurs sont alors concaténées.
Si le STATEMENT : WITH NO ADVANCING n’est pas utilisé. Alors le positionnement du périphérique de sortie standard est réinitialisé à la position la plus à gauche sur une nouvelle ligne.
Le prix d’un ordinateur quantique évolue entre 10 millions de dollars $ et 25 millions de dollars $. Voici quelques repère pour comprendre le prix d’un ordinateur quantique. L’article vous permettra de comprendre comment la course au quantique s’articule entre les différentes technologies et acteurs.
Introduction
Récemment Google a annoncé que sa puce Sycamore était la première à démontrer la «suprématie quantique» (article ici). Cela consiste à prouver que la résolution d’un problème à l’aide d’un algorithme quantique est plus efficace qu’à l’aide d’un algorithme classique. Aussi IBM construit actuellement un ordinateur quantique de 1 121 qubits, Condor (lien). Aussi il sera stocké à l’intérieur d’un « réfrigérateur » à dilution (voir ici). Et le but est de créer un ordinateur quantique et de le rendre disponible en ligne d’ici 2023.
Pour expliquer le prix d’un ordinateur quantique il faut dans un premier temps situer les différents acteurs de cette course au quantique et situer les dates importantes.
Les acteurs et l’écosystème de l’informatique quantique
PRINCIPAUX Acteurs dans le Hardware (CONSTRUCTEURS d’ordinateur quantique ET DE CIRCUITS) :
IBM : IBM construit un ordinateur quantique avec 1121 qubits d’ici 2023. Vous pouvez déjà programmer sur des systèmes Quantiques IBM via le cloud IBM sur des simulateurs ou des ordinateurs quantique réel via IBM Quantum Experience (voir mon article sur la programmation quantique avec IBM qiskit)
GOOGLE : Sycamore est un processeur quantique de 53 qubits créé par Google (en savoir plus)
INTEL : Intel crée un processeur « Tangle Lake ». Comme ses concurrents IBM, Google, Rigetti, IMEC et BBN Technologies Intel se base sur une architecture de qubits supraconducteurs.
ALICE AND BOB : développe une solution qui permet de résoudre le problème des erreurs quantiques.
D-WAVE : La société D-WAVE crée et commercialise des ordinateurs quantiques.
IONQ : crée un ordinateur quantique à ions piégés.
RIGETTI : Rigetti crée un ordinateur full-stack pour l’informatique hybride classique et quantique.
PSIQuantum : L’objectif de PsiQuantum est de construire le premier ordinateur quantique à usage général utile au monde avec au moins 1 millions de Qubits. La société travaille par exemple sur des qubits photoniques.
TURING :XGR-1 est une mémoire quantique révolutionnaire de la première génération de Turing.
QILIMANJARO :Enfin, Qilimanjaro se concentre sur des architectures de qubit de haute qualité de recuit quantique cohérent.
PRINCIPAUX Acteurs dans le SOFTWARE (KIT DE développement, Logiciels, Solutions cryptographiques)
IBM Qiskit :IBM Qiskit permet aux développeurs de créer des algorithmes quantiques à l’aide d’une interface en Python.
MICROSOFT : Q# est un langage de microsoft de programmation qui permet la programmation quantique.
1QBIT : 1QUBIT est une société de service en informatique quantique.
QCWARE : Egalement QCWARE une entreprises qui se concentre sur la création d’algorithmes quantiques.
QUSOFT QuSoft est le centre de recherche néerlandais sur les logiciels quantiques. Sa mission est de développer de nouveaux protocoles, algorithmes et applications pouvant être exécutés sur des prototypes de petite et moyenne taille d’un ordinateur quantique.
STRANGE WORKS : Commercialise des logiciels d’informatique quantiques.
Ordinateur quantique prix – Indication du prix d’un ordinateur quantique
Le prix d’un ordinateur quantique D-WAVE 200Q est par exemple d’environ 15 millions de dollars (15 m$). De plus, cette même entreprise commercialisait un ordinateur quantique 1000Q quelques années auparavant. Et en 2011, D-Wave lance son premier modèle d’ordinateur quantique qui sera disponible dans le commerce. Aussi il coûte 10 millions de dollars. Cela donne une bonne estimation de combien coûte un ordinateur quantique.
Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c’est le cas.
Algorithme glouton : Introduction
Le problème du rendu de monnaie est formulé de la façon suivante. Comment rendre une somme donnée avec un minimum de pièces et billets ?
Voici un exemple en python de la résolution du problème :
Si on considère le système monétaire Euro sans les centimes on a l’ensemble
EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)
Algorithme glouton rendu de monnaie python
Maintenant, pour rendre la monnaie sur une valeur x de en utilisant ces pièces et billets, alors nous vérifierons le premier élément du tableau. Et si il est supérieur à x, nous passons à l’élément suivant. Sinon le gardons. Maintenant, après avoir pris une pièce ou un billet de valeur issu du tableau de pieceEtBillet [i], la valeur totale x que nous devons faire deviendra x – pieceEtBillet [i].
Voici l’algorithme glouton python associé :
def renduMonnaieGlouton(x):
pieceEtBillets = [500,200,100,50,20,10,5,2,1]
i = 0
while(x>0):
if(pieceEtBillets[i] > x):
i = i+1
else:
print(str(pieceEtBillets[i]))
x -= pieceEtBillets[i];
renduMonnaieGlouton(33)#Exemple sur 33 euros
La sortie pour 33 euro est alors :
20
10
2
1
Autre exemple avec 55 euro d’algorithme glouton python :
def renduMonnaieGlouton(x):
pieceEtBillets = [500,200,100,50,20,10,5,2,1]
i = 0
while(x>0):
if(pieceEtBillets[i] > x):
i = i+1
else:
print(str(pieceEtBillets[i]))
x -= pieceEtBillets[i];
renduMonnaieGlouton(55)#Exemple sur 55 euros
La sortie est alors :
50
5
Conclusion
Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré (euro dans cet exemple). Pour aller plus loin on pourra démontrer que pour certains systèmes de monnaie dits canoniques, l’utilisation d’un algorithme glouton est optimal. Un système monétaire est dit canonique si pour toute somme s l’algorithme glouton conduit à une décomposition minimale.
La difficulté NP est la propriété déterminante d’une classe de problèmes informellement « au moins aussi difficiles que les problèmes les plus difficiles de NP ».
Un exemple simple de problème NP-hard est le problème de somme de sous-ensembles. Si P est différent de NP alors il est peu probable de trouver un algorithme en temps polynomial qui résout de façon exact ce problème.
Voici l’implémentation en python de l’algorithme de Wagner & Fischer (Wagner-Fischer). Il permet de calculer la distance de Levenshtein (distance entre deux chaines de caractères).
Premièrement le but de l’algorithme est de trouver le coût minimal. Coût minimal pour transformer une chaîne en une autre. Alors une fonction récursive permet de retourner le nombre minimal de transformation. Et pour transformer une sous-chaine de A avec n caractères en une sous-chaine de B avec le même nombre de caractères. La solution est donnée. Il faut calculer la distance entre les 2 lettres à la même position dans la chaine A et B. Alors Soit les lettres et la lettre précédentes sont identiques. Soit il y a une différence et dans ce cas on calcule 3 côuts. Alors le premier est de supprimer une lettre le la chaine A. Et d’insérer une lettre dans la chaine A pour substituer une lettre de la chaine A. Alors On peut alors trouver le cout minimal.
import numpy as np
def levenshtein(chaine1, chaine2):
taille_chaine1 = len(chaine1) + 1
taille_chaine2 = len(chaine2) + 1
levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
for x in range(taille_chaine1):
levenshtein_matrix [x, 0] = x
for y in range(taille_chaine2):
levenshtein_matrix [0, y] = y
for x in range(1, taille_chaine1):
for y in range(1, taille_chaine2):
if chaine1[x-1] == chaine2[y-1]:
levenshtein_matrix [x,y] = min(
levenshtein_matrix[x-1, y] + 1,
levenshtein_matrix[x-1, y-1],
levenshtein_matrix[x, y-1] + 1
)
else:
levenshtein_matrix [x,y] = min(
levenshtein_matrix[x-1,y] + 1,
levenshtein_matrix[x-1,y-1] + 1,
levenshtein_matrix[x,y-1] + 1
)
return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])
print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))
Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.
Aussi on peut calculer dynamiquement les valeurs dans cette matrice. La dernière valeur calculée sera la distance de Levenshtein entre les deux chaînes entières.
Enfin il y a de nombreux cas d’utilisation de la distance de Levenshtein. La distance de Levenshtein est utilisée dans des domaines. La linguistique informatique, la biologie moléculaire. Et encore la bioinformatique, le machine learning. Également le deep learning, l’analyse de l’ADN. De plus, un programme qui fait de la vérification orthographique utilise par exemple la distance de Levenshtein.
Liens sur l’algorithme de Wagner & Fischer (Wagner-Fischer) et la distance de Levenshtein en Python ou d’autre langage :
Dans cet article je vous propose un algorithme de tri quantique qui permet de trier une liste d’entier codés sur deux qubits. Cet algorithme peut être utilisé et peut servir de base pour résoudre des problèmes de tri sur une liste non triée d’entiers.
Introduction
Nous considérons le problème suivant : Étant donné une liste de quatre entiers compris entre 0 et 3 strictement différents, trier la liste :
Figure 1 : Problem to solve with Quantum sorting algorithm
Un algorithme de tri classique comme par exemple le tri fusion permet de résoudre le problème, voir plus en détail mon article sur le sujet :
Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites.
Quelques concepts d’algorithme quantique
Je rappelle ici quelques concepts que nous allons utiliser dans notre algorithme de tri quantique, aussi je vous conseille de consulter le site IBM Qiskit pour en savoir plus https://qiskit.org/textbook/what-is-quantum.html et le très bon livre « Programming Quantum Computers: Essential Algorithms and Code Samples »de Eric R. Johnston , Nic Harrigan , Mercedes Gimeno-Segovia :
Circuits
Le principe en algorithme quantique est de manipuler des qubits, le processus peut être représenté sous forme de circuit (entrées à gauche, sortie à droite). Nous pouvons effectuer différentes opérations au moyen de portes quantiques (qui agissent sur les qubits de manière similaire en algorithme classique aux portes logiques comme ET, OU, OU Exclusif …).
Dans cet article je vais m’appuyer sur Qiskit qui est le framework IBM pour l’informatique quantique.
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(2, 'qubit')
creg_classic = ClassicalRegister(2, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.x(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
circuit.measure(qreg_qubit[1], creg_classic[1])
Dans ce premier algorithme on initialise un registre quantique à l’état |01> . On mesure dans un registre classique à 2 bits l’état quantique d’un registre quantique de 2 qubits. Le circuit peut être dessiné au moyen de l’instruction circuit.draw() ou via Circuit Composer de IBM Quantum Experience : https://quantum-computing.ibm.com/
Etat quantique d’un qubit seul :
L’état d’un qubit peut s’exprimer sous la forme d’un vecteur d’état si on passe en forme trigonométrique et exponentielle on a avec θ and ϕ qui sont des nombres réels :
Avec alpha et beta qui sont des nombres complexes (c’est à dire une partie réelle et imaginaire) dans ce cas il existe la relation (rappel mathématique sur les nombres complexes : https://www.maths-cours.fr/cours/nombres-complexes-geometrie/) :
Ainsi si on mesure un qubit q on a :
C’est à dire qu’il existe une probabilité de mesurer le qubit dans l’état |0> et une probabilité de mesurer le qubit dans l’état |1>. La mesure d’un qubit révèle si celui-ci est dans l’état 1 ou dans l’état 0, en général la mesure est placée en fin de circuit car elle affecte l’état du qubit en conséquence.
Portes quantiques
Voici quelques portes quantiques à connaitre et que nous allons utiliser dans l’algorithme de tri quantique :
Porte X (Pauli-X) :
La porte X permet de retourner l’état du qubit sans modifier la phase :
<
Voir l’exemple ci-dessus avec l’utilisation de qiskit.
Porte Y (Pauli-Y) :
La porte de pauli Y permet de retourner la phase et l’état du qubit en même temps :
Exemple si on considère ici l’état initialisé |0> du qubit et sa phase de 0, il y a alors 100% de chance de mesurer l’état |0>.
L’application de la porte quantique Y a l’effet suivant sur l’état et la phase du qubit (voir la sphère de bloch) :
Il y a alors 100% de chance de mesurer l’état 1 et la phase se retrouve inversée (voir la sphère de bloch ci-dessus)
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(1, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.y(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
Porte Z (Pauli-Z) :
La porte Z est utilisée pour retourner uniquement la phase et non l’état du qubit.
A noter que les portes Y et Z peuvent être représentées par les matrices suivantes :
La porte Hadamard (porte H) est une porte quantique importante qui permet de créer une superposition de | 0⟩ et | 1⟩.
La matrice de cette porte est :
Porte de SWAP
Une porte SWAP permet d’échange l’état de deux qubits :
Exemple SWAP de l’état | 1⟩ du qubit 0 vers le qbit 2
Et SWAP de l’état | 0⟩ du qubit 1 vers le qbit 2
En Python avec le framework Qiskit on a :
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi
qreg_qubit = QuantumRegister(3, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)
circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.reset(qreg_qubit[2])
circuit.x(qreg_qubit[0])
circuit.swap(qreg_qubit[1], qreg_qubit[2])
circuit.measure(qreg_qubit[2], creg_classic[0])
Porte de Toffoli
La porte quantique Toffoli est à trois qubits (deux commandes et une cible). Il effectue un retournement de phase (porte quantique X sur la cible) uniquement si les deux contrôles sont dans l’état | 1⟩. Un Toffoli est équivalent à une porte NON contrôlée (on l’appelle aussi la porte CCX).
Exemple ci-dessous avec 2 qubits de commande en état | 1⟩ on a alors 100% de chance de mesurer l’état | 1⟩ sur le qubit cible de la porte de Toffoli qui était au départ initialisé à l’état | 0⟩ (soit un retournement de l’état).
Exemple ci-dessous dans le cas inverse (on a alors 0% de chance de mesurer l’état | 1⟩ soit 100% de chance de mesurer l’état | 0⟩):
Porte classique porte ET, porte OU équivalence en porte quantique
On voit ici comment combiner des porte pour créer un comportement équivalent à ce qu’on a l’habitude d’utiliser en circuit classique.
Porte ET :
A partir de Qbit a et b et d’un qubit avec une initialisation forcée à l’état | 0⟩ on peut obtenir l’opération a ET b en utilisant une porte quantique de Toffoli et une pote SWAP.
Le circuit suivant effectue un classique ET sur un algorithme quantique
Il faut noter qu’à la fin de ce circuit on retrouve l’état A ET B sur le qubit B l’état du qubit B se trouve au final sur le qubit C.
Nous utiliserons cette porte pour effectuer notre tri quantique de liste, voici quelques tests :
Pour | 0⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :
Pour | 0⟩ ET | 1⟩ vous avez | 0⟩ sur le qubit B :
Pour | 1⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :
Enfin pour | 1⟩ ET | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Porte OU :
Pour réaliser une porte OU on combine 4 portes quantiques X, une porte de Toffoli et une porte quantique SWAP, également l’état de C doit être initialisé à l’état | 1> :
OPENQASM 2.0;
include "qelib1.inc";
qreg a[1];
qreg b[1];
qreg c[1];
creg aORb[1];
creg aState[1];
creg bState[1];
reset a[0];
reset b[0];
x b[0];
x c[0];
x a[0];
ccx a[0],b[0],c[0];
x a[0];
x b[0];
swap b[0],c[0];
measure b[0] -> aORb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];
Si on teste on obtient bien une porte OU :
Ici pour | 0⟩ OU | 0⟩ vous avez bien | 0⟩ sur le qubit B avec une probabilité de 100% :
Ici pour | 0⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Pour | 1⟩ OU | 0⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Finalement pour | 1⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :
Algorithme de tri quantique
Pour résoudre ce problème nous allons créer tout d’abord un circuit quantique qui permet de mesurer si un chiffre est inférieur à un autre, pour cela l’intuition est de se baser sur un circuit similaire à un circuit classique de comparaison de magnitude à 2 bits.
Comparateur de magnitude quantique :
On considère un chiffre A stocké dans un registre à 2 qubits (A0, A1) et un chiffre B stocké dans un autre registre (B0,B1) :
Pour savoir si A > B avec 2 registre de 2 Qubits il faut appliquer l’équation :
Le circuit équivalent pour créer cela est :
Ici dans l’exemple les 2 bits comparés par ce circuit sont dans le registre a et le registre B
Quantum qubit magnitude comparator
Le code équivalent pour ce comparateur en OpenQASM est :
J’ai créé une GATE comparator4 qui a le code équivalent OPENQASM suivant :
gate comparator4 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
x c;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
Ainsi on voit que cette custom quantum gate est consitué de porte quantum AND et porte quantum OR custom que j’ai créé de la façon suivante. Si on déplie les portes andG1, andG2, andG3, orG1, orG2 on a :
Le code équivalent OpenQASM pour écrire les différentes porte andG1, andG2, andG3, orG1, orG2 pour créer le comparator 4 est :
gate andG1 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG2 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG3 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG1 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate andG4 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG2 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
Circuit de vérification d’une liste triée
Si on considère ici une liste de 4 chiffres stockés dans les 4 registres de 2 qubits : a, b, m, n. Le circuit ci-dessur permet de tester si la liste en entrée est triée ou non. Pour cela j’ai mis en cascade 3 comparateurs de magnitude quantique (vu en détails dans le paragraphe précédent). Ainsi le circuit obtenu va tester si a > b et mettre le résulta sur le qbit c puis vérifier si b>m et stocker le résultat sur le qbit o et enfin il teste si m > n et stocke le résultat sur le qubit q.
La dernière porte quantique andOnCompare permet d’appliquer une parte ET mutliple :si c ET o ET q sont à l’état quantique |1> alors le qubit q est mis à l’état quantique |1> sinon il est à l’état quantique |0> :
Ci-dessous le code de la porte andOnCompare en openQASM :
gate andOnCompare a, b, c, d, f {
ccx a, b, d;
swap b, d;
ccx b, c, f;
swap c, f;
}
Nous avons créé un circuit qui vérifie qu’une liste de 4 chiffres stocké dans les registres a,b,m,n est triée de façon décroissante ou non. Le résultat est stocké dans le qubit q qui a 100% de chance d’être mesuré à l’état | 1> si la liste est triée sinon 100% d’être à | 0> si la liste a,b,m,n n’est pas en ordre décroissante.
Dans le schéma général ci-dessus on remarque que dans l’exemple :
a=0,b=2,m=3,n=1
dans ce cas ce circuit retournera l’état quantique |0 > sur le qubit q
Création d’un circuit de permutations
L’idée de notre algorithme est de permuter ces 4 chiffres en utilisant des qubits de commande qui seront en état de superposition.
Le circuit de permutation est le suivant :
Un registre de 6 Qubit « control » permet de piloter la permutation de la liste sachant qu’il y a pour 4 éléments : 4*3*2*1 permutations possibles soit 24 possibilités les 6 qubits permettent de générer ces différents états.
4 portes quantique de Hadamard sont utilisées pour mettre en oeuvre ces permutations et tirer parti de la superposition du registre de Qubit ‘control’
En d’autre terme dans le circuit ci-dessus on voit que l’on démarre le circuit en initialisant les registres a,b,m,n avec sa liste de chiffre non triée, ici (a=0,b=2,m=3,n=1).
Le circuit de permutation qui est contrôlé par un registre de qubit en superposition permet de permuter la liste en superposition quantique.
Ainsi on obtient sur le qubit q0 l’état quantique | 1> si la liste permutée est triée de façon décroissante sinon l’état quantique | 0>.
Le code OpenQASM de l’algorithme quantique permettant d’effectuer des permutation est le suivant :
gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
cswap k, a, c;
cswap l, a, f;
cswap m, a, i;
cswap k, b, d;
cswap l, b, g;
cswap m, b, j;
cswap n, c, f;
cswap o, c, i;
cswap n, d, g;
cswap o, d, j;
cswap p, f, i;
cswap p, g, j;
}
Amplification du résultat
Je vais appeler cette partie de mon algorithme l’amplification : l’idée est de mettre les qubit a,b,m,n à |00>,|00>,|00>,|00> si la liste est non triée. Si la liste est triée alors l’état quantique de a,b,m,n ne doit pas être modifié.
Ainsi on devrait mesurer le résultat suivant : |00>,|00>,|00>,|00> lorsque la liste est non trié et a,b,m,n avec les chiffre d’entrée en ordre trié (dans le cas de notre exemple cela signifie qu’il y a une probabilité de mesurer l’état |11>,|10>,|01>,|00> soit 3,2,1,0 soit la liste triée).
Le circuit de l’amplificateur quantique est le suivant :
Le circuit se base sur une série de porte quantique AND appliqué à l’état de sortie q0 ET le chiffre de la liste. Lorsque le qubit q0 indique que la liste est triée il est à |1> et laisse l’état des qubit a,b,m,n à leur état d’entrée (ou permuté par superposition) . Lorsque le qubit q0 indique que la liste est non triée il est à l’état | 0> l’application de la porte AND va ainsi mettre les qubit a,b,m,n à | 0>.
Le code de l’amplificateur est le suivant selon un algorithme quantique codé en OpenQASM :
gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, k, l;
swap a, l;
ccx b, k, m;
swap b, m;
ccx c, k, n;
swap c, n;
ccx d, k, o;
swap d, o;
ccx f, k, p;
swap f, p;
ccx g, k, q;
swap g, q;
ccx i, k, r;
swap i, r;
ccx j, k, v;
swap j, v;
}
Algorithme quantique complet pour le tri décroissant d’une liste de quatre chiffres :
Voici le circuit utilisé pour trié la liste suivante : a=0,b=2,m=3,n=1.
Il est possible facilement d’initialiser le circuit avec une autre liste en modifiant l’initialisation des registre a,b,m,n. Aussi l’algorithme actuel permet de trier des chiffres codés sur 2 qubits il reste possible de modifier l’algorithme selon le même principe pour trier des nombres stockés sur 3 qubits et considérer une liste de plus de 4 éléments (il faut alors multiplier le nombre de registres de qubits pour stocker la liste d’entrée).
Le code complet est le suivant en openQASM :
OPENQASM 2.0;
include "qelib1.inc";
gate andG1 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG2 a, b, c {
ccx a, b, c;
swap b, c;
}
gate andG3 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG1 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate andG4 a, b, c {
ccx a, b, c;
swap b, c;
}
gate orG2 a, b, c {
x a;
x b;
ccx a, b, c;
x a;
x b;
swap b, c;
}
gate comparator a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
}
gate comparator2 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
x d;
swap b, g;
}
gate comparator3 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
gate comparator4 a, b, c, d, f, g, i, j, k, l {
x d;
x j;
x l;
andG1 b, d, f;
andG2 a, b, g;
andG3 a, f, i;
orG1 b, f, j;
x c;
andG4 c, f, k;
x c;
orG2 d, f, l;
swap d, i;
x d;
swap b, g;
}
gate permutation a, b, c, d, f, g, i, j, k, l, m, n, o, p {
ccx a, c, k;
ccx a, f, l;
ccx a, i, m;
ccx b, d, k;
ccx b, g, l;
ccx b, j, m;
ccx c, f, n;
ccx c, i, o;
ccx d, g, n;
ccx d, j, o;
ccx f, i, p;
ccx g, j, p;
}
gate andOnCompare a, b, c, d, f {
ccx a, b, d;
swap b, d;
ccx b, c, f;
swap c, f;
}
gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
cswap k, a, c;
cswap l, a, f;
cswap m, a, i;
cswap k, b, d;
cswap l, b, g;
cswap m, b, j;
cswap n, c, f;
cswap o, c, i;
cswap n, d, g;
cswap o, d, j;
cswap p, f, i;
cswap p, g, j;
}
gate amplifier a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx l, a, m;
swap a, m;
ccx l, b, n;
swap b, n;
ccx l, c, o;
swap c, o;
ccx l, d, p;
swap d, p;
ccx l, f, q;
swap f, q;
ccx l, f, q;
swap f, q;
ccx l, g, r;
swap g, r;
ccx l, i, v;
swap i, v;
ccx l, j, k;
swap j, k;
}
gate amplifier1 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, l, m;
swap a, m;
ccx b, l, n;
swap b, n;
ccx c, l, o;
swap c, o;
ccx d, l, p;
swap d, p;
ccx f, l, q;
swap f, q;
ccx f, l, q;
swap f, q;
ccx g, l, r;
swap g, r;
ccx i, l, v;
swap i, v;
ccx j, k, l;
swap j, k;
}
gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
ccx a, k, l;
swap a, l;
ccx b, k, m;
swap b, m;
ccx c, k, n;
swap c, n;
ccx d, k, o;
swap d, o;
ccx f, k, p;
swap f, p;
ccx g, k, q;
swap g, q;
ccx i, k, r;
swap i, r;
ccx j, k, v;
swap j, v;
}
qreg a[2];
qreg b[2];
qreg m[2];
qreg n[2];
qreg c[1];
qreg o[1];
qreg q[1];
qreg d[1];
qreg g[1];
qreg j[1];
qreg k[1];
qreg l[1];
qreg r[1];
qreg uu[1];
qreg zz[1];
qreg control[6];
creg sorted[8];
reset a[0];
reset a[1];
reset b[0];
reset b[1];
reset m[0];
reset m[1];
reset n[0];
reset n[1];
reset c[0];
reset o[0];
reset q[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
h control[0];
h control[1];
h control[2];
h control[3];
h control[4];
h control[5];
reset a[0];
reset a[1];
reset b[0];
x b[1];
x m[0];
x m[1];
reset n[1];
reset c[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
x n[0];
permuter a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],control[0],control[1],control[2],control[3],control[4],control[5];
comparator4 a[0],a[1],b[0],b[1],c[0],d[0],g[0],j[0],k[0],l[0];
reset zz[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 b[0],b[1],m[0],m[1],o[0],d[0],g[0],j[0],k[0],l[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0];
andOnCompare c[0],o[0],q[0],r[0],uu[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
amplifier2 a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0],r[0],uu[0],zz[0];
measure a[0] -> sorted[0];
measure a[1] -> sorted[1];
measure b[0] -> sorted[2];
measure b[1] -> sorted[3];
measure m[0] -> sorted[4];
measure m[1] -> sorted[5];
measure n[0] -> sorted[6];
measure n[1] -> sorted[7];
Voici le code Python Qiskit pour mon algorithme de tri quantique :
Les test s’effectuent en démarrant l’algorithme sur le simulateur quantique :
Pour démarrer l’algorithme quantique il faut au préalable initialiser :
%matplotlib inline
# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from iqx import *
# Loading your IBM Q account(s)
provider = IBMQ.load_account()
Et pour effectuer le test par exemple en exécutant 100 fois le circuit quantique et afficher la probabilité de mesure sous forme d’histogramme :
On obtient le résultat qui confirme qu’on a plus de change de mesurer l’état quantique de la liste trié que les autres combinaison (dans mon test 5%) :
![\[|q\rangle = \cos{(\tfrac{\theta}{2})}|0\rangle + e^{i\phi}\sin{\tfrac{\theta}{2}}|1\rangle\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-3451da2a6973004892db316ab0e4c4b5_l3.png "Rendered by QuickLaTeX.com")
![\[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-7e747384beff7d1e7dc0cba6ffef5a61_l3.png "Rendered by QuickLaTeX.com")
![\[\sqrt{|\alpha|^2 + |\beta|^2} = 1\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-140825f90910f1016720805cd1c30596_l3.png "Rendered by QuickLaTeX.com")
![\[|q\rangle = \alpha|0\rangle + \beta|1\rangle\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-e6a52fa4681f8adee60399c34542b89c_l3.png "Rendered by QuickLaTeX.com")
![\[X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = |0\rangle\langle1| + |1\rangle\langle0|\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-f6748a16d19cd0038b3a77d7496589a3_l3.png "Rendered by QuickLaTeX.com")
![\[Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \quad\quad\quad\quad Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-f5a0690299a4adf7958141450f85a911_l3.png "Rendered by QuickLaTeX.com")
![\[Y = -i|0\rangle\langle1| + i|1\rangle\langle0| \quad\quad Z = |0\rangle\langle0| - |1\rangle\langle1|\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-19bd90544c17442945e7beb47a9a633c_l3.png "Rendered by QuickLaTeX.com")
![\[H = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]](https://128mots.com/wp-content/ql-cache/quicklatex.com-2122e59750b4a857c8c21ce48bbdd532_l3.png "Rendered by QuickLaTeX.com")
