Preguntas frecuentes sobre la excelencia cuántica excelente por Scott Aaronson

Hace un par de días, un borrador de artículo de Google sobre su logro de la superioridad cuántica en una computadora cuántica superconductora se filtró a la red. El texto en sí se eliminó rápidamente, y los rumores y suposiciones, incluidos los erróneos, se multiplicaron a su alrededor. El autor de la publicación es el profesor Scott Aaronson , uno de los principales especialistas en algoritmos cuánticos, y tiene un excelente blog. En la última publicación, responde las principales preguntas sobre la superioridad cuántica.

Del traductor. No soy especialista en complejidad algorítmica y algoritmos cuánticos en particular. Pero la publicación me pareció demasiado interesante para no discutirla en Habré, y por cualquier error en los términos o su uso inusual, por favor dame una patada en PM.

¡Preguntas frecuentes sobre la supremacía cuántica suprema de Scott!

Ya has visto historias, en el Financial Times , Technology Review , CNET , Facebook, Reddit, Twitter o en otros lugares, que hablan de un grupo de Google que logró la superioridad cuántica con una computadora superconductora de 53 qubits. Estas historias son fáciles de encontrar, no las adjuntaré aquí, ya que ninguna de ellas debería haber existido todavía.

Como todo el mundo sabe ahora, Google está preparando una gran declaración sobre la superioridad cuántica, que se planea junto con un artículo científico en una revista genial (¿cuál? La elección es pequeña, una de dos). Espero que esto ocurra dentro de un mes.
Mientras tanto, la NASA, donde trabajan algunos de los autores del artículo, publicó accidentalmente una versión antigua del artículo en un sitio público. Estuvo allí por poco tiempo, pero el tiempo suficiente para estar en el Financial Times, mi correo y un millón de otros lugares. Se espera que la especulación sin hechos sobre su importancia se multiplique.

Parece que el mundo ha sido privado del momento puro del "alunizaje", donde la tesis extendida de Church-Thuring es destruida por evidencia experimental durante una conferencia de prensa. Se parecerá más al vuelo de los hermanos Wright, sobre el cual los rumores y las verdades a medias se filtraron en el espacio público entre 1903 y 1908, cuando Will y Orville finalmente decidieron demostrar su vuelo. (¡Esta vez, afortunadamente, todo se aclarará mucho más rápido!)
Esta publicación no es una declaración oficial o confirmación de nada. Aunque los rayos ya son visibles, el trueno pertenece a un grupo de Google, en el tiempo y el lugar que elijan.

Más bien, quiero detener el flujo de información errónea y ofrecer aquí, como blogger e "intelectual público", mis preguntas frecuentes sobre Supremacía cuántica suprema de Scott. Ya sabes, en caso de que de repente sientas curiosidad por la superioridad cuántica o siempre hayas querido saber qué sucederá si de repente alguna compañía de búsqueda de Mountain View o de otro lugar declara hipotéticamente que se ha logrado la superioridad cuántica.

Sin más preámbulos, aquí está:

B1 ¿Qué es la excelencia computacional cuántica?

A menudo reducido a simplemente "superioridad cuántica", el término se refiere al uso de una computadora cuántica para resolver un conjunto especial de problemas, cuya solución en una computadora clásica usando cualquier algoritmo conocido tomaría órdenes de magnitud más largos, y no por algunas razones aleatorias, sino por debido a la complejidad cuántica asintótica. El énfasis aquí está en estar lo más seguro posible de que el problema se resolvió realmente de una manera cuántica y realmente inalcanzable clásicamente, e idealmente nos permitirá lograr la aceleración de la computación en el futuro cercano (con computadoras cuánticas ruidosas y no universales que ya tenemos) allí o estará pronto). Si la tarea también es útil para algo, mucho mejor, pero no es necesario. El avión Wright y la pila de leña Fermi no fueron útiles por sí solos.

B2 Si Google realmente ha logrado la superioridad cuántica, ¿significa esto que ahora no hay un código crack , ya que Andrew Young, un candidato para la presidencia de los Estados Unidos, cerró recientemente?

