Computación cuántica - Elías Fernández-Combarro Álvarez

Computación cuántica: un pequeño paso para una partícula, un gran paso para la humanidad.

Descarga capítulo pdf.

Los ordenadores son una de las invenciones que más profundamente y con mayor velocidad han transformado nuestro mundo. Aún no se han cumplido cien años del desarrollo de las primeras computadoras y ya están presentes hasta en las tareas más cotidianas. Mientras escribo estas líneas (en un ordenador), escucho música que llega a mis auriculares desde un servidor situado en otro país (después de pasar por varios ordenadores intermedios) a la vez que estoy pendiente del móvil (¡otro ordenador!) para recibir noticias de la revisión médica que tiene hoy mi hija.

Cuando se comenzaron a desarrollar los primeros prototipos, era difícil imaginar el ritmo al que iba a evolucionar la tecnología informática. Sin embargo, ya en 1965 los rápidos avances en la miniaturización de los circuitos integrados llevaron a Gordon Moore [1], uno de los fundadores de Intel, a enunciar su famosa ley¹: aproximadamente cada dos años se duplica el número de transistores de los microprocesadores².

Fig.1.  Gordon Moore (Foto de Science History Institute, bajo licencia CC).

Este crecimiento exponencial ha posibilitado que hoy en día llevemos cómodamente en el bolsillo dispositivos de cómputo que hace apenas unas décadas habrían ocupado habitaciones enteras… si es que hubiera sido posible siquiera construirlos. Pero, de algún modo, la ley de Moore es una profecía autocumplida: los fabricantes de circuitos integrados planifican sus estrategias y buscan desarrollar nuevas tecnologías para que la ley de Moore se siga cumpliendo.

La pregunta, entonces, es ¿hasta cuándo puede mantenerse este ritmo de crecimiento? Parece evidente que una ley así no puede sostenerse indefinidamente y, de hecho, en los últimos años ya se ha constatado un inicio de desaceleración [2]. Es más, incluso si se pudiera mantener la tasa de incremento, en algún momento los componentes de los circuitos digitales serían tan pequeños³ que se producirían problemas por el efecto túnel cuántico: los electrones podrían “atravesar” espontáneamente la barrera establecida por los semiconductores, impidiendo su correcto funcionamiento.

Con el objetivo de seguir aumentando nuestra capacidad de cálculo, incluso cuando la ley de Moore toque a su fin, se han propuesto numerosas alternativas. Entre ellas, una de las más prometedoras (y de las que más publicidad recibe habitualmente) es la computación cuántica.

Cuando se habla de computación cuántica en los medios de comunicación, se le suelen asociar propiedades cuasimilagrosas (“¡Puede resolver en segundos problemas en los que un ordenador normal tardaría miles de millones de años!”) o que, directamente, parecen magia⁴ (“¡Un qubit puede estar en dos estados a la vez!”). Pero ¿cuánto de verdad hay en esas afirmaciones? Y, sobre todo, ¿cómo funciona la computación cuántica y qué la hace tan distinta de la computación tradicional?

En este capítulo, responderemos a esas y otras cuestiones similares, a la vez que intentaremos mostrar brevemente en qué estado se encuentra actualmente el desarrollo de esta tecnología y hacia dónde puede evolucionar en el futuro próximo.

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

Algunas veces, cuando queremos describir de forma rápida lo que es la computación cuántica, decimos simplemente que es el uso de ciertas propiedades de las partículas subatómicas para llevar a cabo cálculos. Sin embargo, esta definición aclara más bien poco y no deja de ser una reescritura poco sutil de las palabras “computación” y “cuántica”. Es más, toda la materia obedece las leyes de la física cuántica (y, de hecho, la electrónica moderna está basada en las propiedades de este tipo que presentan los semiconductores) por lo que no parece que esta explicación nos haga avanzar mucho en entender por qué la computación cuántica debería ser distinta de la clásica.

Una descripción más detallada y, seguramente, mucho más certera pasaría por decir que la computación cuántica explota⁵ propiedades y efectos que solo se manifiestan a niveles microscópicos, como la superposición, el entrelazamiento o la interferencia de las funciones de onda, para llevar a cabo cálculos de forma más eficiente que con los medios de cómputo tradicional.

Pero claro, ahora hemos transformado una pregunta (¿qué es la computación cuántica?) en otras muchas (¿qué son la superposición, el entrelazamiento y la interferencia y cómo pueden usarse para calcular eficientemente?) de apariencia mucho más técnica y, si se me permite, hasta amenazadora. Sin embargo, quien quiera comprender en profundidad cómo funciona un ordenador cuántico no puede rehuir estas preguntas, por lo que lo explicaremos de la manera más indolora posible. O, cuando menos, lo intentaremos.

Los elementos de la computación cuántica: qubits, puertas y medidas.

Describir esquemáticamente el procedimiento que se lleva a cabo para procesar información es una tarea más o menos sencilla. Básicamente, un ordenador recibe unos datos de entrada, que representa internamente de alguna forma, realiza ciertas manipulaciones matemáticas, lógicas, y simbólicas de (la representación de) los datos y, para terminar, ofrece una salida, que es la respuesta que se le da al usuario.

