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 circuito cuántico de computación. ^{[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 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 usando computadoras clásicas siguen siendo indecidibles usando 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 factorización 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 más conocido para factorización, el tamiz de cuerpos numéricos generales . ^[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 se describen habitualmente, en el modelo de circuito de computación cuántica comúnmente utilizado, mediante un circuito cuántico que actúa sobre algunos cúbits 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 cúbits. Los algoritmos cuánticos también pueden enunciarse en otros modelos de computación cuántica, como el modelo de oráculo hamiltoniano. ^[7]

Los algoritmos cuánticos se pueden clasificar según las técnicas principales que se utilizan en el algoritmo. Algunas técnicas o ideas que se utilizan habitualmente en los algoritmos cuánticos incluyen el retroceso de fase, la estimación de fase , la transformada cuántica de Fourier , los recorridos cuánticos , la amplificación de amplitud y la teoría cuántica de campos topológica . Los algoritmos cuánticos también se pueden agrupar según el tipo de problema resuelto; véase, por ejemplo, la encuesta 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 también es un ejemplo de una transformada cuántica de Fourier sobre un espacio vectorial n-dimensional sobre el campo F 2 . La transformada cuántica de Fourier se puede implementar de manera eficiente en una computadora cuántica utilizando solo un número polinomial de puertas cuánticas . ^{[ cita requerida ]}

Algoritmo de Jozsa

Algoritmo de Jozsa en alemán

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 puede resolverse con una sola consulta en una computadora cuántica. 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 una cantidad 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 oracular 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 con respecto a todos los algoritmos clásicos que consideramos eficientes, fue la motivación para el algoritmo de Shor para la factorización.

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 compuerta unitaria, dado un estado cuántico proporcional al vector propio y el acceso a la compuerta. El algoritmo se utiliza con frecuencia como subrutina en otros algoritmos.

Algoritmo de Shor

El algoritmo de Shor resuelve el problema del logaritmo discreto y el problema de factorización de números enteros en tiempo polinomial, ^[9] mientras que los algoritmos clásicos más conocidos requieren tiempo superpolinomial. No se sabe que estos problemas se produzcan en tiempo 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 del subgrupo oculto

El problema del subgrupo oculto abeliano es una generalización de muchos problemas que pueden ser resueltos por un ordenador cuántico, como el problema de Simon, la solució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 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 de ciertos problemas de red . Se conocen algoritmos cuánticos eficientes para ciertos grupos no abelianos. Sin embargo, no se conocen algoritmos eficientes para el grupo simétrico , que daría un algoritmo eficiente para el isomorfismo de grafos ^[11] y el grupo diedro , 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 del logaritmo discreto 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 que 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 comprobación 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 satisface

${\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 la amplificación de amplitud suelen dar lugar a aceleraciones cuadráticas con respecto a los algoritmos clásicos correspondientes. Puede considerarse como una generalización del algoritmo de Grover. ^{[ cita requerida ]}

Algoritmo de Grover

El algoritmo de Grover busca una entrada marcada en una base de datos no estructurada (o una lista desordenada) con N entradas, utilizando solo consultas en lugar de las consultas requeridas clásicamente. ^[15] Clásicamente, se requieren consultas 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, o incluso posible bajo la teoría estándar de la mecánica cuántica). Una computadora hipotética de este tipo podría implementar una búsqueda en una base de datos de N elementos en, como máximo, pasos. Esto es ligeramente más rápido que los pasos tomados por el algoritmo de Grover . Sin embargo, ninguno de los métodos de búsqueda permitiría a ninguno de los modelos de computadora cuántica resolver problemas NP-completos en tiempo polinomial. ^[16] ${\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 una. Específicamente, cuenta el número de entradas marcadas en una lista de elementos con un error de como máximo haciendo solo consultas, donde es el número de elementos marcados en la lista. ^{[17] [18]} Más precisamente, el algoritmo genera una estimación para , el número de entradas marcadas, con una precisión de . ${\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

Un paseo cuántico es el análogo cuántico de un paseo aleatorio clásico . 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 brindan aceleraciones exponenciales para algunos problemas de caja negra. ^{[19] [20]} También brindan aceleraciones polinómicas para muchos problemas. Existe un marco para la creación de algoritmos de paseo cuántico 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 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 un paseo cuántico 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 la 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 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 algoritmos cuánticos. 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 desde 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 una lista de tamaño ; sin embargo, se puede resolver en consultas en una computadora cuántica. El algoritmo óptimo fue propuesto por Andris Ambainis [ ^27] y Yaoyun Shi fue el primero en demostrar un límite inferior estricto cuando el tamaño del rango es suficientemente grande. ^[28] Ambainis ^[29] y Kutin ^[30] de forma independiente (y mediante diferentes pruebas) extendieron 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 búsqueda de triángulos es el problema de determinar si un gráfico dado 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 O( N ^1.297 ) consultas, ^[31] una mejora con respecto a las mejores consultas anteriores O( N ^{1.3 ). [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 de hoja. El problema es evaluar la fórmula, que es la salida del nodo raíz, dado el acceso del oráculo a la entrada.

Una fórmula bien estudiada es el árbol binario balanceado con solo puertas NAND. ^[33] Este tipo de fórmula requiere consultas que utilicen aleatoriedad, ^[34] donde . Sin embargo, con un algoritmo cuántico, se puede resolver en consultas. No se conocía un mejor algoritmo cuántico 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. ^[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 de grupo

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 de oráculo, que debe utilizarse 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 el número de llamadas de oráculo necesarias para resolver el problema. Las complejidades de consulta determinista y aleatoria 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 BQP completos

La clase de complejidad BQP (tiempo polinomial cuántico de error acotado) es el conjunto de problemas de decisión que puede resolver una computadora cuántica en tiempo polinomial con una probabilidad de error de como máximo 1/3 para todas las instancias. ^[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 . Informalmente, la clase de problemas BQP -completos son aquellos que son tan difíciles como los problemas más difíciles en BQP y son ellos mismos solucionables eficientemente por una computadora cuántica (con error acotado).

Cálculo de invariantes de nudos

Witten había demostrado que la teoría cuántica de campos topológicos de Chern-Simons (TQFT) se puede resolver en términos de polinomios de Jones . Una computadora cuántica puede simular una 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 requerida ]}

Simulación cuántica

La idea de que las computadoras cuánticas podrían ser más poderosas que las computadoras 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 a 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 en gran medida. Se han desarrollado algoritmos cuánticos eficientes (es decir, de tiempo polinomial) para simular sistemas bosónicos y fermiónicos, ^[42] así como la simulación de reacciones químicas más allá de las capacidades de las supercomputadoras clásicas actuales utilizando solo unos pocos cientos de qubits. ^[43] Las computadoras cuánticas también pueden simular eficientemente teorías de campos cuánticos topológicos. ^[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 de Turaev-Viro de variedades tridimensionales. ^[47]

Resolver sistemas de ecuaciones lineales

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 escaso 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 solución (en lugar de los valores del vector 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 sobre el 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 apuntan a determinar el vector propio y el valor propio del estado fundamental de un operador hermítico.

AOC de calidad

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 mediante un circuito cuántico. Puede utilizarse para resolver problemas de teoría de grafos. ^[50] El algoritmo utiliza la optimización clásica de operaciones cuánticas para maximizar una "función objetivo".

Eigensolver cuántico variacional

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

Solucionador propio cuántico contraído

El algoritmo de resolución de eigens 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. ^[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 antihermítica. ^[54]

Véase también

• Aprendizaje automático cuántico
• Algoritmos de optimización cuántica
• Ordenación cuántica
• Prueba de primalidad

Referencias

1. Nielsen, Michael A .; Chuang, Isaac L. (2000). Computación cuántica e información cuántica . Cambridge University Press . ISBN 978-0-521-63503-5.
2. Mosca, M. (2008). "Algoritmos cuánticos". arXiv : 0808.0369 [quant-ph].
3. Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 de enero de 2009). Ciencia informática cuántica. Morgan & Claypool Publishers. ISBN 9781598297324.
4. Nielsen, Michael A. ; Chuang, Isaac L. (2010). Computación cuántica e información cuántica (2.ª ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.
5. "Algoritmo de Shor".
6. "Guía del usuario de IBM Quantum Composer: algoritmo de Grover". quantum-computing.ibm.com . Consultado el 7 de junio de 2022 .
7. Farhi, Edward; 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. Childs, 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 Bibliográfico :2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.
9. Shor, PW (1997). "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM sobre 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 Coppersmith, 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 reticulares". 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 [quant-ph].
15. Grover, Lov K. (1996). "Un algoritmo mecánico cuántico rápido para búsquedas en 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 clase en informática. Vol. 1443. págs. 820–831. arXiv : quant-ph/9805082 . doi :10.1007/BFb0055105. ISBN. 978-3-540-64781-2. Número de identificación del sujeto  14147978.
18. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. (2002). "Amplificación y estimación de amplitud cuántica". En Samuel J. Lomonaco, Jr. (ed.). Computación cuántica e información cuántica . AMS Contemporary Mathematics. Vol. 305. págs. 53–74. arXiv : quant-ph/0005055 . Código Bibliográfico :2000quant.ph..5055B. doi :10.1090/conm/305/05215. ISBN: 9780821821404. Número de identificación del sujeto  54753.
19. Childs, AM; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, DA (2003). "Aceleración algorítmica exponencial mediante paseo cuántico". Actas del 35.º Simposio sobre teoría de la computación . Association for Computing Machinery . págs. 59–68. arXiv : quant-ph/0209131 . doi :10.1145/780542.780552. ISBN . 1-58113-674-9.
20. Childs, AM; Schulman, LJ; Vazirani, UV (2007). "Algoritmos cuánticos para estructuras no lineales ocultas". Actas del 48.º Simposio anual 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 paseo cuántico". Actas del 39.° Simposio anual de la ACM sobre teoría de la computación . Association for Computing Machinery . 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). «Figure 1: The boson-sampling problem» (Figura 1: El problema del muestreo de bosones). Nature Photonics . 7 (7). Nature: 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. hdl :10072/53193. ISSN  0036-8075. Número de modelo: PMID  20847264. Número de modelo: S2CID  13896075.
24. Lund, AP; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, JL; Ralph, TC (5 de septiembre de 2014). "Muestreo de bosones a partir de estados gaussianos". Phys. Rev. Lett . 113 (10): 100502. arXiv : 1305.4346 . Código Bibliográfico :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 . Omicron Technology Limited . Consultado el 12 de septiembre de 2014 .
26. Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). "Muestreo de bosones con estados de Fock de fotón único desplazados versus estados coherentes con fotón único añadido: la división cuántico-clásica y las transiciones de complejidad computacional en óptica lineal". Physical Review A . 91 (2): 022334. arXiv : 1402.0531 . Código Bibliográfico :2015PhRvA..91b2334S. doi :10.1103/PhysRevA.91.022334. S2CID  55455992.
27. Ambainis, A. (2007). "Algoritmo de paseo cuántico para distinción de elementos". Revista SIAM de informática . 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 IEEE sobre fundamentos de la informática, 2002. Actas . Actas del 43.° Simposio sobre fundamentos de la informática . pp. 513–519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975. ISBN . 0-7695-1822-2.
29. Ambainis, A. (2005). "Grado polinomial 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 rango pequeño". Teoría de la computación . 1 (1): 29–36. doi : 10.4086/toc.2005.v001a002 .
31. Aleksandrs Belovs (2011). "Programas de extensión para funciones con 1-certificados de tamaño constante". arXiv : 1105.4024 [quant-ph].
32. Magniez, F.; Santha, M.; Szegedy, M. (2007). "Algoritmos cuánticos para el problema del triángulo". Revista SIAM de informática . 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". Shtetl-Optimized . Consultado el 17 de diciembre de 2009 .
34. Saks, ME; Wigderson, A. (1986). "Árboles de decisión probabilísticos booleanos y la complejidad de evaluar árboles de juegos" (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 [quant-ph].
36. Reichardt, BW; Spalek, R. (2008). "Algoritmo cuántico basado en programas Span para evaluar fórmulas". Actas del 40.º simposio anual de la ACM sobre teoría de la computación . Association for Computing Machinery . 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". LMS Journal of Computation and Mathematics . 15 : 38–43. doi : 10.1112/S1461157012000046 .
38. Magniez, F.; Nayak, A. (2007). "Complejidad cuántica de la conmutatividad grupal de pruebas". Algorithmica . 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: Cambridge University Press. ISBN 0-521-63503-9 . 
40. Aharonov, D.; Jones, V.; Landau, Z. (2006). "Un algoritmo cuántico polinomial para aproximar el polinomio de Jones". Actas del 38.º simposio anual de la ACM sobre teoría de la computación . Association for Computing Machinery . págs. 427–436. arXiv : quant-ph/0511096 . doi :10.1145/1132516.1132579. ISBN . 1595931341.
41. Feynman, RP (1982). "Simulación de 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". Physical Review Letters . 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, I.; Jordan, SP; Love, 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 . Bibcode :2008PNAS..10518681K. doi : 10.1073/pnas.0808245105 . PMC 2596249 . PMID  19033207. 
44. Freedman, M.; Kitaev, A.; Wang, Z. (2002). "Simulación de teorías de campos topológicos mediante computadoras cuánticas". Communications in Mathematical Physics . 227 (3): 587–603. arXiv : quant-ph/0001071 . Código Bibliográfico :2002CMaPh.227..587F. doi :10.1007/s002200200635. S2CID  449219.
45. Aharonov, D.; Jones, V.; Landau, Z. (2009). "Un algoritmo cuántico polinomial para aproximar el polinomio de Jones". Algorithmica . 55 (3): 395–421. arXiv : quant-ph/0511096 . doi :10.1007/s00453-008-9168-0. S2CID  7058660.
46. Wocjan, P.; Yard, 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 Bibliográfico :2006quant.ph..3069W. doi :10.26421/QIC8.1-2-10. S2CID  14494227.
47. Alagic, G.; Jordan, SP; König, R.; Reichardt, BW (2010). "La aproximación de invariantes de 3 variedades de Turaev-Viro es universal para la computación cuántica". Physical Review A . 82 (4): 040302. arXiv : 1003.0923 . Código Bibliográfico :2010PhRvA..82d0302A. doi :10.1103/PhysRevA.82.040302. S2CID  28281402.
48. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). "Algoritmo cuántico para resolver sistemas lineales de ecuaciones". Physical Review Letters . 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; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M.; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, John; Tavernelli, Ivano; Temme, Kristan (2018). "Optimización cuántica utilizando algoritmos variacionales en dispositivos cuánticos de corto plazo". Ciencia y tecnología cuántica . 3 (3): 030503. arXiv : 1710.01022 . Código Bibliográfico :2018QS&T....3c0503M. doi :10.1088/2058-9565/aab822. Número de identificación del sujeto  56376912.
50. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (14 de noviembre de 2014). "Un algoritmo de optimización aproximada cuántica". arXiv : 1411.4028 [quant-ph].
51. Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Love, Peter J.; Aspuru-Guzik, Alán; O'Brien, Jeremy L. (23 de julio de 2014). "Un solucionador de valores propios variacional en un procesador cuántico fotónico". Nature Communications . 5 (1): 4213. arXiv : 1304.3061 . Bibcode :2014NatCo...5.4213P. doi :10.1038/ncomms5213. ISSN  2041-1723. PMC 4124861 . PMID  25055053. 
52. Higgott, Oscar; Wang, Daochen; Brierley, Stephen (2019). "Computación cuántica variacional de estados excitados". Quantum . 3 : 156. arXiv : 1805.08138 . Bibcode :2019Quant...3..156H. doi :10.22331/q-2019-07-01-156. S2CID  119185497.
53. Smart, Scott; Mazziotti, David (18 de febrero de 2021). "Solucionador cuántico de ecuaciones de valores propios contraídos para simulaciones moleculares escalables en dispositivos informáticos cuánticos". Phys. Rev. Lett . 125 (7): 070504. arXiv : 2004.11416 . Bibcode :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 antihermítica: determinación directa de las matrices de densidad reducida de dos electrones de moléculas de muchos electrones". Phys. Rev. Lett . 97 (14): 143002. Bibcode :2006PhRvL..97n3002M. doi :10.1103/PhysRevLett.97.143002. PMID  17155245.

Enlaces externos

• El zoológico de algoritmos cuánticos: una lista completa de algoritmos cuánticos que proporcionan una aceleración sobre los algoritmos clásicos más rápidos conocidos.
• Notas de la conferencia de Andrew Childs sobre algoritmos cuánticos
• El algoritmo de búsqueda cuántica: fuerza bruta Archivado el 1 de septiembre de 2018 en Wayback Machine .

Encuestas

• Dalzell, Alexander M.; et al. (2023). "Algoritmos cuánticos: un estudio de aplicaciones y complejidades de extremo a extremo". arXiv : 2310.03011 [quant-ph].
• Smith, J.; Mosca, M. (2012). "Algoritmos para ordenadores cuánticos". 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.S2CID16565723  .​
• Childs, 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 Bibliográfico :2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.