Algoritmo cuántico

Los algoritmos se ejecutan en computadoras cuánticas y generalmente se basan en la superposición y/o el entrelazamiento.

En computación cuántica , un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica , siendo el modelo más comúnmente utilizado el modelo de computación de circuito cuántico . ^{[1] [2]} Un algoritmo clásico (o no cuántico) es una secuencia finita de instrucciones, o un procedimiento paso a paso para resolver un problema, donde cada paso o instrucción se puede realizar en una computadora clásica . De manera similar, un algoritmo cuántico es un procedimiento paso a paso, donde cada uno de los pasos se puede realizar en una computadora cuántica . Aunque todos los algoritmos clásicos también se pueden realizar en una computadora cuántica, ^{[3] : 126} el término algoritmo cuántico generalmente se reserva para algoritmos que parecen inherentemente cuánticos o que utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el entrelazamiento cuántico .

Los problemas que son indecidibles con las computadoras clásicas siguen siendo indecidibles con las computadoras cuánticas. ^{[4] : 127} Lo que hace que los algoritmos cuánticos sean interesantes es que podrían resolver algunos problemas más rápido que los algoritmos clásicos porque la superposición cuántica y el entrelazamiento cuántico que explotan los algoritmos cuánticos generalmente no se pueden simular de manera eficiente en computadoras clásicas (ver Supremacía cuántica ).

Los algoritmos más conocidos son el algoritmo de Shor para factorizar y el algoritmo de Grover para buscar en una base de datos no estructurada o en una lista desordenada. El algoritmo de Shor se ejecuta mucho (casi exponencialmente) más rápido que el algoritmo clásico de factorización más conocido, el tamiz de campo numérico general . ^[5] El algoritmo de Grover se ejecuta cuadráticamente más rápido que el mejor algoritmo clásico posible para la misma tarea, ^[6] una búsqueda lineal .

Descripción general

Los algoritmos cuánticos generalmente se describen, en el modelo de circuito de computación cuántica comúnmente utilizado, mediante un circuito cuántico que actúa sobre algunos qubits de entrada y termina con una medición . Un circuito cuántico consta de puertas cuánticas simples , cada una de las cuales actúa sobre un número finito de qubits. Los algoritmos cuánticos también pueden enunciarse en otros modelos de computación cuántica, como el modelo del oráculo hamiltoniano. ^[7]

Los algoritmos cuánticos se pueden clasificar según las principales técnicas involucradas en el algoritmo. Algunas técnicas/ideas comúnmente utilizadas en algoritmos cuánticos incluyen retroceso de fase, estimación de fase , transformada cuántica de Fourier , paseos cuánticos , amplificación de amplitud y teoría de campos cuánticos topológicos . Los algoritmos cuánticos también pueden agruparse por el tipo de problema resuelto; véase, por ejemplo, el estudio sobre algoritmos cuánticos para problemas algebraicos. ^[8]

Algoritmos basados ​​en la transformada cuántica de Fourier

La transformada cuántica de Fourier es el análogo cuántico de la transformada discreta de Fourier y se utiliza en varios algoritmos cuánticos. La transformada de Hadamard es también un ejemplo de transformada cuántica de Fourier en un espacio vectorial de n dimensiones sobre el campo F 2 . La transformada cuántica de Fourier se puede implementar eficientemente en una computadora cuántica usando sólo un número polinómico de puertas cuánticas . ^{[ cita necesaria ]}

Algoritmo de Deutsch-Jozsa

Algoritmo de Deutsch-Jozsa

El algoritmo Deutsch-Jozsa resuelve un problema de caja negra que requiere exponencialmente muchas 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 de error acotado, no hay aceleración, ya que un algoritmo probabilístico clásico puede resolver el problema con un número constante de consultas con una pequeña probabilidad de error. El algoritmo determina si una función f es constante (0 en todas las entradas o 1 en todas las entradas) o equilibrada (devuelve 1 para la mitad del dominio de entrada y 0 para la otra mitad).