En el caso de la computación tradicional, los datos se representan mediante secuencias de ceros y unos, por lo que se habla de información binaria cuya base es el bit o binary digit. Hay distintas formas de manipular estos bits. Se pueden copiar o mover de un lugar de la memoria a otro, por ejemplo, o se pueden transformar con operaciones que nos permiten sumarlos, multiplicarlos o aplicarles funciones lógicas⁶. Los elementos que realizan estas transformaciones se suelen llamar puertas lógicas o puertas digitales.

Fig.2.  Una trampa de iones, una de las tecnologías utilizadas para implementar físicamente un qubit (Foto de NIST, bajo licencia CC).

Para representar datos más complejos se usan secuencias de varios bits y, si utilizamos varias puertas sobre los bits individuales, podemos obtener las operaciones que deseemos sobre los datos complejos. Los resultados se obtienen al interpretar adecuadamente el patrón de ceros y unos según el tipo de dato que se haya querido representar (un número, un texto, una imagen…).

Aunque parezca imposible, estas sencillas manipulaciones dan lugar a cualquier procedimiento computable que podamos imaginar⁷.

En el caso de los ordenadores cuánticos, hay cambios en todos los elementos del proceso de cálculo: los datos, su manipulación y la forma de obtener la salida. Los datos pasan ahora a identificarse con qubits (quantum bits), las manipulaciones se llevan a cabo mediante puertas cuánticas y para obtener los resultados se han de realizar mediciones explícitas. Veamos cada uno de ellos con más detalle.

Los qubits.

A diferencia de los bits, que pueden tomar solo dos valores bien definidos y claramente separados entre sí, los qubits adoptan un rango continuo de valores. Es sumamente común escuchar cosas como que un qubit puede tener el valor 0 y el 1 a la vez, pero (dejando aparte gatos de Schrödinger y demás consideraciones filosóficas del significado de la mecánica cuántica) la afirmación resulta poco precisa, por no decir directamente errónea. Matemáticamente, lo que sucede es que un qubit es una combinación⁸ de los valores 0 y 1, una especie de valor intermedio entre ellos. Así, podríamos decir que un cierto qubit es un 75% cero y un 25% uno, un 10% cero y un 90% uno, un 57,328% cero y 42,672% uno, o cualquier otra combinación de cero y uno, incluyendo los casos límite en los que es 100% cero o 100% uno. En realidad, la cosa es un poquito más complicada, puesto que los coeficientes de la combinación pueden ser números negativos (e incluso números complejos), pero la idea es esencialmente correcta.

Esta propiedad de los qubits de estar a medio camino entre el 0 y el 1 es lo que se llama superposición y es una característica propia del mundo subatómico⁹. Así, cualquier sistema cuántico que pueda encontrarse en dos estados distintos (por ejemplo, un fotón con dos direcciones posibles de polarización o una partícula con spin, que puede estar “girando” en dos direcciones diferentes) se presenta, potencialmente, como una posibilidad para implementar físicamente un qubit.

Una representación gráfica habitual de un qubit es la llamada esfera de Bloch (ver Fig. 3). En ella, los números que definen a un qubit como combinación del 0 y el 1 se traducen en dos coordenadas que lo sitúan en un punto de la superficie de una esfera, con el 0 situado en el polo norte y el 1, en el polo sur¹⁰. Nótese que, mientras que en computación clásica se trabaja solo con los dos valores 0 y 1, en computación cuántica se usan un número infinito de posibilidades puesto que cualquier punto de la esfera representa un posible qubit.

Fig.3. La esfera de Bloch. El 0 se sitúa en el polo norte y el 1, en el sur. Cualquier punto de la superficie de la esfera es un posible valor del qubit (Imagen de Wikimedia Commons).

El potencial del uso de qubits en lugar de simples bits clásicos se comienza a entrever cuando manejamos no uno, sino varios qubits. En ese caso, un estado del ordenador cuántico es, en general, una superposición de todas las posibles configuraciones de ceros y unos de los qubits individuales¹¹. Si, por ejemplo, manejamos tres qubits, tendremos que el estado es una suma de las combinaciones 000, 001, 010… hasta 111 (ocho posibilidades distintas). Cuando tenemos n qubits, el número de configuraciones es 2ⁿ y un solo estado puede ser una superposición de todas ellas a la vez. De este modo, cuando hacemos una operación sobre un estado de ese tipo, de algún modo estamos operando sobre los 2ⁿ valores. La mayor parte de los algoritmos cuánticos explotan esta propiedad para acelerar los cálculos con respecto a los algoritmos clásicos (pero, como veremos, no es una cuestión trivial y no se puede conseguir en todas las situaciones).

Las puertas cuánticas.

Ahora ya sabemos que en un ordenador cuántico los datos se representan internamente mediante qubits, pero ¿cómo se manejan? Puesto que cada conjunto de qubits en un estado concreto es, en realidad, el estado físico de un cierto sistema cuántico, las transformaciones a las que podemos someterlo son aquellas permitidas por la mecánica cuántica. En concreto, un sistema cuántico queda caracterizado por una función, llamada función de onda, que nos dice en cada instante qué valores tienen los coeficientes de la superposición. Esta función de onda evoluciona según la famosa ecuación de Schrödinger¹² y, por tanto, las transformaciones permitidas son lo que se llaman transformaciones unitarias¹³.

