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.
Míralo en movimiento
Tras registrarte gratis vuelves directamente a este concepto.
Qué significa
Determina si una funcion es constante o balanceada con 1 consulta en vez de 2^(n-1)+1.Analogía cotidiana
Imagina una caja sellada de interruptores conectada a una lámpara que es siempre igual (constante) o se enciende exactamente con la mitad de las entradas (equilibrada). Clásicamente puede que tengas que probar más de la mitad de las entradas; Deutsch-Jozsa hace interferir las amplitudes y revela con una consulta qué tipo de caja es, sin decirte ninguna salida individual.
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
Conceptos relacionados
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 que revisa sus respuestas e indica qué tan seguras son. Los niveles 1–5 son gratuitos.