NeoFronteras

Un algoritmo cuántico permitiría resolver sistemas de ecuaciones lineales muy rápidamente.

La predición del tiempo meteorológico exige resolver sistemas de ecuaciones muy grandes. Fuente: University of Wisconsin-Madison.

Aunque la realización física de la computación cuántica es muy difícil y todavía no contamos con dispositivos que efectúen este tipo de computación de manera práctica, ya disponemos de algunos algoritmos que harán de estás máquinas las computadoras tan potentes que imaginamos, capaces de resolver exponencialmente rápido algunos de los problemas más duros.
Uno de los primeros algoritmos en ser desarrollado hace años fue el que permite factorizar números compuestos (los que no son primos) en sus factores primos. Este algoritmo permitirá quebrar el sistema RSA de cifrado imperante ahora en los sistemas de comunicaciones. Otros algoritmos cuánticos permiten la búsqueda muy rápida en bases de datos.
Pero hay más algoritmos interesantes. Uno de los más recientes permitiría resolver muy rápidamente sistemas de ecuaciones lineales. Sistemas que típicamente podemos simbolizar por Ax=b.
Hay métodos muy sencillos para encontrar las soluciones de sistema de ecuaciones lineales. Cualquiera que haya ido a la escuela y halla prestado atención los sabe aplicar. Esto es más o menos trivial para un par de ecuaciones con dos incógnitas, pero resulta un trabajo muy largo cuando se consideran un mayor número de variables y ecuaciones. A veces hay miles o millones de incógnitas y ecuaciones por sistema que sólo un ordenador potente puede resolver. Pero son justamente ese tipo sistemas lineales grandes los que nos podemos encontrar en la realidad para problemas científicos o de ingeniería, como la predicción del clima. No son problemas teóricamente duros, pues si tenemos N incógnitas y ecuaciones, el tiempo de resolución crece linealmente con N (al menos) con un ordenador moderno. Pero incluso así, a veces se necesita demasiado tiempo para resolver sistemas enormes, incluso con un superordenador.
Ahora, Aram W. Harrow de University of Bristol y Avinatan Hassidim y Seth Lloyd del MIT proponen un algoritmo cuántico para resolver este tipo de problemas.
El algoritmo se basa en la ventaja que los qubits tienen frente a los bits, pues pueden estar en una superposición de estados y ser «0» y «1» a la vez. El algoritmo codifica en una superposición todas las posibles soluciones del sistema, englobando todos los posibles valores de las constantes que están al lado derecho del sistema de ecuaciones (la b de antes). A partir de esta solución universal se puede extraer la solución particular que se busca sin necesidad de calcularla.
La ganancia de tiempo sería enorme. Si con un ordenador convencional tratamos de resolver un sistema de N ecuaciones tardaremos como mínimo 1000 veces más si N es 1000 veces más grande. Pero con el nuevo algoritmo se haría mucho más rápido, aunque N sea muy grande, pues la dificultad del problema no crecería en este caso con N.
Aunque todavía no hay ordenadores cuánticos, Lloyd especula con la posibilidad de aplicar pronto este método de manera indirectamente en Astronomía para obtener imágenes libres de defectos al aprovecharse de la naturaleza cuántica de los fotones.
No deja de ser curioso que desde hace tiempo se viene intentando crear sin éxito algoritmos cuánticos que resuelvan problemas de tipo NP rápidamente (que crecen no polinómicamente según aumenta el tamaño del problema) y que, sin embargo, ahora se proponga uno para un problema mucho más sencillo, pero quizás más práctico.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=2965

Fuentes y referencias:
Phys. Rev. Lett. 103, 250501.