En el caso de trabajar con un solo qubit, las transformaciones unitarias se pueden representar como rotaciones de la esfera de Bloch y, en general, incluso cuando trabajamos con más de un qubit, las transformaciones permitidas son rotaciones de todo el espacio en el sentido de que preservan los ángulos entre las distintas superposiciones de qubits. Esto tiene varias consecuencias importantes, puesto que marca una clara diferencia con respecto a la computación clásica.

Por un lado, todas las operaciones cuánticas son reversibles (puesto que son “rotaciones”, siempre se puede volver “hacia atrás” rotando en sentido contrario). Esto implica que hay ciertos procesos que no se pueden realizar. Por ejemplo, en computación clásica podemos borrar el contenido de una posición de memoria y ponerlo a cero. Sin embargo, esto es imposible en computación cuántica. Imaginemos, por ejemplo, que tenemos almacenado el valor 01 mediante un par de qubits y el valor 10 en otros dos. Si borramos cada uno de ellos, obtendremos 00 en ambos casos. Como las transformaciones cuánticas son reversibles, deberíamos poder volver desde 00 a 01 y a 10, respectivamente, pero al borrar hemos perdido la información que nos permitía deshacer la operación. ¿Debemos volver desde 00 a 01 o a 10? Es imposible saberlo y, por tanto, la operación de borrado no es físicamente realizable¹⁴.

Otra operación habitual en la computación clásica y que, curiosamente, no puede realizarse en computación cuántica es la copia de información. Se puede demostrar con bastante facilidad (es el famoso Teorema de no clonación [3]) que no es posible hacer, en general, una copia independiente del estado de un grupo de qubits en otro grupo de qubits diferente¹⁵.

Pese a estas limitaciones, que pueden parecer muy severas para alguien acostumbrado a las técnicas de programación clásicas (donde copiar y borrar son operaciones ubicuas), es relativamente fácil demostrar [4] que todo lo que se puede realizar con bits y puertas lógicas clásicas se puede conseguir también con qubits y una adecuada elección de las transformaciones unitarias (por ejemplo, con las llamadas puertas de Toffoli y de Fredkin). Eso sí, el coste añadido es que se necesitarán qubits auxiliares para guardar todos los resultados intermedios, ya que es imposible borrar información¹⁶.

Otra diferencia aún más notable entre las transformaciones que se pueden realizar en computación cuántica y las de la computación clásica es que mientras que en este último caso el número de puertas diferentes para un número fijo de bits es siempre finito, en la computación cuántica el número de posibles operaciones (incluso con un solo qubit) es infinito (puesto que hay infinitas formas de rotar la esfera de Bloch). Obviamente, cuando queremos escribir un algoritmo para ejecutar en un ordenador cuántico, no disponemos de un número infinito de operaciones distintas así que ¿qué podemos hacer?

La solución pasa por utilizar ciertos resultados matemáticos¹⁷ que permiten asegurar que usando sólo un número finito de operaciones de uno y dos qubits es posible aproximar cualquier transformación unitaria que se desee con un error tan pequeño como se requiera¹⁸. Este es el camino que se sigue en la mayor parte de los ordenadores cuánticos que se están construyendo en la actualidad, en los que se selecciona un número relativamente pequeño de operaciones con un número reducido de qubits. Estas operaciones reciben el nombre de puertas cuánticas, por analogía con las puertas lógicas, y se usan para construir (o aproximar, según el caso) todas las demás que se necesiten. Estos grupos de puertas cuánticas reciben el nombre de circuitos cuánticos (ver Fig. 4).

Fig.4.  Ejemplo de circuito cuántico que usa puertas de uno y dos qubits para descomponer una puerta de tres qubits.

Entre las puertas más usadas en casi todas las arquitecturas se encuentran las rotaciones de un solo qubit y la puerta CNOT, que actúa sobre dos qubits¹⁹. La puerta CNOT permite realizar entrelazamientos entre dos qubits, de manera que el valor de uno queda ligado al de otro de un modo que es exclusivo del mundo cuántico. Por medio de la puerta CNOT, podemos construir superposiciones de dos qubits que son un 50% 00 y un 50% 11. Si medimos unos de los qubits de este tipo de estados, obtendremos con el 50% de probabilidad un 0 y con el 50% de probabilidad un 1. Supongamos que obtenemos un 0. Entonces, el estado “colapsa” y queda transformado en 00. Si a continuación medimos el otro qubit, obtendremos 0 con el 100% de probabilidad. Con el caso 11 sucede exactamente lo mismo. Así que midiendo estos estados entrelazados obtenemos valores completamente aleatorios en cada qubit por separado pero, a la vez, el valor de ambos qubits es el mismo. Este hecho tiene importantes consecuencias y aplicaciones, por ejemplo, en criptografía cuántica (de la que hablaremos brevemente hacia el final de este capítulo).

