El algoritmo cuántico para sistemas lineales de ecuaciones , también llamado algoritmo HHL , diseñado por Aram Harrow , Avinatan Hassidim y Seth Lloyd , es un algoritmo cuántico formulado en 2009 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. [1]
El algoritmo es uno de los principales algoritmos fundamentales previstos para proporcionar una aceleración respecto a sus homólogos clásicos, junto con el algoritmo de factorización de Shor , algoritmo de búsqueda de Grover y simulación cuántica . 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).
Una implementación del algoritmo cuántico para sistemas lineales de ecuaciones fue demostrada por primera vez en 2013 por Cai et al., Barz et al. y Pan et al. en paralelo. Las demostraciones consistieron en ecuaciones lineales simples en dispositivos cuánticos especialmente diseñados. [2] [3] [4] La primera demostración de una versión de propósito general del algoritmo apareció en 2018 en el trabajo de Zhao et al. [5]
Debido a la prevalencia de los sistemas lineales en prácticamente todas las áreas de la ciencia y la ingeniería, el algoritmo cuántico para sistemas lineales de ecuaciones tiene el potencial de una aplicabilidad generalizada. [6]
Procedimiento
El problema que estamos tratando de resolver es: dado un Matriz hermitiana y un vector unitario , encuentra el vector de solución satisfactorio . Este algoritmo asume que el usuario no está interesado en los valores de en sí mismo, sino más bien el resultado de aplicar algún operador sobre x, .
Primero, el algoritmo representa el vector como un estado cuántico de la forma:
A continuación, se utilizan técnicas de simulación hamiltonianas para aplicar el operador unitario a para una superposición de diferentes tiempos . La capacidad de descomponerse en la base propia de y para encontrar los valores propios correspondientes se ve facilitado por el uso de la estimación de fase cuántica .
El estado del sistema después de esta descomposición es aproximadamente:
dónde es la base del vector propio de , y .
Luego nos gustaría realizar el mapa lineal tomando a , dónde es una constante normalizadora. La operación de mapeo lineal no es unitaria y, por lo tanto, requerirá varias repeticiones, ya que tiene alguna probabilidad de fallar. Una vez que tiene éxito, no calculamos el registrarse y quedan con un estado proporcional a:
dónde es una representación de la mecánica cuántica del vector de solución deseado x . Para leer todos los componentes de x se requeriría que el procedimiento se repitiera al menos N veces. Sin embargo, a menudo ocurre que uno no está interesado enen sí mismo, sino más bien algún valor esperado de un operador lineal M que actúa sobre x . Al mapear M a un operador mecánico-cuántico y realizar la medición cuántica correspondiente a M , obtenemos una estimación del valor esperado. Esto permite extraer una amplia variedad de características del vector x, incluida la normalización, los pesos en diferentes partes del espacio de estados y los momentos sin calcular realmente todos los valores del vector x solución .
Explicación del algoritmo
Inicialización
En primer lugar, el algoritmo requiere que la matriz ser hermitiano para que se convierta en un operador unitario . En el caso donde no es hermitiano, define
Como es hermitiano, el algoritmo ahora se puede utilizar para resolver para obtener .
En segundo lugar, el algoritmo requiere un procedimiento eficiente para preparar , la representación cuántica de b. Se supone que existe algún operador lineal que puede tomar algún estado cuántico arbitrario a eficientemente o que este algoritmo es una subrutina en un algoritmo más grande y se le da como entrada. Cualquier error en la preparación del estado. se ignora.
Finalmente, el algoritmo asume que el estado se puede preparar de manera eficiente. Dónde
para algunos grandes . Los coeficientes de se eligen para minimizar una cierta función de pérdida cuadrática que induce un error en el subrutina descrita a continuación.
Simulación hamiltoniana
La simulación hamiltoniana se utiliza para transformar la matriz hermitiana.en un operador unitario, que luego se puede aplicar a voluntad. Esto es posible si A es es la opción -sparse y eficiente fila computable, lo que significa que tiene a lo sumo s diferente de cero entradas por fila y se le dio un índice de fila estas entradas se pueden calcular en tiempo O ( s ). Bajo estos supuestos, la simulación cuántica hamiltoniana permite para ser simulado en el tiempo .
subrutina
La subrutina clave del algoritmo, denotada , se define de la siguiente manera e incorpora una subrutina de estimación de fase :
1. Preparar en el registro C
2. Aplicar la evolución hamiltoniana condicional (suma)
3. Aplicar la transformada de Fourier en el registro C . Denote los estados base resultantes conpara k = 0, ..., T - 1. Definir.
4. Junto a un registro tridimensional S en el estado
5. Invierta los pasos 1 a 3, sin calcular la basura producida en el camino.
El procedimiento de estimación de fase en los pasos 1-3 permite la estimación de valores propios de A hasta el error.
El registro ancilla en el paso 4 es necesario construir un estado final con valores propios invertidos correspondientes a la inversa diagonalizada de A . En este registro, las funciones f , g , se denominan funciones de filtro. Los estados "nada", "bien" y "mal" se utilizan para instruir al cuerpo del bucle sobre cómo proceder; 'nada' indica que la inversión de matriz deseada aún no ha tenido lugar, 'bien' indica que la inversión ha tenido lugar y el bucle debería detenerse, y 'mal' indica que parte deestá en el subespacio mal acondicionado de A y el algoritmo no podrá producir la inversión deseada. Producir un estado proporcional a la inversa de A requiere que se mida "bien", después de lo cual el estado general del sistema colapsa al estado deseado por la regla de Born extendida .
Bucle principal
El cuerpo del algoritmo sigue el procedimiento de amplificación de amplitud : comenzando con, se aplica repetidamente la siguiente operación:
dónde
y
Después de cada repetición, se mide y producirá un valor de "nada", "bien" o "mal" como se describe anteriormente. Este bucle se repite hasta se mide, lo que ocurre con una probabilidad . En lugar de repetir tiempos para minimizar el error, la amplificación de amplitud se usa para lograr la misma resistencia al error usando solo repeticiones.
Medida escalar
Después de medir con éxito 'bien' en el sistema estará en un estado proporcional a:
Finalmente, realizamos el operador mecánico-cuántico correspondiente a M y obtenemos una estimación del valor de .
Análisis de tiempo de ejecución
Eficiencia clásica
El mejor algoritmo clásico que produce el vector de solución real es la eliminación gaussiana , que se ejecuta en hora.
Si A es s -parse y semidefinido positivo, entonces el método de gradiente conjugado se puede usar para encontrar el vector solución, que se puede encontrar en tiempo minimizando la función cuadrática .
Cuando solo una estadística resumida del vector solución es necesario, como es el caso del algoritmo cuántico para sistemas lineales de ecuaciones, una computadora clásica puede encontrar una estimación de en .
Eficiencia cuántica
El tiempo de ejecución del algoritmo cuántico para resolver sistemas de ecuaciones lineales propuesto originalmente por Harrow et al. se demostró que era, dónde es el parámetro de error y es el número de condición de. Esto se mejoró posteriormente parapor Andris Ambainis [7] y un algoritmo cuántico con polinomio en tiempo de ejecución enfue desarrollado por Childs et al. [8] Dado que el algoritmo HHL mantiene su escala logarítmica ensólo para matrices dispersas o de bajo rango, Wossnig et al. [9] amplió el algoritmo HHL basado en una técnica de estimación de valor singular cuántico y proporcionó un algoritmo de sistema lineal para matrices densas que se ejecuta en tiempo comparado con el del algoritmo estándar HHL.
Optimalidad
Un factor importante en el rendimiento del algoritmo de inversión de matrices es el número de condición , que representa la relación de valores propios más grandes y más pequeños. A medida que aumenta el número de condición, disminuye la facilidad con la que se puede encontrar el vector solución utilizando métodos de descenso de gradiente, como el método de gradiente conjugado , a medida quese acerca a una matriz que no se puede invertir y el vector solución se vuelve menos estable. Este algoritmo asume que todos los valores singulares de la matriz esta entre y 1, en cuyo caso el tiempo de ejecución reclamado es proporcional a se logrará. Por lo tanto, la aceleración sobre los algoritmos clásicos aumenta aún más cuando es un . [1]
Si el tiempo de ejecución del algoritmo se hiciera polilogarítmico en luego, los problemas que se pueden resolver en n qubits podrían resolverse en tiempo poli ( n ), lo que hace que la clase de complejidad BQP sea igual a PSPACE . [1]
Análisis de errores
La realización de la simulación hamiltoniana, que es la principal fuente de error, se realiza simulando . Asumiendo que es s-escaso, esto se puede hacer con un error acotado por una constante , que se traducirá en el error aditivo logrado en el estado de salida .
El paso de estimación de fase se equivoca por en la estimación , que se traduce en un error relativo de en . Si, tomando induce un error final de . Esto requiere que la eficiencia general del tiempo de ejecución se incremente proporcionalmente a para minimizar el error.
Realización experimental
Si bien todavía no existe una computadora cuántica que realmente pueda ofrecer una aceleración sobre una computadora clásica, la implementación de una "prueba de concepto" sigue siendo un hito importante en el desarrollo de un nuevo algoritmo cuántico. Demostrar el algoritmo cuántico para sistemas lineales de ecuaciones siguió siendo un desafío durante años después de su propuesta hasta 2013 cuando fue demostrado por Cai et al., Barz et al. y Pan et al. en paralelo.
Cai y col.
Publicado en Physical Review Letters 110, 230501 (2013), Cai et al. informó una demostración experimental de la instancia significativa más simple de este algoritmo, es decir, resolverecuaciones lineales para varios vectores de entrada. El circuito cuántico se optimiza y se compila en una red óptica lineal con cuatro bits cuánticos fotónicos (qubits) y cuatro puertas lógicas controladas, que se utiliza para implementar coherentemente cada subrutina para este algoritmo. Para varios vectores de entrada, la computadora cuántica ofrece soluciones para las ecuaciones lineales con una precisión razonablemente alta, que van desde fidelidades de 0,825 a 0,993. [10]
Barz y col.
El 5 de febrero de 2013, Stefanie Barz y sus colaboradores demostraron el algoritmo cuántico para sistemas lineales de ecuaciones en una arquitectura de computación cuántica fotónica. Esta implementación utilizó dos puertas entrelazadas consecutivas en el mismo par de qubits codificados por polarización. Se realizaron dos puertas NOT controladas por separado donde la operación exitosa de la primera fue anunciada por una medición de dos fotones auxiliares. Barz y col. encontraron que la fidelidad en el estado de salida obtenido osciló entre el 64,7% y el 98,1% debido a la influencia de las emisiones de orden superior de la conversión descendente paramétrica espontánea. [3]
Pan y col.
El 8 de febrero de 2013 Pan et al. informó una demostración experimental de prueba de concepto del algoritmo cuántico utilizando un procesador de información cuántica de resonancia magnética nuclear de 4 qubit. La implementación se probó utilizando sistemas lineales simples de solo 2 variables. A través de tres experimentos, obtienen el vector de solución con más del 96% de fidelidad. [4]
Wen y col.
Wen et al. Publicaron otra demostración experimental que usa RMN para resolver un sistema 8 * 8. [11] en 2018 utilizando el algoritmo desarrollado por Subaşı et al. [12]
Aplicaciones
Las computadoras cuánticas son dispositivos que aprovechan la mecánica cuántica para realizar cálculos de formas que las computadoras clásicas no pueden. Para ciertos problemas, los algoritmos cuánticos proporcionan aceleraciones exponenciales sobre sus contrapartes clásicas, siendo el ejemplo más famoso el algoritmo de factorización de Shor. Se conocen pocas aceleraciones exponenciales de este tipo, y las que sí lo son (como el uso de computadoras cuánticas para simular otros sistemas cuánticos) hasta ahora han encontrado un uso limitado fuera del dominio de la mecánica cuántica. Este algoritmo proporciona un método exponencialmente más rápido para estimar características de la solución de un conjunto de ecuaciones lineales, que es un problema omnipresente en la ciencia y la ingeniería, tanto por sí solo como como una subrutina en problemas más complejos.
Dispersión electromagnética
Clader y col. proporcionó una versión preacondicionada del algoritmo de sistemas lineales que proporcionó dos avances. Primero, demostraron cómo se podría incluir un preacondicionador dentro del algoritmo cuántico. Esto expande la clase de problemas que pueden lograr la aceleración exponencial prometida, ya que la escala de HHL y los mejores algoritmos clásicos son polinomiales en el número de condición . El segundo avance fue la demostración de cómo usar HHL para resolver la sección transversal del radar de una forma compleja. Este fue uno de los primeros ejemplos de extremo a extremo de cómo usar HHL para resolver un problema concreto exponencialmente más rápido que el algoritmo clásico más conocido. [13]
Resolución de ecuaciones diferenciales lineales
Dominic Berry propuso un nuevo algoritmo para resolver ecuaciones diferenciales lineales dependientes del tiempo como una extensión del algoritmo cuántico para resolver sistemas lineales de ecuaciones. Berry proporciona un algoritmo eficiente para resolver la evolución a tiempo completo bajo ecuaciones diferenciales lineales dispersas en una computadora cuántica. [14]
Método de elementos finitos
El método de los elementos finitos utiliza grandes sistemas de ecuaciones lineales para encontrar soluciones aproximadas a varios modelos físicos y matemáticos. Montanaro y Pallister demuestran que el algoritmo HHL, cuando se aplica a ciertos problemas de FEM, puede lograr una aceleración cuántica polinomial. Sugieren que una aceleración exponencial no es posible en problemas con dimensiones fijas y para los que la solución cumple ciertas condiciones de suavidad.
Las aceleraciones cuánticas para el método de elementos finitos son mayores para problemas que incluyen soluciones con derivadas de orden superior y grandes dimensiones espaciales. Por ejemplo, los problemas en la dinámica de muchos cuerpos requieren la solución de ecuaciones que contienen derivadas en órdenes que escalan con el número de cuerpos, y algunos problemas en las finanzas computacionales , como los modelos de Black-Scholes , requieren grandes dimensiones espaciales. [15]
Ajuste por mínimos cuadrados
Wiebe y col. proporcionan un nuevo algoritmo cuántico para determinar la calidad de un ajuste por mínimos cuadrados en el que se utiliza una función continua para aproximar un conjunto de puntos discretos mediante la extensión del algoritmo cuántico para sistemas lineales de ecuaciones. A medida que aumenta la cantidad de puntos discretos, el tiempo necesario para producir un ajuste por mínimos cuadrados utilizando incluso una computadora cuántica que ejecuta un algoritmo de tomografía de estado cuántico se vuelve muy grande. Wiebe y col. descubren que, en muchos casos, su algoritmo puede encontrar de manera eficiente una aproximación concisa de los puntos de datos, eliminando la necesidad del algoritmo de tomografía de mayor complejidad. [dieciséis]
Aprendizaje automático y análisis de big data
El aprendizaje automático es el estudio de sistemas que pueden identificar tendencias en los datos. Las tareas del aprendizaje automático implican con frecuencia manipular y clasificar un gran volumen de datos en espacios vectoriales de alta dimensión. El tiempo de ejecución de los algoritmos clásicos de aprendizaje automático está limitado por una dependencia polinómica tanto del volumen de datos como de las dimensiones del espacio. Las computadoras cuánticas son capaces de manipular vectores de alta dimensión utilizando espacios de productos tensoriales y, por lo tanto, son la plataforma perfecta para los algoritmos de aprendizaje automático. [17]
El algoritmo cuántico para sistemas lineales de ecuaciones se ha aplicado a una máquina de vectores de soporte, que es un clasificador binario lineal o no lineal optimizado. Se puede utilizar una máquina de vectores de soporte para el aprendizaje automático supervisado, en el que está disponible un conjunto de entrenamiento de datos ya clasificados, o el aprendizaje automático no supervisado, en el que todos los datos proporcionados al sistema no están clasificados. Rebentrost y col. muestran que una máquina de vectores de soporte cuántico se puede utilizar para la clasificación de big data y lograr una aceleración exponencial sobre las computadoras clásicas. [18]
En junio de 2018, Zhao et al. desarrolló un algoritmo para realizar entrenamiento bayesiano de redes neuronales profundas en computadoras cuánticas con una aceleración exponencial sobre el entrenamiento clásico debido al uso del algoritmo cuántico para sistemas lineales de ecuaciones, [5] proporcionando también la primera implementación de propósito general del algoritmo para ejecutarse en computadoras cuánticas basadas en la nube . [19]
Ver también
- Programación diferenciable
Referencias
- ^ a b c Rastra, 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 .
- ^ Cai, X.-D; Weedbrook, C; Su, Z.-E; Chen, M.-C; Gu, Mile; Zhu, M.-J; Li, Li; Liu, Nai-Le; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Computación cuántica experimental para resolver sistemas de ecuaciones lineales". Cartas de revisión física . 110 (23): 230501. arXiv : 1302.4310 . Código Bibliográfico : 2013PhRvL.110w0501C . doi : 10.1103 / PhysRevLett.110.230501 . PMID 25167475 .
- ^ a b Barz, Stefanie; Kassal, Ivan; Ringbauer, Martin; Lipp, Yannick Ole; Dakić, Borivoje; Aspuru-Guzik, Alán; Walther, Philip (2014). "Un procesador cuántico fotónico de dos qubit y su aplicación a la resolución de sistemas de ecuaciones lineales" . Informes científicos . 4 : 6115. arXiv : 1302.1210 . Código Bibliográfico : 2014NatSR ... 4E6115B . doi : 10.1038 / srep06115 . ISSN 2045-2322 . PMC 4137340 . PMID 25135432 .
- ^ a b Pan, Jian; Cao, Yudong; Yao, Xiwei; Li, Zhaokai; Ju, Chenyong; Peng, Xinhua; Kais, Sabre; Du, Jiangfeng; Du, Jiangfeng (2014). "Realización experimental de algoritmo cuántico para la resolución de sistemas lineales de ecuaciones". Physical Review A . 89 (2): 022313. arXiv : 1302.1946 . Código Bibliográfico : 2014PhRvA..89b2313P . doi : 10.1103 / PhysRevA.89.022313 .
- ^ a b Zhao, Zhikuan; Pozas-Kerstjens, Alejandro; Rebentrost, Patrick; Wittek, Peter (2019). "Aprendizaje profundo bayesiano en una computadora cuántica". Inteligencia de la máquina cuántica . 1 (1–2): 41–51. arXiv : 1806.11463 . doi : 10.1007 / s42484-019-00004-7 .
- ^ Computadora cuántica ejecuta el algoritmo cuántico más útil en la práctica, por Lu y Pan .
- ^ Ambainis, Andris (2010). "Amplificación de amplitud de tiempo variable y un algoritmo cuántico más rápido para resolver sistemas de ecuaciones lineales". arXiv : 1010,4458 [ quant-ph ].
- ^ Childs, Andrew M .; Kothari, Robin; Somma, Rolando D. (2017). "Algoritmo cuántico para sistemas de ecuaciones lineales con dependencia de precisión exponencialmente mejorada". Revista SIAM de Computación . 46 (6): 1920-1950. arXiv : 1511.02306 . doi : 10.1137 / 16m1087072 . ISSN 0097-5397 .
- ^ Wossnig, Leonard; Zhao, Zhikuan; Prakash, Anupam (2018). "Un algoritmo de sistema lineal cuántico para matrices densas". Cartas de revisión física . 120 (5): 050502. arXiv : 1704.06174 . Código Bibliográfico : 2018PhRvL.120e0502W . doi : 10.1103 / PhysRevLett.120.050502 . PMID 29481180 .
- ^ Cai, X. -D; Weedbrook, Christian; Su, Z. -E; Chen, M.-C; Gu, Mile; Zhu, M. -J; Pequeño; Liu, N.-L; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Computación cuántica experimental para resolver sistemas de ecuaciones lineales". Cartas de revisión física . 110 (23): 230501. arXiv : 1302.4310 . Código Bibliográfico : 2013PhRvL.110w0501C . doi : 10.1103 / PhysRevLett.110.230501 . PMID 25167475 .
- ^ Jingwei Wen, Xiangyu Kong, Shijie Wei, Bixue Wang, Tao Xin y Guilu Long (2019). "Realización experimental de algoritmos cuánticos para un sistema lineal inspirado en la computación cuántica adiabática". Phys. Rev. A 99 , 012320.
- ^ Subaşı, Yiğit; Somma, Rolando D .; Orsucci, Davide (14 de febrero de 2019). "Algoritmos cuánticos para sistemas de ecuaciones lineales inspirados en la computación cuántica adiabática". Cartas de revisión física . 122 (6): 060504. arXiv : 1805.10549 . doi : 10.1103 / physrevlett.122.060504 . ISSN 0031-9007 . PMID 30822089 .
- ^ Clader, B. D; Jacobs, B. C; Sprouse, C. R (2013). "Algoritmo de sistema lineal cuántico preacondicionado". Cartas de revisión física . 110 (25): 250504. arXiv : 1301.2340 . Código Bibliográfico : 2013PhRvL.110y0504C . doi : 10.1103 / PhysRevLett.110.250504 . PMID 23829722 .
- ^ Berry, Dominic W (2010). "Algoritmo cuántico de alto orden para la resolución de ecuaciones diferenciales lineales". Revista de Física A: Matemática y Teórica . 47 (10): 105301. arXiv : 1010.2745 . Código bibliográfico : 2014JPhA ... 47j5301B . doi : 10.1088 / 1751-8113 / 47/10/105301 .
- ^ Montanaro, Ashley; Pallister, Sam (2016). "Algoritmos cuánticos y el método de elementos finitos". Physical Review A . 93 (3): 032324. arXiv : 1512.05903 . doi : 10.1103 / PhysRevA.93.032324 .
- ^ Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2012). "Ajuste de datos cuánticos". Cartas de revisión física . 109 (5): 050505. arXiv : 1204.5242 . Código Bibliográfico : 2012PhRvL.109e0505W . doi : 10.1103 / PhysRevLett.109.050505 . PMID 23006156 .
- ^ Lloyd, Seth; Mohseni, Masoud; Rebentrost, Patrick (2013). "Algoritmos cuánticos para aprendizaje automático supervisado y no supervisado". arXiv : 1307,0411 [ quant-ph ].
- ^ Rebentrost, Patrick; Mohseni, Masoud; Lloyd, Seth (2013). "Máquina de vectores de soporte cuántico para grandes características y clasificación de grandes datos". arXiv : 1307.0471v2 [ quant-ph ].
- ^ "apozas / bayesian-dl-quantum" . GitLab . Consultado el 30 de octubre de 2018 .