Excelente Quantum Excellence Q & A

De un blog de Scott Joel Aronson, Especialista en Informática y Sistemas, Profesor, Departamento de Informática, Universidad de Texas en Austin

Usted leyó estas historias: en Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [ en Habr / aprox. transl.] o en otro lugar: que un grupo de investigadores de Google ha logrado la superioridad de la computación cuántica con su dispositivo superconductor de 53 qubits. Son fáciles de encontrar, pero no les daré enlaces, simplemente porque todavía no deberían existir.

El mundo sabe que Google realmente está preparando un gran anuncio de excelencia cuántica, que debería aparecer simultáneamente con la publicación de trabajos de investigación en una de las revistas científicas respetadas. Y es probable que esto suceda dentro de un mes.

Mientras tanto, la NASA, que participó en este desarrollo, publicó accidentalmente una versión antigua de Google en un sitio público. Pasó poco tiempo allí, pero lo suficiente como para llegar al Financial Times, mi bandeja de entrada y millones de otros lugares. Los argumentos sobre este trabajo, desprovistos de hechos, se extienden previsiblemente por todas partes.

Aparentemente, nuestro mundo se ha visto privado de la oportunidad de anunciar claramente un nuevo momento de "entrada del hombre al espacio", en el cual la fuerte tesis de Church-Turing será refutada experimentalmente en una conferencia de prensa. Será más como el vuelo de los hermanos Wright, rumores fragmentarios sobre los que surgieron en el intervalo de 1903 a 1908, en el que Wilbur y Orville finalmente acordaron vuelos de demostración (solo en nuestro caso, afortunadamente, la explicación del problema irá a donde ¡Cuánto menos tiempo!)

He estado actualizado por un par de meses; Fue extremadamente difícil para mí no escribir sobre esto en mi blog. Prometí guardar silencio, pero no pude resistir el deseo de dejar diferentes pistas aquí y allá; por ejemplo, durante mi discurso en el último evento dedicado a Paul Bernays , diseñé especialmente el curso de mis conferencias para que llegaran a este punto.

Esta entrada es el anuncio oficial que confirma estos hechos. Y si los rayos ya son visibles para nosotros, entonces el derecho a expresar el trueno pertenece a un grupo de investigadores de Google, así como el tiempo y el lugar para esto.

En cambio, decidí aclarar esta pregunta, aclarar la información errónea que circula en Internet en mi papel de blogger e "intelectual social", y presentarle "Un excelente conjunto de preguntas y respuestas sobre la superioridad cuántica de Scott". En caso de que de repente te interese la superioridad cuántica, o quieras saber qué sucedería si alguna empresa de motores de búsqueda de Mountain View o en otro lugar anunciara hipotéticamente el logro de la superioridad cuántica .

Bueno, no jalemos al gato por la cola:

Pregunta 1: ¿Qué es la excelencia computacional cuántica?

Este término a menudo se abrevia simplemente a la superioridad cuántica (KP). Denota el uso de una computadora cuántica (QC) para resolver un determinado conjunto de problemas bien definidos, cuya solución, utilizando los algoritmos conocidos de hoy en las computadoras clásicas de hoy, tomará órdenes de magnitud más tiempo, y no solo así, sino debido a la complejidad cuántica asintótica. El énfasis aquí está en estar 100% seguro de que la tarea se está resolviendo en QC, y realmente no se puede abordar con la ayuda de las computadoras clásicas; Idealmente, la tarea debería ser tal que ya se pueda resolver en el futuro cercano (con la ayuda de ruidosos, no QC universales que ya existen o aparecerán pronto). Y si esta tarea sigue siendo útil, mejor, pero esto no es necesario. El avión Wright Brothers o el Chicago Woodpile no fueron útiles en sí mismos.

P2: Si los investigadores de Google realmente llegaron a HF, ¿significa esto que "cualquier código puede ser pirateado", como tuiteó recientemente el candidato a la presidencia del Partido Demócrata de los Estados Unidos, Andrew Young?



No es cierto (aunque como candidato, Young es bonita para mí).