Otra puerta muy importante es la puerta de Hadamard o puerta H, que permite poner un qubit en una superposición que es mitad 0 y mitad 1. De esta forma, aplicando puertas H a cada uno de los qubits de un grupo, se puede obtener una superposición con igual contribución de cada una de las posibles configuraciones de ceros y unos, desde 00…0 hasta 11…1. Muchos algoritmos cuánticos comienzan construyendo una superposición de este tipo, puesto que de esta forma las operaciones posteriores se aplican sobre todas esas configuraciones a la vez, aprovechando lo que se suele llamar el paralelismo cuántico.

Las medidas.

Con lo explicado hasta ahora, podría dar la impresión de que aprovechar la computación cuántica para realizar cálculos de forma mucho más rápida que con un ordenador clásico es pan comido. Si, por ejemplo, quisiéramos evaluar una función en un montón de valores a la vez, parecería que sería suficiente con construir un circuito cuántico para esa función y aplicarlo a una superposición de qubits tal como se explica en el último párrafo de la sección anterior. De esta forma, se calcula la función en todos los valores desde el 00…0 hasta el 11…1 de una sola vez, en contraste con las 2ⁿ aplicaciones de la función que serían necesarias en un ordenador clásico.

Esta idea es esencialmente correcta y, de hecho, se encuentra en el núcleo de gran parte de los algoritmos cuánticos conocidos, pero tiene un pequeño problema: cómo recuperar la información.

En un ordenador clásico, consultar el resultado de una operación es tan sencillo como observar los valores que se encuentran almacenados en una serie de bits de la memoria. Pero recordemos que en un ordenador cuántico los datos se almacenan en qubits que normalmente se encuentran en una superposición de estados. Esa superposición cuántica no se puede observar directamente, sino que es necesario realizar una medida que arroja como resultado una cadena de bits y que, además, destruye de forma irreversible la superposición.

Fig.5. Chip cuántico de IBM, con 4 qubits (Imagen de Jay M. Gambetta, Jerry M. Chow y Matthias Steffen, bajo licencia CC).

Por ejemplo, si tenemos un qubit en un estado que es mitad 0 y mitad 1, cuando lo midamos obtendremos como resultado 0 el 50% de las veces y 1 el otro 50%. Además, a partir de ese momento el qubit pasará a estar en estado 0 o 1, según el resultado obtenido, ya sin superposición alguna.

Por este motivo, la estrategia esbozada al inicio de esta sección no se puede usar directamente: si aplicamos una función sobre una superposición, el estado cuántico será una superposición de todos los valores de la función a la vez, pero al intentar “leerlos”, obtendremos solo uno de ellos… y además será uno al azar, no el que nosotros queramos.

El arte de programar un ordenador cuántico pasa, por tanto, por ser capaz de encontrar operaciones que permitan ir modificando nuestra superposición de manera que aumente la probabilidad de obtener el resultado que necesitamos mientras disminuye la de los valores no deseados. Por ejemplo, si tenemos una superposición en la que el 00 es el valor “correcto” e inicialmente su proporción es del 25%, nuestro circuito deberá localizarlo haciendo que aumente su probabilidad hasta un valor mucho más alto (un 90%, por ejemplo), para que al medir lo obtengamos en la mayor parte de los casos. Si esa probabilidad es suficientemente alta, quizá no hallemos el valor a la primera, pero repitiendo todo el proceso un número pequeño de veces lo obtendremos casi con total seguridad.

Los siguientes apartados describirán a vista de pájaro cómo se pueden implementar este tipo de ideas para resolver ciertos problemas de forma más rápida que en un ordenador clásico.

Un problema que no interesa a nadie… o puede que sí.

Hasta ahora hemos descrito los distintos elementos que se usan para desarrollar circuitos cuánticos (qubits, puertas cuánticas y medidas) y, ¡por fin!, estamos en condiciones de describir algunos de los algoritmos más famosos de la computación cuántica. Comenzaremos con uno de los más sencillos de comprender, un problema que no tiene demasiado interés práctico pero que fue el primero para el que se desarrolló un método cuántico eficiente: el algoritmo de Deutsch-Jozsa [6].

Para comprender el problema, imaginemos que tenemos un armario con cuatro cajones, numerados del 0 al 3. En cada uno de ellos hay una bola, que puede ser de color blanco o de color negro. No sabemos de qué color es la bola de cada cajón antes de abrirlo, pero nos han prometido que o bien todas las bolas son del mismo color o bien la mitad son de un color y la otra mitad de otro. Es decir, o hay cuatro bolas blancas, o hay cuatro bolas negras o hay dos blancas y dos negras. El problema consiste en determinar con total certeza en cuál de las dos situaciones estamos (todas las bolas iguales o la mitad de cada color) abriendo el menor número posible de cajones.

Es obvio que abrir un solo cajón no sirve para resolver el problema, independientemente de cuál sea el color de la bola que nos encontremos. Si abrimos un segundo cajón, hay dos posibilidades: o bien la bola es del mismo color que la del primer cajón que abrimos o bien es de color opuesto. En este segundo caso, ya no necesitamos abrir más cajones, porque sabremos inmediatamente que no todas las bolas son del mismo color y, por tanto, la mitad serán blancas y la mitad negras. Si hemos obtenido bolas del mismo color en ambos cajones, necesitaremos abrir un tercero y, ahí sí, salga lo que salga, habremos resuelto el problema: si la tercera bola también es del mismo color, entonces la que hay en el cajón sin abrir también será igual (recordemos que nos prometieron que serían todas iguales o la mitad de cada color, y ya hemos visto tres del mismo color); si, por el contrario, ahora obtenemos una bola distinta, entonces no todas son del mismo color y la única posibilidad que nos queda es que sean blancas y negras a partes iguales.

