Mecanica Cuántica

¿Qué es la computación cuántica?

La computación cuántica es una forma radicalmente nueva de procesar la información, posibilitada por propiedades exclusivas de la mecánica cuántica tales como la superposición de estados (que origina el denominado paralelismo cuántico) y la existencia de correlaciones sin análogo clásico (entrelazamiento y correlaciones cuánticas).

La ventaja de estas propiedades es que permiten en principio resolver ciertos problemas que resultan muy difíciles para la computación actual. Este tipo de problemas se denominan duros o hard: En ellos, el número de pasos, es decir de operaciones necesarias para llevar a cabo cierto cálculo (y por lo tanto el tiempo de cálculo) aumenta "exponencialmente" con el tamaño de la entrada. En forma sencilla, esto quiere decir esencialmente que el tiempo de cálculo se duplica (o se multiplica por algún factor mayor a 1) cada vez que aumentamos el tamaño de la entrada en una unidad. El tiempo de cómputo de un problema de este tipo puede pasar de unas horas a un tiempo aún mayor que la edad del universo!, tan sólo aumentado ligeramente el tamaño de la entrada.

Un ejemplo típico y de sumo interés actual de un problema considerado hard es el de la factorización. Factorizar un número natural significa escribirlo como producto de factores primos, es decir de números más pequeños que sólo son divisibles por 1 y por si mismos. Por ejemplo, factorizar el número 15 (un número de dos dígitos) significa escribirlo como 3x5, de modo que 15 es divisible por 3 (15/3=5) y por 5 (15/5=3), pero 3 y 5 no son divisibles por ningún número salvo por 1 y el mismo número.

Factorizar parece pues a primera vista un problema fácil y sin interés práctico. En realidad es todo lo contrario: Difícil y de sumo interés práctico. Si bien la factorización de un número de pocos dígitos parece y es de hecho una tarea fácil para cualquier PC actual, la factorización de un número de muchos dígitos (por ejemplo 300) no lo es en absoluto. El número de pasos aumenta en realidad exponencialmente con el número de dígitos. Por ejemplo, la factorización del siguiente número de 232 dígitos,

N=12301866845301177551304949583849627207728535695953347921973224521517264005072636575

18745202199786469389956474942774063845925192573263034537315482685079170261221429134

61670429214311602221240479274737794080665351419597459856902143413

se logró recién en 2010 y demandó alrededor de dos años en cientos de máquinas (hubiese tardado alrededor de mil años en una sóla PC actual). Para un número de 300 dígitos el tiempo sería de alrededor de un millón de años en una PC actual.

La pregunta que surge inmediatamente es ¿Pero a quien puede interesarle factorizar números de este tamaño? Parecería que sólo a matemáticos (y posiblemente a algunos físicos teóricos) pero a nadie más. Sin embargo, es un problema que interesa enormemente no sólo a los matemáticos y físicos sino también a los bancos y al sistema financiero y especialmente a los servicios de espionaje: La criptografía actual,

empleada tanto en las transacciones con tarjetas de crédito por internet como en el envío de mensajes en clave por parte de organismos militares, se basa esencialmente en la dificultad para factorizar tales números grandes. De ser posible una rápida factorización de estos números, se podrían quebrar las claves empleadas y hacer temblar el sistema financiero y el aparato militar mundial.

La criptografía actual se denomina asimétrica o de clave pública, pues la clave para encriptar el mensaje es de público conocimiento pero la clave para descifrar el mismo sólo está en poder del receptor. La obtención de la clave del receptor a partir de la clave pública es en principio posible, pero requiere precisamente la factorización de un número grande.

Y a todo esto, ¿Qué es lo que puede hacer la computación cuántica? Precisamente, en el año 1994, Peter Shor, un matemático de los laboratorios Bell, demostró que de ser posible construir una computadora cuántica, esta podría transformar el problema de la factorización de hard a factible, y podría entonces quebrar la criptografía actual (al menos la basada

...