Una computadora cuántica es una computadora que aprovecha los fenómenos de la mecánica cuántica .
A pequeñas escalas, la materia física exhibe propiedades tanto de partículas como de ondas , y la computación cuántica aprovecha este comportamiento, específicamente la superposición y el entrelazamiento cuánticos, utilizando hardware especializado que respalda la preparación y manipulación de estados cuánticos .
La física clásica no puede explicar el funcionamiento de estos dispositivos cuánticos, y una computadora cuántica escalable podría realizar algunos cálculos exponencialmente más rápido (con respecto al escalamiento del tamaño de entrada) [2] que cualquier computadora "clásica" moderna . En particular, una computadora cuántica a gran escala podría romper los esquemas de cifrado ampliamente utilizados y ayudar a los físicos a realizar simulaciones físicas ; sin embargo, el estado actual de la técnica es en gran medida experimental y poco práctico, con varios obstáculos para aplicaciones útiles. Además, las computadoras cuánticas escalables no son prometedoras para muchas tareas prácticas, y para muchas tareas importantes se ha demostrado que las aceleraciones cuánticas son imposibles.
La unidad básica de información en la computación cuántica es el qubit , similar al bit en la electrónica digital tradicional. A diferencia de un bit clásico, un qubit puede existir en una superposición de sus dos estados "básicos". Cuando se mide un qubit, el resultado es una salida probabilística de un bit clásico, por lo que las computadoras cuánticas en general no son deterministas. Si una computadora cuántica manipula el qubit de una manera particular, los efectos de interferencia de ondas pueden amplificar los resultados de medición deseados. El diseño de algoritmos cuánticos implica la creación de procedimientos que permitan a una computadora cuántica realizar cálculos de manera eficiente y rápida.
La ingeniería física de qubits de alta calidad ha demostrado ser un desafío. Si un qubit físico no está suficientemente aislado de su entorno, sufre decoherencia cuántica , introduciendo ruido en los cálculos. Paradójicamente, aislar perfectamente los qubits tampoco es deseable porque los cálculos cuánticos normalmente necesitan inicializar los qubits, realizar interacciones controladas de los qubits y medir los estados cuánticos resultantes. Cada una de esas operaciones introduce errores y sufre ruido, y esas imprecisiones se acumulan.
En principio, una computadora no cuántica (clásica) puede resolver los mismos problemas computacionales que una computadora cuántica, si se le da suficiente tiempo. La ventaja cuántica se presenta en forma de complejidad temporal en lugar de computabilidad , y la teoría de la complejidad cuántica muestra que algunos algoritmos cuánticos para tareas cuidadosamente seleccionadas requieren exponencialmente menos pasos computacionales que los algoritmos no cuánticos más conocidos. En teoría, estas tareas pueden resolverse en una computadora cuántica a gran escala, mientras que las computadoras clásicas no terminarían los cálculos en un período de tiempo razonable. Sin embargo, la aceleración cuántica no es universal ni siquiera típica en las tareas computacionales, ya que se ha demostrado que tareas básicas como la clasificación no permiten ninguna aceleración cuántica asintótica. Las afirmaciones de supremacía cuántica han llamado mucho la atención sobre la disciplina, pero se demuestran en tareas artificiales, mientras que los casos de uso práctico a corto plazo siguen siendo limitados.
Durante muchos años, los campos de la mecánica cuántica y la informática formaron comunidades académicas distintas. [3] La teoría cuántica moderna se desarrolló en la década de 1920 para explicar la dualidad onda-partícula observada a escalas atómicas, [4] y las computadoras digitales surgieron en las décadas siguientes para reemplazar a las computadoras humanas en los cálculos tediosos. [5] Ambas disciplinas tuvieron aplicaciones prácticas durante la Segunda Guerra Mundial ; Las computadoras desempeñaron un papel importante en la criptografía en tiempos de guerra , [6] y la física cuántica fue esencial para la física nuclear utilizada en el Proyecto Manhattan . [7]
A medida que los físicos aplicaron modelos de mecánica cuántica a problemas computacionales e intercambiaron bits digitales por qubits , los campos de la mecánica cuántica y la informática comenzaron a converger. En 1980, Paul Benioff introdujo la máquina cuántica de Turing , que utiliza la teoría cuántica para describir una computadora simplificada. [8] Cuando las computadoras digitales se volvieron más rápidas, los físicos enfrentaron un aumento exponencial de los gastos generales al simular la dinámica cuántica , [9] lo que llevó a Yuri Manin y Richard Feynman a sugerir de forma independiente que el hardware basado en fenómenos cuánticos podría ser más eficiente para la simulación por computadora. [10] [11] [12] En un artículo de 1984, Charles Bennett y Gilles Brassard aplicaron la teoría cuántica a los protocolos de criptografía y demostraron que la distribución de claves cuánticas podría mejorar la seguridad de la información . [13] [14]
Luego surgieron algoritmos cuánticos para resolver problemas de oráculos , como el algoritmo de Deutsch en 1985, [15] el algoritmo de Bernstein-Vazirani en 1993, [16] y el algoritmo de Simon en 1994. [17] Estos algoritmos no resolvieron problemas prácticos, pero demostraron matemáticamente que se podría obtener más información consultando una caja negra con un estado cuántico en superposición , a veces denominado paralelismo cuántico . [18] Peter Shor se basó en estos resultados con sus algoritmos de 1994 para romper los protocolos de cifrado RSA y Diffie-Hellman , ampliamente utilizados, [19] que atrajeron una atención significativa al campo de la computación cuántica. [20] En 1996, el algoritmo de Grover estableció una aceleración cuántica para el problema de búsqueda no estructurada de amplia aplicación . [21] [22] El mismo año, Seth Lloyd demostró que las computadoras cuánticas podían simular sistemas cuánticos sin la sobrecarga exponencial presente en las simulaciones clásicas, [23] validando la conjetura de Feynman de 1982. [24]
A lo largo de los años, los experimentadores han construido computadoras cuánticas a pequeña escala utilizando iones atrapados y superconductores . [25] En 1998, una computadora cuántica de dos qubits demostró la viabilidad de la tecnología, [26] [27] y experimentos posteriores aumentaron el número de qubits y redujeron las tasas de error. [25] En 2019, Google AI y la NASA anunciaron que habían logrado la supremacía cuántica con una máquina de 54 qubits, realizando un cálculo que es imposible para cualquier computadora clásica. [28] [29] [30] Sin embargo, la validez de esta afirmación todavía se está investigando activamente. [31] [32]
El teorema del umbral muestra cómo aumentar el número de qubits puede mitigar los errores, [33] pero la computación cuántica totalmente tolerante a fallos sigue siendo "un sueño bastante lejano". [34] Según algunos investigadores, las ruidosas máquinas cuánticas de escala intermedia ( NISQ ) pueden tener usos especializados en un futuro próximo, pero el ruido en las puertas cuánticas limita su confiabilidad. [34]
La inversión en investigación en computación cuántica ha aumentado en los sectores público y privado. [35] [36] Como resumió una empresa consultora, [37]
... Los dólares de inversión están llegando a raudales y están proliferando las nuevas empresas de computación cuántica. ... Si bien la computación cuántica promete ayudar a las empresas a resolver problemas que están más allá del alcance y la velocidad de las computadoras convencionales de alto rendimiento , los casos de uso son en gran medida experimentales e hipotéticos en esta etapa inicial.
Centrándose en el punto de vista de la gestión empresarial, las aplicaciones potenciales de la computación cuántica se dividen en cuatro categorías principales: ciberseguridad, análisis de datos e inteligencia artificial, optimización y simulación, y gestión y búsqueda de datos. [38]
En diciembre de 2023, los físicos informaron por primera vez sobre el entrelazamiento de moléculas individuales, que puede tener aplicaciones importantes en la computación cuántica. [39] También en diciembre de 2023, los científicos de Harvard crearon con éxito "circuitos cuánticos" que corrigen errores de manera más eficiente que los métodos alternativos, lo que potencialmente puede eliminar un obstáculo importante para las computadoras cuánticas prácticas. [40] [41] El equipo de investigación de Harvard contó con el apoyo del MIT , QuEra Computing , Caltech y Princeton y fue financiado por el programa de optimización con dispositivos cuánticos ruidosos de escala intermedia (ONISQ) de DARPA . [42] [43] Se están realizando esfuerzos de investigación para impulsar la computación cuántica también a través de enfoques topológicos y fotónicos. [44]
Los ingenieros informáticos suelen describir el funcionamiento de una computadora moderna en términos de electrodinámica clásica . Dentro de estas computadoras "clásicas", algunos componentes (como semiconductores y generadores de números aleatorios ) pueden depender del comportamiento cuántico, pero estos componentes no están aislados de su entorno, por lo que cualquier información cuántica se desacopla rápidamente . Si bien los programadores pueden depender de la teoría de la probabilidad al diseñar un algoritmo aleatorio , las nociones de la mecánica cuántica como la superposición y la interferencia son en gran medida irrelevantes para el análisis de programas .
Los programas cuánticos , por el contrario, se basan en un control preciso de sistemas cuánticos coherentes . Los físicos describen estos sistemas matemáticamente utilizando álgebra lineal . Los números complejos modelan amplitudes de probabilidad , los vectores modelan estados cuánticos y las matrices modelan las operaciones que se pueden realizar en estos estados. Programar una computadora cuántica es entonces una cuestión de componer operaciones de tal manera que el programa resultante calcule un resultado útil en teoría y sea implementable en la práctica.
Como el físico Charlie Bennett describe la relación entre las computadoras cuánticas y clásicas, [45]
Una computadora clásica es una computadora cuántica... así que no deberíamos preguntarnos "¿de dónde vienen las aceleraciones cuánticas?" Deberíamos decir: "bueno, todas las computadoras son cuánticas... ¿De dónde vienen las desaceleraciones clásicas?"
Así como el bit es el concepto básico de la teoría de la información clásica, el qubit es la unidad fundamental de información cuántica . El mismo término qubit se utiliza para referirse a un modelo matemático abstracto y a cualquier sistema físico que esté representado por ese modelo. Un bit clásico, por definición, existe en cualquiera de dos estados físicos, que pueden denominarse 0 y 1. Un qubit también se describe mediante un estado, y dos estados a menudo escritos |0⟩ y |1⟩ sirven como contrapartes cuánticas de los estados clásicos 0 y 1. Sin embargo, los estados cuánticos |0⟩ y |1⟩ pertenecen a un espacio vectorial , lo que significa que pueden multiplicarse por constantes y sumarse, y el resultado es nuevamente un estado cuántico válido. Esta combinación se conoce como superposición de |0⟩ y |1⟩ . [46] [47]
Un vector bidimensional representa matemáticamente un estado de qubit. Los físicos suelen utilizar la notación de Dirac para el álgebra lineal de la mecánica cuántica , escribiendo | ψ ⟩ ' ket psi ' para un vector etiquetado como ψ . Debido a que un qubit es un sistema de dos estados, cualquier estado de qubit toma la forma α |0⟩ + β |1⟩ , donde |0⟩ y |1⟩ son los estados base estándar , [a] y α y β son la probabilidad amplitudes , que son en general números complejos . [47] Si α o β es cero, el qubit es efectivamente un bit clásico; cuando ambos son distintos de cero, el qubit está en superposición. Un vector de estado cuántico de este tipo actúa de manera similar a un vector de probabilidad (clásico) , con una diferencia clave: a diferencia de las probabilidades, las amplitudes de probabilidad no son necesariamente números positivos. [49] Las amplitudes negativas permiten interferencias de ondas destructivas.
Cuando un qubit se mide en base estándar , el resultado es un bit clásico. La regla de Born describe la correspondencia norma-cuadrática entre amplitudes y probabilidades: cuando se mide un qubit α |0⟩ + β |1⟩ , el estado colapsa a |0⟩ con probabilidad | α | 2 , o a |1⟩ con probabilidad | β | 2 . Cualquier estado de qubit válido tiene coeficientes α y β tales que | α | 2 + | β | 2 = 1 . Como ejemplo, midiendo el qubit1/√2|0⟩ +1/√2|1⟩ produciría |0⟩ o |1⟩ con la misma probabilidad.
Cada qubit adicional duplica la dimensión del espacio de estados . [48] Como ejemplo, el vector1/√2|00⟩ +1/√2|01⟩ representa un estado de dos qubits, un producto tensorial del qubit |0⟩ con el qubit1/√2|0⟩ +1/√2|1⟩ . Este vector habita en un espacio vectorial de cuatro dimensionesabarcado por los vectores base |00⟩ , |01⟩ , |10⟩ y |11⟩ . El estado de Bell 1/√2|00⟩ +1/√2|11⟩ es imposible descomponerse en el producto tensorial de dos qubits individuales: los dos qubits están entrelazados porque sus amplitudes de probabilidad están correlacionadas . En general, el espacio vectorial para unsistema de n -qubits es 2n -dimensional, y esto hace que sea difícil para una computadora clásica simular uno cuántico: representar un sistema de 100 qubits requiere almacenar 2.100 valores clásicos.
El estado de esta memoria cuántica de un qubit se puede manipular aplicando puertas lógicas cuánticas , de forma análoga a cómo se puede manipular la memoria clásica con puertas lógicas clásicas . Una puerta importante tanto para la computación clásica como para la cuántica es la puerta NOT, que puede representarse mediante una matriz.
Las matemáticas de las puertas de un solo qubit se pueden ampliar para operar en memorias cuánticas de múltiples qubits de dos maneras importantes. Una forma es simplemente seleccionar un qubit y aplicar esa puerta al qubit objetivo sin afectar el resto de la memoria. Otra forma es aplicar la puerta a su objetivo sólo si otra parte de la memoria está en el estado deseado. Estas dos opciones pueden ilustrarse con otro ejemplo. Los posibles estados de una memoria cuántica de dos qubits son
En resumen, la computación cuántica puede describirse como una red de puertas y mediciones de lógica cuántica. Sin embargo, cualquier medición puede posponerse hasta el final de la computación cuántica, aunque este aplazamiento puede tener un costo computacional, por lo que la mayoría de los circuitos cuánticos representan una red que consta únicamente de puertas lógicas cuánticas y ninguna medición.
El paralelismo cuántico es la heurística según la cual se puede considerar que las computadoras cuánticas evalúan una función para múltiples valores de entrada simultáneamente. Esto se puede lograr preparando un sistema cuántico en una superposición de estados de entrada y aplicando una transformación unitaria que codifique la función a evaluar. El estado resultante codifica los valores de salida de la función para todos los valores de entrada en la superposición, lo que permite el cálculo de múltiples salidas simultáneamente. Esta propiedad es clave para acelerar muchos algoritmos cuánticos. Sin embargo, el "paralelismo" en este sentido es insuficiente para acelerar un cálculo, porque la medición al final del cálculo da sólo un valor. Para ser útil, un algoritmo cuántico también debe incorporar algún otro ingrediente conceptual. [50] [51]
Existen varios modelos de computación para la computación cuántica, que se distinguen por los elementos básicos en los que se descompone el cálculo.
Una matriz de puertas cuánticas descompone la computación en una secuencia de puertas cuánticas de unos pocos qubits . Una computación cuántica puede describirse como una red de puertas y mediciones lógicas cuánticas. Sin embargo, cualquier medición puede posponerse hasta el final de la computación cuántica, aunque este aplazamiento puede tener un costo computacional, por lo que la mayoría de los circuitos cuánticos representan una red que consta únicamente de puertas lógicas cuánticas y ninguna medición.
Cualquier cálculo cuántico (que es, en el formalismo anterior, cualquier matriz unitaria de tamaño sobre qubits) puede representarse como una red de puertas lógicas cuánticas de una familia de puertas bastante pequeña. La elección de una familia de puertas que permite esta construcción se conoce como conjunto de puertas universales , ya que una computadora que puede ejecutar dichos circuitos es una computadora cuántica universal . Un conjunto común de este tipo incluye todas las puertas de un solo qubit, así como la puerta CNOT desde arriba. Esto significa que cualquier cálculo cuántico se puede realizar ejecutando una secuencia de puertas de un solo qubit junto con puertas CNOT. Aunque este conjunto de puertas es infinito, se puede reemplazar con un conjunto de puertas finitas apelando al teorema de Solovay-Kitaev .
Una computadora cuántica basada en mediciones descompone el cálculo en una secuencia de mediciones del estado de Bell y puertas cuánticas de un solo qubit aplicadas a un estado inicial altamente entrelazado (un estado de cúmulo ), utilizando una técnica llamada teletransportación de puerta cuántica .
Una computadora cuántica adiabática , basada en el recocido cuántico , descompone el cálculo en una lenta transformación continua de un hamiltoniano inicial en un hamiltoniano final, cuyos estados fundamentales contienen la solución. [52]
Una computadora cuántica topológica descompone la computación en el trenzado de cualquiera en una red 2D. [53]
Una máquina cuántica de Turing es el análogo cuántico de una máquina de Turing . [8] Se ha demostrado que todos estos modelos de computación (circuitos cuánticos, [54] computación cuántica unidireccional, [55] computación cuántica adiabática, [56] y computación cuántica topológica [57]) son equivalentes al modelo cuántico de Turing. máquina; dada una implementación perfecta de una de esas computadoras cuánticas, puede simular todas las demás con no más que una sobrecarga polinómica. Esta equivalencia no tiene por qué ser válida para los ordenadores cuánticos prácticos, ya que los gastos generales de la simulación pueden ser demasiado grandes para ser prácticos.
La criptografía cuántica permite nuevas formas de transmitir datos de forma segura; por ejemplo, la distribución de claves cuánticas utiliza estados cuánticos entrelazados para establecer claves criptográficas seguras . [58] Cuando un remitente y un receptor intercambian estados cuánticos, pueden garantizar que un adversario no intercepte el mensaje, ya que cualquier espía no autorizado perturbaría el delicado sistema cuántico e introduciría un cambio detectable. [59] Con protocolos criptográficos apropiados , el remitente y el receptor pueden establecer información privada compartida resistente a las escuchas ilegales. [13] [60]
Los cables de fibra óptica modernos pueden transmitir información cuántica a distancias relativamente cortas. La investigación experimental en curso tiene como objetivo desarrollar hardware más confiable (como repetidores cuánticos), con la esperanza de escalar esta tecnología a redes cuánticas de larga distancia con entrelazamiento de extremo a extremo. En teoría, esto podría permitir aplicaciones tecnológicas novedosas, como la computación cuántica distribuida y la detección cuántica mejorada . [61] [62]
Los avances en la búsqueda de algoritmos cuánticos normalmente se centran en este modelo de circuito cuántico, aunque existen excepciones como el algoritmo adiabático cuántico . Los algoritmos cuánticos se pueden clasificar aproximadamente por el tipo de aceleración lograda con respecto a los algoritmos clásicos correspondientes. [63]
Los algoritmos cuánticos que ofrecen más que una aceleración polinómica sobre el algoritmo clásico más conocido incluyen el algoritmo de Shor para factorización y los algoritmos cuánticos relacionados para calcular logaritmos discretos , resolver la ecuación de Pell y, de manera más general, resolver el problema de subgrupos ocultos para grupos finitos abelianos . [63] Estos algoritmos dependen de la primitiva de la transformada cuántica de Fourier . No se ha encontrado ninguna prueba matemática que demuestre que no se pueda descubrir un algoritmo clásico igualmente rápido, pero la evidencia sugiere que esto es poco probable. [64] Ciertos problemas de oráculo, como el problema de Simon y el problema de Bernstein-Vazirani, dan aceleraciones demostrables, aunque esto ocurre en el modelo de consulta cuántica , que es un modelo restringido donde los límites inferiores son mucho más fáciles de probar y no necesariamente se traducen en aceleraciones. para problemas prácticos.
Otros problemas, incluida la simulación de procesos físicos cuánticos de la química y la física del estado sólido, la aproximación de ciertos polinomios de Jones y el algoritmo cuántico para sistemas lineales de ecuaciones, tienen algoritmos cuánticos que parecen dar aceleraciones superpolinomiales y son BQP completos. Debido a que estos problemas son BQP completos, un algoritmo clásico igualmente rápido para ellos implicaría que ningún algoritmo cuántico proporciona una aceleración superpolinomial, lo que se cree que es poco probable. [sesenta y cinco]
Algunos algoritmos cuánticos, como el algoritmo de Grover y la amplificación de amplitud , proporcionan aceleraciones polinómicas sobre los algoritmos clásicos correspondientes. [63] Aunque estos algoritmos brindan una aceleración cuadrática comparativamente modesta, son ampliamente aplicables y, por lo tanto, brindan aceleraciones para una amplia gama de problemas. [22]
Dado que la química y la nanotecnología se basan en la comprensión de los sistemas cuánticos, y dichos sistemas son imposibles de simular de manera eficiente de manera clásica, la simulación cuántica puede ser una aplicación importante de la computación cuántica. [66] La simulación cuántica también podría usarse para simular el comportamiento de átomos y partículas en condiciones inusuales, como las reacciones dentro de un colisionador . [67] En junio de 2023, los científicos informáticos de IBM informaron que una computadora cuántica producía mejores resultados para un problema de física que una supercomputadora convencional. [68] [69]
Alrededor del 2% de la producción energética mundial anual se utiliza para la fijación de nitrógeno para producir amoníaco para el proceso Haber en la industria de fertilizantes agrícolas (aunque los organismos naturales también producen amoníaco). Se podrían utilizar simulaciones cuánticas para comprender este proceso y aumentar la eficiencia energética de la producción. [70] Se espera que un uso temprano de la computación cuántica sea un modelo que mejore la eficiencia del proceso Haber-Bosch [71] a mediados de la década de 2020 [72] , aunque algunos han predicho que llevará más tiempo. [73]
Una aplicación notable de la computación cuántica son los ataques a sistemas criptográficos que se utilizan actualmente. Se cree que la factorización de enteros , que sustenta la seguridad de los sistemas criptográficos de clave pública , es computacionalmente inviable con una computadora común para enteros grandes si son producto de unos pocos números primos (por ejemplo, productos de dos primos de 300 dígitos). [74] En comparación, una computadora cuántica podría resolver este problema exponencialmente más rápido usando el algoritmo de Shor para encontrar sus factores. [75] Esta capacidad permitiría a una computadora cuántica romper muchos de los sistemas criptográficos que se utilizan hoy en día, en el sentido de que habría un algoritmo de tiempo polinómico (en el número de dígitos del número entero) para resolver el problema. En particular, la mayoría de los cifrados de clave pública populares se basan en la dificultad de factorizar números enteros o en el problema del logaritmo discreto , los cuales pueden resolverse mediante el algoritmo de Shor. En particular, los algoritmos RSA , Diffie-Hellman y de curva elíptica Diffie-Hellman podrían romperse. Se utilizan para proteger páginas web seguras, correo electrónico cifrado y muchos otros tipos de datos. Romperlos tendría ramificaciones importantes para la privacidad y la seguridad electrónicas.
La identificación de sistemas criptográficos que puedan ser seguros contra los algoritmos cuánticos es un tema de investigación activa en el campo de la criptografía poscuántica . [76] [77] Algunos algoritmos de clave pública se basan en problemas distintos de la factorización de números enteros y los problemas de logaritmos discretos a los que se aplica el algoritmo de Shor, como el criptosistema McEliece basado en un problema de teoría de codificación . [76] [78] Tampoco se sabe que los criptosistemas basados en celosías sean rotos por computadoras cuánticas, y encontrar un algoritmo de tiempo polinomial para resolver el problema del subgrupo oculto del diédrico , que rompería muchos criptosistemas basados en celosías, es un problema abierto bien estudiado. . [79] Se ha demostrado que aplicar el algoritmo de Grover para romper un algoritmo simétrico (clave secreta) mediante fuerza bruta requiere un tiempo equivalente a aproximadamente 2 n /2 invocaciones del algoritmo criptográfico subyacente, en comparación con aproximadamente 2 n en el caso clásico, [ 80] , lo que significa que las longitudes de claves simétricas se reducen efectivamente a la mitad: AES-256 tendría la misma seguridad contra un ataque utilizando el algoritmo de Grover que AES-128 contra la búsqueda clásica de fuerza bruta (consulte Tamaño de clave ).
El ejemplo más conocido de un problema que permite una aceleración cuántica polinómica es la búsqueda no estructurada , que implica encontrar un elemento marcado en una lista de elementos en una base de datos. Esto puede resolverse mediante el algoritmo de Grover mediante consultas a la base de datos, cuadráticamente menos que las consultas requeridas para los algoritmos clásicos. En este caso, la ventaja no sólo es demostrable sino también óptima: se ha demostrado que el algoritmo de Grover proporciona la máxima probabilidad posible de encontrar el elemento deseado para cualquier número de búsquedas de Oracle. Muchos ejemplos de aceleraciones cuánticas demostrables para problemas de consulta se basan en el algoritmo de Grover, incluido el algoritmo de Brassard, Høyer y Tapp para encontrar colisiones en funciones dos a uno, [81] y el algoritmo de Farhi, Goldstone y Gutmann para evaluar árboles NAND. [82]
Los problemas que pueden abordarse eficientemente con el algoritmo de Grover tienen las siguientes propiedades: [83] [84]
Para problemas con todas estas propiedades, el tiempo de ejecución del algoritmo de Grover en una computadora cuántica se escala como la raíz cuadrada del número de entradas (o elementos en la base de datos), a diferencia del escalamiento lineal de los algoritmos clásicos. Una clase general de problemas a los que se puede aplicar el algoritmo de Grover [85] es un problema de satisfacibilidad booleano , donde la base de datos a través de la cual itera el algoritmo es la de todas las respuestas posibles. Un ejemplo y una posible aplicación de esto es un descifrador de contraseñas que intenta adivinar una contraseña. Romper cifrados simétricos con este algoritmo es de interés para las agencias gubernamentales. [86]
El recocido cuántico se basa en el teorema adiabático para realizar cálculos. Se coloca un sistema en el estado fundamental para un hamiltoniano simple, que lentamente evoluciona hacia un hamiltoniano más complicado cuyo estado fundamental representa la solución al problema en cuestión. El teorema adiabático establece que si la evolución es lo suficientemente lenta, el sistema permanecerá en su estado fundamental en todo momento durante el proceso.La optimización adiabática puede resultar útil para resolver problemas de biología computacional . [87]
Dado que las computadoras cuánticas pueden producir resultados que las computadoras clásicas no pueden producir de manera eficiente, y dado que la computación cuántica es fundamentalmente algebraica lineal, algunos expresan esperanza en desarrollar algoritmos cuánticos que puedan acelerar las tareas de aprendizaje automático . [88] [34]
Por ejemplo, se cree que el algoritmo cuántico para sistemas lineales de ecuaciones , o "algoritmo HHL", que lleva el nombre de sus descubridores Harrow, Hassidim y Lloyd, proporciona mayor velocidad que sus homólogos clásicos. [89] [34] Algunos grupos de investigación han explorado recientemente el uso de hardware de recocido cuántico para entrenar máquinas de Boltzmann y redes neuronales profundas . [90] [91] [92]
Los modelos de química generativa profunda emergen como herramientas poderosas para acelerar el descubrimiento de fármacos . Sin embargo, el inmenso tamaño y la complejidad del espacio estructural de todas las posibles moléculas similares a las drogas plantean obstáculos importantes que los ordenadores cuánticos podrían superar en el futuro. Las computadoras cuánticas son naturalmente buenas para resolver problemas complejos de muchos cuerpos cuánticos [23] y, por lo tanto, pueden ser fundamentales en aplicaciones que involucran la química cuántica. Por lo tanto, se puede esperar que los modelos generativos mejorados cuánticamente [93] , incluidas las GAN cuánticas [94], eventualmente puedan convertirse en algoritmos de química generativa definitivos.
A partir de 2023, [actualizar]las computadoras clásicas superarán a las cuánticas en todas las aplicaciones del mundo real. Si bien las computadoras cuánticas actuales pueden acelerar las soluciones a problemas matemáticos particulares, no ofrecen ninguna ventaja computacional para tareas prácticas. Para muchas tareas no hay promesa de una aceleración cuántica útil, y algunas tareas probablemente prohíben cualquier aceleración cuántica en el sentido de que cualquier aceleración está descartada por teoremas probados. Los científicos e ingenieros están explorando múltiples tecnologías para el hardware de computación cuántica y esperan desarrollar arquitecturas cuánticas escalables, pero persisten serios obstáculos. [95] [96]
Hay una serie de desafíos técnicos en la construcción de una computadora cuántica a gran escala. [97] El físico David DiVincenzo ha enumerado estos requisitos para una computadora cuántica práctica: [98]
También es muy difícil conseguir piezas para ordenadores cuánticos. Las computadoras cuánticas superconductoras , como las construidas por Google e IBM , necesitan helio-3 , un subproducto de la investigación nuclear , y cables superconductores especiales fabricados únicamente por la empresa japonesa Coax Co. [99]
El control de sistemas multi-qubit requiere la generación y coordinación de una gran cantidad de señales eléctricas con una resolución temporal ajustada y determinista. Esto ha llevado al desarrollo de controladores cuánticos que permiten la interfaz con los qubits. Escalar estos sistemas para que admitan un número creciente de qubits es un desafío adicional. [100]
Uno de los mayores desafíos relacionados con la construcción de computadoras cuánticas es controlar o eliminar la decoherencia cuántica . Esto generalmente significa aislar el sistema de su entorno, ya que las interacciones con el mundo externo hacen que el sistema se decoherya. Sin embargo, también existen otras fuentes de decoherencia. Los ejemplos incluyen las puertas cuánticas y las vibraciones de la red y el giro termonuclear de fondo del sistema físico utilizado para implementar los qubits. La decoherencia es irreversible, ya que efectivamente no es unitaria y, por lo general, es algo que debe controlarse en gran medida, si no evitarse. Los tiempos de decoherencia para los sistemas candidatos en particular, el tiempo de relajación transversal T 2 (para la tecnología de RMN y RM , también llamado tiempo de desfase ), normalmente oscilan entre nanosegundos y segundos a baja temperatura. [101] Actualmente, algunas computadoras cuánticas requieren que sus qubits se enfríen a 20 mikelvin (generalmente usando un refrigerador de dilución [102] ) para evitar una decoherencia significativa. [103] Un estudio de 2020 sostiene que, no obstante, la radiación ionizante, como los rayos cósmicos, puede hacer que ciertos sistemas se decoheran en milisegundos. [104]
Como resultado, las tareas que consumen mucho tiempo pueden hacer que algunos algoritmos cuánticos sean inoperables, ya que intentar mantener el estado de los qubits durante un tiempo suficientemente largo eventualmente corromperá las superposiciones. [105]
Estos problemas son más difíciles para los enfoques ópticos, ya que las escalas de tiempo son órdenes de magnitud más cortas y un enfoque citado con frecuencia para superarlos es la conformación del pulso óptico . Las tasas de error suelen ser proporcionales a la relación entre el tiempo de operación y el tiempo de decoherencia, por lo que cualquier operación debe completarse mucho más rápido que el tiempo de decoherencia.
Como lo describe el teorema del umbral , si la tasa de error es lo suficientemente pequeña, se cree que es posible utilizar la corrección de errores cuánticos para suprimir errores y decoherencia. Esto permite que el tiempo total de cálculo sea mayor que el tiempo de decoherencia si el esquema de corrección de errores puede corregir los errores más rápido de lo que los introduce la decoherencia. Una cifra que se cita con frecuencia para la tasa de error requerida en cada puerta para el cálculo tolerante a fallas es 10 −3 , suponiendo que el ruido es despolarizante.
Cumplir esta condición de escalabilidad es posible para una amplia gama de sistemas. Sin embargo, el uso de la corrección de errores conlleva el coste de un número mucho mayor de qubits necesarios. El número requerido para factorizar números enteros usando el algoritmo de Shor sigue siendo polinomio y se cree que está entre L y L 2 , donde L es el número de dígitos del número que se va a factorizar; Los algoritmos de corrección de errores inflarían esta cifra en un factor adicional de L. Para un número de 1000 bits, esto implica la necesidad de aproximadamente 10 4 bits sin corrección de errores. [106] Con la corrección de errores, la cifra aumentaría a aproximadamente 10 7 bits. El tiempo de cálculo es de aproximadamente L 2 o aproximadamente 10 7 pasos y a 1 MHz, aproximadamente 10 segundos. Sin embargo, los gastos generales de codificación y corrección de errores aumentan el tamaño de una computadora cuántica real tolerante a fallas en varios órdenes de magnitud. Estimaciones cuidadosas [107] [108] muestran que al menos 3 millones de qubits físicos factorizarían un entero de 2048 bits en 5 meses en una computadora cuántica de iones atrapados con errores totalmente corregidos. En términos del número de qubits físicos, hasta la fecha, esta sigue siendo la estimación más baja [109] para un problema de factorización de enteros prácticamente útil con un tamaño de 1.024 bits o mayor.
Otro enfoque al problema de estabilidad-decoherencia es crear una computadora cuántica topológica con anyons , cuasipartículas utilizadas como hilos, y basándose en la teoría de la trenza para formar puertas lógicas estables. [110] [111]
El físico John Preskill acuñó el término supremacía cuántica para describir la hazaña de la ingeniería de demostrar que un dispositivo cuántico programable puede resolver un problema que va más allá de las capacidades de las computadoras clásicas de última generación. [112] [113] [114] El problema no tiene por qué ser útil, por lo que algunos ven la prueba de supremacía cuántica solo como un posible punto de referencia futuro. [115]
En octubre de 2019, Google AI Quantum, con la ayuda de la NASA, se convirtió en el primero en afirmar haber alcanzado la supremacía cuántica al realizar cálculos en el ordenador cuántico Sycamore más de 3.000.000 de veces más rápido de lo que se podían hacer en Summit , generalmente considerado el más rápido del mundo. computadora. [29] [116] [117] Esta afirmación ha sido cuestionada posteriormente: IBM ha declarado que Summit puede realizar muestras mucho más rápido de lo que se afirma, [118] [119] y desde entonces los investigadores han desarrollado mejores algoritmos para el problema de muestreo utilizado para afirmar que la tecnología cuántica supremacía, reduciendo sustancialmente la brecha entre Sycamore y las supercomputadoras clásicas [120] [121] [122] e incluso superándola. [123] [124] [125]
En diciembre de 2020, un grupo de la USTC implementó un tipo de muestreo de bosones en 76 fotones con una computadora cuántica fotónica , Jiuzhang , para demostrar la supremacía cuántica. [126] [127] [128] Los autores afirman que una supercomputadora clásica contemporánea requeriría un tiempo de cálculo de 600 millones de años para generar la cantidad de muestras que su procesador cuántico puede generar en 20 segundos. [129]
Las afirmaciones de supremacía cuántica han generado revuelo en torno a la computación cuántica, [130] pero se basan en tareas de referencia artificiales que no implican directamente aplicaciones útiles en el mundo real. [95] [131]
A pesar de las grandes esperanzas en la computación cuántica, los avances significativos en el hardware y el optimismo sobre las aplicaciones futuras, un artículo destacado de Nature de 2023 resumió las computadoras cuánticas actuales como "Por ahora, [no sirven para] absolutamente nada". [95] El artículo detalla que las computadoras cuánticas aún no son más útiles o eficientes que las computadoras convencionales en cualquier caso, aunque también argumenta que a largo plazo dichas computadoras probablemente sean útiles. Un artículo de Communications of the ACM de 2023 [96] encontró que los algoritmos de computación cuántica actuales son "insuficientes para una ventaja cuántica práctica sin mejoras significativas en toda la pila de software/hardware". Sostiene que los candidatos más prometedores para lograr la aceleración con las computadoras cuánticas son los "problemas de datos pequeños", por ejemplo en química y ciencia de materiales. Sin embargo, el artículo también concluye que una amplia gama de aplicaciones potenciales que consideró, como el aprendizaje automático, "no lograrán una ventaja cuántica con los algoritmos cuánticos actuales en el futuro previsible", e identificó limitaciones de E/S que hacen que la aceleración sea poco probable para "Problemas de big data, sistemas lineales no estructurados y búsqueda de bases de datos basada en el algoritmo de Grover".
Esta situación puede atribuirse a varias consideraciones actuales y de largo plazo.
En particular, construir computadoras con una gran cantidad de qubits puede ser inútil si esos qubits no están lo suficientemente bien conectados y no pueden mantener un grado de entrelazamiento suficientemente alto durante mucho tiempo. Cuando intentan superar a las computadoras convencionales, los investigadores de computación cuántica a menudo buscan nuevas tareas que puedan resolverse en computadoras cuánticas, pero esto deja la posibilidad de que se desarrollen técnicas no cuánticas eficientes como respuesta, como se vio en las demostraciones de supremacía cuántica . Por lo tanto, es deseable demostrar límites inferiores a la complejidad de los mejores algoritmos no cuánticos posibles (que pueden ser desconocidos) y mostrar que algunos algoritmos cuánticos mejoran asintomáticamente esos límites.
Algunos investigadores han expresado escepticismo sobre la posibilidad de construir computadoras cuánticas escalables, generalmente debido a la cuestión de mantener la coherencia a gran escala, pero también por otras razones.
Bill Unruh dudaba de la practicidad de las computadoras cuánticas en un artículo publicado en 1994. [134] Paul Davies argumentó que una computadora de 400 qubits incluso entraría en conflicto con la información cosmológica vinculada al principio holográfico . [135] Escépticos como Gil Kalai dudan de que alguna vez se logre la supremacía cuántica. [136] [137] [138] El físico Mikhail Dyakonov ha expresado su escepticismo sobre la computación cuántica de la siguiente manera:
Una computadora cuántica práctica debe utilizar un sistema físico como registro cuántico programable. [141] Los investigadores están explorando varias tecnologías como candidatas para implementaciones confiables de qubits. [142] Los superconductores y los iones atrapados son algunas de las propuestas más desarrolladas, pero los experimentadores también están considerando otras posibilidades de hardware. [143]
Cualquier problema computacional que pueda resolverse con una computadora clásica también lo puede resolver una computadora cuántica. [144] Intuitivamente, esto se debe a que se cree que todos los fenómenos físicos, incluido el funcionamiento de las computadoras clásicas, pueden describirse utilizando la mecánica cuántica , que es la base del funcionamiento de las computadoras cuánticas.
Por el contrario, cualquier problema que pueda resolverse con una computadora cuántica también lo puede resolver una computadora clásica. Es posible simular manualmente computadoras cuánticas y clásicas con solo un poco de papel y un bolígrafo, si se le da suficiente tiempo. Más formalmente, cualquier computadora cuántica puede ser simulada por una máquina de Turing . En otras palabras, las computadoras cuánticas no proporcionan potencia adicional sobre las computadoras clásicas en términos de computabilidad . Esto significa que las computadoras cuánticas no pueden resolver problemas indecidibles como el problema de la detención , y la existencia de computadoras cuánticas no refuta la tesis de Church-Turing . [145]
Si bien las computadoras cuánticas no pueden resolver ningún problema que las computadoras clásicas ya no puedan resolver, se sospecha que pueden resolver ciertos problemas más rápido que las computadoras clásicas. Por ejemplo, se sabe que las computadoras cuánticas pueden factorizar números enteros de manera eficiente , mientras que no se cree que este sea el caso de las computadoras clásicas.
La clase de problemas que puede resolver eficientemente una computadora cuántica con error acotado se llama BQP , que significa "error acotado, tiempo polinómico cuántico". Más formalmente, BQP es la clase de problemas que pueden resolverse mediante una máquina cuántica de Turing de tiempo polinomial con una probabilidad de error de como máximo 1/3. Como clase de problemas probabilísticos, BQP es la contraparte cuántica de BPP ("error acotado, probabilístico, tiempo polinomial"), la clase de problemas que pueden resolverse mediante máquinas de Turing probabilísticas de tiempo polinomial con error acotado. [146] Se sabe y se sospecha ampliamente que , lo que intuitivamente significaría que las computadoras cuánticas son más poderosas que las computadoras clásicas en términos de complejidad temporal . [147]
Se desconoce la relación exacta de BQP con P , NP y PSPACE . Sin embargo, se sabe que ; es decir, todos los problemas que pueden resolverse eficientemente con una computadora clásica determinista también pueden resolverse eficientemente con una computadora cuántica, y todos los problemas que pueden resolverse eficientemente con una computadora cuántica también pueden resolverse con una computadora clásica determinista con recursos espaciales polinomiales . Además, se sospecha que BQP es un superconjunto estricto de P, lo que significa que hay problemas que pueden resolverse eficientemente mediante computadoras cuánticas que no pueden resolverse eficientemente mediante computadoras clásicas deterministas. Por ejemplo, se sabe que la factorización de números enteros y el problema de logaritmos discretos están en BQP y se sospecha que están fuera de P. Sobre la relación de BQP con NP, poco se sabe más allá del hecho de que algunos problemas de NP que se cree que no están en P también están en BQP (la factorización de números enteros y el problema de logaritmos discretos están ambos en NP, por ejemplo). Se sospecha que ; es decir, se cree que existen problemas comprobables de manera eficiente que no pueden resolverse de manera eficiente mediante una computadora cuántica. Como consecuencia directa de esta creencia, también se sospecha que BQP está separado de la clase de problemas NP-completos (si un problema NP-completo estuviera en BQP, entonces se seguiría de la dureza NP que todos los problemas en NP están en BQP). [148]