Algoritmo de Bernstein-Vazirani

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

algoritmo de simon

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 acotado. Este algoritmo, que logra una aceleración exponencial sobre todos los algoritmos clásicos que consideramos eficientes, fue la motivación para el algoritmo de factorización de Shor .

Algoritmo de estimación de fase cuántica

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 al acceso a la puerta. El algoritmo se utiliza frecuentemente como subrutina en otros algoritmos.

algoritmo de shor

El algoritmo de Shor resuelve el problema de logaritmos discretos y el problema de factorización de enteros en tiempo polinomial, ^[9] mientras que los algoritmos clásicos más conocidos toman tiempo superpolinomial. No se sabe que estos problemas estén en P o NP-completo . También es uno de los pocos algoritmos cuánticos que resuelve un problema que no es de caja negra en tiempo polinomial, mientras que los algoritmos clásicos más conocidos se ejecutan en tiempo superpolinomial.

Problema de subgrupo oculto

El problema abeliano de subgrupos ocultos es una generalización de muchos problemas que pueden resolverse mediante una computadora cuántica, como el problema de Simon, la resolución de la ecuación de Pell , la prueba del ideal principal de un anillo R y la factorización . Existen algoritmos cuánticos eficientes conocidos para el problema de subgrupos ocultos abelianos. ^[10] El problema de subgrupos ocultos más general, donde el grupo no es necesariamente abeliano, es una generalización de los problemas mencionados anteriormente, así como el isomorfismo de gráficos y ciertos problemas de celosía . Se conocen algoritmos cuánticos eficientes para ciertos grupos no abelianos. Sin embargo, no se conocen algoritmos eficientes para el grupo simétrico , lo que daría un algoritmo eficiente para el isomorfismo de grafos ^[11] y el grupo diédrico , que resolvería ciertos problemas de red. ^[12]

Estimación de sumas de Gauss

Una suma de Gauss es un tipo de suma exponencial . El algoritmo clásico más conocido para estimar estas sumas requiere un tiempo exponencial. Dado que el problema de los logaritmos discretos se reduce a la estimación de la suma 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 poco probable. Sin embargo, las computadoras cuánticas pueden estimar sumas de Gauss con precisión polinómica en tiempo polinómico. ^[13]

Pesca de Fourier y control de Fourier

Considere 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 satisfacen

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

y al menos 1/4 de satisfacer

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

Esto se puede hacer en tiempo polinomial cuántico de error acotado (BQP). ^[14]

Algoritmos basados ​​en amplificación de amplitud.

La amplificación de amplitud es una técnica que permite la amplificación de un subespacio elegido de un estado cuántico. Las aplicaciones de amplificación de amplitud suelen conducir a aceleraciones cuadráticas con respecto a los algoritmos clásicos correspondientes. Puede considerarse como una generalización del algoritmo de Grover. ^{[ cita necesaria ]}

algoritmo de Grover

El algoritmo de Grover busca una base de datos no estructurada (o una lista desordenada) con N entradas para una entrada marcada, utilizando sólo consultas en lugar de las consultas requeridas clásicamente. ^[15] Clásicamente, las consultas son necesarias incluso permitiendo algoritmos probabilísticos de error acotado. ${\displaystyle O({\sqrt {N}})}$ ${\displaystyle O({N})}$ ${\displaystyle O({N})}$

Los teóricos han considerado una generalización hipotética de una computadora cuántica estándar que podría acceder a las historias de las variables ocultas en la mecánica de Bohm . (Una computadora de este tipo es completamente hipotética y no sería una computadora cuántica estándar, ni siquiera sería posible según la teoría estándar de la mecánica cuántica). Una computadora tan hipotética podría implementar una búsqueda en una base de datos de N elementos en la mayoría de los pasos. Esto es un poco más rápido que los 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. ^[dieciséis] ${\displaystyle O({\sqrt[{3}]{N}})}$ ${\displaystyle O({\sqrt {N}})}$

