Quora tiene mucho interés con la computación cuántica, y el diálogo se está volviendo difícil sin más carne técnica, por lo que decidí proporcionar un tutorial autónomo sobre el algoritmo de Deutsch.
(Realmente tampoco puedo entenderlo de Neilsen y Chuang y el artículo de Wiki también me parece bastante denso y conciso).
El algoritmo Deutsch fue el primer algoritmo de computación cuántica en mostrar una velocidad exponencial, y fundó el tema de la computación cuántica. Puedo recordar lo sorprendido que estaba de escucharlo. Cuando aprendí cuántica en la década de 1970, nadie soñó que alguna vez tendría algún uso en los cálculos. En el gran esquema de las cosas, este algoritmo es joven, ¡se desarrolló hace solo 30 años!
Así que aquí está el problema en cuestión. Tengo una función sin memoria [puntual] f (x) que aplico a dos bits. Hay dos casos y necesito probar y ver qué caso es correcto.
(A) f (x) = 0, o f (x) = 1, lo que significa que la función es constante, o
(B) f (x) = x, o f (x) = x ‘, donde primo denota un cambio de bit, lo que significa que la función tiene un número par de 1 resultados y 0 resultados.
Entonces, por ejemplo, si comenzamos con [0,0], [0,1], [1,0], [1,1] obtenemos
(A) 1,1 o 0,0 o (B) [0,0], [0,1], [1,0], [1,1] o [1,1], [1,0], [0,1], [0,0].
Debería poder convencerse fácilmente de que necesitamos dos pares de bits para resolver qué caso, (A) o (B) es cierto. Esto toma [matemáticas] 2 ^ 2 = 4 [/ matemáticas] evaluaciones de f () y 4 comparaciones. ¿Podemos hacerlo mejor con la computación cuántica? ¡Sí! Primero formamos la superposición [matemáticas] \ frac {1} {2} (| 00 \ rangle – | 01 \ rangle + | 10 \ rangle- | 11 \ rangle). [/mates]
[Aquí tenemos cada [matemática] | .. \ rangle [/ matemática] que denota un posible par de bits, siendo el coeficiente la amplitud de la superposición. Si no está familiarizado con la superposición cuántica, consulte wikipedia o Shtetl-Optimized, o
PHYS771 Computación cuántica desde Demócrito].
- ¿Cuáles son algunas posibles aplicaciones interesantes de la computadora cuántica D-Wave?
- ¿Es la renormalización un postulado fundamental de la mecánica cuántica?
- ¿Es posible la comunicación cuántica?
- ¿Cuáles son los mejores efectos cuánticos para incluir en una historia de ciencia ficción? Piense en cómo un efecto cuántico podría ser utilizado como un efecto de macroescala por una tecnología suficientemente avanzada.
- Cómo calcular resultados con los qubits cuánticos
A continuación, formamos una consulta de la función f (.) Con este estado de superposición como:
[matemáticas] s = \ frac {1} {2} (| 0f (0) \ rangle- | 0f (0) ‘\ rangle + | 1f (1) \ rangle- | 1f (1)’ \ rangle). [/ mates]
Aquí nuevamente denotamos conjugado. Si bien esto parece arbitrario, en realidad no lo es, y es la clave de todo el algoritmo. Tenga en cuenta que si denotamos el par de bits como x, y para cada posible estado en superposición, obtenemos la expresión anterior siempre que realicemos la operación y + f (x), donde el más es un operador u exclusivo. Al igual que la ecuación de Schroedinger no pide una derivación, ¡esto acaba de salir de la mente de Deutsch! Esto es lo difícil de la computación cuántica, solo está hurgando en la oscuridad tal como está hoy. Tenga en cuenta que solo necesitamos hacer una evaluación de y + f (.), Ya que todos los datos están en superposición.
El resultado final es:
[matemáticas] f (x) = 0 \ rightarrow s = \ frac {1} {2} [1, -1,1, -1], \ f (x) = 1 \ rightarrow s = \ frac {1} { 2} [- 1,1, -1,1], \\ f (x) = x \ rightarrow s = \ frac {1} {2} [1, -1, -1,1], f (x) = x ‘\ rightarrow s = \ frac {1} {2} [- 1,1,1, -1]. [/mates]
Ahora formamos un operador unitario y calculamos S = Qs donde
[matemáticas] Q = \ frac {1} {2} \ left [\ begin {array} {cccc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \ end {array } \Derecha]. [/mates]
Entonces encontramos que solo necesitamos medir el primer bit de S. Cuando lo hacemos, encontramos que si este bit es O, entonces A es verdadero, si el bit es 1, entonces B es verdadero. Este es un problema muy simple, pero muestra cómo la computación cuántica puede simplificar las cosas. Hay 4 () + f () evaluaciones y 2 mediciones y comparaciones asociadas. Para el enfoque cuántico tenemos una evaluación ‘() + f ()’ y una medición, más la implementación de Q, que puede hacerse mucho menos compleja al expresarla como un producto de operadores unitarios dispersos, reduciéndola a 2 puertas cuánticas y 3 rotaciones Hadamard.
7 años más tarde, en 1992, con Jozsa, Deutsch extendió esto a una partición más amplia en la que A) ahora es nuevamente constante, y B) está equiparticionada pero por lo demás arbitraria. Los detalles son una extensión bastante sencilla del algoritmo Deutsch. Vea la página en pdx.edu para más detalles.
Es fácil mostrar que para n bits, el enfoque clásico crece exponencialmente en complejidad, es decir, como [matemática] 2 ^ n [/ matemática] y exacto el Deutsch-Josza es lineal en n, con posible constante (sub lineal) con algún error probabilidad, pequeña pero distinta de cero. Incluso la solución exacta es una velocidad increíble. Suponga que tiene n = 1.e26 posibles patrones binarios para aplicar el algoritmo de Deutsch.
El conjunto completo de las 500 mejores supercomputadoras del mundo tiene un exo-flop por segundo disponible, o 1.e18 operaciones / seg., Vea Inicio | Sitios de supercomputadora TOP500. Entonces, si fueran cuánticos, podríamos terminar el algoritmo de Deutsch en 100 días. Pero, clásicamente, este caso requeriría más operaciones que los átomos estimados en todo el universo, ¡o 1.e52 veces más operaciones! ¡Equivalentemente necesitaríamos toda la vida del universo funcionando en 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000 veces más supercomputadoras que existen actualmente en la tierra para obtener la respuesta!
