COMPUTACIÓN CUÁNTICA

INTRODUCCIÓN

La computación cuántica es lo que se obtiene de la convergencia de dos teorías tan fascinantes

como la cuántica y la computación. Los mismos conceptos que hacen que la primera haya sido

tan discutida en sus inicios parece que abren un nuevo horizonte a la segunda. Seguidamente,

voy a ofrecer una visión lo más simple y concisa posible y a la vez completa, a nivel de

licenciado, sobre este campo.

A mediados de la década de los 40 toma impulso la ciencia de la información, pronto parece

claro que el concepto propio de información contiene un significado mucho más profundo. De

repente, se hace importante conocer cómo la naturaleza previene o permite que la

información se exprese o sea manipulada. ¿Cuánto ocupa un bit? ¿Cuántos recursos (energía,

masa,...) son necesarios para transmitir un cierto tamaño de información dado? Y qué hay del

‘ruido’, ¿es posible enviar satisfactoriamente información a través de un canal ‘ruidoso’

(entiéndase ruido como interferencia)?

En esos años, Shannon, Golay y Hamming presentan las bases de la codificación y la corrección

de errores en la información. Simultáneamente, y no por casualidad, nace la computación. A

mediados de los años 30 Alan Turing presenta la ‘maquina universal de Turing’(1)

, basada en el

trabajo de Charles Babbage en el siglo XIX.

Más allá de los usos iniciales en decriptación-encriptación y otros usos militares, la

computación se hizo cada vez importante en el ámbito científico. Al principio se centró en la

resolución de algunas proposiciones matemáticas, como por ejemplo la conjetura ‘fuerte’ de

Goldbach (cualquier número entero par mayor que 2 puede descomponer como suma de 2

números primos) pero pronto se extendió y hoy en día es un recurso valoradísimo en todos los

aspectos cotidianos. Los avances posteriores representaron un avance enorme en cuanto a

tamaño y velocidad, pero no variaron sustancialmente el concepto esencial de lo que era una

computadora. La computación cuántica, en cambio, sí que transforma el ‘núcleo’ conceptual

de la computación.

En los años siguientes, se pone de manifiesto las importantes correlaciones entre sistemas

cuánticos separados que han interaccionado en (y sólo en) el pasado. El grado de correlación

en estos sistemas es mayor que el que podría ser previsto en base a cualquier ley física que

describa interacciones locales.

El desarrollo de todas estas teorías llevó primeramente a la criptografía cuántica, justo cuando

la computación cuántica aun se encontraba en estado ‘fetal’.

El desarrollo teórico del ‘qubit’ por Benjamin Schumacher (5), y el trabajo de Deutsch en 1985 (6)

(presentando las ‘puertas cuánticas’, los análogos a las puertas lógicas de la computación

clásica) junto con el desarrollo de los primeros algoritmos para la computación cuántica y el

desarrollo de un sistema para corregir errores en la transmisión de información de forma

cuántica (mediados de los 90) decidieron a la comunidad científica a apostar por esta

disciplina.Más allá de la teoría, los esfuerzos actuales también incluyen el diseño de dispositivos físicos

capaces de llevar a cabo la llamada computación cuántica. En los siguientes capítulos voy a

adentrarme en los principales aspectos apuntados en esta breve introducción.

TEORÍA CLÁSICA DE LA INFORMACIÓN (TCI)

De la misma forma que en determinadas circunstancias, aproximamos algunas leyes cuánticas

a sus hermanas clásicas, es necesario conocer las bases de la computación clásica y la teoría

clásica de la información, antes de definir sus análogos cuánticos.

Existen tres ideas centrales en la teoría clásica de la información que deben ser transportadas

al contexto cuántico:

-El problema más básico en esta teoría es obtener una medida elemental de información:

La máxima cantidad de información que puede ser almacenada por una variable que puede

tomar N valores diferentes es log2(N). De esta forma, una variable doble-evaluada contiene

una unidad de información. Una unidad de información se llama bit. Los dos valores que puede

tomar un bit son 0 y 1.

-Por otro lado, debemos poder codificar secuencias enteras de información mediante fuentes

idénticas e independientes, en este caso bits, de forma que cualquier secuencia de bits va a

transportar un cierto tamaño de información (coherente o no, dependiendo del mensaje).

-No es necesario que el codificado sea totalmente exento de error, es suficiente que la

fidelidad del mensaje sea cercana a 1:

