Supremacía cuántica

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de octubre de 2020; las comprobaciones requieren 8 ediciones .

La supremacía cuántica  es la capacidad de los dispositivos de computación cuántica para resolver problemas que las computadoras clásicas prácticamente no pueden resolver. La ventaja cuántica es la capacidad de resolver problemas más rápido. Desde el punto de vista de la teoría de la complejidad computacional, esto generalmente significa proporcionar una aceleración superpolinomial en comparación con el algoritmo clásico más conocido o posible [1] . El término fue popularizado por John Preskill , pero el concepto de ventaja computacional cuántica, especialmente en la simulación de sistemas cuánticos, se remonta a la propuesta de computación cuántica dada por Yuri Manin (1980) [2] yRichard Feynmann (1981) [3] .

El algoritmo de Shor para la factorización de enteros, que se ejecuta en tiempo polinomial en una computadora cuántica, proporciona tal aceleración superpolinomial en comparación con el algoritmo clásico más conocido [4] . Aunque aún no se ha probado, la factorización se considera un desafío cuando se utilizan recursos clásicos. La dificultad de probar lo que no se puede hacer con la computación clásica es un problema común para demostrar definitivamente la superioridad cuántica. También influye en la propuesta de muestreo de bosones de Aaronson y Arkhipov, los problemas especializados de D-Wave sobre bucles de agrupamiento frustrados y el muestreo de salida para circuitos cuánticos aleatorios .

Al igual que la factorización de enteros, el problema de muestrear las distribuciones de salida de circuitos cuánticos aleatorios se considera difícil para las computadoras clásicas basadas en suposiciones razonables sobre la complejidad.

Historia

Google anunció previamente planes para demostrar la supremacía cuántica para fines de 2017 utilizando una matriz de 49 qubits superconductores [5] . Sin embargo, a principios de enero de 2018, solo Intel ha anunciado dicho hardware [6] .

En octubre de 2017, IBM demostró una simulación de 56 qubits en una supercomputadora convencional, aumentando la cantidad de qubits necesarios para la supremacía cuántica [7] .

En noviembre de 2018, Google anunció una asociación con la NASA en la que la NASA "analizará los resultados de los circuitos cuánticos que se ejecutan en los procesadores cuánticos de Google y... la superioridad" [8] .

Un artículo teórico de 2018 sugiere que la supremacía cuántica se puede lograr en "una matriz bidimensional de 7 × 7 qubits y alrededor de 40 ciclos de reloj", pero si la tasa de error es lo suficientemente baja [9] .

El 21 de junio de 2019, Scientific American sugirió que, de acuerdo con la ley de Neven , la supremacía cuántica se logrará en 2019 [10] .

El 20 de septiembre de 2019, el Financial Times informó que "Google afirma haber logrado la supremacía cuántica en una matriz de 54 qubits, de los cuales 53 eran funcionales y se usaban para realizar cálculos en 200 segundos, lo que llevaría alrededor de 10 000 años para una supercomputadora convencional". " [11] . Inicialmente, apareció un informe sobre esto en el sitio web de la NASA, pero se eliminó poco después de la publicación [12] . Más tarde, el 23 de octubre, se anunció oficialmente la supremacía cuántica [13] . Sin embargo, los expertos de IBM, después de analizar los datos presentados, indicaron que algunos momentos no son óptimos y que, de hecho, tal cálculo en una supercomputadora clásica tomará solo 2,5 días en lugar de los 10 000 años declarados. [14] [15] [16]

El 3 de diciembre de 2020, científicos chinos informaron que su computadora cuántica Jiuzhang , alimentada por fotones entrelazados, había logrado la supremacía cuántica. En 200 segundos, calcularon con éxito un problema que la computadora clásica más rápida del mundo tardaría más de 500 millones de años en resolver [17] .

Complejidad computacional

El problema de la complejidad se refiere a cómo la cantidad de recursos necesarios para resolver un problema se escala con el tamaño de la entrada. Como extensión de la teoría clásica de la complejidad computacional , la teoría de la complejidad cuántica describe el funcionamiento de una computadora cuántica universal sin tener en cuenta la complejidad de su creación o la eliminación de los efectos de decoherencia y ruido [18] . Debido a que la información cuántica es una generalización de la información clásica , una computadora cuántica puede simular cualquier algoritmo clásico .

