Algoritmo de Bernstein-Vazirani

Algoritmo cuántico

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 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]

Planteamiento del problema

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

Algoritmo

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

${\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 consultas de la función para encontrar , con la computación cuántica solo se necesita una consulta. El algoritmo cuántico es el siguiente: ^[2] ${\displaystyle n}$ ${\displaystyle s}$

Aplique una transformada de Hadamard al estado del qubit para obtener ${\displaystyle n}$ ${\displaystyle |0\rangle ^{\otimes n}}$

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

A continuación, aplique 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 adición módulo dos). Esto transforma la superposición en ${\displaystyle U_{f}}$ ${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }$ ${\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }$ ${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }$ ${\displaystyle \oplus }$

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

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

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

${\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 porque, para un particular , ${\displaystyle |s\rangle }$ ${\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{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.}$

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

Se ha propuesto una generalización del problema de Bernstein-Vazirani que implica 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 fallan completamente en la resolución del problema en el caso general.

Véase también

• Problema de función lineal oculta

Referencias

1. Ethan Bernstein y Umesh Vazirani (1997). "Teoría de la complejidad cuántica". Revista SIAM de informática . 26 (5): 1411–1473. doi :10.1137/S0097539796300921.
2. SD Fallek, CD Herold, BJ McMahon, KM Maller, KR Brown y JM Amini (2016). "Implementación de transporte del algoritmo Bernstein–Vazirani con cúbits iónicos". New Journal of Physics . 18 . arXiv : 1710.01378 . doi : 10.1088/1367-2630/aab341 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Alok Shukla y Prakash Vedula (2023). "Una generalización del algoritmo de Bernstein-Vazirani con múltiples claves secretas y un oráculo probabilístico". Procesamiento de información cuántica . 22:244 (6): 1–18. arXiv : 2301.10014 . doi :10.1007/s11128-023-03978-3.