Hay dos problemas En primer lugar, los dispositivos que Google, IBM y otros están creando hoy consisten en 50-100 qubits y no tienen un sistema de corrección de errores. Para ejecutar el algoritmo Shore para descifrar el cifrado RSA, se requieren varios miles de qubits lógicos. Y con los métodos de corrección de errores conocidos hoy en día, esto puede requerir fácilmente millones de qubits físicos, y la calidad es mejor que las existentes. No creo que nadie se haya acercado a esto, y no sabemos cuánto tiempo llevará.

En segundo lugar, incluso en un futuro hipotético, los QC escalables con corrección de errores, como nos parece hoy, podrán descifrar algunos códigos, pero no todos. Casualmente, las claves públicas que pueden descifrar incluyen la mayoría de las claves que usamos hoy para la seguridad de Internet: RSA, el protocolo Diffie-Hellman, curvas elípticas, etc. El cifrado de clave privada tendrá un impacto mínimo. Y también hay candidatos para sistemas de clave pública (por ejemplo, basados ​​en rejillas), cuyo método de piratería no ha sido conocido por nadie durante 20 años de intentos de control de calidad; Además, ya se están haciendo intentos para cambiar a tales sistemas. Los detalles están en mi carta a Rebecca Goldstein .

P3: ¿Qué cálculos, considerados clásicamente complejos, planea hacer Google o ya lo han hecho?

Puedo decir, aunque estoy avergonzado. Los cálculos son los siguientes: el "probador" genera un circuito cuántico aleatorio C (una secuencia aleatoria de puertas de 1 qubit y el segundo qubit más cercano a él, profundidad de aproximadamente 20, en una red bidimensional de 50-60 qubits). Luego, el probador envía C a la computadora cuántica y le indica que aplique el circuito al estado inicial de all-0, mida el resultado con la base {0,1}, envíe la cadena observada de n bits y repita esto varios miles o millones de veces. Finalmente, usando su conocimiento de C, el probador clásico aplica una prueba estadística para verificar que la salida confirma que el control de calidad realizó los cálculos.

Es decir, no es una tarea como factorizar, tener una respuesta correcta. El circuito C produce una distribución de probabilidad, llamémosla D _C , sobre cadenas de n bits, y la tarea es producir muestras a partir de esta distribución. De hecho, 2 ⁿ líneas hablarán en apoyo de D _C , y habrá tantas de ellas que si el control de calidad funciona como debería, nunca veremos la misma salida. Es importante destacar que la distribución de D _C no _es uniforme. Algunas líneas experimentarán interferencias constructivas de amplitudes, y sus probabilidades serán mayores, mientras que otras sufrirán interferencias destructivas, y sus probabilidades serán menores. Y aunque solo veremos unas pocas muestras, cuyo número será pequeño en comparación con 2 ⁿ , podemos verificar si gravitan en las filas, lo que consideramos más probable, y al final esto aumentará nuestra confianza en que algo clásico no se puede lograr. .

En pocas palabras, simplemente se le pedirá a KK que realice una secuencia de operaciones aleatoria (pero conocida), no porque necesitemos un resultado específico, sino porque estamos tratando de demostrar que puede adelantarse a una computadora clásica en una tarea claramente definida.

P4: Pero si KK existe solo para dar basura al azar, cuyo único significado es que es difícil de simular en una computadora clásica, ¿a quién le importa? ¿No es un sándwich enlatado sin nada?

No Como ya escribí, este no es un sándwich con todo a la vez, ¡pero definitivamente es un sándwich con algo!

Respete la inmensidad del tema en discusión y los terriblemente complejos logros de ingeniería necesarios para su implementación. Antes del inicio de la PC, los escépticos pueden divertirse al mismo tiempo que después de todos los miles de millones gastados en más de 20 años, nunca se ha utilizado un KK para resolver un problema que se habría completado más rápido que su computadora portátil, o al menos el problema no se pudo resolver de una manera que depende de la naturaleza cuántica de esta computadora. Pero en el mundo del próximo KP, esto ya está mal. Una superposición de 2 ⁵⁰ o 2 ⁶⁰ números complejos se dominó computacionalmente, utilizando tiempo y recursos que eran pequeños en comparación con 2 ⁵⁰ o 2 ⁶⁰ .

