Algoritmo de Bernstein–Vazirani

El Algoritmo de Bernstein–Vazirani es un algoritmo cuántico desarrollado por Ethan Bernstein y Umesh Vazirani en 1992.​ En esencia, permite conocer un string $s$ 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 $f(x)=sx\quad mod\ (2)$, donde $x$ 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 $s$, 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 $x_{n}=00...1...0$, 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 $s$. Tras repetir el proceso para todas las posiciones se obtiene el string buscado. En resumen, para un string de N bits

${\begin{cases}f(1...0)=s_{1}\\f(01...0)=s_{2}\\...\\f(0...1)=s_{N}\end{cases}}$

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 $|0\rangle$), es decir

$|00...0\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}{|x\rangle }$

El segundo paso es hacer la llamada al oráculo cuántico. Se utiliza el oráculo $U_{f}$ que realiza la transformación $|x\rangle \rightarrow (-1)^{f(x)}|x\rangle$. Con ello, el estado obtenido anteriormente queda

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}{|x\rangle }\xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{|x\rangle }$

Una vez hecho esto, el último paso consiste en volver a aplicar las puertas Hadamard y obtener así el estado $|s\rangle$

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{|x\rangle }\xrightarrow {H^{\otimes n}} |s\rangle$

En el paso anterior ha de tenerse en cuenta que ${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{|x\rangle }\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x,y=0}^{2^{n}-1}(-1)^{xs+sy}{|x\rangle }={\frac {1}{2^{n}}}\sum _{x,y=0}^{2^{n}-1}(-1)^{x(s\oplus y)}{|y\rangle }=|s\rangle$, ya que si $y\neq s$ el exponente no se anula y la suma en $x$ 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

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