Algoritmo de Bernstein–Vazirani
El Algoritmo de Bernstein–Vazirani es un algoritmo cuántico desarrollado por Ethan Bernstein y Umesh Vazirani en 1992.[1] En esencia, permite conocer un string binario, esto es, una cadena de caracteres compuesta de ceros y unos (por ejemplo: s = 0010110101001), que está contenido en una función. Más concretamente, se sabe que dicha función toma la forma , donde es otro string y la multiplicación se entiende como producto binario. Este algoritmo funciona de manera similar al de Deutsch-Jozsa, pero en vez de tratar de distinguir entre clases de funciones, busca el string que caracteriza a la función dada. Supongamos a modo de ejemplo que se participa en un juego consistente en encontrar un número oculto escrito en código binario. Con la versión clásica del algoritmo, la única manera de obtener la solución sería ir haciendo comprobaciones del número oculto bit a bit, lo cual requiere al menos N ejecuciones, siendo N el número de bits de s (esto se denota como O(N) en teoría de la complejidad computacional). En el caso del algoritmo de Bernstein-Vazirani, si se consigue codificar dicho número en el string s, una única ejecución del algoritmo bastaría para encontrar el número completo.
La importancia de este algoritmo radica en la superioridad que muestra frente a su equivalente clásico, pudiéndose encontrar el string buscado tras una única ejecución.
Solución clásica
En el caso clásico, es necesario utilizar tantos strings de entrada como bits tenga , esto es, el número de iteraciones depende de la longitud del string buscado. La manera óptima de obtener dicho string sería por tanto ejecutar la función con bits de la forma , donde el 1 se encuentra en el n-ésimo bit, de tal forma que la función devolvería el bit colocado en la misma posición del string . Tras repetir el proceso para todas las posiciones se obtiene el string buscado. En resumen, para un string de N bits
Algoritmo
La versión cuántica del algoritmo parte de un estado generado tras aplicar una puerta Hadamard a todos los cúbits (que se sobreentienden inicialmente en el estado ), es decir
El segundo paso es hacer la llamada al oráculo cuántico. Se utiliza el oráculo que realiza la transformación . Con ello, el estado obtenido anteriormente queda
Una vez hecho esto, el último paso consiste en volver a aplicar las puertas Hadamard y obtener así el estado
En el paso anterior ha de tenerse en cuenta que , ya que si el exponente no se anula y la suma en cancela todos los términos entre sí. Otra forma de verlo es que una puerta Hadamard es su propia inversa.
Véase también
- Algoritmo de Deutsch-Jozsa
Referencias
- ↑ Bernstein, Ethan; Vazirani, Umesh (1997-10). «Quantum Complexity Theory». SIAM Journal on Computing (en inglés) 26 (5): 1411-1473. ISSN 0097-5397. doi:10.1137/S0097539796300921. Consultado el 14 de noviembre de 2021.
Bibliografía
- Michael A. Nielsen e Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Reino Unido, 2000, ISBN 0-521-63503-9
- Alberto Galindo y Miguel Ángel Martin-Delgado (2002). Information and computation: classical and quantum aspects. Reviews of Modern Physics, 74(2), 347
Enlaces externos
- https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html
Datos: Q65053013