Accueil▸Informatique Quantique▸Algorithme de Deutsch–Jozsa — Une Requête Bat le Classique

🧮 Algorithme de Deutsch–Jozsa — Une Requête Bat le Classique

Simulateur interactif de l'algorithme de Deutsch–Jozsa : choisissez un oracle constant ou équilibré, observez la transformée de Walsh–Hadamard décider la réponse avec une seule requête quantique.

Informatique Quantique2DAvancé60 IPS

À propos de l'Algorithme de Deutsch–Jozsa

L'algorithme de Deutsch–Jozsa répond à un simple problème de promesse : étant donné une fonction en boîte noire f qui associe n bits à un seul bit et qui est garantie d'être soit constante (même sortie pour chaque entrée) soit équilibrée (0 pour exactement la moitié des entrées et 1 pour l'autre moitié), décider laquelle. Un ordinateur classique qui ne peut interroger f que comme une boîte noire peut avoir besoin de vérifier plus de la moitié des 2ⁿ entrées avant d'être certain — jusqu'à 2⁽ⁿ⁻¹⁾ + 1 requêtes dans le pire des cas. Un ordinateur quantique règle la même question avec un seul appel à l'oracle, en encodant f dans une phase et en laissant l'interférence concentrer toute la probabilité au résultat tout-zéro exactement quand f est constante.

Ce simulateur construit l'état quantique exact à la main : il applique des portes de Hadamard pour atteindre une superposition égale, encode l'oracle choisi comme un basculement de signe sur chaque état de base, puis effectue une véritable transformée de Walsh–Hadamard pour obtenir les probabilités de mesure finales. La bannière de verdict lit la probabilité de mesurer la chaîne tout-zéro en direct — proche de 1 signifie constante, proche de 0 signifie équilibrée — exactement comme fonctionne l'algorithme réel. Il reste un exemple fondateur dans les cours d'informatique quantique car ce fut la première démonstration rigoureuse que l'interférence quantique peut fournir une accélération inconditionnelle par rapport à toute stratégie classique, des années avant que l'algorithme de Shor ne rende l'idée célèbre.

Questions Fréquentes

Quel problème l'algorithme de Deutsch–Jozsa résout-il ?

Il décide, avec certitude, si une fonction booléenne en boîte noire f est constante ou équilibrée, en utilisant le moins de requêtes possible à f. La fonction est promise à l'avance d'être l'une ou l'autre, donc l'algorithme n'a jamais besoin de gérer une fonction qui n'est ni l'une ni l'autre.

Pourquoi un ordinateur classique est-il tellement plus lent pour cela ?

Classiquement, vous devez interroger f sur les entrées une par une. Si vous obtenez par hasard la même sortie 2⁽ⁿ⁻¹⁾ fois de suite, vous ne pouvez toujours pas être sûr que la fonction est constante — la prochaine requête pourrait révéler une valeur différente. Ce n'est qu'après avoir vérifié un peu plus de la moitié des entrées, 2⁽ⁿ⁻¹⁾ + 1 requêtes dans le pire des cas, que vous pouvez être certain.

Comment une seule requête quantique décide-t-elle de la réponse ?

La superposition permet d'appliquer l'oracle à toutes les 2ⁿ entrées simultanément, encodant f(x) dans une phase plutôt qu'un basculement de bit. Une seconde couche de portes de Hadamard fait ensuite interférer ces phases ensemble. Si f est constante, chaque chemin s'additionne de manière constructive au résultat tout-zéro, lui donnant une probabilité de 1. Si f est équilibrée, les chemins s'annulent complètement là, donnant une probabilité de 0.

Que signifient le diagramme à barres et la valeur P(0…0) ?

Le diagramme à barres montre la probabilité de mesurer chaque chaîne de sortie possible. La barre à y = 0 (la chaîne tout-zéro) est mise en évidence car elle seule porte le verdict : ce simulateur lit cette probabilité unique en direct et rapporte CONSTANTE lorsqu'elle est proche de 1 ou ÉQUILIBRÉE lorsqu'elle est proche de 0.

⚙ Sous le capot

Quantum ComputingQuantum AlgorithmCircuit DiagramCanvas 2DHadamard Transform

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install