Algoritmo de Bernstein-Vazirani

El algoritmo de Bernstein-Vazirani , que resuelve el problema de Bernstein-Vazirani , es un algoritmo cuántico inventado por Ethan Bernstein y Umesh Vazirani en 1997. ^{[ 1 ]} Es una versión restringida del algoritmo de 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 demostrar una separación de oráculo entre las clases de complejidad BQP y BPP . ^{[ 1 ]}

Dado un oráculo que implementa una función${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$en el cual${\displaystyle f(x)}$se promete que será el producto escalar entre${\displaystyle x}$y una cadena secreta${\displaystyle s\in \{0,1\}^{n}}$módulo 2,${\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}}$, encontrar${\displaystyle s}$.

Clásicamente, el método más eficiente para encontrar la cadena secreta es evaluando la función.${\displaystyle n}$veces con los valores de entrada${\displaystyle x=2^{i}}$a pesar de${\displaystyle i\in \{0,1,\dots ,n-1\}}$: ^{[ 2 ]}

${\displaystyle {\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}}$

A diferencia de la solución clásica que necesita al menos${\displaystyle n}$consultas de la función para encontrar${\displaystyle s}$, solo se necesita una consulta utilizando computación cuántica. El algoritmo cuántico es el siguiente: ^{[ 2 ]}

Aplicar una transformación de Hadamard al${\displaystyle n}$estado del cúbit${\displaystyle |0\rangle ^{\otimes n}}$Llegar

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle .}$

A continuación, aplique el oráculo.${\displaystyle U_{f}}$que transforma${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }$Esto se puede simular mediante el oráculo estándar que transforma${\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }$aplicando este oráculo a${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }$. (${\displaystyle \oplus }$(denota la suma módulo dos.) Esto transforma la superposición en

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

Se aplica otra transformación de Hadamard a cada cúbit, lo que hace que para los cúbits donde${\displaystyle s_{i}=1}$, su estado se convierte de${\displaystyle |-\rangle }$a${\displaystyle |1\rangle }$y para cúbits donde${\displaystyle s_{i}=0}$, su estado se convierte de${\displaystyle |+\rangle }$a${\displaystyle |0\rangle }$Para obtener${\displaystyle s}$, una medición en la base estándar (${\displaystyle \{|0\rangle ,|1\rangle \}}$) se realiza en los cúbits.

Gráficamente, el algoritmo puede representarse mediante el siguiente diagrama, donde${\displaystyle H^{\otimes n}}$denota la transformada de Hadamard en${\displaystyle n}$cúbits:

${\displaystyle |0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle }$

La razón por la que el último estado es${\displaystyle |s\rangle }$es porque, para un caso particular${\displaystyle y}$,

${\displaystyle {\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ si }}s\oplus y={\vec {0}},\,0{\text{ en caso contrario}}.}$

Desde${\displaystyle s\oplus y={\vec {0}}}$es cierto solo cuando${\displaystyle s=y}$, esto significa que la única amplitud distinta de cero está en${\displaystyle |s\rangle }$. Por lo tanto, al medir la salida del circuito en la base computacional se obtiene la cadena secreta.${\displaystyle s}$.

Se ha propuesto una generalización del problema de Bernstein-Vazirani que consiste en encontrar una o más claves secretas utilizando un oráculo probabilístico. ^{[ 3 ]} Este es un problema interesante para el cual un algoritmo cuántico puede proporcionar soluciones eficientes con certeza o con un alto grado de confianza, mientras que los algoritmos clásicos no logran resolver el problema en el caso general.

El problema de Bernstein-Vazirani se suele plantear en su versión sin decisión . En esta forma, es un ejemplo de un problema resoluble por una máquina de Turing cuántica (QTM) con${\displaystyle O(1)}$consultas al oráculo del problema, pero para las cuales cualquier algoritmo de máquina de Turing probabilística (PTM) debe realizar${\displaystyle \Omega (n)}$consultas.

Para proporcionar una separación entre BQP y BPP , el problema debe reformularse como un problema de decisión (ya que estas clases de complejidad se refieren a problemas de decisión). Esto se logra con una construcción recursiva y la inclusión de un segundo oráculo aleatorio. ^{[ 1 ] [ 4 ]} El problema de decisión resultante es resoluble por un QTM con${\displaystyle O(n)}$consultas al oráculo del problema, mientras que un PTM debe realizar${\displaystyle \Omega (n^{\log n})}$consultas para resolver el mismo problema. Por lo tanto, Bernstein-Vazirani proporciona una separación superpolinómica entre BPP y BQP.

El circuito cuántico que se muestra aquí es un ejemplo sencillo de cómo se puede implementar el algoritmo de Bernstein-Vazirani en Python utilizando Qiskit , un marco de desarrollo de software de computación cuántica de código abierto de IBM.

• Problema de la función lineal oculta
• El problema de Simon