Se define fidelidad (F) como la probabilidad de que el mensaje decodificado sea idéntico al

mensaje anterior a la codificación. De esta forma, la probabilidad de error será: 1-F

Si podemos enviar a través del canal más bits de los estrictamente necesarios, la fidelidad se

podrá hacer arbitrariamente cercana a 1. Si no podemos usar suficientes bits de información,

la fidelidad será cercana a 0. Este hecho es muy común en lo cotidiano, si alguien no es capaz

de escuchar lo que digo, se lo voy a repetir tantas veces sea necesario para que el mensaje sea

correctamente transmitido y por lo tanto, tenga fidelidad 1. Este teorema es particularmente

interesante ya que a priori podemos compensar cualquier ‘ruido’ en el canal mediante una

secuencia suficientemente larga de bits.

TEORÍA CLÁSICA DE LA COMPUTACIÓN (TCC)

En este momento, nos conciernen cuestiones como: ¿qué es computable? ¿Cuántos recursos

son necesarios? La segunda pregunta la puede resolver cualquier usuario de ordenador:

memoria y procesador. De forma general, la computación será difícil e inefectiva si los recursos

necesarios crecen exponencialmente con el tamaño del input (cantidad de información

necesaria para especificar el problema), partiendo de esta máxima, se diseñan los ordenadores a partir del uso del sistema binario, descartando el sistema unitario (1 variable) o el decimal

(10 variables). Esta elección simplifica mucho el diseño de un ordenador y su sistema de

análisis. Para manipular los bits, se definen las puertas lógicas de forma que:

-Cualquier transformación de n bits puede ser llevada a cabo mediante sucesivas

transformaciones de 1 o 2 bits.

-Se definen un total de 16 puertas lógicas capaces de hacer dichas transformaciones. En

realidad, la acción cualquiera de estas 16 puertas lógicas puede ser reproducida mediante la

combinación de 2 o más puertas lógicas idénticas o diferentes, de esta forma se puede concluir

que sólo una puerta lógica es necesaria para cualquier transformación: la puerta NAND (NOT

AND).

Esta visión básica de la computación nos presenta los dos componentes esenciales para que

ésta tenga lugar: muchos bits y varias puertas lógicas (y los cables para conectarlas).

Respecto a la primera pregunta (¿qué es computable?), se define la complejidad

computacional como la cantidad de pasos que una ‘máquina de Turing’ debe realizar para

completar cualquier algoritmo y resolver el problema. En general, la complejidad

computacional va a depender del tamaño del Input, si la dependencia es polinomial (clase P) el

problema será en general tratable. Si la complejidad crece exponencialmente (clase NP) el

problema se considerará difícil y a menudo será más eficiente testear posibles soluciones en

lugar de encontrar una.

Un problema de clase NP es el de la factorización. El método actualmente más eficiente

(Menezes et al 1997), necesita 1018

pasos para factorizar un número de 130 dígitos, que

equivale a 42 días a 1012 operaciones por segundo. Si aumentamos el número de dígitos

llegamos rápidamente a tiempos de cálculo de un millón de años con la tecnología actual. La

lección a aprender en este caso es que un problema computacionalmente difícil es uno que en

práctica no es imposible pero necesita demasiados recursos para su resolución.

El problema de la factorización ha adquirido mucha importancia debido a su uso en sistemas

de encriptación/decriptación: Un sujeto ‘A’ llamado por convención Alice, emite una clave

codificada que consiste en un número ‘c’ que puede ser descompuesto en dos números primos

‘p’ y ‘q’ que sólo conoce Alice. Un espía que no conozca ‘p’ y ‘q’ deberá factorizar ‘c’ para

encontrarlos, si ‘c’ es suficientemente largo, el espía necesitaría un millón de años en

decodificar las claves ‘p’ y ‘q’. Sin embargo para un receptor autorizado llamado (también por

convención) Bob, sería suficiente con conocer ‘p’ o ‘q’ para obtener a partir de ‘c’ la otra clave

del mensaje.

TEORÍA CUÁNTICA

Antes de adentrarnos en la computación cuántica, es necesario presentar algunos conceptos

inherentes a la mecánica cuántica que han sido de gran importancia en su desarrollo. En 1935, Albert Einstein, Boris Podolsky y Nathan Rosen publican un artículo (7) en el que

ponen en duda la completitud de la mecánica cuántica. En su planteamiento,

...