Ce que les algorithmes quantiques accélèrent

Un algorithme quantique n’essaie pas toutes les réponses à la fois. Il arrange les amplitudes pour que la bonne réponse devienne probable, et il n’accélère que certains problèmes.

Après cette leçon, vous saurez dire ce que le quantique accélère, ce qu’il n’accélère pas, et pourquoi un simulateur ne peut pas le montrer.

Imaginez quatre éléments, dont un seul est le bon. L’oracle reconnaît le bon : il change le signe de son amplitude, sans changer aucune chance.

Puis une seconde étape reflète chaque amplitude par rapport à la moyenne. La bonne amplitude, devenue négative, bondit vers le haut. Les autres tombent vers 0.

# Quatre éléments, numérotés de 0 à 3. L'élément 3 est le marqué.
etat = [0.5, 0.5, 0.5, 0.5]
marque = 3

# Étape 1 : retourner le signe de l'amplitude du marqué.
etat[marque] = -etat[marque]

# Étape 2 : refléter chaque amplitude par rapport à la moyenne.
moyenne = sum(etat) / len(etat)
nouvel_etat = []
for a in etat:
    nouvel_etat.append(2 * moyenne - a)
print("amplitudes :", nouvel_etat)
# Changez marque = 3 en marque = 1, puis relancez.

Le script amplify.py refait cette étape avec des portes. Ses lignes sont en anglais : start, every item equal veut dire « départ, tous les éléments égaux ». sign of the marked item flipped veut dire « signe de l’élément marqué retourné ».

after one amplification step veut dire « après une étape d’amplification ». chance of each veut dire « chance de chacun ».

docker exec jupyter python3 steps/amplify.py

Avec N éléments, une recherche ordinaire en essaie environ N, au pire. L’amplification demande de l’ordre de la racine carrée de N étapes.

C’est une vraie accélération, mais modeste : la racine de un million vaut mille. Elle ne rend pas un problème difficile facile.

Factoriser un grand nombre, c’est retrouver les deux nombres premiers dont il est le produit. Un ordinateur ordinaire met un temps énorme. Un algorithme quantique, celui de Shor, ferait la tâche bien plus vite.

Mais il demande une machine très grande, avec des erreurs corrigées. Aucune machine actuelle n’en est là. Les chercheurs préparent déjà de nouveaux codes secrets pour le jour où ce serait possible.

Un qubit réel est fragile : la chaleur, les vibrations et les erreurs de portes abîment son état. Ces petites erreurs forment le bruit.

Plus un programme a de portes, plus le bruit s’accumule. Pour le corriger, il faut beaucoup de qubits physiques pour un seul qubit fiable.

# Chaque qubit en plus double le nombre d'amplitudes à garder en mémoire.
for n in [10, 20, 30]:
    amplitudes = 2 ** n
    mega_octets = amplitudes * 16 / 1000000
    print(n, "qubits :", amplitudes, "amplitudes, environ", round(mega_octets, 2), "Mo")
# Chaque amplitude complexe prend 16 octets. Ajoutez 40 dans la liste, puis relancez.

Faites tourner l’étape sur huit éléments, puis une deuxième fois, puis une troisième. La chance du marqué monte-t-elle toujours ?

Écrivez en une phrase ce qui arrive quand on fait trop d’étapes. Que dit cela du nombre d’étapes qu’un programme doit prévoir ?