No, no es así (aunque todavía me gusta la candidatura de Young).
Hay dos problemas En primer lugar, los dispositivos creados por Google, IBM y otros tienen 50-100 qubits y no tienen corrección de errores. Hackear RSA usando el algoritmo Shore requerirá varios miles de qubits lógicos. Con métodos conocidos de corrección de errores, millones de qubits físicos, y una mejor calidad que la que tenemos ahora, pueden ser fácilmente necesarios para esto. No me parece que alguien esté cerca de esto, y no tenemos idea de cuán pronto podrán acercarse a esto.

Y el segundo problema es que incluso en el futuro hipotético del control de calidad con corrección de errores, podremos descifrar solo algunos códigos, pero no todos, al menos hasta donde sabemos ahora. Casualmente, las claves públicas que se pueden descifrar incluyen la mayoría de los algoritmos que usamos para proteger Internet: RSA, Diffie-Hellman, criptografía elíptica, etc. Pero la criptografía basada en claves privadas no debería verse afectada. Y también hay criptosistemas para claves públicas (por ejemplo, basadas en rejillas) que nadie sabe cómo descifrar usando QC incluso después de más de 20 años de intentarlo, y hay intentos de cambiar a estos sistemas. Por ejemplo, vea mi carta a Rebecca Goldstein .

B3 ¿Qué tipo de cálculos planea hacer Google (o ya ha hecho), que se consideran clásicamente complejos?

Por supuesto, puedo decírtelo, pero me siento estúpido al mismo tiempo. El cálculo es el siguiente: el experimentador genera un circuito cuántico aleatorio C (es decir, una secuencia aleatoria de 1 qubit y 2 qubit - entre los vecinos más cercanos - puertas, con una profundidad de 20, por ejemplo, actuando en una red 2D n = 50-60 qubits). Después de eso, el experimentador envía C a la computadora cuántica y le pide que aplique C al estado inicial de 0, mida el resultado en la base {0,1}, envíe la secuencia observable de n bits (cadena) y repita varios miles o millones de veces. Finalmente, usando su conocimiento de C, el experimentador realiza una verificación estadística sobre el cumplimiento del resultado con la salida esperada de la computadora cuántica.

Esta tarea no es una de las tareas con la única respuesta correcta, a diferencia de la factorización de números. El resultado de la operación del esquema C resulta ser una distribución estadística (llamémosla D _C ) sobre cadenas de n bits, de las cuales necesitamos seleccionar muestras. De hecho, generalmente D _C puede corresponder a 2 ⁿ líneas, tantas que si el QC funciona como se espera, nunca producirá la misma línea en la salida dos veces. Es importante que la distribución de D _C no sea uniforme. Algunas líneas surgieron como resultado de la interferencia constructiva de las amplitudes y, por lo tanto, tienen una probabilidad más alta, y otras como resultado de la destrucción, y tienen una probabilidad más baja. Y aunque obtenemos solo una pequeña fracción de todas las muestras posibles de 2 ⁿ , podemos verificar estadísticamente la distribución de estas muestras para la distribución desigual esperada, y asegurarnos de obtener algo que sea difícil de reproducir de manera clásica.

TL; DR, se le pide a una computadora cuántica que aplique una secuencia aleatoria (pero conocida) de operaciones cuánticas, no porque estemos interesados ​​en el resultado, sino porque estamos tratando de demostrar que QC puede realizar esta tarea claramente definida mejor que una computadora clásica.

B4 Pero si una computadora cuántica solo ejecuta algún código basura, cuyo único propósito es ser difícil para la simulación clásica, ¿a quién le importa? ¿No es un gran pastel con ... nada?

No Esto, por supuesto, no es un pastel con todo lo sabroso, sino al menos un pastel con algo.
Tenga al menos un poco de respeto por la inmensidad de lo que estamos hablando aquí y qué tipo de genio de la ingeniería se necesitó para traducir esto en realidad. Antes de la superioridad cuántica (KP), los escépticos de KP simplemente se rieron entre dientes de que incluso después de miles de millones de dólares y más de 20 años de trabajo, una computadora cuántica todavía no puede hacer algo más rápido que su computadora portátil. Al menos no usar la cuántica. Después de alcanzar la supremacía cuántica en el mundo, ya no se ríen. La superposición de 2 ⁵⁰ o 2 ⁶⁰ números complejos se calculó utilizando un recurso de tiempo y volumen de datos significativamente menor que 2 ⁵⁰ o 2 ⁶⁰

