Algoritmo cuántico

El algoritmo de Deutsch-Jozsa resuelve un problema de caja negra que requiere un número exponencial de consultas a la caja negra para cualquier computadora clásica determinista, pero que una computadora cuántica puede resolver con una sola consulta. Sin embargo, al comparar algoritmos clásicos y cuánticos con error limitado, no se observa una mejora en la velocidad, ya que un algoritmo probabilístico clásico puede resolver el problema con un número constante de consultas con una baja probabilidad de error. El algoritmo determina si una función f es constante (0 para todas las entradas o 1 para todas las entradas) o equilibrada (devuelve 1 para la mitad del dominio de entrada y 0 para la otra mitad).

El algoritmo de Bernstein-Vazirani es el primer algoritmo cuántico que resuelve un problema de manera más eficiente que el mejor algoritmo clásico conocido. Fue diseñado para crear una separación de oráculo entre BQP y BPP .

El algoritmo de Simon resuelve un problema de caja negra exponencialmente más rápido que cualquier algoritmo clásico, incluidos los algoritmos probabilísticos de error limitado. Este algoritmo, que logra una aceleración exponencial con respecto a todos los algoritmos clásicos que consideramos eficientes, fue la inspiración para el algoritmo de Shor para la factorización.

El algoritmo de estimación de fase cuántica se utiliza para determinar la fase propia de un vector propio de una puerta unitaria, dado un estado cuántico proporcional al vector propio y el acceso a la puerta. Este algoritmo se utiliza frecuentemente como subrutina en otros algoritmos.

El algoritmo de Shor resuelve el problema del logaritmo discreto y el problema de la factorización de enteros en tiempo polinomial, ^{[ 9 ]} mientras que los mejores algoritmos clásicos conocidos requieren tiempo superpolinomial. Se desconoce si estos problemas son P o NP-completos . Además, es uno de los pocos algoritmos cuánticos que resuelve un problema no de caja negra en tiempo polinomial, mientras que los mejores algoritmos clásicos conocidos se ejecutan en tiempo superpolinomial.

El problema del subgrupo oculto abeliano es una generalización de muchos problemas que pueden ser resueltos por una computadora cuántica, como el problema de Simon, la resolución de la ecuación de Pell , la comprobación del ideal principal de un anillo R y la factorización . Se conocen algoritmos cuánticos eficientes para el problema del subgrupo oculto abeliano. ^{[ 10 ]} El problema del subgrupo oculto más general, donde el grupo no es necesariamente abeliano, es una generalización de los problemas mencionados anteriormente, así como del isomorfismo de grafos y ciertos problemas de retículos . Se conocen algoritmos cuánticos eficientes para ciertos grupos no abelianos. Sin embargo, no se conocen algoritmos eficientes para el grupo simétrico , que proporcionaría un algoritmo eficiente para el isomorfismo de grafos ^{[ 11 ]} y el grupo diedral , que resolvería ciertos problemas de retículos. ^{[ 12 ]}

Una suma de Gauss es un tipo de suma exponencial . El algoritmo clásico más conocido para estimar estas sumas requiere tiempo exponencial. Dado que el problema del logaritmo discreto se reduce a la estimación de sumas de Gauss, un algoritmo clásico eficiente para estimar sumas de Gauss implicaría un algoritmo clásico eficiente para calcular logaritmos discretos, lo cual se considera improbable. Sin embargo, las computadoras cuánticas pueden estimar sumas de Gauss con precisión polinómica en tiempo polinómico. ^{[ 13 ]}

Consideremos un oráculo que consta de n funciones booleanas aleatorias que asignan cadenas de n bits a un valor booleano, con el objetivo de encontrar n cadenas de n bits z ₁ ,..., z _n tales que, para la transformada de Hadamard-Fourier, al menos 3/4 de las cadenas satisfagan

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

y al menos 1/4 satisfacen

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2.}$

Esto se puede hacer en tiempo polinomial cuántico con error limitado (BQP). ^{[ 14 ]}

