Source vérifiéeNiveau 3
Algorithme de Deutsch-Jozsa
L'algorithme de Deutsch-Jozsa determine si une fonction booleenne est constante ou equilibree avec une seule requete.
Le voir en mouvement
Après une inscription gratuite, vous revenez directement à ce concept.
Ce que cela signifie
Determine si une fonction est constante ou equilibree avec 1 requete au lieu de 2^(n-1)+1.Analogie du quotidien
Imaginez une boîte scellée d'interrupteurs reliée à une lampe qui est soit toujours identique (constante), soit allumée pour exactement la moitié des entrées (équilibrée). Classiquement, il peut falloir tester plus de la moitié des entrées ; Deutsch-Jozsa fait interférer les amplitudes et révèle en une requête de quel type de boîte il s'agit — sans donner aucune sortie individuelle.
Comme verifier une urne scellee.
Idées reçues fréquentes
- L'acceleration est par rapport aux algorithmes deterministes.
- Ne dit pas ce que la fonction calcule.
À retenir
- 1 requete oracle pour constante vs equilibree.
- Premier algorithme prouvant l'avantage quantique.
- Utilise superposition et interference.
Vérifiez votre compréhension
Combien de requetes oracle?
- A.n
- B.2^n
- C.1
- D.log(n)
Voir la réponse
Réponse: C. 1
Pourquoi: 1 seule requete oracle.
S’appuie sur
Notions liées
Source primaire: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167
Apprendre en pratiquant
Ce concept fait partie d’un cursus de 46 niveaux, avec un simulateur interactif et Lumen — un tuteur qui contrôle ses réponses et indique leur degré de certitude. Les niveaux 1–5 sont gratuits.