Ordenadores cuánticos y ecuaciones lineales

Los ordenadores cuánticos son capaces de hacer cosas maravillosas, y es una pena que no existan todavía. Sin embargo, los físicos y los matemáticos ya están desarrollando algoritmos que permitirán usar estos increíbles cacharros para resolver problemas que los ordenadores actuales no pueden ni siquiera encarar con posibilidades de éxito. Aram Harrow, Avinatan Hassidim y Seth Lloyd acaban de proponer un algoritmo cuántico capaz resolver un conjunto de ecuaciones lineales  exponencialmente más rápido que cualquier algoritmo clásico. ¿Deberemos aprender a programar nuevamente?

A pesar del incremento de potencia que cada año hace de nuestros ordenadores máquinas más poderosas, existen una serie de problemas que por su complejidad resultan imposibles de resolver mediante hardware y algoritmos “clásicos”. Los futuros ordenadores cuánticos, que utilizan las extrañas leyes de la física de partículas para realizar sus operaciones, no tienen prácticamente limitaciones, y se ha demostrado que algunos problemas -como la factorización de enteros sobre la que se basa casi toda la criptografía actual– pueden resolverse en un tiempo casi despreciable. Día a día los matemáticos y los físicos ponen a punto nuevos algoritmos especialmente concebidos para ser ejecutados sobre estos dispositivos, a pesar de que aún no sepamos cómo construirlos. En un artículo publicado recientemente en Physical Review Letters, Aram Harrow de la Universidad de Bristol (Reino Unido), junto Avinatan Hassidim y Seth Lloyd del MIT (EEUU), proponen un algoritmo cuántico capaz resolver un conjunto de ecuaciones lineales que es exponencialmente más rápido que cualquier algoritmo clásico.

Una ecuación de primer grado o ecuación lineal es un planteamiento de igualdad, involucrando una o más variables a la primera potencia, que no contiene productos entre las variables. Es decir, una ecuación que involucra solamente sumas y restas de una variable a la primera potencia. Son expresiones similares a la siguiente:  3x + 2y = 7. Representadas sobre un sistema de ejes cartesianos, estas ecuaciones se convierten en rectas. La ecuación anterior puede ser resuelta por cualquier estudiante, pero el problema se complica cuando forma parte de un sistema más grande, que contiene miles de millones de variables y miles de millones de ecuaciones. Tales sistemas no son son inusuales en las aplicaciones modernas, y resultan esenciales para elaborar simulaciones de las condiciones meteorológicas, las reacciones nucleares u otros fenómenos físicos. Los algoritmos más eficientes pueden resolver grandes sistemas "N x N" (sistemas con N ecuaciones lineales y N incógnitas) utilizando ordenadores convencionales. Sin embargo, el tiempo de cálculo necesario para llegar a la solución crece al menos tan rápido como N: si N se hace 1.000 veces más grande, el problema tomará -en el mejor de los casos- 1.000 veces más tiempo para ser resuelto. A menudo mucho más.

El algoritmo cuántico que proponen Harrow, Avinatan Hassidim y Lloyd es una especie de “atajo inteligente”. En efecto, su trabajo demuestra que un ordenador cuántico puede proporcionar soluciones relevantes sin necesidad de resolver la totalidad de las ecuaciones implicadas. Con este algoritmo (y un ordenador capaz de ejecutarlo) seríamos capaces de hacer predicciones meteorológicas que en lugar de referirse a una provincia o ciudad, se refieran a cada uno de los bloques de casas que la conforman. Al igual que otros algoritmos cuánticos, este codifica toda la información relevante sobre el sistema a resolver en “bits cuánticos” o qbits. A diferencia de los bits ordinarios, los bits cuánticos pueden poseer valores 0 y 1 al mismo tiempo. Para los físicos, esta especie de esquizofrenia informática se denomina “superposición de estados”. El algoritmo transforma los bits en un estado que  codifica una superposición de todas las posibles soluciones del sistema, asignando todos los posibles valores a las variables de las ecuaciones. De esta “solución universal” se puede entonces extraer información relevante sobre las soluciones particulares sin necesidad de calcularlas completamente.

Dejando de lado la complejidad matemática del asunto, lo concreto es que el aumento de velocidad es enorme: el tiempo necesario para encontrar esta solución universal sólo crece con el número de dígitos de N. Así, si N se hace 1,000 veces más grande, el algoritmo demora solamente el triple de tiempo en encontrar la solución, ya que N -a pesar de ser 1,000 veces mayor- solo tiene tres veces más dígitos. Este tipo de algoritmo, como es de esperar, entusiasma a los científicos. En la década de 1990 se encontró uno similar capaz de factorizar grandes números primos de forma casi instantánea, que nos obligará a buscar nuevos sistemas de seguridad cuando seamos capaces de construir ordenadores cuánticos. Y ese día no está muy lejos.

Efectivamente, ya hemos sido capaces de construir ordenadores cuánticos experimentales, capaces de operar con unos pocos bits. Los científicos creen que fabricar un ordenador más poderoso será posible dentro de una o dos décadas. Cuando llegue ese día, algoritmos como este revolucionaran campos tan dispares como la bioestadística, la ecología, la ingeniería y -por supuesto- los videojuegos: todos dependen en gran medida en la resolución de ecuaciones lineales.