Pensemos ahora en el mismo problema, pero con cajones numerados del 0 al 2ⁿ-1. De nuevo, nos aseguran que o bien todas las bolas son del mismo color o bien hay una mitad de cada color. ¿Cuántos cajones deberemos abrir para averiguar en cuál de las dos situaciones nos encontramos? Si tenemos suerte y encontramos inmediatamente dos bolas distintas, con abrir dos cajones será suficiente. Pero si todas las bolas son del mismo color, nunca podremos estar completamente seguros hasta que no abramos 2^n-1+1 cajones (la mitad más uno).

Pues bien, podemos plantear este problema como una cuestión puramente matemática y resolverlo mediante computación cuántica… ¡abriendo solamente un cajón!

En lugar de cajones y bolas blancas y negras, supondremos que tenemos una función f que a cada valor del 0 al 2ⁿ-1 le asigna un 0 o un 1.Entonces podemos identificar la afirmación “hay una bola negra” en el cajón x con “el valor de f(x) es 1”, y “hay una bola blanca” en el cajón x con “el valor de f(x) es 0”. Así, “abrir el cajón x” es, ahora, “consultar el valor f(x)”. Por la suposición acerca de las bolas que hay en los cajones, la función será o bien constante (vale siempre 0 o siempre 1) o bien balanceada (vale 0 en la mitad de los “cajones” x y 1 en la otra mitad).

La función f se puede implementar mediante puertas cuánticas para usarla en un circuito que nos permita determinar en cuál de las situaciones estamos (ver Fig. 6). Basta con crear una superposición de los valores del 0 al 2ⁿ-1, evaluar la función f sobre todo ellos a la vez y, con un pequeño truco, conseguir que cuando f(x) sea 1, el coeficiente correspondiente a x cambie de signo. Finalmente, deshacemos la superposición y medimos.

Fig.6.  Esquema del circuito cuántico del algoritmo de Deutsch-Jozsa (Imagen tomada de Wikimedia Commons).

Si todos los valores de f son iguales, no pasará nada y obtendremos 00…0 como resultado. Sin embargo, si la mitad de los valores de f son 0 y la otra mitad son 1, el signo negativo de unos se compensará con el positivo de otros (decimos que se produce una interferencia destructiva) y obtendremos un valor distinto de 00…0. Así, podemos fácilmente saber en qué situación nos encontramos… consultando f una sola vez.

Aunque el problema es poco útil en la práctica, hemos demostrado algo muy importante: con un ordenador cuántico podemos determinar una propiedad de la función f mediante una sola evaluación, mientras que con un ordenador clásico necesitaríamos, en el peor caso, aplicar f 2^n-1+1 veces. 

Buscando una aguja en un pajar.

Un ejemplo más útil de lo que un ordenador cuántico puede llegar a lograr lo encontramos en el llamado algoritmo de Grover [7]. El problema que debemos resolver en este caso es mucho más natural: tenemos una lista de elementos y queremos encontrar uno que cumpla una condición concreta. Por ejemplo, imaginemos que tenemos un listín telefónico y queremos averiguar el nombre de la persona a la que corresponde un cierto número. Como la lista no está ordenada por números, con un ordenador clásico nuestra única opción es ir mirando uno por uno todos los teléfonos hasta encontrar el que nos interesa.

El algoritmo de Grover nos permite reducir el número de veces que tenemos que consultar la lista de elementos. En lugar de tener que mirar los N registros, podemos mirar solo √N con la garantía de tener una probabilidad muy alta de encontrar el elemento que buscamos (recordemos que, en general, los algoritmos cuánticos no son deterministas y podría ser necesario repetirlos varias veces para tener éxito). Por ejemplo, si nuestra lista tuviera 10.000 elementos, con el algoritmo de Grover solo sería necesario consultarla unas 100 veces para dar con el dato que necesitamos.

Fig.7.  Circuito que usa el algoritmo de Grover para resolver un problema algebraico.

Este método comparte algunas ideas con el algoritmo de Deutsch-Jozsa. Se forma una superposición de todos los elementos y se evalúa sobre todos ellos una función que cambia el signo de aquel que nos interesa encontrar. A continuación, se hace una rotación que va ampliando poco a poco la probabilidad del valor buscado. Este proceso se repite aproximadamente √N veces y, voilá, cuando midamos tendremos muchas posibilidades de hallar el elemento buscado.

El tiempo ganado no es tan espectacular como en el caso del problema de los cajones y las bolas, pero a cambio es un algoritmo con muchísimas más aplicaciones prácticas y que, por ejemplo, puede utilizarse también para encontrar mínimos o máximos [8].

Rompiendo códigos con un ordenador cuántico.