La clase de complejidad de los problemas de error acotado en el tiempo polinómico cuántico (BQP) es una clase de problemas de decisión que se pueden resolver en tiempo polinomial mediante una computadora cuántica universal . La clase BPQ está relacionada con las clases de complejidad clásicas por una jerarquía [19] . Sigue siendo una pregunta abierta si alguna de estas incrustaciones es estricta.

A diferencia de los problemas de decisión que requieren una respuesta de sí o no, los problemas de muestreo requieren el muestreo de distribuciones de probabilidad [20] . Si existe un algoritmo clásico que puede muestrear la salida de un circuito cuántico arbitrario , la jerarquía de polinomios se moverá al tercer nivel, lo que se considera muy poco probable. BosonSampling  es una propuesta más específica cuya complejidad clásica depende de la insolubilidad del problema de calcular el permanente de una matriz grande con elementos complejos, que es un problema P#-completo. Los argumentos utilizados para derivar esta afirmación también se han aplicado al muestreo IQP [21] , donde solo se necesita la hipótesis de que la complejidad del problema promedio y la del peor de los casos es la misma.

Aceleración superpolinomial

Los siguientes algoritmos proporcionan una aceleración superpolinomial en comparación con los algoritmos clásicos más conocidos [22] :

Algoritmo de Shor para la factorización de enteros

Este algoritmo encuentra la factorización prima de un entero de n bits en el tiempo [4] , el algoritmo clásico más famoso toma el tiempo y el mejor límite superior de la complejidad de este problema . También puede acelerar cualquier problema que se reduzca a la factorización de enteros , incluido el problema de si los grupos de matrices pertenecen a campos de orden impar.

Para la computación cuántica, este algoritmo es importante tanto práctica como históricamente. Se convirtió en el primer algoritmo cuántico polinomial propuesto para un problema que se considera difícil para las computadoras clásicas [4] . La confianza en esta complejidad es tan fuerte que la seguridad del protocolo de cifrado RSA más común en la actualidad se basa en el algoritmo de factorización [23] . Una computadora cuántica que ejecute este algoritmo de manera exitosa y reproducible puede romper este sistema de encriptación [24] . Este riesgo de piratería se denomina problema Y2Q, similar al problema Y2K, el problema Y2K .

Muestreo de bosones

Este paradigma computacional se basa en fotones idénticos enviados a través de una red óptica lineal y puede resolver ciertos problemas de muestreo y búsqueda que, asumiendo múltiples hipótesis, son irresolubles para las computadoras clásicas [25] . Sin embargo, se demostró que el muestreo de bosones en un sistema con pérdidas y ruido suficientemente grandes se puede simular de manera efectiva [26] .

La implementación experimental más grande de muestreo de bosones hasta la fecha tiene 6 modos y, por lo tanto, puede procesar hasta 6 fotones simultáneamente [27] . El mejor algoritmo clásico para modelar el muestreo de bosones se ejecuta en orden de tiempo para un sistema con n fotones y m modos de salida [28] . BosonSampling es una implementación R de código abierto  del algoritmo . El algoritmo da una estimación de 50 fotones , lo que es necesario para demostrar la superioridad cuántica utilizando el muestreo de bosones.

Muestreo de la distribución de salida de circuitos cuánticos aleatorios

El algoritmo más conocido para simular un circuito cuántico aleatorio arbitrario requiere un tiempo que se escala exponencialmente con el número de qubits , según el cual un grupo de investigadores estima que unos 50 qubits pueden ser suficientes para demostrar la superioridad cuántica [9] . Google ha anunciado su intención de demostrar la supremacía cuántica para fines de 2017 mediante la creación y el lanzamiento de un chip de 49 qubits que puede muestrear distribuciones en un tiempo razonable que son inaccesibles para cualquier computadora clásica moderna [5] . Pero la simulación más grande de circuitos cuánticos realizada con éxito en una supercomputadora tiene 56 qubits . Por lo tanto, puede ser necesario aumentar la cantidad de qubits necesarios para demostrar la superioridad cuántica [7] .

Crítica

Las computadoras cuánticas son mucho más propensas a errores que las computadoras clásicas debido a la decoherencia y el ruido. El teorema del umbral establece que una computadora cuántica ruidosa puede usar códigos cuánticos de corrección de errores [29] [30] para simular una computadora cuántica no ruidosa, asumiendo que el error introducido en cada ciclo de computadora es menor que un cierto número. Las simulaciones numéricas muestran que este número puede llegar al 3% [31] .