Estoy hablando del avión de Wright solo porque la brecha entre lo que estamos hablando y la negación, algo que veo en diferentes partes de Internet, es completamente incomprensible. Es como si creyeras que, en principio, era imposible volar, y luego viste un endeble aeroplano de madera: es posible que no afecte tu fe, pero ciertamente no debería fortalecerlo.
¿Tenía razón, preocupándome hace muchos años de que la exageración constante sobre los logros mucho menores del KK cansará a las personas y les importará cuando finalmente suceda algo realmente valioso?

B5 Hace muchos años, culpó a las masas por su entusiasmo por D-Wave y sus afirmaciones de una sorprendente ventaja cuántica en problemas de optimización mediante recocido cuántico. Ahora les reprochas su falta de entusiasmo por la superioridad cuántica. ¿Por qué eres tan voluble?

Porque mi objetivo no es cambiar el nivel de entusiasmo en una dirección claramente elegida, sino tener la razón. En retrospectiva, ¿no tenía razón sobre D-Wave, incluso cuando mis declaraciones me hicieron muy impopular en algunos círculos? Bueno, ahora también estoy tratando de tener razón sobre la superioridad cuántica.

B6. Si los cálculos de superioridad cuántica se basan simplemente en muestras de una distribución de probabilidad, ¿cómo se puede verificar que se hayan realizado correctamente?

Gracias por preguntar! Este es precisamente el tema sobre el cual yo y otros hemos desarrollado muchos fundamentos teóricos en los últimos diez años. Ya dije la versión corta en mi respuesta B3: usted prueba esto ejecutando pruebas estadísticas en las muestras que entrega la computadora cuántica para verificar que se concentran alrededor de los picos de la distribución de probabilidad aleatoria D _C. Una forma conveniente de hacer esto, que Google llama la "prueba de entropía cruzada lineal", es simplemente sumar todos los Pr [C produce s _i ] para todas las muestras s ₁ , ..., s _k que KK devolvió, y luego declarar la prueba exitosa si y solo si la suma excede un cierto nivel, digamos, bk / 2 ⁿ , donde b es una constante entre 1 y 2.

Honestamente, para aplicar esta prueba, debe calcular todas las probabilidades Pr [C da s _i ] en una computadora clásica, y la única forma conocida de hacerlo es iterar en un tiempo de ~ 2 ⁿ . ¿Pero le molesta a alguien? No, si n = 50, y usted google y puede contar números como 2 ⁵⁰ (aunque no obtendrá 2 ¹⁰⁰⁰ , que es superior a google , khe-khe). Después de haber expulsado un gran grupo de núcleos clásicos durante, por ejemplo, un mes, terminará con el resultado que produjo el CC en un par de segundos; al mismo tiempo, asegúrese de que el CC sea un par de pedidos más rápido. Sin embargo, esto significa que los experimentos basados ​​en muestreo están diseñados especialmente para dispositivos con ~ 50 qubits. Incluso con 100 qubits, no tenemos idea de cómo asegurar el resultado, incluso utilizando toda la potencia informática disponible en la Tierra.
(Observo por separado que este problema es específico solo para los experimentos de muestreo, similar a lo que se está llevando a cabo ahora. Si utilizó el algoritmo Shor para factorizar un número de 2000 dígitos, puede verificar fácilmente el resultado simplemente multiplicando todos los factores y verificando su simplicidad. si se usa KK para simular una biomolécula compleja, puede verificar el resultado experimentando con la molécula).

B7 Espera un momento Si las computadoras clásicas solo pueden verificar los resultados de un experimento de superioridad cuántica solo en un modo en el que las computadoras clásicas aún pueden simular un experimento (aunque muy lentamente), ¿cómo se puede hablar de "superioridad cuántica"?

Bueno, entonces tu. Con un chip de 53 qubit, puede ver la aceleración varios millones de veces, y aún puede verificar el resultado, y también verificar que la aceleración crece exponencialmente con el número de qubits, tal como lo predice el análisis asintótico. Esto no es insignificante.

