Algoritmo de Bernstein-Wazirani

El algoritmo de Bernstein-Vazirani es un algoritmo cuántico que resuelve el problema de encontrar un número de bits (el término cadena oculta [1] también se usa en la literatura extranjera ) escondido en una caja negra . Propuesto por Ethan Bernstein y Umesh Wazirani en 1993 . Este algoritmo resuelve el problema mucho más rápido de lo que es posible en la formulación no cuántica . El algoritmo se puede utilizar en bases de datos , ataques a cifrados de bloque , pruebas de rendimiento para computadoras cuánticas , se implementó en computadoras cuánticas IBM de 5 y 16 qubits . $norte$

Historia

El algoritmo fue propuesto por el profesor de Berkeley Vazirani y su alumno Ethan Bernstein Al describir el algoritmo, las fuentes modernas, por regla general, se refieren al discurso de Bernstein y Vazirani [2] en un simposio sobre la teoría de la computación en 1993 [3] . El algoritmo de Bernstein-Vazirani es una versión extendida del algoritmo de Deutsch-Yozhi , porque en lugar de determinar si una función pertenece a una determinada clase, equilibrada o constante (es decir, toma el valor 0 o 1 para cualquier argumento), la El algoritmo encuentra un vector "oculto" que le permite determinar de forma única las funciones de valor en cualquier punto [4] .

El algoritmo de Bernstein-Vazirani demuestra en el problema que resuelve la brecha entre los algoritmos clásicos y cuánticos en términos del menor número requerido de solicitudes al oráculo (caja negra). Incluso si permite el uso de algoritmos probabilísticos (con una probabilidad de error pre-limitada), la solución del problema clásico requerirá llamadas al oráculo, mientras que en el algoritmo cuántico basta con llamarlo [5] . $En)$ $O(1)$

Enunciado del problema de Bernstein-Vazirani

El problema clásico

Considere un oráculo que convierte un número de -bit en un bit, es decir, . ${\ estilo de visualización n}$ $f:\{0,1\}^{n}\rightarrow \{0,1\}$

Además , donde es el producto escalar de la forma: . Consideramos que una llamada de función se realiza en tiempo constante. $f(x)=a\cdot x$ $\cdot$ ${\displaystyle x\cdot y=x_{1}y_{1}\oplus x_{2}y_{2}\oplus ...\oplus x_{n}y_{n))$ $F$

Se requiere encontrar [1] . $a$

El problema cuántico

El enunciado del problema en el modelo cuántico es similar, pero el acceso al oráculo en él no se realiza directamente a través de la función , sino a través de un operador lineal que actúa sobre un sistema de qubits : $F$ $U_{f}$ $n+1$

U_{f}=\sum _{x\in \{0,1\}^{n},y\in \{0,1\}}|x\rangle \langle x|\otimes |y \oplus f(x)\rangle \langle y|

donde es el vector ket correspondiente al estado cuántico , es el vector bra correspondiente al estado cuántico , es el producto de Kronecker y es la suma módulo 2 . ${\ estilo de visualización | x \ ángulo}$ $X$ ${\ estilo de visualización \ langle x |}$ $X$ $\otimes$ $\oplus$

Los estados cuánticos y corresponden a los vectores y . El vector para el estado conjunto se puede representar como un producto [6] . ${\ estilo de visualización 0}$ $una$ ${\estilo de texto |0\rangle ={\binom {1}{0}}}$ ${\textstyle |1\rangle ={\binom {0}{1))}$ ${\displaystyle x_{1}x_{2}\puntos x_{n))$ $|x_{1}x_{2}\puntos x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \dots \otimes |x_{n}\rangle$

De forma similar al caso clásico, se supone que la llamada al oráculo, que calcula el resultado de aplicar el operador al sistema de entrada desde el qubit , se realiza en tiempo constante. $U_{f}$ $n+1$

En el caso cuántico, como en el caso clásico, se supone que , y se requiere encontrar [1] . $f(x)=a\cdot x$ $a$

Algoritmo

El problema clásico

En el caso clásico, cada llamada de Oracle devuelve un bit del número , por lo que para encontrar el número de bits , debe llamar a Oracle times. A continuación se muestra una variante de llamadas al oráculo, que le permite restaurar completamente [1] : $a$ $norte$ $a$ $norte$ $norte$ $a$

$f(1000...0_{n})=a_{1}$

$f(0100...0_{n})=a_{2}$

$\vpuntos$

$f(0000...1_{n})=a_{n}$

