Algoritmo Deutsch-Yozhi

El algoritmo Deutsch-Joja (también conocido como algoritmo Deutsch-Joza ) es un algoritmo cuántico propuesto por David Deutsch y Richard Joja en 1992 , y uno de los primeros algoritmos cuánticos . El algoritmo se basa en el fenómeno del entrelazamiento cuántico y el principio de superposición , por lo que demuestra una superioridad cuántica , una operación mucho más eficiente en comparación con los algoritmos clásicos conocidos.

El algoritmo de Deutsch es la primera versión del algoritmo desarrollado por Deutsch en 1985 ; considera una funciónde una variable. $f(x_{1})$

Reto

Se sabe que una función booleana es constante (toma el mismo valor para todos los conjuntos de argumentos) o balanceada (para la mitad de los conjuntos de argumentos toma el valor , para la otra mitad toma ). Es necesario determinar el tipo de función refiriéndose al oráculo que evalúa la función el menor número de veces posible. Además, para abreviar, el conjunto completo también se puede denotar con un número de a con la notación binaria correspondiente . ${\ estilo de visualización f (x_ {1}, x_ {2}, \ puntos, x_ {n})}$ ${\ estilo de visualización 0}$ $una$ $x_{1},x_{2},\puntos,x_{n}$ ${\ estilo de visualización 0}$ $2^{n}-1$

Para obtener una respuesta exacta, cualquier algoritmo determinista clásico en el peor de los casos necesita hacer llamadas al oráculo, ya que los primeros cálculos pueden dar el mismo valor, a pesar de que la función está balanceada. El algoritmo probabilístico clásico requerirá menos cálculos para garantizar una alta probabilidad de obtener la respuesta correcta, pero también alcanzará la unidad solo después de no menos de cálculos. $2^{{n-1}}+1$ $2^{{n-1}}$ $2^{{n-1}}+1$

En el entorno cuántico, el cálculo de una función se produce en forma de llamada a un oráculo cuántico , que produce una transformación unitaria que actúa sobre un conjunto de qubits que actúan como argumentos de la función, así como un qubit objetivo , sobre que se reflejarán los cálculos. El resultado de tal transformación para cualquier estado propio es el conjunto , donde es la designación del “o” exclusivo , correspondiente al resultado de la operación de negación controlada de un qubit con la ayuda de un qubit . Dado que las transformaciones unitarias son lineales , el resultado de una transformación dada para una superposición de estados propios se define como $U_{f}$ $|x_{1}x_{2}\dots x_{n}\rangle |y\rangle =|x\rangle |y\rangle$ $norte$ $x_{1},x_{2},\puntos,x_{n}$ $y$ ${\ estilo de visualización | x \ ángulo}$ $|x\rangle |y\oplus f(x)\rangle$ $\oplus$ ${\ estilo de visualización | y \ ángulo}$ ${\ estilo de visualización | f (x) \ rangle}$ $|x\rangle =\alpha _{0}|0\rangle +\ldots +\alpha _{2^{n}-1}|2^{n}-1\rangle$ $U_{f}(|x\rangle |y\rangle )=\alpha _{0}|0\rangle |y\oplus f(0)\rangle +\ldots +\alpha _{2^{n }-1}|{2^{n}-1}\rangle |y\oplus f(2^{n}-1)\rangle .$

Para el algoritmo Deutsch-Jozhi, una sola llamada al oráculo cuántico es suficiente para resolver el problema de manera confiable.

Algoritmo

El algoritmo se basa en la transformada de Hadamard , que da como resultado superposiciones de estados propios de qubit ${\ estilo de texto H}$

|+\rangle =H|0\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle +|1\rangle {\big )},

|-\rangle =H|1\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}.

Si, al acceder al oráculo, el qubit de destino está en el estado , el oráculo implementa la llamada consulta de fase, cuyo resultado para los estados propios es multiplicar el estado completo por [1] : ${\ estilo de visualización |-\ ángulo}$ ${\ estilo de visualización (-1) ^ {f (x)))$

U_{f}{\big (}|x\rangle |-\rangle {\big )}={\frac {1}{\sqrt {2))}|x\rangle {\big (}| f(x)\rangle -|1\oplus f(x)\rangle {\big )}=(-1)^{f(x)}|x\rangle |-\rangle .

Así, en el caso de superposición de estados, la consulta de fase invierte la fase de todos los estados correspondientes a , y deja sin cambios los estados correspondientes a . Como argumento de consulta de fase, el algoritmo Deutsch-Joji utiliza el estado $X$ $f(x)=1$ $f(x)=0$

H^{\otimes n}|0\rangle ^{\otimes n}=|+\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}|x\rangle ,

que es una superposición uniforme de todos los estados propios de un conjunto de qubits. Aquí denota la exponenciación a través de un producto tensorial (Kronecker) . El resultado de aplicar una consulta de fase a dicho estado es $norte$ ${\ estilo de visualización \ veces n}$ $norte$

U_{f}{\big (}|+\rangle ^{\otimes n}|-\rangle {\big )}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle |-\rangle .

Después de volver a aplicar la transformación a los primeros qubits, la amplitud del estado será igual a ${\displaystyle H^{\otimes n))$ $norte$ ${\displaystyle |0\rangle ^{\otimes n))$

{\frac {1}{2^{n}}}\sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)},