conteo cuántico

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 lista de elementos con un error de como máximo realizando solo consultas, donde es el número de elementos marcados en la lista. ^{[17] [18]} Más precisamente, el algoritmo genera una estimación de , el número de entradas marcadas, con precisión . ${\displaystyle N}$ ${\displaystyle \varepsilon }$ ${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$ ${\displaystyle k}$ ${\displaystyle k'}$ ${\displaystyle k}$ ${\displaystyle |k-k'|\leq \varepsilon k}$

Algoritmos basados ​​en paseos cuánticos

Una caminata cuántica es el análogo cuántico de una caminata aleatoria clásica . Un paseo aleatorio clásico puede describirse mediante una distribución de probabilidad sobre algunos estados, mientras que un paseo cuántico puede describirse mediante una superposición cuántica sobre estados. Se sabe que los paseos cuánticos dan aceleraciones exponenciales para algunos problemas de caja negra. ^{[19] [20]} También proporcionan aceleraciones polinómicas para muchos problemas. Existe un marco para la creación de algoritmos de caminata cuántica y es una herramienta versátil. ^[21]

Problema de muestreo de bosones

El problema de muestreo de bosones en una configuración experimental supone ^[22] una entrada de bosones (por ejemplo, fotones) de un número moderado que se dispersan aleatoriamente en una gran cantidad de modos de salida, restringidos por una unitaridad definida . Cuando se utilizan fotones individuales, el problema es isomorfo a una caminata cuántica de múltiples fotones. ^[23] El problema es entonces 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 unitaridad. ^[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 absolutamente imposible. En 2014, se propuso ^[25] que la tecnología existente y los métodos probabilísticos estándar para generar estados de fotón único podrían usarse como entrada en una red óptica lineal computable cuántica adecuada y que el muestreo de la distribución de probabilidad de salida sería demostrablemente superior utilizando la tecnología cuántica. algoritmos. En 2015, una investigación predijo ^[26] que el problema de muestreo tenía una complejidad similar para entradas distintas de los fotones del estado de Fock e identificó una transición en la complejidad computacional de lo clásicamente simulable a tan difícil como el problema de muestreo de bosones, dependiendo del tamaño de las entradas de amplitud coherente. .

Problema de distinción de elementos

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

Problema de búsqueda de triángulos

El problema de encontrar triángulos es el problema de determinar si una gráfica dada contiene un triángulo (una camarilla de tamaño 3). El límite inferior más conocido para los algoritmos cuánticos es , pero el mejor algoritmo conocido requiere consultas O ( N ^{1,297 ), [31]} , una mejora con respecto a las mejores consultas O ( N ^{1,3 ) anteriores. [21] [32]} ${\displaystyle \Omega (N)}$

Evaluación de fórmulas

Una fórmula es un árbol con una puerta en cada nodo interno y un bit de entrada en cada nodo hoja. El problema es evaluar la fórmula, que es la salida del nodo raíz, dado el acceso de Oracle a la entrada.

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

También se conocen algoritmos cuánticos rápidos para fórmulas más complicadas. ^[36]

Conmutatividad grupal

El problema es 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 de Oracle, que debe usarse para realizar las operaciones del grupo (multiplicación, inversión y comparación con identidad). El interés en este contexto radica en la complejidad de la consulta, que es la cantidad de llamadas a Oracle necesarias para resolver el problema. Las complejidades de las consultas deterministas y aleatorias son y , respectivamente. ^[37] Un algoritmo cuántico requiere consultas, mientras que el algoritmo clásico más conocido utiliza consultas. ^[38] ${\displaystyle \Theta (k^{2})}$ ${\displaystyle \Theta (k)}$ ${\displaystyle \Omega (k^{2/3})}$ ${\displaystyle O(k^{2/3}\log k)}$

Problemas completos de BQP

La clase de complejidad BQP (tiempo polinómico cuántico de error acotado) es el conjunto de problemas de decisión que puede resolver una computadora cuántica en tiempo polinómico con una probabilidad de error de como máximo 1/3 para todos los casos. ^[39] Es el análogo cuántico de la clase de complejidad clásica BPP .

Un problema es BQP completo si está en BQP y cualquier problema en BQP puede reducirse a él en tiempo polinomial . De manera informal, la clase de problemas completos de BQP son aquellos que son tan difíciles como los problemas más difíciles de BQP y que en sí mismos pueden resolverse eficientemente mediante una computadora cuántica (con error acotado).

Calcular invariantes de nudos

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

Simulación cuántica

La idea de que las computadoras cuánticas podrían ser más poderosas 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, pero los sistemas cuánticos de muchos cuerpos son capaces de "resolverse por sí mismos". ^[41] 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 enormemente. Se han desarrollado algoritmos cuánticos eficientes (es decir, de tiempo polinomial) para simular sistemas bosónicos y fermiónicos, ^[42] así como para la simulación de reacciones químicas más allá de las capacidades de las supercomputadoras clásicas actuales utilizando sólo unos pocos cientos de qubits. ^[43] Las computadoras cuánticas también pueden simular eficientemente teorías topológicas de campos cuánticos. ^[44] Además de su interés intrínseco, este resultado ha llevado a algoritmos cuánticos eficientes para estimar invariantes topológicos cuánticos como los polinomios de Jones ^[45] y HOMFLY , ^[46] y el invariante Turaev-Viro de variedades tridimensionales. ^[47]

Resolver sistemas lineales de ecuaciones.

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 en el vector solución de un sistema lineal de ecuaciones dado. ^[48]

Siempre que el sistema lineal sea disperso y tenga un número de condición bajo , y que el usuario esté interesado en el resultado de una medición escalar en el vector de solución (en lugar de los valores del vector de solución en sí), entonces el algoritmo tiene un tiempo de ejecución de , donde 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 (o para matrices semidefinidas positivas). ${\displaystyle \kappa }$ ${\displaystyle O(\log(N)\kappa ^{2})}$ ${\displaystyle N}$ ${\displaystyle O(N\kappa )}$ ${\displaystyle O(N{\sqrt {\kappa }})}$

Algoritmos híbridos cuánticos/clásicos

Los algoritmos híbridos cuánticos/clásicos combinan la preparación y medición del estado cuántico con la optimización clásica. ^[49] Estos algoritmos generalmente tienen como objetivo determinar el vector propio del estado fundamental y el valor propio de un operador hermitiano.

QAOA

El algoritmo de optimización cuántica aproximada se inspira en el recocido cuántico y realiza una aproximación discretizada del recocido cuántico utilizando un circuito cuántico. Se puede utilizar para resolver problemas de teoría de grafos. ^[50] El algoritmo hace uso de la optimización clásica de operaciones cuánticas para maximizar una "función objetivo".

Eigensolver cuántico variacional

El algoritmo de resolución propia cuántica variacional (VQE) aplica la optimización clásica para minimizar el valor esperado de energía de un estado ansatz para encontrar el estado fundamental de un operador hermitiano, como el hamiltoniano de una molécula. ^[51] También se puede ampliar para encontrar energías excitadas de hamiltonianos moleculares. ^[52]

Eigensolver cuántico contratado

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

Ver también

• Aprendizaje automático cuántico
• Algoritmos de optimización cuántica
• clasificación cuántica
• prueba de primalidad

Referencias

1. Nielsen, Michael A .; Chuang, Isaac L. (2000). Computación cuántica e información cuántica . Prensa de la Universidad de Cambridge . ISBN 978-0-521-63503-5.
2. Mosca, M. (2008). "Algoritmos cuánticos". arXiv : 0808.0369 [cuántico-ph].
3. Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 de enero de 2009). Informática cuántica. Editores Morgan y Claypool. ISBN 9781598297324.
4. Nielsen, Michael A .; Chuang, Isaac L. (2010). Computación cuántica e información cuántica (2ª ed.). Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-1-107-00217-3.
5. "Algoritmo de Shor".
6. "Guía del usuario de IBM Quantum Composer: algoritmo de Grover". computación-cuántica.ibm.com . Consultado el 7 de junio de 2022 .
7. Farhi, Eduardo; Goldstone, Jeffrey; Gutmann, Sam (2008). "Un algoritmo cuántico para el árbol NAND hamiltoniano". Teoría de la Computación . 4 : 169-190. arXiv : quant-ph/0702144 . doi : 10.4086/toc.2008.v004a008 .
8. Niños, Andrew M .; van Dam, W. (2010). "Algoritmos cuánticos para problemas algebraicos". Reseñas de Física Moderna . 82 (1): 1–52. arXiv : 0812.0380 . Código Bib : 2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.
9. Corto, PW (1997). "Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación Científica y Estadística . 26 (5): 1484-1509. arXiv : quant-ph/9508027 . Código bibliográfico : 1995quant.ph..8027S. doi :10.1137/s0097539795293172. S2CID  2337707.
10. Boneh, D.; Lipton, RJ (1995). "Criptoanálisis cuántico de funciones lineales ocultas". En Calderero, D. (ed.). Actas de la 15ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología . Springer-Verlag . págs. 424–437. ISBN 3-540-60221-6.
11. Moore, C .; Russell, A.; Schulman, LJ (2005). "El grupo simétrico desafía el muestreo fuerte de Fourier: parte I". arXiv : quant-ph/0501056 .
12. Regev, O. (2003). "Computación cuántica y problemas de red". arXiv : cs/0304005 .
13. van Dam, W.; Seroussi, G. (2002). "Algoritmos cuánticos eficientes para estimar sumas de Gauss". arXiv : quant-ph/0207131 .
14. Aaronson, S. (2009). "BQP y la jerarquía polinómica". arXiv : 0910.4698 [cuántico-ph].
15. Grover, Lov K. (1996). "Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos". arXiv : quant-ph/9605043 .
16. Aaronson, Scott. "Computación cuántica y variables ocultas" (PDF) .
17. Brassard, G.; Hoyer, P.; Tapp, A. (1998). "Conteo cuántico". Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 1443, págs. 820–831. arXiv : quant-ph/9805082 . doi :10.1007/BFb0055105. ISBN 978-3-540-64781-2. S2CID  14147978.
18. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. (2002). "Estimación y amplificación de amplitud cuántica". En Samuel J. Lomonaco, Jr. (ed.). Computación cuántica e información cuántica . AMS Matemáticas Contemporáneas. vol. 305, págs. 53–74. arXiv : quant-ph/0005055 . Código Bib : 2000quant.ph..5055B. doi :10.1090/conm/305/05215. ISBN 9780821821404. S2CID  54753.
19. Niños, AM; Inteligente.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, DA (2003). "Aceleración algorítmica exponencial mediante caminata cuántica". Actas del 35º Simposio sobre Teoría de la Computación . Asociación para Maquinaria de Computación . págs. 59–68. arXiv : quant-ph/0209131 . doi :10.1145/780542.780552. ISBN 1-58113-674-9.
20. Niños, AM; Schulman, LJ; Vazirani, UV (2007). "Algoritmos cuánticos para estructuras no lineales ocultas". Actas del 48.º Simposio anual del IEEE sobre fundamentos de la informática . IEEE . págs. 395–404. arXiv : 0705.2784 . doi :10.1109/FOCS.2007.18. ISBN 978-0-7695-3010-9.
21. Magniez, F.; Nayak, A.; Roland, J.; Santha, M. (2007). "Búsqueda mediante caminata cuántica". Actas del 39º Simposio Anual ACM sobre Teoría de la Computación . Asociación para Maquinaria de Computación . págs. 575–584. arXiv : quant-ph/0608026 . doi :10.1145/1250790.1250874. ISBN 978-1-59593-631-8.
22. Ralph, TC (julio de 2013). "Figura 1: El problema del muestreo de bosones". Fotónica de la naturaleza . Naturaleza. 7 (7): 514–515. doi :10.1038/nphoton.2013.175. S2CID  110342419 . Consultado el 12 de septiembre de 2014 .
23. Peruzzo, Alberto; Lobino, Mirko; Matthews, Jonathan CF; Matsuda, Nobuyuki; Politi, Alberto; Poulios, Konstantinos; Zhou, Xiao-Qi; Lahini, Yoav; Ismail, Nur; Wörhoff, Kerstin; Bromberg, Yaron; Silberberg, Yaron; Thompson, Mark G.; O'Brien, Jeremy L. (17 de septiembre de 2010). "Paseos cuánticos de fotones correlacionados". Ciencia . 329 (5998): 1500-1503. arXiv : 1006.4764 . Código Bib : 2010 Ciencia... 329.1500P. doi : 10.1126/ciencia.1193515. ISSN  0036-8075. PMID  20847264. S2CID  13896075.
24. Lund, AP; Laing, A.; Rahimi-Keshari, S.; Rudolf, T.; O'Brien, JL; Ralph, TC (5 de septiembre de 2014). "Muestreo de bosones de estados gaussianos". Física. Rev. Lett . 113 (10): 100502. arXiv : 1305.4346 . Código Bib : 2014PhRvL.113j0502L. doi : 10.1103/PhysRevLett.113.100502. PMID  25238340. S2CID  27742471.
25. "La revolución cuántica está un paso más cerca". Phys.org . Tecnología Omicron limitada . Consultado el 12 de septiembre de 2014 .
26. Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motas, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). "Muestreo de bosones con estados de Fock de fotón único desplazados versus estados coherentes de fotón único agregado: la división cuántica-clásica y las transiciones de complejidad computacional en óptica lineal". Revisión física A. 91 (2): 022334. arXiv : 1402.0531 . Código Bib : 2015PhRvA..91b2334S. doi : 10.1103/PhysRevA.91.022334. S2CID  55455992.
27. Ambainis, A. (2007). "Algoritmo de caminata cuántica para la distinción de elementos". Revista SIAM de Computación . 37 (1): 210–239. arXiv : quant-ph/0311001 . doi :10.1137/S0097539705447311. S2CID  6581885.
28. Shi, Y. (2002). "Límites inferiores cuánticos para los problemas de colisión y distinción de elementos". 43º Simposio anual del IEEE sobre fundamentos de la informática, 2002. Actas . Actas del 43º Simposio sobre fundamentos de la informática . págs. 513–519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975. ISBN 0-7695-1822-2.
29. Ambainis, A. (2005). "Grado polinómico y límites inferiores en complejidad cuántica: colisión y distinción de elementos con rango pequeño". Teoría de la Computación . 1 (1): 37–46. doi : 10.4086/toc.2005.v001a003 .
30. Kutin, S. (2005). "Límite inferior cuántico para el problema de colisión con alcance pequeño". Teoría de la Computación . 1 (1): 29–36. doi : 10.4086/toc.2005.v001a002 .
31. Aleksandrs Belovs (2011). "Programas de amplitud para funciones con certificados 1 de tamaño constante". arXiv : 1105.4024 [cuántico-ph].
32. Magniez, F.; Santa, M.; Szegedy, M. (2007). "Algoritmos cuánticos para el problema del triángulo". Revista SIAM de Computación . 37 (2): 413–424. arXiv : quant-ph/0310134 . doi : 10.1137/050643684. S2CID  594494.
33. Aaronson, S. (3 de febrero de 2007). "NAND ahora para algo completamente diferente". Optimizado para Shtetl . Consultado el 17 de diciembre de 2009 .
34. Saks, YO; Wigderson, A. (1986). "Árboles de decisión booleanos probabilísticos y la complejidad de evaluar árboles de juego" (PDF) . Actas del 27º Simposio Anual sobre Fundamentos de la Informática . IEEE . págs. 29-38. doi :10.1109/SFCS.1986.44. ISBN 0-8186-0740-8.
35. Ambainis, A. (2007). "Un algoritmo cuántico de consulta discreta casi óptimo para evaluar fórmulas NAND". arXiv : 0704.3628 [cuántico-ph].
36. Reichardt, BW; Spalek, R. (2008). "Algoritmo cuántico basado en programa Span para evaluar fórmulas". Actas del 40º simposio anual de ACM sobre teoría de la computación . Asociación para Maquinaria de Computación . págs. 103-112. arXiv : 0710.2630 . doi :10.1145/1374376.1374394. ISBN 978-1-60558-047-0.
37. Pak, Igor (2012). "Prueba de conmutatividad de un grupo y el poder de la aleatorización". Revista LMS de Computación y Matemáticas . 15 : 38–43. doi : 10.1112/S1461157012000046 .
38. Magniez, F.; Nayak, A. (2007). "Complejidad cuántica de la conmutatividad del grupo de pruebas". Algorítmica . 48 (3): 221–232. arXiv : quant-ph/0506265 . doi :10.1007/s00453-007-0057-8. S2CID  3163328.
39. Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-63503-9 . 
40. Aharonov, D.; Jones, V.; Landau, Z. (2006). "Un algoritmo cuántico polinómico para aproximar el polinomio de Jones". Actas del 38º simposio anual de ACM sobre teoría de la informática . Asociación para Maquinaria de Computación . págs. 427–436. arXiv : quant-ph/0511096 . doi :10.1145/1132516.1132579. ISBN 1595931341.
41. Feynman, RP (1982). "Simulando la física con ordenadores". Revista Internacional de Física Teórica . 21 (6–7): 467–488. Código bibliográfico : 1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310 . doi :10.1007/BF02650179. S2CID  124545445. 
42. Abrams, DS; Lloyd, S. (1997). "Simulación de sistemas Fermi de muchos cuerpos en una computadora cuántica universal". Cartas de revisión física . 79 (13): 2586–2589. arXiv : quant-ph/9703054 . Código bibliográfico : 1997PhRvL..79.2586A. doi : 10.1103/PhysRevLett.79.2586. S2CID  18231521.
43. Kassal, yo; Jordania, SP; Con cariño, PJ; Mohseni, M.; Aspuru-Guzik, A. (2008). "Algoritmo cuántico de tiempo polinomial para la simulación de dinámica química". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 105 (48): 18681–86. arXiv : 0801.2986 . Código Bib : 2008PNAS..10518681K. doi : 10.1073/pnas.0808245105 . PMC 2596249 . PMID  19033207. 
44. Liberto, M.; Kitaev, A.; Wang, Z. (2002). "Simulación de teorías de campos topológicos mediante computadoras cuánticas". Comunicaciones en Física Matemática . 227 (3): 587–603. arXiv : quant-ph/0001071 . Código Bib : 2002CMaPh.227..587F. doi :10.1007/s002200200635. S2CID  449219.
45. Aharonov, D.; Jones, V.; Landau, Z. (2009). "Un algoritmo cuántico polinómico para aproximar el polinomio de Jones". Algorítmica . 55 (3): 395–421. arXiv : quant-ph/0511096 . doi :10.1007/s00453-008-9168-0. S2CID  7058660.
46. Wocjan, P.; Yarda, J. (2008). "El polinomio de Jones: algoritmos cuánticos y aplicaciones en la teoría de la complejidad cuántica". Información y Computación Cuántica . 8 (1): 147–180. arXiv : quant-ph/0603069 . Código Bib : 2006quant.ph..3069W. doi :10.26421/QIC8.1-2-10. S2CID  14494227.
47. Alagico, G.; Jordania, SP; König, R.; Reichardt, BW (2010). "La aproximación de los invariantes de 3 variedades de Turaev-Viro es universal para la computación cuántica". Revisión física A. 82 (4): 040302. arXiv : 1003.0923 . Código Bib : 2010PhRvA..82d0302A. doi : 10.1103/PhysRevA.82.040302. S2CID  28281402.
48. Grada, Aram W; Jasidim, Avinatan; Lloyd, Seth (2008). "Algoritmo cuántico para la resolución de sistemas lineales de ecuaciones". Cartas de revisión física . 103 (15): 150502. arXiv : 0811.3171 . Código bibliográfico : 2009PhRvL.103o0502H. doi : 10.1103/PhysRevLett.103.150502. PMID  19905613. S2CID  5187993.
49. Moll, Nikolaj; Barkoutsos, Panagiotis; Obispo, Lev S.; Chow, Jerry M.; Cruz, Andrés; Egger, Daniel J.; Filipp, Stefan; Führer, Andreas; Gambetta, Jay M.; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, Juan; Tavernelli, Ivano; Temmé, Kristan (2018). "Optimización cuántica mediante algoritmos variacionales en dispositivos cuánticos a corto plazo". Ciencia y tecnología cuánticas . 3 (3): 030503. arXiv : 1710.01022 . Código Bib : 2018QS&T....3c0503M. doi :10.1088/2058-9565/aab822. S2CID  56376912.
50. Farhi, Eduardo; Goldstone, Jeffrey; Gutmann, Sam (14 de noviembre de 2014). "Un algoritmo de optimización cuántica aproximada". arXiv : 1411.4028 [cuántico-ph].
51. Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Con cariño, Peter J.; Aspuru-Guzik, Alán; O'Brien, Jeremy L. (23 de julio de 2014). "Un solucionador de valores propios variacionales en un procesador cuántico fotónico". Comunicaciones de la naturaleza . 5 (1): 4213. arXiv : 1304.3061 . Código Bib : 2014NatCo...5.4213P. doi : 10.1038/ncomms5213. ISSN  2041-1723. PMC 4124861 . PMID  25055053. 
52. Higgott, Óscar; Wang, Daochen; Brierley, Stephen (2019). "Computación cuántica variacional de estados excitados". Cuántico . 3 : 156. arXiv : 1805.08138 . Código Bib : 2019Cantidad...3..156H. doi :10.22331/q-2019-07-01-156. S2CID  119185497.
53. Inteligente, Scott; Mazziotti, David (18 de febrero de 2021). "Solucionador cuántico de ecuaciones de valores propios contraídas para simulaciones moleculares escalables en dispositivos de computación cuántica". Física. Rev. Lett . 125 (7): 070504. arXiv : 2004.11416 . Código Bib : 2021PhRvL.126g0504S. doi : 10.1103/PhysRevLett.126.070504. PMID  33666467. S2CID  216144443.
54. Mazziotti, David (6 de octubre de 2006). "Ecuación de Schrödinger contraída antihermitiana: determinación directa de las matrices de densidad reducida de dos electrones de moléculas de muchos electrones". Física. Rev. Lett . 97 (14): 143002. Código bibliográfico : 2006PhRvL..97n3002M. doi : 10.1103/PhysRevLett.97.143002. PMID  17155245.

enlaces externos

• The Quantum Algorithm Zoo: una lista completa de algoritmos cuánticos que proporcionan una mayor velocidad que los algoritmos clásicos más rápidos conocidos.
• Apuntes de conferencias de Andrew Childs sobre algoritmos cuánticos
• El algoritmo de búsqueda cuántica: fuerza bruta.

Encuestas

• Dalzell, Alexander M.; et al. (2023). "Algoritmos cuánticos: un estudio de aplicaciones y complejidades de un extremo a otro". arXiv : 2310.03011 [cuántico-ph].
• Smith, J.; Mosca, M. (2012). "Algoritmos para computadoras cuánticas". Manual de Computación Natural . págs. 1451-1492. doi :10.1007/978-3-540-92910-9_43. ISBN 978-3-540-92909-3. S2CID  16565723.
• Niños, AM; Van Dam, W. (2010). "Algoritmos cuánticos para problemas algebraicos". Reseñas de Física Moderna . 82 (1): 1–52. arXiv : 0812.0380 . Código Bib : 2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.