En informatique, les algorithmes de recherche binaire ou de recherche semi-intervalle peuvent trouver la position de la valeur cible dans le tableau trié. Recherche dichotomique python, les algorithmes de recherche binaire peuvent être classés comme des algorithmes de recherche dichotomiques «diviser et conquérir» et s’exécuter en temps logarithmique.
def dichotomie(tableau, x):
premier = 0
dernier = len(tableau)-1
trouve = False
while( premier<=dernier and not trouve):
mid = (premier + dernier)//2
if tableau[mid] == x :
trouve = True
else:
if x < tableau[mid]:
dernier = mid - 1
else:
premier = mid + 1
return trouve
tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
x = 8999
trouve = dichotomie(tableau, x)
if not trouve:
print("n'est pas trouvé")
else:
print("est trouvé")
L’algorithme de recherche binaire calcule les chemins binaires sur une cible à partir d’une représentation binaire standard. L’algorithme de recherche binaire utilise une variété de paramètres pour calculer les chemins binaires. Une fois ces informations disponibles, l’algorithme de recherche binomiale peut être comparé et classé par rapport à d’autres algorithmes similaires et est communément appelé recherche binomiale. Une recherche binaire en est une lorsque des longueurs différentes des données cibles sont utilisées ou que les données cibles sont supérieures à un kilo-octet. La longueur de la recherche binaire peut être déterminée à partir de la position de la valeur cible dans les tableaux ordonnés de chemins binaires.
L’algorithme de recherche binaire, qui s’exécute en temps logarithmique et dans un intervalle de temps fini d’une seconde, est également appelé randomisation binaire.
Comment fonctionne l’algorithme de recherche binaire?
Une recherche binaire aléatoire binaire est un sous-ensemble de la recherche en informatique traditionnelle. L’algorithme utilise un processus discret pour générer une séquence binaire. Un ensemble de données initial de chemins binaires est analysé à l’aide d’une procédure appelée recherche pour identifier chaque emplacement dans l’ensemble de données cible (figure 1).
L’algorithme de recherche binaire peut être comparé à d’autres algorithmes similaires et est communément appelé recherche binaire. Par exemple, un algorithme utilisant un algorithme de recherche binaire produit une recherche où
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%) :
Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.
Introduction
L’algorithme est le suivant : Diviser en deux moitiés la liste à trier. On trie chacune d’entre elles. Fusionner les deux moitiés obtenues pour reconstituer la liste triée.
On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
if len(tableau) <= 1:
return tableau
pivot = len(tableau)//2
tableau1 = tableau[:pivot]
tableau2 = tableau[pivot:]
gauche = tri_fusion(tableau1)
droite = tri_fusion(tableau2)
fusionne = fusion(gauche,droite)
return fusionne
#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
indice_tableau1 = 0
indice_tableau2 = 0
taille_tableau1 = len(tableau1)
taille_tableau2 = len(tableau2)
tableau_fusionne = []
while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
tableau_fusionne.append(tableau1[indice_tableau1])
indice_tableau1 += 1
else:
tableau_fusionne.append(tableau2[indice_tableau2])
indice_tableau2 += 1
while indice_tableau1<taille_tableau1:
tableau_fusionne.append(tableau1[indice_tableau1])
indice_tableau1+=1
while indice_tableau2<taille_tableau2:
tableau_fusionne.append(tableau2[indice_tableau2])
indice_tableau2+=1
return tableau_fusionne
tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)
A propos de tri fusion
Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.
La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).
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.
L’algorithme du tri par tas est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.
Le principe de l’algorithme du tri par tas python est le suivant :
Alors on recherche le père du dernier nœud de l’arbre et on le tamise : le père d’un noeud dans un arbre binaire corresponds à l’arrondi inférieur de (i-1)/2 avec i la position du noeud dans le tableau qui stocke l’arbre.
Le tamisage d’un noeud consiste à visiter son fils droit et son fils gauche et permuter la racine avec le plus grand des deux.
Et il faut tamiser l’arbre jusqu’à arriver à la racine, le plus grand nombre de l’arbre se retrouve alors en position de racine au début du tableau.
On permute la racine qui est le plus grand nombre avec la dernière feuille (soit la position n du tableau qui stocke l’arbre de taille n). On considère alors que ce nombre est bien ordonné (càd il est en dernière position et c’est le plus grand)
Enfin, l’opération de tamisage et permutation est réitérée en considérant le sous arbre qui va de la racine à n-1 (pour ne pas déplacer le nombre qui a été correctement ordonné) jusqu’à ce qu’on arrive au fils gauche de la racine (l’indice 1)
from math import *
#128mots.com
def indice_fils_gauche(noeud_pere:int):
return (noeud_pere * 2)+ 1
def indice_fils_droit(noeud_pere:int):
return (noeud_pere * 2) + 2
#Retourne l'indice du noeud pere si il existe (noeud doit être > 0)
def indice_noeud_pere(noeud):
#Si il existe il s'agit de l'arrondi inférieur de (noeud-1)/2
return floor((noeud - 1)/2)
#permute 2 éléments d'un tableau et incrément la variable globale compteur_permutation à initialiser dans le main
def permute(tableau, indice1: int, indice2:int):
print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
print("**Avant permutation : " + str(tableau))
global compteur_permutation
if(indice1 != indice2):
#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
tmp = tableau[indice1]
tableau[indice1] = tableau[indice2]
tableau[indice2] = tmp
compteur_permutation += 1
print("**Apres permutation : " + str(tableau))
#Tamise un arbre binaire à partir d'un noeud en parametre
#1. on compare le noeud avec le fils droit et le fils gauche (si ils existent)
#2. on permute avec la plus grande valeur
#128mots.com
def tamise(arbre,noeud,longueur):
#On visite le fils droit et le fils gauche
print("++Tamisage de " + str(noeud) + " arbre: " + str(arbre))
indiceFilsDroit = indice_fils_droit(noeud)
indiceFilsGauche = indice_fils_gauche(noeud)
print("indiceFilsDroit>>" + str(indiceFilsDroit))
print("indiceFilsGauche>>" + str(indiceFilsGauche))
if(indiceFilsDroit < longueur): # si le fils droit existe
if(arbre[indiceFilsDroit] > arbre[indiceFilsGauche]): #Si le fils droit est plus grand que le fils gauche
if(arbre[indiceFilsDroit] > arbre[noeud]): #Si le fils droit est plus grand que le noeud tamisé
permute(arbre,indiceFilsDroit,noeud)
elif(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
permute(arbre,indiceFilsGauche,noeud)
elif(indiceFilsGauche < longueur): #Si le fils gauche existe
if(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
permute(arbre,indiceFilsGauche,noeud)
print("++Apres tamisage : " + str(arbre))
#128mots.com
compteur_permutation = 0
arbre = [11, 222, 3, 24, 5, 46, 67, 899] #On écrit un arbre sous forme de tableau
print("démarrage arbre : " + str(arbre))
#128mots.com
#Tamisage initial
#on prend le dernier élément de l'arbe qui est une feuille et on recherche son père
indiceDuNoeudPere = indice_noeud_pere(len(arbre)-1)
#on tamise càd on compare le noeud pere avec le fils droit et le fils gauche
#puis on permute avec la plus grande valeur
for i in range(indiceDuNoeudPere,-1,-1): #On tamise jusqu'à la racine
tamise(arbre,i,len(arbre))
permute(arbre,len(arbre)-1,0) #on permute le premier element et le dernier
#suite au tamisage c'est la plus grande valeur on la place donc à la fin du tableau
#on répete le tamisage
for i in range(len(arbre)-1,1,-1):
indiceDuNoeudPereDeI = indice_noeud_pere(i-1) #on prend l'élément i de l'arbe qui est une feuille et on recherche son père
for j in range(indiceDuNoeudPereDeI,-1,-1): #On tamise jusqu'à la racine
tamise(arbre,j,i)
permute(arbre,i-1,0)
print("resultat final du tri : " + str(arbre))
print("nombre de permutation : " + str(compteur_permutation))
Conclusion
En conclusion, L’algorithme est utilisé pour trier sur place les éléments d’un tableau en un temps de l’ordre de n log n.
Et l’étape qui coûte le plus dans cet algorithme est la seconde boucle (extraction des éléments du tas).
Enfin, et algorithme a l’avantage de consommer peu de mémoire par rapport à d’autres algorithme de tri.
Le tri rapide (QuickSort) choisir aléatoirement un élément (appelé pivot) et de le positionner à sa place définitive, en permutant tous les éléments pour que ceux qui sont inférieurs au pivot soient à sa gauche et que ceux qui sont supérieurs au pivot soient à sa droite.
L’opération est appelée le partitionnement. Pour chacune des sous-listes (ou sous-tableaux), on choisit aléatoirement un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que tous les éléments soit trié.
Le partitionnement consiste à :
permuter le pivot avec le dernier élément du sous-tableau
placer en début du sous-tableau les éléments inférieurs au pivot
déplacer le pivot à droite du dernier élément déplacé en début de tableau (les autres éléments étant supérieur au pivot).
Exemple d’une itération de partitionnement (source wikipedia) : Ici le pivot est 5
from random import randint
#Choix d'un pivot aléatoirement
#128mots.com
def choix_pivot(tableau,premier: int,dernier: int):
pivot = randint(premier,dernier)
print("La sous-liste non triée est : " + str(tableau[premier:dernier+1]))
print("Le pivot choisi aleatoirement est l'indice " + str(pivot) + " de valeur =" + str(tableau[pivot]))
return pivot
#Fonction pour effectuer le partitionnement du tableau
#Permutation de tous les éléments pour que ceux qui sont inférieurs au pivot
# soient à sa gauche et que tous ceux qui sont supérieurs au pivot
#soient à sa droite.
#128mots.com
def partitionner(tableau, debut: int, fin: int, pivot: int):
#Etape 1 : on positionne le pivot à la fin de la sous-liste arbitrairement
#On permute le pivot et le dernier element
print("Partitionnement de la sous-liste = " + str(tableau[debut:fin+1]))
print("---Placement du pivot à la fin la sous-liste")
permute(tableau, pivot, fin)
print("---")
j = debut #indice d'avancement dans le début de la sous-liste
#Pour i du début de la sous-liste à la fin
for i in range(debut,fin):
#Tous les élément inférieur au pivot sont placés au début de la sous-liste
if(tab[i] <= tab[fin]):
#Si la valeur est inférieure on déplace au début du tableau
#Et que la valeur n'est pas déjà bien placée alors on déplace au début du tableau
permute(tableau,i,j)
j+=1
#On place le pivot à la bonne place en permuttant l'élément après le dernier trouvé comme inférieur au pivot
print("**permutation du pivot")
permute(tableau,fin,j)
#on retourne la position de j qui est alors la nouvelle position du pivot dans le tableau
return j
#Fonction de permutation de deux élément d'un tableau
#128mots.com
def permute(tableau, indice1: int, indice2:int):
print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
print("**Avant permutation : " + str(tab))
global compteur_permutation
if(indice1 != indice2):
#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
tmp = tableau[indice1]
tableau[indice1] = tableau[indice2]
tableau[indice2] = tmp
compteur_permutation += 1
print("**Apres permutation : " + str(tab))
#Fonction de tri rapide d'une sous-liste d'un tableau
#128mots.com
def tri_rapide(tableau,debut: int,fin: int):
# Si on a une sous-liste qui contient au moins 2 éléments
if debut < fin :
#on choisit un pivot dans la sous-liste
pivot = choix_pivot(tableau,debut,fin)
#on déplace tout les élément inférieur au pivot à gauche du pivot
pivot = partitionner(tableau,debut,fin,pivot)
#recursion pour refaire l'algorithme sur la sous-liste à gauche du pivot trouvé
tri_rapide(tableau,debut,pivot - 1)
#recursion pour refaire l'algorithme sur la sous-liste à droite du pivot trouvé
tri_rapide(tableau,pivot + 1,fin)
compteur_permutation = 0
tab = [111, 34, 22, 55, 4, 2, 1, 77]
tri_rapide(tab,0,len(tab)-1)
print("resultat final du tri : " + str(tab))
print("nombre de permutation : " + str(compteur_permutation))
La sortie du programme est la suivante :
La sous-liste non triée est : [111, 34, 22, 55, 4, 2, 1, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =1
Partitionnement de la sous-liste = [111, 34, 22, 55, 4, 2, 1, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 7
**Avant permutation : [111, 34, 22, 55, 4, 2, 1, 77]
**Apres permutation : [111, 34, 22, 55, 4, 2, 77, 1]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 0
**Avant permutation : [111, 34, 22, 55, 4, 2, 77, 1]
**Apres permutation : [1, 34, 22, 55, 4, 2, 77, 111]
La sous-liste non triée est : [34, 22, 55, 4, 2, 77, 111]
Le pivot choisi aleatoirement est l'indice 5 de valeur =2
Partitionnement de la sous-liste = [34, 22, 55, 4, 2, 77, 111]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 34, 22, 55, 4, 2, 77, 111]
**Apres permutation : [1, 34, 22, 55, 4, 111, 77, 2]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 1
**Avant permutation : [1, 34, 22, 55, 4, 111, 77, 2]
**Apres permutation : [1, 2, 22, 55, 4, 111, 77, 34]
La sous-liste non triée est : [22, 55, 4, 111, 77, 34]
Le pivot choisi aleatoirement est l'indice 4 de valeur =4
Partitionnement de la sous-liste = [22, 55, 4, 111, 77, 34]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 22, 55, 4, 111, 77, 34]
**Apres permutation : [1, 2, 22, 55, 34, 111, 77, 4]
---
**permutation du pivot
Permutation de l'élément 7 avec l'element 2
**Avant permutation : [1, 2, 22, 55, 34, 111, 77, 4]
**Apres permutation : [1, 2, 4, 55, 34, 111, 77, 22]
La sous-liste non triée est : [55, 34, 111, 77, 22]
Le pivot choisi aleatoirement est l'indice 4 de valeur =34
Partitionnement de la sous-liste = [55, 34, 111, 77, 22]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 4 avec l'element 7
**Avant permutation : [1, 2, 4, 55, 34, 111, 77, 22]
**Apres permutation : [1, 2, 4, 55, 22, 111, 77, 34]
---
Permutation de l'élément 4 avec l'element 3
**Avant permutation : [1, 2, 4, 55, 22, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**permutation du pivot
Permutation de l'élément 7 avec l'element 4
**Avant permutation : [1, 2, 4, 22, 55, 111, 77, 34]
**Apres permutation : [1, 2, 4, 22, 34, 111, 77, 55]
La sous-liste non triée est : [111, 77, 55]
Le pivot choisi aleatoirement est l'indice 5 de valeur =111
Partitionnement de la sous-liste = [111, 77, 55]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 5 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 111, 77, 55]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 7 avec l'element 7
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
La sous-liste non triée est : [55, 77]
Le pivot choisi aleatoirement est l'indice 6 de valeur =77
Partitionnement de la sous-liste = [55, 77]
---Placement du pivot à la fin la sous-liste
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
---
Permutation de l'élément 5 avec l'element 5
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**permutation du pivot
Permutation de l'élément 6 avec l'element 6
**Avant permutation : [1, 2, 4, 22, 34, 55, 77, 111]
**Apres permutation : [1, 2, 4, 22, 34, 55, 77, 111]
resultat final du tri : [1, 2, 4, 22, 34, 55, 77, 111]
nombre de permutation : 10
Le nombre de permutation est 10 pour un tableau de 8 éléments.
La complexité moyenne du tri rapide est Θ(n log n) soit 7.22 pour un tableau de 8 éléments.
![\[|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")