El algoritmo de Grover busca una entrada marcada en una base de datos no estructurada (o una lista desordenada) con N entradas, utilizando únicamente${\displaystyle O({\sqrt {N}})}$consultas en lugar de la${\displaystyle O({N})}$consultas requeridas clásicamente. ^{[ 15 ]} Clásicamente,${\displaystyle O({N})}$Se requieren consultas incluso permitiendo algoritmos probabilísticos con error limitado.

Los teóricos han considerado una generalización hipotética de una computadora cuántica estándar que podría acceder a los historiales de las variables ocultas en la mecánica de Bohm . (Tal computadora es completamente hipotética y no sería una computadora cuántica estándar, ni siquiera posible bajo la teoría estándar de la mecánica cuántica). Dicha computadora hipotética podría implementar una búsqueda en una base de datos de N elementos en como máximo${\displaystyle O({\sqrt[{3}]{N}})}$pasos. Esto es un poco más rápido que el${\displaystyle O({\sqrt {N}})}$pasos dados por el algoritmo de Grover. Sin embargo, ninguno de los métodos de búsqueda permitiría que ninguno de los modelos de computadora cuántica resolviera problemas NP-completos en tiempo polinomial. ^{[ 16 ]}

El conteo cuántico resuelve una generalización del problema de búsqueda. Resuelve el problema de contar el número de entradas marcadas en una lista desordenada, en lugar de simplemente detectar si existe alguna. Específicamente, cuenta el número de entradas marcadas en una${\displaystyle N}$-lista de elementos con un error de como máximo${\displaystyle \varepsilon }$haciendo solo${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$consultas, donde${\displaystyle k}$es el número de elementos marcados en la lista. ^{[ 17 ] [ 18 ]} Más precisamente, el algoritmo produce una estimación${\displaystyle k'}$para${\displaystyle k}$, el número de entradas marcadas, con precisión${\displaystyle |kk'|\leq \varepsilon k}$.

El problema del muestreo de bosones en una configuración experimental asume ^{[ 22 ]} una entrada de bosones (por ejemplo, fotones) de número moderado que se dispersan aleatoriamente en un gran número de modos de salida, restringidos por una unitariedad definida . Cuando se utilizan fotones individuales, el problema es isomorfo a un paseo cuántico multifotónico. ^{[ 23 ]} El problema consiste entonces en producir una muestra justa de la distribución de probabilidad de la salida que depende de la disposición de entrada de los bosones y la unitariedad. ^{[ 24 ]} Resolver este problema con un algoritmo informático clásico requiere calcular el permanente de la matriz de transformación unitaria, lo que puede llevar un tiempo prohibitivamente largo o ser directamente imposible. En 2014, se propuso ^{[ 25 ]} que la tecnología existente y los métodos probabilísticos estándar de generación de estados de un solo fotón podrían utilizarse como entrada en una red óptica lineal computable cuánticamente adecuada y que el muestreo de la distribución de probabilidad de salida sería demostrablemente superior utilizando algoritmos cuánticos. En 2015, la investigación predijo ^{[ 26 ]} que el problema de muestreo tenía una complejidad similar para entradas distintas a los fotones del estado de Fock e identificó una transición en la complejidad computacional de simulable clásicamente a tan difícil como el problema de muestreo de bosones, dependiendo del tamaño de las entradas de amplitud coherente.

El problema de la distinción de elementos es el problema de determinar si todos los elementos de una lista son distintos. Clásicamente,${\displaystyle \Omega (N)}$Se requieren consultas para una lista de tamaño${\displaystyle N}$; sin embargo, se puede resolver en${\displaystyle \Theta (N^{2/3})}$consultas en una computadora cuántica. El algoritmo óptimo fue propuesto por Andris Ambainis , ^{[ 27 ]} y Yaoyun Shi demostró por primera vez una cota inferior ajustada cuando el tamaño del rango es suficientemente grande. ^{[ 28 ]} Ambainis ^{[ 29 ]} y Kutin ^{[ 30 ]} de forma independiente (y mediante diferentes demostraciones) extendieron ese trabajo para obtener la cota inferior para todas las funciones.

El problema de encontrar triángulos es el problema de determinar si un grafo dado con N vértices contiene un triángulo (una camarilla de tamaño 3). Dado el acceso de oráculo a la matriz de adyacencia del grafo, la complejidad de consulta clásica es${\displaystyle \Theta (N^{2})}$, ya que para un grafo con un solo triángulo esta es la complejidad de consulta necesaria para encontrar cualquier arista. Mientras tanto, para los algoritmos cuánticos el límite inferior es${\displaystyle \Omega (N)}$, el número de consultas necesarias para encontrar cualquier arista con el algoritmo de Grover. Sin embargo, encontrar cualquier arista no garantiza encontrar un triángulo si existe alguno. Una búsqueda de Grover sobre todas${\displaystyle \Theta (N^{3})}$El método de triángulos potenciales resuelve el problema, pero la complejidad de la consulta, O( N³ ^/² ), puede mejorarse. ^{[ 31 ]}

Mientras${\displaystyle \Omega (N)}$sigue siendo el límite inferior más conocido para algoritmos cuánticos, el mejor algoritmo conocido requiere O( N ^5/4 ) consultas, ^{[ 32 ]} una mejora sobre el mejor anterior O( N ^1.3 ) consultas. ^{[ 21 ] [ 33 ]}

Una fórmula es un árbol con una puerta lógica en cada nodo interno y un bit de entrada en cada nodo hoja. El problema consiste en evaluar la fórmula, que es la salida del nodo raíz, teniendo acceso de oráculo a la entrada.

Una fórmula bien estudiada es el árbol binario balanceado con solo puertas NAND. ^{[ 34 ]} Este tipo de fórmula requiere${\displaystyle \Theta (N^{c})}$consultas que utilizan aleatoriedad, ^{[ 35 ]} donde${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$Sin embargo, con un algoritmo cuántico, se puede resolver en${\displaystyle \Theta (N^{1/2})}$consultas. No se conocía ningún algoritmo cuántico mejor para este caso hasta que se encontró uno para el modelo de oráculo hamiltoniano no convencional. ^{[ 7 ]} Pronto se obtuvo el mismo resultado para la configuración estándar. ^{[ 36 ]}

También se conocen algoritmos cuánticos rápidos para fórmulas más complejas. ^{[ 37 ]}

El problema consiste en determinar si un grupo de caja negra , dado por k generadores, es conmutativo . Un grupo de caja negra es un grupo con una función oráculo, que debe utilizarse para realizar las operaciones del grupo (multiplicación, inversión y comparación con la identidad). El interés en este contexto radica en la complejidad de la consulta, que es el número de llamadas al oráculo necesarias para resolver el problema. Las complejidades de consulta deterministas y aleatorias son:${\displaystyle \Theta (k^{2})}$y${\displaystyle \Theta (k)}$, respectivamente. ^{[ 38 ]} Un algoritmo cuántico requiere${\displaystyle \Omega (k^{2/3})}$consultas, mientras que el algoritmo clásico más conocido utiliza${\displaystyle O(k^{2/3}\log k)}$consultas. ^{[ 39 ]}

Witten había demostrado que la teoría cuántica de campos topológica (TQFT) de Chern-Simons se puede resolver en términos de polinomios de Jones . Una computadora cuántica puede simular una TQFT y, por lo tanto, aproximar el polinomio de Jones, ^{[ 41 ]} que, hasta donde sabemos, es difícil de calcular clásicamente en el peor de los casos.

La idea de que las computadoras cuánticas podrían ser más potentes que las clásicas se originó en la observación de Richard Feynman de que las computadoras clásicas parecen requerir un tiempo exponencial para simular sistemas cuánticos de muchas partículas, mientras que los sistemas cuánticos de muchos cuerpos son capaces de "resolverse a sí mismos". ^{[ 42 ]} Desde entonces, la idea de que las computadoras cuánticas pueden simular procesos físicos cuánticos exponencialmente más rápido que las computadoras clásicas se ha desarrollado y elaborado ampliamente. Se han desarrollado algoritmos cuánticos eficientes (es decir, de tiempo polinomial) para simular sistemas bosónicos y fermiónicos, ^{[ 43 ]} así como la simulación de reacciones químicas que van más allá de las capacidades de las supercomputadoras clásicas actuales utilizando solo unos pocos cientos de cúbits. ^{[ 44 ]} Las computadoras cuánticas también pueden simular eficientemente teorías de campos cuánticos topológicos. ^{[ 45 ]} Además de su interés intrínseco, este resultado ha dado lugar a algoritmos cuánticos eficientes para estimar invariantes topológicos cuánticos como los polinomios de Jones ^{[ 46 ]} y HOMFLY , ^{[ 47 ]} y el invariante de Turaev-Viro de variedades tridimensionales. ^{[ 48 ]}

En 2009, Aram Harrow , Avinatan Hassidim y Seth Lloyd formularon un algoritmo cuántico para resolver sistemas lineales . El algoritmo estima el resultado de una medición escalar sobre el vector solución de un sistema de ecuaciones lineales dado. ^{[ 49 ]}

Siempre que el sistema lineal sea disperso y tenga un número de condición bajo.${\displaystyle \kappa }$y que el usuario está interesado en el resultado de una medición escalar en el vector solución (en lugar de los valores del propio vector solución), entonces el algoritmo tiene un tiempo de ejecución de${\displaystyle O(\log(N)\kappa ^{2})}$, dónde${\displaystyle N}$es el número de variables en el sistema lineal. Esto ofrece una aceleración exponencial con respecto al algoritmo clásico más rápido, que se ejecuta en${\displaystyle O(N\kappa )}$(o${\displaystyle O(N{\sqrt {\kappa }})}$para matrices semidefinidas positivas).

El algoritmo de optimización cuántica aproximada se inspira en el recocido cuántico, realizando una aproximación discretizada del mismo mediante un circuito cuántico. Puede utilizarse para resolver problemas en teoría de grafos. ^{[ 51 ]} El algoritmo emplea la optimización clásica de operaciones cuánticas para maximizar una "función objetivo".

El algoritmo de resolución de valores propios cuánticos variacionales (VQE) aplica la optimización clásica para minimizar el valor esperado de la energía de un estado de prueba y así encontrar el estado fundamental de un operador hermitiano, como el hamiltoniano de una molécula. ^{[ 52 ]} También puede extenderse para encontrar energías excitadas de hamiltonianos moleculares. ^{[ 53 ]}

El algoritmo de resolución de autovalores cuánticos contraídos (CQE) minimiza el residuo de una contracción (o proyección) de la ecuación de Schrödinger sobre el espacio de dos (o más) electrones para encontrar la energía del estado fundamental o excitado y la matriz de densidad reducida de dos electrones de una molécula. ^{[ 54 ]} Se basa en métodos clásicos para resolver energías y matrices de densidad reducidas de dos electrones directamente a partir de la ecuación de Schrödinger contraída antihermítica. ^{[ 55 ]}

• Dalzell, Alexander M.; et  al. (2025). Algoritmos cuánticos . arXiv : 2310.03011 . doi : 10.1017/9781009639651 . ISBN 978-1-009-63965-1.
• Smith, J.; Mosca, M. (2012). «Algoritmos para computadoras cuánticas». Manual de computación natural . págs. 1451–1492 . arXiv : 1001.0767 . doi : 10.1007/978-3-540-92910-9_43 . ISBN  978-3-540-92909-3. S2CID 16565723 . 
• Childs, AM; Van Dam, W. (2010). "Algoritmos cuánticos para problemas algebraicos". Reviews of Modern Physics . 82 (1): 1– 52. arXiv : 0812.0380 . Bibcode : 2010RvMP...82....1C . doi : 10.1103/RevModPhys.82.1 . S2CID 119261679 .