Ya lo contamos en «Algoritmo cuántico para resolver sistemas lineales exponencialmente rápido (o con coste logarítmico),» Publicado por emulenews en 25 Noviembre 2008, pero a veces, hay que volverlo a contar. Lo mejor, una buena excusa, el artículo (una versión corta) ha sido aceptado en la prestigiosa revista Physical Review Letters (PRL): Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, «Quantum Algorithm for Linear Systems of Equations,» Physical Review Letters 103: 150502, 9 October 2009 (versión gratis en el MIT). Los interesados en los detalles técnicos que quieran leer dicha versión, deberán leer también la información suplementaria, que detalla el algoritmo y la demostración de sus propiedades. Por supuesto yo os recomiendo la versión larga, que incluye ambos documentos en uno solo, en el preprint aparecido en ArXiv. Muchos medios se han hecho eco de esta importante contribución científica que ha sido destacada en las sinopsis de la revista de la APS Physics, «The quantum shortcut to a solution» [como no, meneada por mezvan] y que ya fue noticia a finales del año pasado.
La mecánica cuántica de matrices de Heisenberg parece la formulación más natural para la resolución de problemas de álgebra lineal numérica mediante algoritmos cuánticos. ¿Por qué a nadie se le había ocurrido utilizarla? Quizás hay que ser un genio, como Seth Lloyd. Él y sus colaboradores han mostrado cómo utilizarla para resolver problemas como la resolución de sistemas lineales para matrices hermíticas de una dimensión enorme (creo que próximamente se extenderá dicho algoritmo a la resolución de problemas de autovalores). El nuevo algoritmo cuántico permite resolver sistemas lineales dispersos con un speedup exponencial respecto al mejor algoritmo clásico (bajo ciertas condiciones técnicas). Si se logra implementar este nuevo algoritmo permitirá la resolución de sistemas lineales con billones de variables. Para mí lo más importante es que muestra un nuevo camino en la computación cuántico que no ha sido recorrido y que generará muchos frutos en los próximos años, la computación cuántica aplicada a problemas de álgebra lineal numérica.
En muchos casos la solución de un sistema lineal, es decir, el vector tal que , donde y son una matriz y un vector dados de la misma dimensión, no es necesaria. Por ejemplo, cuando dicha solución es utilizada para evaluar una forma cuadrática como , donde es una matriz. El mejor algoritmo clásico para evaluar esta última expresión tiene un coste computacional en tiempo de si la matriz es dispersa (es una matriz de con sólo elementos no nulos) y es su número de condición. Lloyd y colaboradores han encontrado un algoritmo cuántico que lo logra en tan sólo donde es un polinomio. Para sistemas de gran dimensionalidad, esto implica una ganancia exponencial en la eficiencia del algoritmo. Además, el algoritmo cuántico utiliza solamente registros cuánticos de cubits y no requiere «cablear» cuánticamente ni la matriz ni los vectores y . Por otro lado, si no es hermítica no pasa nada se puede volver hermítica fácilmente duplicando su dimensión .
¿Está suponiendo que A es dispersa en el algoritmo cuántico?
Vale, sí. ¿Hay algo para matrices densas?