¿Cómo cambiará la computación cuántica la programación? [cerrado]

¿Cómo es diferente la programación de un algoritmo cuántico? ¿Cómo sería un lenguaje similar a C si estuviera diseñado para qubits? ¿Cambiarían los tipos?

Cuando analicé esto hace algún tiempo, estaba claro que los algoritmos cuánticos, aunque no particularmente rápidos, permiten un paralelismo exponencialmente masivo. Por lo tanto, brillarán en casos que involucren búsquedas en espacios que no son prácticos con hardware secuencial, incluso hardware secuencial masivamente paralelo.

Una propiedad de los algoritmos cuánticos es que tienen que ser reversibles . Cualquier algoritmo dado puede traducirse en uno que sea reversible, al agregarle suficiente mantenimiento de registros para permitir que se ejecute hacia atrás.

Otra propiedad es que obtener una respuesta de un algoritmo cuántico es un asunto aleatorio, porque lo que obtienes al final de un cálculo son respuestas múltiples, cada una con su propia probabilidad. Debe ejecutarse de tal manera que la respuesta que desee tenga una alta probabilidad. Esto puede implicar ejecutar el algoritmo hacia adelante y hacia atrás varias veces.

Echa un vistazo al algoritmo de búsqueda de Grover .

INSERTADO para mostrar la operación fundamental del algoritmo de Grover. Supongamos que hay un problema de búsqueda. Las respuestas posibles son 0, 1, 2 y 3, pero la respuesta correcta es 2. Entonces, la computadora cuántica se coloca en una superposición de los cuatro estados, y sigue una secuencia de pasos para ver cuál es la correcta, y invierte su amplitud, como los puntos negros y las flechas a continuación:

Puede ver que la flecha 2 se ha invertido dentro de la máquina, pero no hay forma de decir eso afuera, porque solo las probabilidades son visibles afuera, que son amplitudes al cuadrado , y cuando están al cuadrado son todas iguales.

Sin embargo, las amplitudes tienen una media, indicada por la línea roja, y se puede hacer que la computadora siga una secuencia de pasos que invierte cada amplitud sobre la media . Cuando se hace eso, las amplitudes y las probabilidades, se transfieren al estado 2, ¡la respuesta correcta ! Entonces, si se observa la máquina, el estado 2 brilla.

No es tan simple. En general, se requieren múltiples ciclos de la máquina, hacia adelante y hacia atrás, invirtiendo al final de cada ciclo, para maximizar la probabilidad de la respuesta correcta. Además, uno debe tener cuidado de no hacerlo más de esa cantidad de veces, ya que puede revertirse fácilmente.

Entonces, ¿por qué dicen que las computadoras cuánticas son tan rápidas ? Porque cada vez que duplica el número de qubits, cuadra el paralelismo, pero no cuadra el período de tiempo, por lo que finalmente gana.

¿No es divertido?

Personalmente, me interesaba cómo se podría aplicar esto a la verificación de la corrección del software. Ahora probamos el software arrojándole un montón de entradas de prueba y (para ser demasiado simple) viendo si golpea un Assert. En una computadora cuántica, podría ser posible ejecutarlo en paralelo contra un conjunto de entradas mucho más denso y ver si alguno de esos casos golpea un Assert.

Al igual que si la entrada al algoritmo fuera de 128 bytes, o 1024 bits, hay 2 ^ 1024 o 10 ^ 308 posibles entradas diferentes. No hay forma de probar tantas entradas en una computadora convencional, pero una computadora cuántica podría probarlas todas en paralelo.

¿Cómo sería un lenguaje similar a C si estuviera diseñado para qubits? ¿Cambiarían los tipos?

Sería tan drásticamente diferente como para ser incomprensible como C.

El problema principal (según tengo entendido) es que la computación cuántica no funciona de una manera imperativa agradable 'haz esto, luego eso, luego esta otra cosa'. Intentar forzar la capacidad de C para hacer eso en el 'procesador' de la computadora cuántica será, si no imposible, tremendamente ineficiente.

Los algoritmos de programación para computadoras cuánticas (una vez más, según tengo entendido) tienden a estar más cerca del mapa / reducción de estilo de programación funcional, ya que la computación cuántica permite que todos los candidatos en la parte 'reducir' existan simultáneamente y se "caigan" de la computadora cuando se observa

Tenga en cuenta que hay algunos algoritmos existentes para las computadoras cuánticas, a pesar de que los dispositivos no existen para ejecutarlos. El algoritmo de Simon, por ejemplo.

Para hacer el uso más efectivo posible de una computadora cuántica, uno debe ser capaz de manejar entradas y salidas que son estados de un registro cuántico, para el cual no existe realmente un análogo clásico. Hablando de algunos años de experiencia en el campo de la información cuántica, debo advertirle que nadie realmente tiene una buena intuición para esto más allá de las matemáticas abstractas de álgebras C *, y me dicen que incluso esta intuición resulta ser inadecuada si comienzas a preguntarte sobre la teoría de la relatividad.

La clase de problemas que se pueden resolver de manera eficiente en una computadora cuántica se conoce como BQP, para Polinomio cuántico acotado. Esta es la versión cuántica de BPP, y puede encontrar más información en este documento: http://www.scottaaronson.com/papers/bqpph.pdf

Anoche, un investigador de algoritmos cuánticos me dijo que hay un problema muy importante que es completo con BQP: resolver un sistema lineal de N ecuaciones. Clásicamente, esto se puede resolver en pasos O (N) con eliminación gaussiana. El algoritmo Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) lo resuelve en polylog (N), siempre que esté dispuesto a aceptar una respuesta que tenga la solución codificada como un estado cuántico. Si desea hacer un uso completo de una computadora cuántica, por lo tanto, parece necesario que tenga un tipo correspondiente al estado de un registro cuántico.

Aunque estoy un poco fuera de mi experiencia particular en este momento, me arriesgaría a suponer que sería capaz de programar una computadora cuántica siempre que tuviera acceso a un tipo correspondiente a estados mágicos. Sin embargo, ese es un concepto difícil que requiere bastante estudio del tema.

Tenga en cuenta que estamos muy lejos de tener un lenguaje de programación cuántico, porque estamos en una etapa muy primitiva de la investigación en computación cuántica. Pedir un C cuántico en este momento sería como ir a Alan Turing y pedirle que diseñe Python. ¡Aún no tenemos la versión cuántica del tubo de vacío!