En la 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 se usa generalmente para aquellos algoritmos que parecen inherentemente cuánticos, o usan 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 probablemente no se puedan simular de manera eficiente en computadoras clásicas (ver Supremacía cuántica ) .
Los algoritmos más conocidos son el algoritmo de factorización de Shor y el algoritmo de Grover para buscar una base de datos no estructurada o una lista desordenada. Los algoritmos de Shor se ejecutan mucho (casi exponencialmente) más rápido que el algoritmo clásico más conocido para la factorización, 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, [ cita requerida ] 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, por 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 que actúan sobre un número fijo de qubits como máximo. El número de qubits debe fijarse porque un número cambiante de qubits implica una evolución no unitaria. Los algoritmos cuánticos también se pueden establecer en otros modelos de computación cuántica, como el modelo del oráculo de Hamilton . [6]
Los algoritmos cuánticos se pueden clasificar según las principales técnicas utilizadas por el algoritmo. Algunas técnicas de uso común / ideas en algoritmos cuánticos incluyen fase de lanzamiento hacia atrás , estimación de fase , la cuántica transformada de Fourier , paseos cuánticos , la amplificación de la amplitud y la teoría cuántica de campos topológica . Los algoritmos cuánticos también pueden agruparse según el tipo de problema resuelto, por ejemplo, consulte la encuesta sobre algoritmos cuánticos para problemas algebraicos. [7]
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 Deutsch – Jozsa
El algoritmo Deutsch-Jozsa resuelve un problema de caja negra que probablemente requiere exponencialmente muchas consultas a la caja negra para cualquier computadora clásica determinista, pero puede realizarse con exactamente una consulta por una computadora cuántica. Si permitimos tanto los algoritmos cuánticos de error acotado como los clásicos, entonces 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 balanceada (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 de 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 del 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 autofase de un autovector de una puerta unitaria dado un estado cuántico proporcional al autovector y al acceso a la puerta. El algoritmo se utiliza con frecuencia 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, [8] 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 donde los algoritmos clásicos más conocidos se ejecutan en tiempo superpolinomial.
Problema de subgrupo oculto
El problema del subgrupo oculto abeliano es una generalización de muchos problemas que pueden resolverse con una computadora cuántica, como el problema de Simon, resolviendo la ecuación de Pell , probando el ideal principal de un anillo R y factorizando . Existen algoritmos cuánticos eficientes conocidos por el problema del subgrupo oculto abeliano. [9] El problema de subgrupo oculto más general, donde el grupo no es necesariamente abeliano, es una generalización de los problemas mencionados anteriormente, el isomorfismo de grafos 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 [10] y el grupo diedro , lo que resolvería ciertos problemas de celosía. [11]
Problema de muestreo de bosones
El problema de muestreo de bosones en una configuración experimental supone [12] una entrada de bosones (por ejemplo, fotones de luz) de un número moderado que se dispersa aleatoriamente en un gran número de modos de salida restringidos por una unitaridad definida . 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. [13] Resolver este problema con un algoritmo informático clásico requiere calcular el permanente de la matriz de transformación unitaria, lo que puede ser imposible o tomar un tiempo prohibitivamente largo. En 2014, se propuso [14] 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 algoritmos cuánticos. En 2015, la investigación predijo [15] que el problema de muestreo tenía una complejidad similar para las entradas distintas de los fotones de estado de Fock e identificó una transición en la complejidad computacional de clásicamente simulable a tan difícil como el problema de muestreo de bosones, dependiendo del tamaño de las entradas de amplitud coherente.
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 las 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 polinomial en tiempo polinomial. [dieciséis]
Pesca de Fourier y control de Fourier
Tenemos un oráculo que consta de n funciones booleanas aleatorias que mapean cadenas de n bits a un valor booleano. Estamos obligados a encontrar n cadenas de n bits z 1 , ..., z n tales que para la transformada de Hadamard-Fourier, al menos 3/4 de las cadenas satisfacen
y al menos 1/4 satisface
Esto se puede hacer en tiempo polinomial cuántico de error acotado (BQP). [17]
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 generalmente conducen a aceleraciones cuadráticas sobre los algoritmos clásicos correspondientes. Puede considerarse una generalización del algoritmo de Grover.
El 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, usando solo consultas en lugar de consultas requeridas clásicamente. [18] Clásicamente, Se requieren consultas incluso permitiendo algoritmos probabilísticos de error acotado.
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 así es completamente hipotética y no sería una computadora cuántica estándar, ni siquiera sería 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 de una base de datos de N elementos como máximo enpasos. Esto es un poco más rápido que elpasos dados por el algoritmo de Grover . 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. [19]
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 un-lista de elementos, con error haciendo solo consultas, donde es el número de elementos marcados en la lista. [20] [21] Más precisamente, el algoritmo genera una estimación por , el número de entradas marcadas, con la siguiente precisión: .
Algoritmos basados en paseos cuánticos
Un paseo cuántico es el análogo cuántico de un paseo aleatorio clásico , que puede describirse mediante una distribución de probabilidad en algunos estados. Un paseo cuántico se puede describir mediante una superposición cuántica sobre estados. Se sabe que las caminatas cuánticas dan aceleraciones exponenciales para algunos problemas de caja negra. [22] [23] 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 bastante versátil. [24]
Problema de distinción de elementos
El problema de la distinción de elementos es el problema de determinar si todos los elementos de una lista son distintos. Clásicamente, Ω ( N se requieren) consultas para una lista de tamaño N . Sin embargo, se puede resolver enconsultas en una computadora cuántica. El algoritmo óptimo es de Andris Ambainis . [25] Yaoyun Shi demostró por primera vez un límite inferior ajustado cuando el tamaño del rango es suficientemente grande. [26] Ambainis [27] y Kutin [28] independientemente (ya través de diferentes pruebas) ampliaron su trabajo para obtener el límite inferior para todas las funciones.
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 Ω ( N ), pero el mejor algoritmo conocido requiere consultas O ( N 1.297 ), [29] una mejora con respecto a las mejores consultas anteriores O ( N 1.3 ). [24] [30]
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 solo puertas NAND. [31] Este tipo de fórmula requiere consultas Θ ( N c ) utilizando aleatoriedad, [32] donde. Sin embargo, con un algoritmo cuántico, se puede resolver en consultas Θ ( N 0.5 ). No se conocía un algoritmo cuántico mejor para este caso hasta que se encontró uno para el modelo de oráculo hamiltoniano no convencional. [6] Pronto siguió el mismo resultado para el establecimiento de normas. [33]
También se conocen algoritmos cuánticos rápidos para fórmulas más complicadas. [34]
Conmutatividad de grupo
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 oráculo, que debe usarse para realizar las operaciones de grupo (multiplicación, inversión y comparación con identidad). Estamos interesados en la complejidad de la consulta, que es la cantidad de llamadas de Oracle necesarias para resolver el problema. Las complejidades de las consultas deterministas y aleatorias son y respectivamente. [35] Un algoritmo cuántico requiere consultas, pero el algoritmo más conocido utiliza consultas. [36]
Problemas completos de BQP
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. [37] 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 se puede reducir a él en tiempo polinomial . De manera informal, la clase de problemas BQP -completos son aquellos que son tan difíciles como los problemas más difíciles en BQP y ellos mismos pueden resolverse eficientemente por una computadora cuántica (con error acotado).
Calcular invariantes de nudos
Witten había demostrado que la teoría de campos cuánticos topológicos de Chern-Simons (TQFT) 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, [38] 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. [39] 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 desarrollado en gran medida. Se han desarrollado algoritmos cuánticos eficientes (es decir, tiempo polinómico) para simular sistemas bosónicos y fermiónicos [40] y, en particular, la simulación de reacciones químicas más allá de las capacidades de las supercomputadoras clásicas actuales requiere sólo unos pocos cientos de qubits. [41] Las computadoras cuánticas también pueden simular de manera eficiente teorías de campos cuánticos topológicos. [42] 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 [43] y HOMFLY , [44] y el invariante de Turaev-Viro de variedades tridimensionales. [45]
Resolver un sistema lineal 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 a un sistema lineal de ecuaciones dado. [46]
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 , dónde 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).
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. [47] 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 aproximada cuántica es un modelo de juguete de recocido cuántico que se puede utilizar para resolver problemas en la teoría de grafos. [48] 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 VQE aplica la optimización clásica para minimizar la expectativa de energía de un estado ansatz para encontrar la energía del estado fundamental de una molécula. [49] Esto también se puede ampliar para encontrar energías excitadas de moléculas. [50]
Ver también
- Algoritmos de optimización cuántica
- Orden cuántico
- Prueba de primordialidad
Referencias
- ^ 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.
- ^ Mosca, M. (2008). "Algoritmos cuánticos". arXiv : 0808.0369 [ quant-ph ].
- ^ Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 de enero de 2009). Ciencias de la Computación Cuántica . Editores Morgan & Claypool. ISBN 9781598297324.
- ^ 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.
- ^ https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
- ^ a b Farhi, E .; Goldstone, J .; Gutmann, S. (2007). "Un algoritmo cuántico para el árbol NAND de Hamilton". arXiv : quant-ph / 0702144 .
- ^ 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 .
- ^ Shor, PW (1997). "Algoritmos de polinomio-tiempo 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 .
- ^ 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.
- ^ Moore, C .; Russell, A .; Schulman, LJ (2005). "El grupo simétrico desafía el muestreo de Fourier fuerte: parte I". arXiv : quant-ph / 0501056 .
- ^ Regev, O. (2003). "Problemas de celosía y computación cuántica". arXiv : cs / 0304005 .
- ^ Ralph, TC "Figura 1: El problema del muestreo de bosones" . Nature Photonics . Naturaleza . Consultado el 12 de septiembre de 2014 .
- ^ Lund, AP; Laing, A .; Rahimi-Keshari, S .; Rudolph, T .; O'Brien, JL; Ralph, TC (5 de septiembre de 2014). "Muestreo de bosones 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 .
- ^ "La revolución cuántica está un paso más cerca" . Phys.org . Omicron Technology Limited . Consultado el 12 de septiembre de 2014 .
- ^ Seshadreesan, Kaushik P .; Olson, Jonathan P .; Motes, Keith R .; Rohde, Peter P .; Dowling, Jonathan P. (2015). "Muestreo de bosones con estados Fock de fotón único desplazado frente a estados coherentes de fotón único añadido: la división clásica cuántica 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 .
- ^ van Dam, W .; Seroussi, G. (2002). "Algoritmos cuánticos eficientes para estimar sumas de Gauss". arXiv : quant-ph / 0207131 .
- ^ Aaronson, S. (2009). "BQP y la jerarquía polinomial". arXiv : 0910,4698 [ quant-ph ].
- ^ 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 .
- ^ Aaronson, Scott. "Computación cuántica y variables ocultas" (PDF) .
- ^ Brassard, G .; Hoyer, P .; Tapp, A. (1998). Conteo cuántico . Apuntes de conferencias en Ciencias de la Computación. 1443 . págs. 820–831. arXiv : quant-ph / 9805082 . doi : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2. S2CID 14147978 .
- ^ 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. 305 . págs. 53–74. arXiv : quant-ph / 0005055 . Código Bibliográfico : 2000quant.ph..5055B . doi : 10.1090 / conm / 305/05215 . ISBN 9780821821404.
- ^ Childs, AM; Inteligente.; Deotto, E .; Farhi, E .; Gutmann, S .; Spielman, DA (2003). "Aceleración algorítmica exponencial por caminata cuántica". Actas del 35º Simposio de Teoría de la Computación . Asociación de Maquinaria Informática . págs. 59–68. arXiv : quant-ph / 0209131 . doi : 10.1145 / 780542.780552 . ISBN 1-58113-674-9.
- ^ Childs, AM; Schulman, LJ; Vazirani, UV (2007). "Algoritmos cuánticos para estructuras no lineales ocultas". Actas del 48º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación . IEEE . págs. 395–404. arXiv : 0705.2784 . doi : 10.1109 / FOCS.2007.18 . ISBN 978-0-7695-3010-9.
- ^ a b Magniez, F .; Nayak, A .; Roland, J .; Santha, M. (2007). "Búsqueda a través de la caminata cuántica". Actas del 39º Simposio Anual ACM sobre Teoría de la Computación . Asociación de Maquinaria Informática . págs. 575–584. arXiv : quant-ph / 0608026 . doi : 10.1145 / 1250790.1250874 . ISBN 978-1-59593-631-8.
- ^ 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 .
- ^ Shi, Y. (2002). Límites cuánticos inferiores para la colisión y los problemas de distinción del elemento . Actas del 43º Simposio sobre fundamentos de la informática . págs. 513–519. arXiv : quant-ph / 0112086 . doi : 10.1109 / SFCS.2002.1181975 .
- ^ 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 .
- ^ Kutin, S. (2005). "Quantum Lower Bound 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 .
- ^ Aleksandrs Belovs (2011). "Programas de extensión para funciones con certificados 1 de tamaño constante". arXiv : 1105.4024 [ quant-ph ].
- ^ Magniez, F .; Santha, 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 .
- ^ Aaronson, S. (3 de febrero de 2007). "NAND ahora por algo completamente diferente" . Optimizado para Shtetl . Consultado el 17 de diciembre de 2009 .
- ^ Saks, ME; 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 las Ciencias de la Computación . IEEE . págs. 29–38. doi : 10.1109 / SFCS.1986.44 . ISBN 0-8186-0740-8.
- ^ Ambainis, A. (2007). "Un algoritmo cuántico de consulta discreta casi óptimo para evaluar fórmulas NAND". arXiv : 0704,3628 [ quant-ph ].
- ^ 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 de Maquinaria Informática . págs. 103–112. arXiv : 0710.2630 . doi : 10.1145 / 1374376.1374394 . ISBN 978-1-60558-047-0.
- ^ 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 .
- ^ Magniez, F .; Nayak, A. (2007). "Complejidad cuántica de la conmutatividad del grupo de prueba". Algoritmica . 48 (3): 221–232. arXiv : quant-ph / 0506265 . doi : 10.1007 / s00453-007-0057-8 . S2CID 3163328 .
- ^ Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN 0-521-63503-9 .
- ^ Aharonov, D .; Jones, V .; Landau, Z. (2006). "Un algoritmo cuántico polinomial para aproximar el polinomio de Jones". Actas del 38º simposio anual de ACM sobre teoría de la computación . Asociación de Maquinaria Informática . págs. 427–436. arXiv : quant-ph / 0511096 . doi : 10.1145 / 1132516.1132579 .
- ^ Feynman, RP (1982). "Simulando física con computadoras". 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 .
- ^ 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 .
- ^ Kassal, I .; Jordan, SP; Con amor, 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 Bibliográfico : 2008PNAS..10518681K . doi : 10.1073 / pnas.0808245105 . PMC 2596249 . PMID 19033207 .
- ^ Freedman, M .; Kitaev, A .; Wang, Z. (2002). "Simulación de teorías de campos topológicos por computadoras cuánticas". Comunicaciones en Física Matemática . 227 (3): 587–603. arXiv : quant-ph / 0001071 . Código Bibliográfico : 2002CMaPh.227..587F . doi : 10.1007 / s002200200635 . S2CID 449219 .
- ^ Aharonov, D .; Jones, V .; Landau, Z. (2009). "Un algoritmo cuántico polinomial para aproximar el polinomio de Jones". Algoritmica . 55 (3): 395–421. arXiv : quant-ph / 0511096 . doi : 10.1007 / s00453-008-9168-0 . S2CID 7058660 .
- ^ Wocjan, P .; Yarda, J. (2008). "El polinomio de Jones: algoritmos cuánticos y aplicaciones en la teoría de la complejidad cuántica". Computación e informació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 .
- ^ Alagic, G .; Jordan, SP; König, R .; Reichardt, BW (2010). "Aproximación de invariantes de tres 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 .
- ^ Harrow, Aram W; Hassidim, 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 .
- ^ Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S .; Chow, Jerry M .; Cruz, 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 mediante algoritmos variacionales en dispositivos cuánticos a corto plazo". Ciencia y Tecnología Cuántica . 3 (3): 030503. arXiv : 1710.01022 . doi : 10.1088 / 2058-9565 / aab822 . S2CID 56376912 .
- ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (14 de noviembre de 2014). "Un algoritmo de optimización aproximada cuántica". arXiv : 1411,4028 [ quant-ph ].
- ^ Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Con amor, 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 Bibliográfico : 2014NatCo ... 5E4213P . doi : 10.1038 / ncomms5213 . ISSN 2041-1723 . PMC 4124861 . PMID 25055053 .
- ^ Higgott, Oscar; Wang, Daochen; Brierley, Stephen (2019). "Computación cuántica variacional de estados emocionados". Quantum . 3 : 156. arXiv : 1805.08138 . doi : 10.22331 / q-2019-07-01-156 . S2CID 119185497 .
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 .
Encuestas
- Smith, J .; Mosca, M. (2012). "Algoritmos para computadoras cuánticas". Manual de Computación Natural . pag. 1451. 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". 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 .