Recuerdo constantemente el avión de los hermanos Wright porque me sorprende el abismo entre lo que estamos hablando y la negligencia en Internet de todas las partes a este tema. Esto es similar a la reacción de una persona que creía sagradamente que era imposible hacer un vuelo útil por el aire, y luego vio un avión de hélice de madera que flotaba en el aire: este espectáculo no refutaría sus puntos de vista, pero tampoco lo respaldaría.

¿Realmente he estado preocupado durante todos estos años por nada de que la exageración constante sobre los hitos mucho menos significativos logrados por el CC agote la paciencia de las personas y no les importe cuando suceda algo realmente valioso?

P5: Hace muchos años, avergonzaba a las masas por alabar demasiado a D-Wave y sus declaraciones sobre la enorme aceleración cuántica de resolver problemas de optimización a través del recocido cuántico. Ahora te avergüenzas de las masas porque no están lo suficientemente entusiasmadas con el Partido Comunista. ¿Por qué no decides?

¡Porque mi objetivo no es dirigir el "nivel de entusiasmo" en ninguna dirección en particular, sino asegurarme de que sea correcto! ¿No puede decir, mirando hacia atrás, que generalmente tenía razón sobre la onda D, incluso cuando mi crítica de este tema me hizo impopular en algunos círculos? Entonces, sobre el KP, también trato de tener razón.

P6: Si los cálculos relacionados con KP solo tienen en cuenta muestras de la distribución de probabilidad, ¿cómo puedo verificar que los cálculos sean correctos?

¡Qué bueno que preguntaste! Esta es una cuestión de la teoría que nosotros y otros científicos hemos estado desarrollando durante la última década. Ya lo he explicado brevemente en B3: los cálculos pueden verificarse estadísticamente a partir de las muestras devueltas por el CC, y asegurarse de que prefieren agregar a los "picos" de la distribución de probabilidad D _C. Una de las formas convenientes de hacer esto es lo que Google llama una "verificación lineal de entropía cruzada": es sumar Pr [C output s _i ] para todas las muestras s ₁ , .., s _k que produce el control de calidad y luego declarar la verificación exitosa si esta cantidad sale más allá de cierto límite, por ejemplo, bk / 2 ⁿ para una constante 1 <b <2.

Por supuesto, para llevar a cabo esta prueba, es necesario calcular las probabilidades Pr [C output s _i ] en una computadora clásica, y la única forma de hacerlo es tomar exhaustivamente 2 ^{n de} tiempo. ¿Hay algún problema con esto? No, si n = 50, y usted es Google, y puede procesar números como 2 ⁵⁰ (aunque no puede hacer frente a 2 ¹⁰⁰⁰ , un número que excede googol - ha, ha). Al lanzar un grupo de núcleos clásicos en algún lugar durante un mes, eventualmente podrá confirmar la salida correcta de su control de calidad, que emitió en un par de segundos, y al mismo tiempo que el control de calidad trabaja muchos órdenes de magnitud más rápido. Sin embargo, esto también significa que los experimentos de CP basados ​​en muestreo están diseñados para los dispositivos de 50 qubits que crean hoy. E incluso con cien qubits, no podríamos confirmar los resultados del control de calidad, incluso utilizando toda la potencia informática del planeta.

Insisto en que este problema es típico en experimentos con muestras similares a las que estamos realizando ahora. Si el algoritmo de Shore factorizara un número de 2000 dígitos, verificaríamos esto fácilmente simplemente multiplicando los factores resultantes y verificando que pertenecen a números primos. O, si se usó CC para simular una biomolécula compleja, podríamos probar su funcionamiento en un experimento.

P7: Espera un minuto. Si las computadoras clásicas pueden verificar los resultados de un experimento en KP solo en el modo de simulación del experimento (aunque lento), entonces ¿cómo puede ser esto "superioridad cuántica"?