Sin duda el algoritmo que más fama le ha dado a la computación cuántica es el de Shor [9], que permite descomponer un número entero en sus factores primos. Este proceso, que a primera vista parece carecer de utilidad práctica alguna, es de vital importancia por su relación con algunos algoritmos criptográficos muy utilizados, como el famoso RSA [10].

La fortaleza de estos métodos de cifrado de información reside en que, a día de hoy, no conocemos ningún algoritmo que se pueda ejecutar eficientemente en un ordenador clásico y que sea capaz de encontrar los factores primos de un número entero dado. En el caso del RSA, por ejemplo, cada usuario tiene una clave pública (que se puede usar para enviarle mensajes que nadie más pueda leer y para certificar los mensajes que ha firmado) que es el producto de dos primos muy grandes²⁰. Cada parte debe mantener sus números primos en secreto, porque si se conocieran, se podrían utilizar para leer sus mensajes y para suplantar su identidad.

La importancia del algoritmo de Shor radica en que se puede utilizar para obtener esos números primos de manera mucho más rápida que con un algoritmo tradicional. El mejor algoritmo clásico conocido²¹ emplea un tiempo que crece (sub-)exponencialmente con el número de dígitos del entero a factorizar. En la práctica, esto supone que aumentar en un solo bit la longitud de la clave multiplica por un número mayor que uno el tiempo que se tarda en romperla. Así, aumentar en, digamos, 100 bits el tamaño de la clave, cosa relativamente sencilla, multiplicaría por un número inmenso el tiempo necesario para factorizarla.

Sin embargo, el algoritmo de Shor emplea un tiempo que sólo crece polinomialmente²², con lo que un aumento de la longitud de la clave se traduce en un aumento moderado (al menos en comparación con el caso clásico, ver Fig. 8) del tiempo empleado en romperla. Explicar los detalles del proceso requeriría bastante más espacio del que tenemos disponible, así que baste con decir que la clave de la eficiencia del algoritmo de Shor se basa en la posibilidad de ejecutar mucho más rápidamente que en un ordenador tradicional el cómputo de la transformada discreta de Fourier, que permite hallar el periodo de ciertas funciones aritméticas.

Fig.8. Comparación entre el tiempo de ejecución de un algoritmo subexponencial y de uno polinomial en función de la longitud de la clave a factorizar. A partir de un cierto valor, el algoritmo polinomial es mucho más rápido.

¿Qué más pueden hacer los ordenadores cuánticos?

Además de la posibilidad de ejecutar los algoritmos ya mencionados (Deutsch-Jozsa, Grover y Shor), los ordenadores cuánticos abren otras posibilidades para realizar más eficientemente tareas que son costosas (o prácticamente imposibles) con recursos tradicionales.

Por ejemplo, ya en 1982, Richard Feynman observó [11] que simular la evolución de un sistema cuántico es un proceso intratable en un ordenador clásico. Como ya hemos mencionado, el número de parámetros necesarios para especificar un estado cuántico de n qubits es 2ⁿ. Si n es del orden de varios cientos o miles, sólo la cantidad de bits de memoria necesarios para guardar el estado superaría el número de partículas de todo el universo. Sin embargo, los ordenadores cuánticos son sistemas cuánticos, por lo que es natural utilizarlos para reproducir el comportamiento de otros sistemas del mismo tipo. Esto abre la posibilidad, entre otras muchas cosas, de estudiar reacciones químicas complejas, con el abanico de aplicaciones que eso supone, desde el diseño de nuevos materiales al desarrollo de fármacos más efectivos.

Además, en ciertas situaciones, es posible resolver sistemas de ecuaciones lineales eficientemente en ordenadores cuánticos [12]. Por medio del algoritmo HHL²³, podemos resolver este tipo de problemas de forma exponencialmente más rápida que con los métodos clásicos. La limitación del proceso radica en que los datos de entrada deben estar codificados como estados cuánticos y la salida también se da como un estado cuántico. Aunque esto puede impedir recuperar la información de forma rápida, como ya hemos visto, se han encontrado aplicaciones del método HHL para acelerar algoritmos de inteligencia artificial y aprendizaje automático (machine learning). De hecho, el campo del quantum machine learning es uno de los más prometedores dentro de la investigación actual en computación cuántica.

Otro ámbito que puede beneficiarse ampliamente de los desarrollos en las tecnologías cuánticas de la información es el de la criptografía. No se trata de una aplicación pura de la computación cuántica, pero está relacionada de manera muy íntima con ella. La idea es usar propiedades como la superposición y el entrelazamiento de qubits para desarrollar esquemas (uno de los más conocidos es el BB84 [13]) que permiten compartir claves cien por cien seguras y, a la vez, cerciorarse de que nadie ha estado espiando el intercambio de información. La clave es que al medir dos bits entrelazados se obtienen valores aleatorios pero idénticos, como ya hemos visto. Si Alice y Bob quieren comunicarse de forma secreta, pueden compartir pares de qubits entrelazados y utilizarlos para intercambiar una clave de cifrado que se puede demostrar que es irrompible. Así que, ironías de la vida, aunque las tecnologías cuánticas pueden servir para romper la criptografía tradicional, a cambio podrían ofrecernos un medio incluso más seguro de intercambio de claves y, por tanto, de comunicación.

Y todo esto, ¿para cuándo?

