Fuente verificadaNivel 3
Algoritmo de Deutsch-Jozsa
El algoritmo de Deutsch-Jozsa determina si una funcion booleana es constante o balanceada con solo una consulta.
Qué significa
Determina si una funcion es constante o balanceada con 1 consulta en vez de 2^(n-1)+1.Analogía cotidiana
Como verificar si una moneda es justa.
Como verificar una urna sellada.
Errores comunes
- La aceleracion es respecto a algoritmos deterministas.
- No dice que calcula la funcion.
Puntos clave
- 1 consulta oraculo para constante vs balanceada.
- Primer algoritmo probando ventaja cuantica.
- Usa superposicion e interferencia.
Comprueba tu comprensión
¿Cuantas consultas oraculo?
- A.n
- B.2^n
- C.1
- D.log(n)
Ver la respuesta
Respuesta: C. 1
Por qué: Solo 1 consulta oraculo.
Se apoya en
Fuente primaria: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167
Apréndelo con la práctica
Este concepto forma parte de un plan de 46 niveles, con un simulador interactivo y Lumen, un tutor cuyas respuestas se verifican antes de mostrarse. Los niveles 1–5 son gratuitos.