¿Cuál es el algoritmo cuántico más fácil de aprender para principiantes?

Pregunta : ¿Cuál es el algoritmo cuántico más fácil de aprender para principiantes?

En mi humilde opinión, el más fácil para comenzar es el algoritmo Deutsch-Jozsa.

Es uno de los primeros ejemplos de un algoritmo cuántico que es exponencialmente más rápido que cualquier algoritmo clásico determinista posible. También es un algoritmo determinista, lo que significa que siempre produce una respuesta, y esa respuesta siempre es correcta.

El problema es el siguiente: se nos da una computadora cuántica de caja negra (llamada oráculo) que implementa alguna función [matemática] {\ displaystyle f: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \ }}[/mates]. Básicamente, toma valores binarios de n dígitos como entrada y produce un 0 o un 1 como salida para cada valor. Se nos promete que la función es constante (0 en todas las entradas o 1 en todas las entradas) o equilibrada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad); la tarea es determinar si [math] {\ displaystyle f} [/ math] es constante o equilibrado usando el oráculo.

Este es el algoritmo cuántico que uno puede aprender con una base muy básica en computación cuántica.

Si quieres algo más avanzado, ¡sigue leyendo!

Los algoritmos cuánticos se clasifican en términos generales como:

  1. Algoritmos cuánticos basados ​​en la transformada cuántica de Fourier
    que incluye el popular algoritmo de factorización de Shor.
  2. Algoritmos cuánticos basados ​​en amplificación de amplitud.
    que incluye el algoritmo de búsqueda de Grover.
  3. y algoritmos cuánticos basados ​​en caminatas cuánticas
    que incluye el problema de distinción de elementos.

Nota : le sugiero que comience estudiando el primer capítulo de un libro elegante y completo, a saber, Computación Cuántica e Información Cuántica de Nielsen y Chuang (N&C).

Es un libro increíble para obtener la perspectiva de “información” y “computación” incluso para ideas simples de mecánica cuántica.

Si siente que se siente cómodo tanto con las ideas / álgebra / notación como con los cálculos involucrados en la sección de teletransportación cuántica, entonces sabe que está listo para aprender los algoritmos cuánticos.

Si no se siente tan cómodo con estas ideas, puede seguir las instrucciones aquí: la respuesta de Namit Anand a ¿Cómo puedo aprender la computación cuántica desde cero?

Ahora, personalmente, en orden de dificultad, iría con el algoritmo de búsqueda de Grover [matemáticas] \ leq [/ matemáticas] algoritmo de factorización de Shor.

Por lo tanto, sugeriría que pueda comenzar con el sexto capítulo de N&C que le enseñará desde cero sobre los algoritmos de búsqueda Quantum (el algoritmo de búsqueda de Grover está aquí). Si desea aprender el algoritmo de Shor, vaya al capítulo anterior sobre la transformación cuántica de Fourier y sus aplicaciones, que también analizará el popular problema de los subgrupos ocultos.

Algunas otras fuentes para aprender estas cosas son:

Algunas video conferencias:

Si desea un buen conjunto breve de video conferencias introductorias para apreciar los temas, intente este curso en línea en edX por el Prof. Umesh Vazirani (uno de los pioneros en el campo).

Algunas notas de clase:

Cualquier mención de información cuántica y apuntes de computación está incompleta sin los legendarios apuntes de John Preskill: información del curso de física 219. (¡Una generación de teóricos de la información cuántica aprendió el tema a través de ellos y muchos aún lo hacen! ¡Muy recomendable!)

Si está dispuesto a mirar algunas notas de clase de posgrado, entonces sugeriría: Notas de conferencia de John Watrous. (¡De hecho, son muy perspicaces!)

Espero que ayude.

¡Paz!

Edición 1: se eliminó la conferencia Información y Entropía, que aunque es útil, no es exactamente el tema.
Nota: Otra introducción al tema: una introducción a la computación cuántica por KLM.

IBM Quantum Experience ofrece el algoritmo de Grover como el primer algoritmo completo en su tutorial. Puede ser necesario pasar por el proceso de solicitud de IBM para obtener acceso a su tutorial. El valor de ese enfoque es que tiene acceso a su simulador de computadora cuántica para que, a medida que aprenda, pueda probar sus intentos.

Algoritmo de Grover como se explica en Wiki.

  1. Inicializar el sistema al estado
  2. Realice las siguientes “iteraciones de Grover” r ( N ) veces. La función r ( N ), que es asintóticamente O ( N 1/2), se describe a continuación.
  3. Realice la medición Ω. El resultado de la medición será un valor propio λω con una probabilidad cercana a 1 para N ≫ 1. De λω , se puede obtener ω .

[1405.7479v2] Un algoritmo cuántico para la decodificación de Viterbi de códigos convolucionales clásicos es la primera explicación completa que he encontrado para un algoritmo para el que podría tener un uso real.

En este artículo, el algoritmo propuesto se aplica a la decodificación de códigos convolucionales clásicos, por ejemplo; longitud de restricción grande Q y cuadros decodificadores cortos N.

La adición en una computadora cuántica también podría ser útil.

Se presenta un nuevo método para calcular sumas en una computadora cuántica. Esta técnica utiliza la transformación cuántica de Fourier y reduce el número de qubits necesarios para la adición al eliminar la necesidad de bits de transporte temporales. Este enfoque también permite la adición de un número clásico a una superposición cuántica sin codificar el número clásico en el registro cuántico. Este método también permite la paralelización masiva en su ejecución.

Grover es el más simple, pero necesitará comprender la mecánica cuántica para comprender los algoritmos cuánticos. Y necesita comprender varias otras cosas (cálculo, álgebra lineal, ecuaciones diferenciales, etc.) para hacerlo. Dependiendo de sus antecedentes, puede llevar mucho tiempo llegar a un punto en el que comprenda los algoritmos cuánticos.

No recuerdo quién recomendó el último Capítulo del libro escrito por Sanjoy Dasgupta.

He terminado de leer ese capítulo, y realmente me gustó como principiante. Siento que tengo una idea sobre el mecanismo de la computación cuántica después de leerlo. Omitió algunos detalles complicados, y como resultado es claro y bueno para principiantes.