Está muy bien hablar de algoritmos y de sus potenciales aplicaciones, pero de nada sirve un método que funciona de forma perfecta sobre el papel si no tenemos un ordenador donde ejecutarlo. La pregunta del millón es, por tanto, cuándo podremos disponer de ordenadores cuánticos que se puedan utilizar en la práctica. Y la respuesta es que… no resulta fácil decirlo.

Aunque en los últimos años se está impulsando de forma significativa la investigación en tecnologías cuánticas y son muchas las grandes compañías, como IBM, Google o Microsoft, que están invirtiendo decididamente en su desarrollo, lo cierto es que los retos a superar no son triviales. Como hemos visto, la mayor parte de los algoritmos dependen de la posibilidad de poner nuestros qubits en superposición, de realizar sobre ellos operaciones que los modifiquen y los entrelacen, y de mantener estos estados durante periodos de tiempo lo suficientemente largos como para completar los cómputos.

El problema es que estos sistemas son sumamente delicados y cualquier interacción con el entorno les hace perder las propiedades que necesitamos para nuestros cálculos²⁴. Se están estudiando y probando distintas propuestas para la implementación de qubits y puertas cuánticas (por ejemplo, mediante trampas de iones o con circuitos superconductores) pero en casi todas ellas es necesario mantener temperaturas muy cercanas al cero absoluto²⁵ así como un grado extremo de aislamiento ante cualquier perturbación externa.

En los últimos años, algunos de estos ordenadores han pasado de ser prototipos de laboratorio a convertirse, como en el caso de los fabricados por IBM, en dispositivos accesibles de forma gratuita y libre a través de la red [14], posibilitando que cualquier persona interesada pueda realizar experimentos con ellos. Por el momento, sin embargo, el número de qubits de estas computadoras es del orden de unas pocas decenas²⁶ y las puertas cuánticas aún presentan más error del que sería necesario para realizar cálculos largos y estables. Se habla, por tanto, de tecnología cuántica de escala intermedia y con ruido²⁷ que, aun así, puede ser útil en ciertas tareas que son difíciles para los ordenadores tradicionales [15].

Cuando todas estas tecnologías maduren, algo que según algunos expertos podría ocurrir tan pronto como en unos diez años [16], lo más probable es que los ordenadores cuánticos no reemplacen por completo a los computadores clásicos, sino que convivan con ellos, especializándose en las tareas en las que más destacan. Por ejemplo, podrían emplearse al estilo de las actuales aceleradoras gráficas, recibiendo los datos y devolviendo las respuestas una vez realizados los cálculos. Eso sí, esa comunicación con los ordenadores tradicionales seguramente se llevará a cabo a través de la red, como una especie de servicio en la nube, dadas las especiales condiciones de refrigeración y aislamiento necesarias (ver Fig. 9).

Fig.9. Laboratorio con varios de los ordenadores cuánticos de IBM (Foto de Connie Zhou para IBM).

En cualquier caso, disponer en el futuro de ordenadores cuánticos con los que resolver problemas que quedan más allá de las capacidades de la computación clásica supondrá, sin duda, un pequeño²⁸ paso para las partículas involucradas, pero un gran paso para la humanidad. 

Referencias:

[1] Moore, G.E. “Cramming more components onto integrated circuits”. Electronics 38(8), 1965.

[2] “Is Moore’s Law still the law?” Electronics Weekly, Sep 2017. https://www.electronicsweekly.com/news/moores-law-still-law-2017-09/

[3] Wootters, W.K., Zurek, W.H. “A single quantum cannot be cloned”. Nature 299, 1982.

[4] Nielsen, M.A., Chuang, I.L. Quantum computationand quantum information: 10^th anniversary edition. Cambridge University Press, 2010.

[5] Dawson, C.M., Nielsen, M.A. “The Solovay-Kitaev algorithm”. Quantum Information & Computation 6(1), 2006.

[6] Deutsch, D., Jozsa, R. “Rapid solutions of problems by quantum computation”. Proceedings of the Royal Society of London A 439(1997), 1992.

[7] Grover L.K. “A fast quantum mechanical algorithm for database search”. Proceedings, 28th Annual ACM Symposium on the Theory of Computing, 1996.

[8]Dürr, C., Høyer, P. “A quantum algorithm for finding the minimum”. https://arxiv.org/abs/quant-ph/9607014

[9] Shor, P.W. “Algorithms for quantum computation: discrete logarithms and factoring”. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994.

[10] Rivest, R.L., Shamir, A., Adleman, L. “A method for obtaining digital signatures and public-key cryptosystems”. Communications of the ACM 21(2), 1978.

[11] Feynman, R.P. “Simulating physics with computers”. International Journal of Theoretical Physics 21(6-7), 1982.

[12] Harrow, A.W., Hassidim, A., Lloyd, S. “Quantum algorithm for linear systems of equations”. Physical Review Letters 103, 209.

[13] Bennett, C.H., Brassard, G. “Quantum cryptography: public key distribution and coin tossing”. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, vol. 175, Nueva York, 1984

[14] IBM Q Experience https://quantumexperience.ng.bluemix.net/

[15] Preskill, J. “Quantum computing in the NISQ era and beyond”. Quantum 2(79), 2018.

