El algoritmo Bernstein-Vazirani , que resuelve el problema Bernstein-Vazirani, es un algoritmo cuántico inventado por Ethan Bernstein y Umesh Vazirani en 1992. [1] Es una versión restringida del algoritmo Deutsch-Jozsa donde en lugar de distinguir entre dos clases diferentes de funciones , intenta aprender una cadena codificada en una función. [2] El algoritmo de Bernstein-Vazirani fue diseñado para probar una separación de oráculo entre las clases de complejidad BQP y BPP . [1]
Planteamiento del problema
Dado un oráculo que implementa una función en el cual se promete ser el producto escalar entre y una cadena secreta módulo 2,, encontrar .
Algoritmo
Clásicamente, el método más eficiente para encontrar la cadena secreta es evaluando la función veces con los valores de entrada para todos : [2]
En contraste con la solución clásica que necesita al menos consultas de la función para encontrar , solo se necesita una consulta utilizando la computación cuántica. El algoritmo cuántico es el siguiente: [2]
Aplicar una transformación de Hadamard al estado qubit Llegar
A continuación, aplica el oráculo. que transforma . Esto se puede simular a través del oráculo estándar que transforma aplicando este oráculo a . ( denota suma mod dos.) Esto transforma la superposición en
Se aplica otra transformada de Hadamard a cada qubit, lo que hace que para qubits donde , su estado se convierte de a y para qubits donde , su estado se convierte de a . Para obtener, una medida en la base estándar () se realiza en los qubits.
Gráficamente, el algoritmo se puede representar mediante el siguiente diagrama, donde denota la transformación de Hadamard en qubits:
La razón por la que el último estado es es porque, para un particular ,
Desde solo es cierto cuando , esto significa que la única amplitud distinta de cero está en . Entonces, medir la salida del circuito en la base computacional produce la cadena secreta.
Ver también
Referencias
- ↑ a b Ethan Bernstein y Umesh Vazirani (1997). "Teoría de la complejidad cuántica". Revista SIAM de Computación . 26 (5): 1411–1473. doi : 10.1137 / S0097539796300921 .
- ^ a b c SD Fallek, CD Herold, BJ McMahon, KM Maller, KR Brown y JM Amini (2016). "Implementación de transporte del algoritmo de Bernstein-Vazirani con qubits de iones" . Nueva Revista de Física . 18 . doi : 10.1088 / 1367-2630 / aab341 .CS1 maint: varios nombres: lista de autores ( enlace )