es decir, con o con , o si la función está balanceada. Por lo tanto, verificar el saldo de una función es equivalente a verificar que todos los qubits estén en el estado al final del algoritmo. $una$ $f(x)=0$ $-una$ $f(x)=1$ ${\ estilo de visualización 0}$ $|0\rango$

En otras palabras, el algoritmo es la aplicación del operador al vector cero y la medida del estado del registro. Si todos los bits de registro son iguales , entonces el valor de la función no depende de , de lo contrario, la función está balanceada. ${\displaystyle |0\rangle ^{\otimes n))$ ${\displaystyle H^{\otimes n}U_{f}H^{\otimes n))$ ${\ estilo de visualización 0}$ $f(x)$ $X$

Si la función está desequilibrada, el algoritmo puede dar la respuesta "constante" con una probabilidad que crece con el aumento de la diferencia entre el número de "0" y "1" [2] . $F$

El funcionamiento del algoritmo en el ejemplo del problema de Deutsch

La entrada al algoritmo es una función booleana de una variable . Hay cuatro funciones de este tipo [1] : $f(x)$

No.	$f(0)$	$f(1)$
una	0	0	$f(x) \equiv 0$
2	una	una	$f(x)\equivalente a 1$
3	0	una	$f(x) = x$
cuatro	una	0	${\ estilo de visualización f (x) = \ neg x}$

Las funciones 1 y 2 son constantes y las funciones 3 y 4 están balanceadas.

En el primer paso , el qubit recibe un estado cero:

|\varphi \rangle =1\cdot |0\rangle +0\cdot |1\rangle .

La aplicación de la transformada de Hadamard da

|\varphi \rangle ={\frac {1}{\sqrt {2}}}\cdot |0\rangle +{\frac {1}{\sqrt {2}}}\cdot |1\rangle .

En principio, sería posible asignar inmediatamente dicho estado a un qubit, pero técnicamente es más fácil establecer primero el estado cero y luego transformarlo usando transformaciones unitarias a la forma deseada.

Una llamada de fase a una función da el siguiente estado: ${\ Displaystyle O_ {f}}$ $F$

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{\sqrt {2))}\cdot |0\rangle +(-1)^{f (1)}\cdot {\frac {1}{\sqrt {2))}\cdot |1\rangle .

La segunda transformación de Hadamard conduce al siguiente estado:

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{2))\cdot {\big (}|0\rangle +|1\rangle {\ grande )}+(-1)^{f(1)}\cdot {\frac {1}{2}}\cdot {\grande (}|0\rangle -|1\rangle {\grande )}=

=\left((-1)^{f(0)}+(-1)^{f(1)}\right)\cdot {\frac {1}{2))\cdot |0\ rangle +\left((-1)^{f(0)}-(-1)^{f(1)}\right)\cdot {\frac {1}{2))\cdot |1\rangle .

Al medir el estado de un qubit, obtenemos 0 para funciones constantes y 1 para balanceadas:

No.	$f(0)$	$f(1)$	estado qubit ${\ estilo de visualización \| \ varphi \ rangle}$	Probabilidad de obtener 0	probabilidad de obtener 1
una	${\ estilo de visualización 0}$	${\ estilo de visualización 0}$	${\grande (}(-1)^{0}+(-1)^{0}{\grande)}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \grande (}(-1)^{0}-(-1)^{0}{\grande)}\cdot {\frac {1}{2))\cdot \|1\rangle =1\cdot \|0 \rangle +0\cdot \|1\rangle$	${\ estilo de visualización 1 ^ {2} = 1}$	${\ estilo de visualización 0}$
2	$una$	$una$	${\grande (}(-1)^{1}+(-1)^{1}{\grande )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \grande (}(-1)^{1}-(-1)^{1}{\grande)}\cdot {\frac {1}{2))\cdot \|1\rangle =-1\cdot \| 0\rangle +0\cdot \|1\rangle$	${\ estilo de visualización (-1) ^ {2} = 1}$	${\ estilo de visualización 0}$
3	${\ estilo de visualización 0}$	$una$	$((-1)^{0}+(-1)^{1})\cdot {\frac {1}{2}}\cdot \vert 0\rangle +((-1)^{0}-( -1)^{1})\cdot {\frac {1}{2}}\cdot \vert 1\rangle =0\cdot \vert 0\rangle +1\cdot \vert 1\rangle$	${\ estilo de visualización 0}$	$1^{{2}}=1$
cuatro	$una$	${\ estilo de visualización 0}$	${\grande (}(-1)^{1}+(-1)^{0}{\grande)}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \grande (}(-1)^{1}-(-1)^{0}{\grande)}\cdot {\frac {1}{2))\cdot \|1\rangle =0\cdot \|0 \rangle -1\cdot \|1\rangle$	${\ estilo de visualización 0}$	${\ estilo de visualización (-1) ^ {2} = 1}$

Literatura

Lobo R. d. Computación cuántica (inglés) : notas de clase - 2019. - 176 p. arXiv : 1907.09415

Notas

↑ 1 2 M. Lento . Quantum Algorithms: Opportunities and Limitations, Lecture 2 ( Archivado el 10 de junio de 2011 en Wayback Machine ), p. 12-13. - San Petersburgo, primavera de 2011.
↑ M. Lento . Quantum Algorithms Lecture 2 Archivado el 26 de abril de 2013 en Wayback Machine .

Algoritmos cuánticos
Algoritmo de Shor algoritmo de Grover Algoritmo Deutsch-Yozhi problema feynman Algoritmo de Zalka-Wiesner recocido cuántico

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