Algoritmo cuántico para sistemas de ecuaciones lineales

El algoritmo cuántico para sistemas de ecuaciones lineales, diseñado por Aram Harrow, Avinatan Hassidim, y Seth Lloyd es un algoritmo cuántico para resolver sistemas de ecuaciones lineales formulado en 2009. El algoritmo estima el resultado de una medida sobre el vector solución de un sistema de ecuaciones lineales dado.Es uno de los algoritmos fundamentales que junto con el algoritmo de Shor, el algoritmo de Grover y el algoritmo de simulación cuántica de Feynman esperan proporcionar un aumento de la velocidad exponencial respecto de sus versiones clásicas. Dado un sistema lineal disperso con un número de condición k, bajo y estando el usuario interesado en una medida sobre el vector solución, en vez del propio vector solución, el algoritmo tiene un tiempo de ejecución de O(log Nk2). Esto ofrece un aumento exponencial de la velocidad respecto al algoritmo clásico mas rápido, cuyo tiempo de ejecución es O(N√k), donde N es el número de variables del sistema lineal.Una implementación del algoritmo fue realizada en paralelo por primera vez en 2013 por Cai et al., Barz et al. y Pan et al. La demostración consistió en la resolución de un sistema simple de ecuaciones lineales especialmente diseñado para dispositivos cuánticos.Debido al uso de los sistemas lineales en prácticamente todas las áreas de la ciencia y la ingeniería, el algoritmo cuántico para sistemas de ecuaciones lineales tiene el potencial de ser el algoritmo cuántico más utilizado hasta ahora. Este es un importante hito para la computación cuántica ya que los anteriores algoritmos ofrecen una aceleración exponencial pero no tienen ni versatilidad ni obvias aplicaciones en el mundo real.