Vamos Con un chip de 53 qubits, es bastante lógico esperar una aceleración de varios millones de veces en el modo en el que todavía puede verificar directamente el resultado del trabajo, y también ver que la aceleración crece exponencialmente con un aumento en el número de qubits, tal como lo predijo el análisis asintótico.

P8: ¿Hay alguna prueba matemática de que no existe un algoritmo clásico rápido que supere el experimento KP con el muestreo?

No hoy ¡Pero esto no es culpa de los investigadores de KP! Los expertos en informática teórica son incapaces incluso de probar las hipótesis más simples, como P ≠ NP o P ≠ PSPACE, por lo que no debe esperar que sea posible excluir inequívocamente la presencia de una simulación clásica rápida. Solo podemos esperar la complejidad condicional. Y realmente probamos algunos de estos resultados . El mayor problema teórico en esta área es la prueba de los mejores resultados de la complejidad condicional.

P9: ¿Tiene el marco de muestreo algún uso útil?

Al pensar en este tema por primera vez, la gente generalmente creía que la respuesta obvia a esta pregunta era "no" (y yo era uno de ellos). Pero últimamente, la situación ha cambiado, por ejemplo, gracias a mi protocolo de aleatoriedad confirmada, que demuestra cómo un experimento con un CP con muestreo puede convertirse rápidamente en un generador de bits, cuya aleatoriedad puede demostrarse a un observador escéptico de terceros (bajo algunos supuestos computacionales). Y esto puede aplicarse potencialmente a la creación de criptomonedas PoS y otros protocolos criptográficos. Espero que en el futuro cercano se descubran más aplicaciones de este tipo.

P10: Si los experimentos de KP solo generan bits aleatorios, ¿es interesante? ¿No es una tarea trivial convertir qubits en bits aleatorios simplemente midiéndolos?

La conclusión es que el experimento con el KP no genera bits aleatorios uniformes. Él hace una selección de algunas distribuciones de probabilidad de correlación complejas en líneas de 50 bits o 60 bits. En mi protocolo de aleatoriedad confirmado, las desviaciones de la homogeneidad juegan un papel central en cómo el CP puede convencer a un escéptico clásico de que los bits son realmente aleatorios y no tienen un sistema secreto (como un generador de números pseudoaleatorio).

P11: ¿Pero no han demostrado KP décadas de experimentos de mecánica cuántica, por ejemplo, aquellos que violan las desigualdades de Bell ?

Esto es solo una confusión en términos. Esos experimentos mostraron otros tipos de "superioridad cuántica". Por ejemplo, en el caso de violación de las desigualdades de Bell, se trataba de "superioridad de correlación cuántica". No mostró superioridad computacional, es decir, algo que no se puede simular en una computadora clásica (a pesar de que la simulación clásica no tendría restricciones en la localidad espacial o algo así). Hoy, las personas generalmente se refieren a la superioridad de la computación cuántica por KP.

P12: Bueno, pero hay innumerables ejemplos de materiales y reacciones químicas que son difíciles de simular clásicamente, así como simuladores cuánticos especiales (por ejemplo, el grupo Lukin de Harvard). ¿Por qué no se consideran ejemplos de KP?

¡Según algunas definiciones, pueden considerarse ejemplos de KP! La diferencia clave entre el trabajo de los investigadores de Google es que su dispositivo es totalmente programable: se puede programar en una secuencia arbitraria de puertas de 2 qubits con el vecino más cercano, simplemente enviando las señales necesarias desde una computadora cuántica.

En otras palabras, los escépticos de KP ya no pueden gruñir eso, dicen, si hay sistemas cuánticos que son difíciles de simular clásicamente, es solo porque la naturaleza es difícil de simular, y no podemos cambiar arbitrariamente qué compuesto químico aleatorio encontramos en naturaleza, por lo tanto, estos sistemas no pueden considerarse "computadoras que se simulan". Según cualquier definición razonable, los dispositivos superconductores que Google, IBM y otras compañías están construyendo hoy en día son computadoras reales.

P13: ¿Has inventado el concepto de superioridad cuántica?

