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.
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
Comme verifier si une piece est truquee.
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
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 dont les réponses sont vérifiées avant affichage. Les niveaux 1–5 sont gratuits.