B8 ¿Existe alguna evidencia matemática de que ninguna computadora clásica rápida pueda vencer los resultados de un experimento KP basado en el muestreo?

No por el momento. ¡Pero esto no es culpa de los investigadores de la superioridad cuántica! Mientras los teóricos no puedan probar siquiera hipótesis básicas, como P ≠ NP o P ≠ PSPACE, y sin esto no podemos excluir incondicionalmente la posibilidad de una simulación clásica rápida. Lo mejor que podemos esperar es la complejidad condicional. Y tenemos algunos resultados sobre esto, por ejemplo, un artículo sobre muestreo de bosones o un artículo de Bouldand et al. sobre la complejidad # P promedio de calcular las amplitudes de los circuitos aleatorios, o mi artículo con Lijie Chen ("Fundamentos teóricos de la complejidad de los experimentos de supremacía cuántica"). La pregunta abierta más importante en esta área, en mi opinión, es la prueba de las mejores dificultades condicionales.

B9. ¿Hay algún uso para muestrear la superioridad cuántica?

Hasta hace poco, ¡la respuesta era obviamente no! (Y lo sé, porque yo mismo era una de esas personas). Recientemente, sin embargo, la situación ha cambiado, por ejemplo, gracias a mi protocolo de aleatoriedad certificado , que muestra cómo el KP basado en el muestreo puede usarse de forma independiente para generar bits que pueden probarse al azar incluso para un tercero escéptico (bajo suposiciones sobre los cálculos). Esto a su vez tiene una aplicación en criptomonedas y otros protocolos criptográficos. Espero que más aplicaciones de este tipo lleguen pronto.

B10. Si los experimentos sobre la superioridad cuántica generan bits aleatorios todo, ¿por qué es esto interesante? ¿No es posible convertir qubits trivialmente en bits aleatorios simplemente midiéndolos?

La conclusión es que QC genera bits aleatorios no distribuidos uniformemente. En cambio, crea una selección de una distribución de probabilidad compleja y correlacionada en cadenas de 50-60 bits. En mi protocolo, las desviaciones de la uniformidad juegan un papel central en cómo el control de calidad convence al escéptico de que en realidad seleccionó bits aleatorios, en lugar de usar algún tipo de generador pseudoaleatorio en secreto.

B11. ¿Han demostrado décadas de experimentos de mecánica cuántica, por ejemplo, con violación de la desigualdad de Bell, superioridad cuántica demostrada?

Esta es una pregunta puramente léxica. Esos experimentos demostraron otros tipos de superioridad cuántica: por ejemplo, en el caso de la desigualdad de Bell, se les puede llamar "superioridad de correlación cuántica". No mostraron superioridad computacional cuántica, es decir la capacidad de encontrar algo inaccesible para una computadora clásica (donde la simulación clásica no tiene restricciones en el espacio local, etc.). Hoy en día, cuando las personas usan la frase "superioridad cuántica", significan superioridad computacional cuántica.

B12. Aun así, no existen innumerables ejemplos de materiales y reacciones químicas que son difíciles de simular clásicamente, y simuladores cuánticos especialmente construidos (como los del grupo Lukin en Harvard). ¿Por qué no se consideran superioridad de la computación cuántica?

¡En las definiciones de algunas personas, se consideran! La principal diferencia con una computadora de Google es que tienen una computadora totalmente programable: puede ingresar cualquier secuencia arbitraria de compuertas de 2 qubits (para qubits vecinos) simplemente ingresando comandos desde una computadora clásica.

En otras palabras, los escépticos de KP ya no pueden notar burlonamente que, por supuesto, los sistemas cuánticos son difíciles de simular clásicamente, pero esto es simplemente porque la naturaleza generalmente es difícil de simular, y no se puede reprogramar la molécula aleatoria encontrada en el campo en una computadora para simularse a sí misma usted mismo Según cualquier definición razonable, los dispositivos superconductores creados por Google, IBM y otros son computadoras en el sentido completo de la palabra.

B13 ¿Usted (Scott Aaronson) inventó el concepto de excelencia cuántica?