No Jugué un papel en su definición, razón por la cual Sabina Hossenfelder y otros me atribuyeron un papel demasiado importante en esta idea. El término "superioridad cuántica" fue acuñado por John Preskill en 2012, aunque de alguna manera el concepto clave se remonta al comienzo de la computación cuántica a principios de los años ochenta. En 1994, el uso del algoritmo Shore para factorizar grandes números se convirtió en un experimento real en el campo de KP, aunque este problema es demasiado difícil de resolver hoy.

Barbara Theral y David Divincenzo propusieron por primera vez en un trabajo visionario de 2002 la esencia de la idea, que consistía en demostrar el PC utilizando el problema de muestreo, hasta donde yo sé. Los intentos "modernos" de organizar experimentos comenzaron en 2011, cuando Alex Arkhipov y yo publicamos nuestro trabajo en BosonSampling, y Bremner, Yosa y Shepherd publicaron nuestro trabajo en Hamiltonianos cambiados. Estos trabajos mostraron no solo que los sistemas cuánticos "simples", no universales, pueden resolver problemas aparentemente complejos con el muestreo, sino también que un algoritmo clásico efectivo para estos problemas conducirá al colapso de la jerarquía polinómica . Arkhipov y yo también dimos los primeros pasos para demostrar que incluso las versiones aproximadas de los problemas de muestreo cuántico pueden ser clásicamente complejas.

Hasta donde sé, la idea de "muestreo aleatorio de circuitos", es decir, generar un problema de muestreo complejo a través de la selección de secuencias de válvulas aleatorias de 2 qubits en una arquitectura superconductora, apareció en la correspondencia por correo electrónico que comencé en diciembre de 2015, en la que John también participó Martinis, Hartmut Niven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Josa, Aram Harrow, Greg Cooperberg y otros. La correspondencia se llamó "un difícil problema de muestreo de 40 qubits", y mi carta comenzó con las palabras "perdón por el spam". Discutí algunas de las ventajas y desventajas de tres opciones para demostrar KP con muestreo: (1) contornos aleatorios, (2) Hamiltonianos conmutados, (3) BosonSampling. Después de que Cooperberg defendió la primera opción, rápidamente se formó un consenso entre los participantes,que la primera opción era la mejor desde el punto de vista de la ingeniería, y que si el análisis teórico existente para (1) no es suficiente, entonces podemos llegar a algo.

Después de eso, un grupo de Google realizó una gran cantidad de análisis de muestras de contornos aleatorios, tanto teóricos como numéricos, y Lijie Chen y Buland y mis colegas presentaron evidencia de varios tipos para la complejidad clásica del problema.

P14: Si se logra KP, ¿qué significará esto para los escépticos?

¡No quisiera estar en su lugar! Pueden moverse a una posición donde KP sea posible (¿y quién dijo que es imposible? ¡Ciertamente no lo son!), Y esa corrección cuántica de errores siempre ha sido un problema real. Y muchos de ellos realmente apoyaron esta posición particular. Pero otros, incluido mi amigo Gil Kalay, aquí en una publicación de blog, afirmaron que KP no se pudo lograr por razones fundamentales. Y no los dejaré salir.

Q15: ¿Qué sigue?

Llegar a KP significa que el grupo de Google ya tiene el equipo necesario para demostrar mi protocolo para generar bits aleatorios confirmados. Y esta es realmente una de las primeras cosas que planeamos hacer.

El próximo hito obvio será el uso de un control de calidad programable con 50-100 qubits para simulaciones cuánticas útiles (por ejemplo, sistemas de estado condensado) que son más rápidos que cualquier método clásico conocido. El segundo hito obvio será la demostración del uso de la corrección de errores cuánticos para que el qubit codificado viva más que los qubits físicos subyacentes. No hay duda de que Google, IBM y otros jugadores competirán para luchar por estos dos hitos.

Después de publicar el artículo, Steve Girwin me recordó que el grupo de Yale ya había alcanzadocorrección cuántica de errores, aunque en el sistema bosónico, y no en el sistema de qubits superconductores. Entonces, quizás, el próximo hito esté mejor formulado de la siguiente manera: lograr la superioridad computacional cuántica y la corrección útil de errores cuánticos en un sistema.