[16] Bauer, B., Wecker, D., Millis, A.J., Hastings, M.B., Troyer, M. “Hybrid quantum-classical approach to correlated materials”. Physical Review X 6, 2016.

Elías Fernández-Combarro Álvarez

Licenciado en Matemáticas e Ingeniero Técnico en Informática.

Doctor en Matemáticas.

Profesor Titular del Departamento de Informática, Área de Ciencia de la Computación e Inteligencia Artificial, Universidad de Oviedo.

Grupo de Computación Cuántica y de Altas Prestaciones.

Notas:

1 La “ley de Moore” no es una ley en el sentido habitual del término (como puede serlo la ley de la gravitación universal, por ejemplo), sino más bien una observación acerca de la velocidad con la que se producen ciertos desarrollos tecnológicos.

2 En realidad, al principio Moore estableció que el periodo necesario para duplicar el número de transistores era de un año, pero posteriormente amplió este tiempo a dos.

3 En la actualidad, los procesadores comerciales más avanzados se fabrican con tecnología de 7 nanómetros, un tamaño unas diez mil veces menor que el de un cabello humano.

4 Como bien observó el escritor de ciencia ficción Arthur C. Clarke, “cualquier tecnología suficientemente avanzada es indistinguible de la magia”.

5 Cuenta Seth Lloyd, uno de los más destacados investigadores en computación cuántica a nivel mundial, que una vez le aconsejaron no utilizar la palabra “explotar” para referirse a este tratamiento de las partículas subatómicas, sino que más bien deberíamos decir que se las “empodera” para realizar cálculos.

6 En este sentido, se suele identificar el 1 con el valor “verdadero” y el 0 con “falso”. Así, una operación común entre dos bits es el “y lógico” o “and”: el resultado de aplicar un and a dos bits es verdadero (es decir, 1) si y solo si ambos bits tienen valor verdadero.

7 Este hecho suele llamarse, técnicamente, la tesis de Church-Turing.

8 Formalmente, un qubit es un elemento de un espacio vectorial de Hilbert de dimensión dos, por lo que es una combinación lineal de dos elementos de una base ortonormal del espacio. Los elementos de la base se suelen denotar como |0> y |1>.

9 La ecuación de Schrödinger, a la que obedecen los sistemas cuánticos, es lineal, lo que quiere decir que la superposición (es decir, la suma ponderada) de varias soluciones de la ecuación es también una solución de la ecuación.

10 En realidad, hay otro parámetro extra, una fase global que puede afectar a todo el qubit y no queda reflejada en esta representación, pero este valor no influye en las mediciones y, por tanto, podemos obviarlo en este punto.

11 Matemáticamente, tenemos un producto tensorial de los espacios (bidimensionales) donde viven cada uno de los qubits individuales.

12 La ecuación de Schrödinger es una ecuación diferencial que especifica cómo evoluciona un sistema cuántico.

13 En el caso de un número finito de dimensiones, una transformación unitaria viene dada por una matriz cuadrada de números complejos cuya inversa es, precisamente, la matriz que se obtiene tomando la transpuesta y cambiando cada número por su conjugado complejo.

14 ¿Cómo es posible, entonces, que un ordenador clásico borre información si, en realidad, también sigue las leyes cuánticas? La respuesta es que, en realidad, “borra” esa información gastando energía y transfiriéndola al entorno, aumentando de esta manera su entropía. La información sigue estando ahí, pero es irrecuperable en la práctica.

15 Lo que sí se puede hacer es una copia dependiente, en el sentido de que ambos grupos de qubits quedarán entrelazados y, en lo subsiguiente, cualquier operación que se realice sobre uno de los dos grupos afectará también al otro.

16 Hay un pequeño truco, sin embargo, que permite “descomputar” algunos valores y volver a reutilizar los qubits auxiliares.

17 Véase, por ejemplo, [5].

18 Pero, en general, ese error existirá y deberá tenerse en cuenta al analizar el funcionamiento de nuestro algoritmo.

19 La puerta CNOT es una negación controlada: cambia el valor del segundo qubit de 0 a 1 y de 1 a 0, pero sólo si el primer qubit tiene valor 1; si el primer qubit es 0, el segundo qubit permanece inalterado.

20 Cada uno de ellos con cientos de dígitos.

21 Basado en la criba general del cuerpo de números (general number field sieve).

22 Con más precisión, tiene orden de crecimiento O(n2log(n) log(log(n))), siendo n el número de dígitos de la clave.

23 Sus descubridores son Aram Harrow, Avinatan Hassidim y Seth Lloyd.

24 Técnicamente, decimos que se pierde la coherencia de los estados cuánticos.

25 Tan bajas, en algunos casos, como 20 milikelvins, muchísimo menos que la temperatura del espacio exterior.

26 Es cierto que la empresa canadiense D-Wave ha fabricado dispositivos con varios cientos de qubits, pero se trata de ordenadores enfocados a resolver ciertas tareas de optimización concretas, no capaces de ejecutar todo tipo de algoritmos cuánticos.

27 En inglés, Noisy Intermediate-Scale Quantum technology o NISQ.

28 Microscópico, literalmente.