Resolver el problema Ax=b, un sistema lineal de ecuaciones, donde A es una matriz cuadrada y b y x son vectores columna, requiere un coste computacional cuadrático en la dimensión de la matriz, al menos hay que mirar alguna vez todos los elementos de la matriz A. Salvo que la matriz tenga muchos ceros y sepamos donde están (matriz dispersa o sparse). Como mínimo, para que la solución exista, ya que el determinante tiene que ser distinto de cero, tiene que tener O(n) elementos no nulos, con lo que el coste de resolver el sistema lineal será como mínimo de O(n). Por supuesto, en un ordenador clásico. ¿Pero qué pasa en un ordenador cuántico?

Un ordenador cuántico puede ver muchas «cosas» al mismo tiempo (tiene una «visión holística»). Por ello, un algoritmo cuántico puede ordenar un vector de O(n) números en un tiempo O(log n), es decir, «sin verlos todos,» el famoso algoritmo de Grover. El artículo «Quantum algorithm for solving linear systems of equations,» Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, ArXiv preprint, November 20, 2008 , presenta un algoritmo para resolver el sistema lineal Ax=b con un tiempo O(log n). Esto supone una reducción exponencial en el coste respecto al mejor algoritmo clásico existente.

No entraré en los detalles técnicos (no es este el foro adecuado). El artículo, como la mayoría de los del genial Seth Lloyd, del M.I.T., se lee muy fácil pues está muy bien escrito. Es un artículo pensado para que lo puedan entender tanto físicos como informáticos (ambos interesados en los ordenadores cuánticos, se entiende). El algoritmo se basa en un método de Montecarlo que se puede implementar en un ordenador clásico pero para ser eficiente (en un ordenador clásico alcanzar O(n) pasos) requiere un oráculo que le indique dónde tiene que muestrear. El algoritmo cuántico no requiere dicho oráculo y, más aún, converge más rápido que el clásico.

Ha nacido el álgebra numérica cuántica. ¡Increíble! ¡Qué parto! En los próximos meses aparecerán gran número de artículos con versiones cuánticas de la mayoría de los algoritmos del álgebra numérica. En los próximos años asistiremos «al parto» del Matlab cuántico. ¡Increíble! ¡Quién la iba a decir cuando en 1993 Peter Shor, ahora en el M.I.T., logró factorizar números en tiempo polinomial!

Por supuesto, hasta que no haya ordenadores cuánticos construidos físicamente, todo esto no es más que Matemáticas. ¿Quién dijo que la Informática no era más que Matemática Aplicada?

Más información: M.I.T. líder de la computación cuántica.

Fuente de la foto del ordenador cuántico con gato de Schrödinger incluido.