El número de llamadas al oráculo en el caso clásico es , donde es el número de bits del número . El simple razonamiento teórico de la información puede mostrar que este límite no se puede mejorar incluso dentro del marco de la clase BPP [1] . $En)$ $norte$ $a$

Algoritmo Cuántico

El algoritmo se basa en el operador Hadamard n-qubit :

{\textstyle H^{\otimes n}={\frac {1}{\sqrt {2^{n))))\sum \limits _{x,y\in \{0,1\}^{n }}{{(-1)}^{x\cdot y}|y\rangle \langle x|}}

Y también el hecho de que aplicar un operador a un estado de la forma , donde da como resultado el valor [1] . ${\ estilo de texto U_ {f})$ ${\textstyle |x\rangle |-\rangle =|x\rangle \otimes |-\rangle }$ ${\textstyle |-\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2))))$ ${\textstyle U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle }$

Paso a paso, el funcionamiento del algoritmo se puede representar de la siguiente manera [1] :

En el primer paso, el operador de Hadamard se aplica a un estado -qubit que consta de un estado fundamental y un bit auxiliar : $H^{\otimes {(n+1)))$ $(n+1)$ ${\ estilo de visualización | 0 \ ángulo ^ {n} | 1 \ ángulo}$ ${\ estilo de visualización | 0 \ ángulo ^ {n}}$ $|1\rango$ ${\textstyle |0\rangle ^{n}|1\rangle {\xrightarrow {H^{\otimes {(n+1))))}{\frac {1}{\sqrt {2^{n)) }}\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle }$ ;
Luego se aplica el operador al resultado del paso anterior : $U_{f}$ ${\textstyle {\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle {\xrightarrow {~U_{f}~}}{\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n} }{(-1)}^{f(x)}|x\rangle |-\rangle }$ ;
Luego se aplica , a los primeros qubits del resultado , que teniendo en cuenta que , da [4] : $norte$ ${\displaystyle H^{\otimes (n)))$ $f(x)=a\cdot x$ ${\textstyle {\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{ a\cdot x}|x\rangle |-\rangle {\xrightarrow {~H^{\otimes (n)}~}}{\frac {1}{2^{n}}}\sum \limits_{ x,y\in \{0,1\}^{n}}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y\rangle |-\rangle \sim |a\ángulo |-\ángulo }$ .

Como resultado, medir el registro de entrada dará el valor [1] . Así, en la formulación cuántica del problema basta con referirse al oráculo. En el caso general, la construcción y uso de un oráculo requiere elementos lógicos , pero esto no se tiene en cuenta al analizar el algoritmo en este modelo, ya que solo el número de llamadas al oráculo es significativo para él [1] . El algoritmo de esta forma se implementó en computadoras IBM de 5 y 16 qubits [1] , también es posible ensamblar un sistema óptico que implemente el algoritmo [7] . ${\ estilo de visualización | un \ ángulo}$ $O(1)$ ${\ estilo de visualización O (4 ^ {n})}$

Implementación del algoritmo en computadoras IBM

En cualquier implementación práctica del algoritmo de Bernstein-Vazirani, la principal dificultad es la creación de un oráculo, ya que la construcción y uso de un oráculo requiere un elemento lógico . [una] ${\ estilo de visualización O (4 ^ {n})}$

Además de la complejidad de construir un oráculo, la implementación práctica va acompañada de problemas de precisión. El sistema se probó en cadenas de 1, 2 y 3 bits, en las que el simulador IBM-Qiskit la con un 100 % de precisión Luego, se realizaron pruebas de cadenas de 1 y 2 bits en una máquina ibmqx4 de 5 qubits y una máquina ibmqx5 de 16 qubits, donde se registraron errores de cálculo y una fuerte desviación del resultado esperado [1] .

Aplicación práctica

El algoritmo de Bernstein-Wazirani se puede aplicar:

En bases de datos [8] . Con la ayuda de un algoritmo, el acceso a los datos necesarios teóricamente se puede obtener mucho más rápido que en el caso clásico.
En el ataque al cifrado de bloques [9] . El algoritmo de Bernstein-Wazirani proporciona varias formas nuevas, más avanzadas que en el caso clásico, de atacar un cifrado de bloque.
En la prueba de rendimiento para computadoras cuánticas [10] . El algoritmo se utiliza como prueba de rendimiento para una computadora cuántica de 11 qubits.

Notas

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al, 2018 , pág. 10-13.
↑ Ethan Bernstein, Umesh Vazirani. Teoría de la complejidad cuántica // Actas del vigésimo quinto simposio anual de ACM sobre teoría de la computación. - Nueva York, NY, USA: ACM, 1993. - S. 11-20 . — ISBN 978-0-89791-591-5 . -doi : 10.1145/ 167088.167097 .
↑ Hidary, 2019 , pág. 104-107.
↑ 1 2 Sevag Gharibian. Conferencia 7: Los algoritmos de Deutsch-Josza y Berstein-Vazirani // Introducción a la Computación Cuántica Verano 2018, Universidad de Paderborn. - P. 1-10 .
↑ Hidary, 2019 , pág. 12-13.
↑ Coles et al, 2018 , pág. cuatro
↑ P. Londero, K. Banaszek, IA Walmsley, C. Dorrer, M. Anderson. Implementación óptica eficiente del algoritmo de Bernstein-Vazirani (inglés) // Physical Review A. - 2004. - V. 69 , no. 1 . — S. 010302–010302.4 . — ISSN 1050-2947 . -doi : 10.1103 / PhysRevA.69.010302 .
↑ A.A. Yezhov. Algunos problemas de la neurotecnología cuántica (ruso) // Sesión científica MEPhI–2003. V Conferencia científica y técnica de toda Rusia "Neuroinformática-2003": conferencias sobre neuroinformática. Parte 2. - 2003. - S. 44-45 . Archivado desde el original el 21 de enero de 2022.
↑ Huiqin Xie, Li Yang. Uso del algoritmo de Bernstein-Vazirani para atacar cifrados en bloque // Diseños, códigos y criptografía. — 2019-05-01. — vol. 87 , edición. 5 . — pág. 1161–1182 . — ISSN 1573-7586 . -doi : 10.1007/ s10623-018-0510-5 .
↑ K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, NC Pisenti, M. Chmielewski, C. Collins, KM Hudek, J. Mizrahi, JD Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, AM Ducore, A. Blinov, SM Kreikemeier , V. Chaplin, M. Keesan, C. Monroe y J. Kim. Evaluación comparativa de una computadora cuántica de 11 qubits // Nature Communications. - 2019. - Vol. 10. - S. 5464. - doi : 10.1038/s41467-019-13534-2 .

Enlaces

Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Implementaciones de algoritmos cuánticos para principiantes // arXiv:1804.03719 [quant-ph]. — 2018.
David Deutsch, Roger Penrose. Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal (inglés) // Actas de la Royal Society of London. A. Ciencias Matemáticas y Físicas. - 1985. - 8 de julio ( vol. 400 , ed. 1818 ). — pág. 97–117 . -doi : 10.1098/ rspa.1985.0070 .
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Fortalezas y debilidades de la computación cuántica (inglés) // SIAM J. Comput .. - 1997. - Vol. 26. - Pág. 1510-1523. -doi : 10.1137/ S0097539796300933 . — arXiv : quant-ph/9701001 .
Jack D.Hidary. Computación cuántica: un enfoque aplicado . - Springer International Publishing, 2019. - P. 104-107. — ISBN 978-3030239213 . -doi : 10.1007 / 978-3-030-23922-0 .

informatica cuantica

Conceptos generales

comunicaciones cuánticas

canal cuántico
- red cuántica
criptografía cuántica
- Distribución de clave cuántica
Teletransportación de energía cuántica
teletransportación cuántica
Codificación cuántica ultradensa
LOCC
destilación cuántica

Algoritmos cuánticos

simulador cuántico
Algoritmo Deutsch-Yozhi
Algoritmo de Bernstein-Wazirani
algoritmo de Grover
Transformada cuántica de Fourier
Algoritmo de Shor
el problema de simon
Algoritmo de estimación de fase cuántica
Algoritmo de computación cuántica
recocido cuántico
Enfriamiento algorítmico
Algoritmo cuántico para resolver un sistema de ecuaciones lineales
ganancia de amplitud

Teoría de la complejidad cuántica

Modelos de computación cuántica

circuito cuántico
- puerta cuántica
Computadora cuántica unilateral
- grupo
Computación cuántica adiabática
Computadora cuántica topológica

Prevención de decoherencia

Corrección de errores cuánticos
Códigos de estabilización
Formalismo de estabilización
Código convolucional cuántico

Implementaciones físicas

óptica cuántica	Electrodinámica cuántica de cavitación Electrodinámica cuántica de contorno Computación cuántica basada en óptica lineal Protocolo KLM Muestreo bosónico
átomos superfríos	Computadora cuántica de iones absorbidos rejilla óptica
basado en la espalda	Computadora cuántica basada en resonancia magnética nuclear La computadora cuántica de Kane Computadora cuántica perdida - DiVincenzo centro NV
Computadoras cuánticas superconductoras	qubit de carga qubit de transmisión qubit de fase Transmón