Algoritmo de Bernstein–Vazirani

En el caso clásico, es necesario utilizar tantos strings de entrada como bits tenga ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle s}$. Tras repetir el proceso para todas las posiciones se obtiene el string buscado. En resumen, para un string de N bits

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

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

${\displaystyle |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 ${\displaystyle U_{f}}$ que realiza la transformación ${\displaystyle |x\rangle \rightarrow (-1)^{f(x)}|x\rangle }$. Con ello, el estado obtenido anteriormente queda

${\displaystyle {\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 ${\displaystyle |s\rangle }$

${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle y\neq s}$ el exponente no se anula y la suma en ${\displaystyle x}$ cancela todos los términos entre sí. Otra forma de verlo es que una puerta Hadamard es su propia inversa.

• Algoritmo de Deutsch-Jozsa

• 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

• https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html