Sin embargo, no se sabe cómo escalarán los recursos necesarios para la corrección de errores con la cantidad de qubits . escépticos[ ¿Qué? ] indican que se desconoce el comportamiento del ruido en los sistemas cuánticos escalables como barreras potenciales para la implementación exitosa de la computación cuántica y la demostración de la supremacía cuántica.

Véase también

Notas

  1. ↑ Anargyros; papageorgiou. Medidas de aceleración de la computación cuántica  (inglés)  // Revisión física A  : revista. - 2013. - 12 de agosto ( vol. 88 , no. 2 ). — Pág. 022316 . — ISSN 1050-2947 . -doi : 10.1103 / PhysRevA.88.022316 . - . -arXiv : 1307.7488 . _
  2. ↑ Manin, Yu. I. Vychislimoe i nevychislimoe  (neopr.) . - Sov.Radio, 1980. - S. 13-15.
  3. ↑ Ricardo P.; Feynman. Simulación de física con computadoras  //  Revista internacional de física teórica : diario. - 1982. - 1 de junio ( vol. 21 , n. 6-7 ). - Pág. 467-488 . — ISSN 0020-7748 . -doi : 10.1007/ BF02650179 . - .
  4. ↑ 1 2 3 P.; corto Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica  (inglés)  // SIAM Review: revista. - 1999. - 1 de enero ( vol. 41 , no. 2 ). - Pág. 303-332 . — ISSN 0036-1445 . -doi : 10.1137/ S0036144598347011 . - . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 Planes de Google para demostrar la supremacía de la computación cuántica , IEEE Spectrum: Technology, Engineering, and Science News . Archivado desde el original el 25 de abril de 2021. Consultado el 11 de enero de 2018.
  6. ↑ CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy , IEEE Spectrum: Technology, Engineering, and Science News . Archivado desde el original el 23 de marzo de 2021. Consultado el 22 de julio de 2017.
  7. ↑ 1 2 Los planes de computación cuántica de Google amenazados por la bola curva de IBM (20 de octubre de 2017). Consultado el 22 de octubre de 2017. Archivado desde el original el 25 de enero de 2021.
  8. ↑ Harris . Google ha reclutado a la NASA para que lo ayude a probar la supremacía cuántica en unos meses  , MIT Technology Review . Archivado el 10 de marzo de 2020. Consultado el 30 de noviembre de 2018.
  9. ↑ 12 Sergio ; Boixó. Caracterización de la supremacía cuántica en dispositivos a corto plazo  // Nature Physics  : revista  . - 2018. - 23 de abril ( vol. 14 , no. 6 ). - Pág. 595-600 . -doi : 10.1038 / s41567-018-0124-x . -arXiv : 1608.00263 . _
  10. ↑ https://www.scientificamerican.com/article/a-new-law-suggests-quantum-supremacy-could-happen-this-year/ Archivado el 2 de marzo de 2021 en Wayback Machine Una nueva "ley" sugiere supremacía cuántica Podría suceder este año] , Scientific American, Daily Digest, 21 de junio de 2019
  11. ↑ Google afirma haber alcanzado la supremacía cuántica  , The Financial Times  (21 de septiembre de 2019). Archivado desde el original el 29 de abril de 2021. Consultado el 23 de octubre de 2019.
  12. ↑ Karpukhin, Vladimir The Financial Times: Google anunció la creación de la computadora cuántica más poderosa, pero luego eliminó el informe - Tecnologías en TJ . TJ (21 de septiembre de 2019). Consultado el 23 de octubre de 2019. Archivado desde el original el 23 de octubre de 2019.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Supremacía cuántica utilizando un procesador superconductor programable   // Naturaleza . - 2019. - Octubre ( iss. 7779 , no. 574 ). - Pág. 505-510 . — ISSN 1476-4687 . -doi : 10.1038/ s41586-019-1666-5 . Archivado desde el original el 23 de octubre de 2019.
  14. ↑ Lo que Google vs. Debate de IBM sobre medios de supremacía cuántica | ZDNet . www.zdnet.com . Consultado el 12 de febrero de 2020. Archivado desde el original el 5 de marzo de 2020.
  15. ↑ Sobre "Supremacía cuántica" . Blog de investigación de IBM (22 de octubre de 2019). Consultado el 24 de octubre de 2019. Archivado desde el original el 11 de noviembre de 2021.
  16. ↑ Google afirma alcanzar la supremacía cuántica: IBM retrocede . NPR.org . Consultado el 24 de octubre de 2019. Archivado desde el original el 23 de octubre de 2019.
  17. ↑ La computadora cuántica basada en luz Jiuzhang logra la supremacía cuántica | noticias de ciencia . Consultado el 4 de diciembre de 2020. Archivado desde el original el 2 de noviembre de 2021.
  18. ↑ Watrous, John. Complejidad computacional cuántica // Enciclopedia de complejidad y ciencia de sistemas  (inglés) . - Springer Nueva York, 2009. - Pág. 7174-7201. — ISBN 9780387758886 . -doi : 10.1007 / 978-0-387-30440-3_428 .
  19. ↑ Umesh; Vazirani. Una revisión de la teoría de la complejidad cuántica  (neopr.)  // Actas de simposios en matemáticas aplicadas.
  20. ↑ AP; Lund. Problemas de muestreo cuántico, BosonSampling y supremacía cuántica  //  Npj Quantum Information : diario. - 2017. - 13 de abril ( vol. 3 , no. 1 ). - ISSN 2056-6387 . -doi : 10.1038/ s41534-017-0018-2 . — . -arXiv : 1702.03061 . _
  21. ↑ Michael J.; Bremner. Complejidad de caso promedio versus simulación aproximada de cálculos cuánticos de desplazamiento  // Cartas de revisión física  : revista  . - 2016. - 18 de agosto ( vol. 117 , no. 8 ). — ISSN 0031-9007 . -doi : 10.1103 / PhysRevLett.117.080501 . - . -arXiv : 1504.07999 . _ — PMID 27588839 .
  22. ↑ Jordán. Zoológico de algoritmos cuánticos (enlace no disponible) . math.nist.gov . Consultado el 29 de julio de 2017. Archivado desde el original el 29 de abril de 2018. 
  23. ↑ RL; remache. Un método para obtener firmas digitales y criptosistemas de clave pública  (inglés)  // Commun. ACM  : diario. - 1978. - febrero ( vol. 21 , no. 2 ). - P. 120-126 . — ISSN 0001-0782 . -doi : 10.1145/ 359340.359342 .
  24. ↑ Bernstein, Daniel. Criptografía  poscuántica (neopr.) .
  25. ↑ Aaronson, Scott. La Complejidad Computacional de la  Óptica Lineal .
  26. ↑ Saleh; Rahimi-Keshari. Condiciones suficientes para una simulación clásica eficiente de la óptica cuántica  (inglés)  // Physical Review X  : revista. - 2016. - 20 junio ( vol. 6 , n. 2 ). — Pág. 021039 . -doi : 10.1103/ PhysRevX.6.021039 . - . -arXiv : 1511.06526 . _
  27. ↑ Jacques; carolan Óptica lineal universal  (inglés)  // Ciencia. - 2015. - 14 agosto ( vol. 349 , no. 6249 ). - P. 711-716 . — ISSN 0036-8075 . -doi : 10.1126 / ciencia.aab3642 . -arXiv : 1505.01182 . _ —PMID 26160375 .
  28. ↑ Álex; Neville. No hay supremacía cuántica inminente por muestreo de bosones  // Nature Physics  : revista  . - 2017. - 2 de octubre ( vol. 13 , núm. 12 ). - P. 1153-1157 . — ISSN 1745-2473 . -doi : 10.1038/ nphys4270 . -arXiv : 1705.00686 . _
  29. ↑ Pedro W.; corto Esquema para reducir la decoherencia en la memoria de la computadora cuántica  // Revisión física A  : revista  . - 1995. - 1 de octubre ( vol. 52 , no. 4 ). - P.R2493-R2496 . -doi : 10.1103 / PhysRevA.52.R2493 . - .
  30. ↑ AM; Steane. Códigos de corrección de errores en la teoría cuántica  (inglés)  // Cartas de revisión física  : revista. - 1996. - 29 de julio ( vol. 77 , n. 5 ). - Pág. 793-797 . -doi : 10.1103 / PhysRevLett.77.793 . - . —PMID 10062908 .
  31. ↑ E.; knill Computación cuántica con dispositivos ruidosos realistas  (inglés)  // Nature. - 2005. - 3 de marzo ( vol. 434 , núm. 7029 ). - P. 39-44 . — ISSN 0028-0836 . -doi : 10.1038/ naturaleza03350 . — . — arXiv : quant-ph/0410199 . —PMID 15744292 .