No Jugué un papel en su desarrollo y, por lo tanto, por ejemplo, Sabina Hosenfelder, entre otros, me atribuyó erróneamente la autoría de toda la idea. El término "superioridad cuántica" fue propuesto por John Preskill en 2012, aunque en cierto sentido, la idea básica apareció en los albores de las contribuciones cuánticas a principios de los años 80. En 1994, el uso del algoritmo Shore para factorizar un gran número se convirtió en el experimento principal para probar la superioridad cuántica, aunque en este momento todavía es demasiado difícil de producir.

La idea clave de que el muestreo puede usarse en su lugar fue, hasta donde yo sé, propuesta por primera vez por Barbara Terhal y David DiVincenzo en un artículo de 2002. El esfuerzo actual en una muestra de CP comenzó alrededor de 2011, cuando Alex Arkhipov y yo publicamos nuestro artículo sobre muestreo bosónico , y Bremner, Jozsa y Shepherd publicaron de forma independiente un artículo sobre modelos de desplazados hamiltonianos . Estos artículos mostraron no solo sistemas cuánticos "simples", no universales que pueden resolver problemas de muestreo obviamente complejos, sino también que la existencia de un algoritmo clásico efectivo significaría una caída en la jerarquía polinómica . Arkhipov y yo también sentamos las bases para el argumento de que incluso las versiones aproximadas del muestreo cuántico pueden ser clásicamente complejas.

Hasta donde yo sé, la idea de "circuitos de muestreo aleatorio", es decir, generar un problema de muestreo complejo al seleccionar aleatoriamente una secuencia de puertas de 2 qubits en, digamos, una arquitectura superconductora, surgió su correspondencia, que comencé en diciembre de 2015, que incluía a John Martinis, Hartmut Neven , Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg y otros. El hilo se tituló "Problemas de muestreo desafiantes con 40 Qubits", y la carta comenzó con "Lo siento por el spam".En él, discutí las diversas ventajas y desventajas de tres opciones para demostrar una ventaja cuántica usando el muestreo: (1) circuitos aleatorios, (2) desplazando a los hamiltonianos, (3) muestreo de bosones. Después de que Greg Cooperberg defendió la opción (1), rápidamente se llegó a un consenso de que (1) realmente sería la mejor opción desde el punto de vista de la ingeniería, y que si todavía no tenemos una justificación teórica satisfactoria para (1), podemos de alguna manera evitar esto.

Después de eso, el equipo de Google hizo un gran trabajo al analizar esquemas de muestreo aleatorio, tanto teórica como numéricamente, mientras que Lijie Chen y yo y Bouland et al. proporcionó evidencia diferente de la complejidad clásica de este problema desde el punto de vista de la teoría de la complejidad.

B14. Si se logra la superioridad cuántica, ¿qué significa esto para los escépticos?

¡Guau, no quisiera estar en su lugar ahora! Pueden volver a la posición de que, bueno, por supuesto, la superioridad cuántica es posible (¿y quién dijo lo contrario? ¡Bueno, por supuesto que no!), Y toda la dificultad siempre ha estado en la corrección de errores cuánticos. Y, de hecho, algunos lo han dicho desde el principio. Y otros, mi buen amigo Gil Kalai, entre ellos, al escribir, justo en este blog, predijeron que la superioridad cuántica nunca se lograría por razones fundamentales. Ahora no serán atornillados.

B15. Entonces, ¿qué sigue?

Si esto realmente se logra la superioridad cuántica, entonces creo que el grupo de Google tiene todo el hardware para demostrar mi protocolo para la generación aleatoria certificada de bits. Y esta es realmente una de las siguientes cosas en su plan.
Y además de esto, el siguiente paso obvio es usar un control de calidad programable, con 50-100 qubits para una simulación cuántica útil (por ejemplo, un sistema con un estado de materia condensado) mucho más rápido que cualquier método clásico. Y el segundo paso obvio es demostrar el uso de la corrección de errores para mantener vivo el qubit lógico por más tiempo que la vida útil de los qubits físicos en los que se basa. No hay duda de que IBM, Google y el resto de los jugadores se perseguirán por la primacía en estos pasos.