Mi charla Ciencia Jot Down 2017: “El superpoder de los ordenadores cuánticos”

Dibujo20170924 slide 01 Superpoder Cuantico Ciencia Jot Down 2017

Ya está disponible el vídeo de mi charla “El superpoder de los ordenadores cuánticos” en Ciencia Jot Down 2017, en el CICUS Centro de Iniciativas Culturales de la Universidad de Sevilla. Te recomiendo ver el vídeo, a partir del minuto 13:00 hasta el 42:00. Y por supuesto el resto de las charlas del sábado 23 de septiembre, y las del viernes 22 de septiembre.

Todos habéis oído alguna vez que los ordenadores cuánticos del futuro serán más poderosos que los ordenadores clásicos actuales, más aún, serán superpoderosos y podrán hacer cosas que son imposibles de hacer con ordenadores clásicos. Desde el punto de vista de la calculabilidad, o computabilidad, lo que se puede o no se puede hacer con recursos ilimitados, esto es mentira, todo ordenador cuántico se puede simular mediante un ordenador clásico (repito, con recursos ilimitados en memoria y tiempo). Pero con recursos limitados, desde el punto de vista de la complejidad computacional o algorítmica, los ordenadores cuánticos pueden ser más eficientes que los ordenadores clásicos en ciertos problemas muy concretos. Para estos problemas concretos difíciles de resolver en ordenadores clásicos, un ordenador cuántico podría resolverlos en un tiempo razonable.

Dibujo20170924 slide 02-05 Superpoder Cuantico Ciencia Jot Down 2017

Para presentar las ideas básicas de la teoría de la calculabilidad y de la teoría de la complejidad hay que presentar el concepto de algoritmo. ¿Qué es un algoritmo? Un procedimiento de cálculo, un conjunto de operaciones que se realizan sobre un conjunto de datos. Podemos ejecutar un algoritmo a mano, tomando datos escritos en hojas de papel, realizando ciertas operaciones elementales (sumas, productos o divisiones) y escribiendo el resultado en otras hojas de papel. Así ejecutaban algoritmos las calculadoras o computadoras, personas, normalmente mujeres, durante gran parte del siglo XX. Con la llegada de los ordenadores electrónicos, microelectrónicos e, incluso, nanoelectrónicos, los algoritmos se ejecutan gracias a una unidad de control de procesos a partir de programas almacenados en una memoria y usando datos almacenados en dicha memoria. Por cierto, muchos ordenadores durante el siglo XX fueron programados por mujeres.

Los ordenadores cuánticos también ejecutan algoritmos cuánticos: se prepara el ordenador en un estado cuántico inicial, se ejecutan una serie de operaciones paso a paso, y se finaliza con una medida del estado final del sistema que ofrece un resultado clásico. Si todo ha ido bien el resultado clásico final será solución del problema. Los operaciones sobre la memoria cuántica cambian las probabilidades de los estados de la mecánica cuántica, haciendo más probables los estados que representan soluciones a nuestro problema y menos probables los que no representan soluciones.

Dibujo20170924 slide 06-07 Superpoder Cuantico Ciencia Jot Down 2017

El concepto intuitivo de algoritmo se puede formalizar matemáticamente de muchas maneras. Por ejemplo, mediante funciones mu-recursivas de Gödel, mediante máquinas de Turing, mediante fórmulas del cálculo lambda de Church, etc. Se puede demostrar que todas ellas son equivalentes entre sí. Todo lo que se puede calcular (con recursos ilimitados) se puede calcular con una máquina de Turing (o con cualquier otra formalización matemática equivalente). Este hecho se llama tesis de Church-Turing (1936).

En 1985 David Deutsch introdujo la máquina de Turing cuántica o máquina de Deutsch. Además, demostró que es equivalente a la máquina de Turing, todo lo que se puede calcular con una se puede calcular con la otra y viceversa; la tesis Church-Turing-Deutsh afirma que el concepto de algoritmo cuántico coincide con el concepto de algoritmo clásico y desde el punto de vista de la calculabilidad (lo calculable con recursos infinitos, ambos conceptos son equivalentes).

Dibujo20170924 slide 08-10 Superpoder Cuantico Ciencia Jot Down 2017

En la práctica, con recursos limitados, tenemos que tener en cuenta la complejidad computacional o algorítmica. Se habla de complejidad en tiempo (TIME), para referirse al número de pasos de un algoritmo, y de complejidad en espacio (SPACE), para el número de bits (o celdas de memoria) necesario para resolver un problema. Hay problemas fáciles de resolver y problemas difíciles de resolver, entre estos últimos destacan los que tienen soluciones fáciles de verificar.

¿El número de la transparencia es primo? Quizás te parezca un problema muy difícil de resolver, y así era durante gran parte del siglo XX. Sin embargo, ya en el siglo XXI, los indios Agrawal, Kayal y Saxena (2002) descubrieron que es un problema fácil, de costo polinómico. Se llama clase P a los infinitos algoritmos que resuelven un problema (obtienen su solución) en un número polinómico de operaciones. El test de primalidad es un algoritmo en P.

¿Cómo podemos saber si alguno de los divisores de un número acaba en 7? El único algoritmo conocido para hacerlo requiere factorizar el número en divisores primos y mirar su último dígito. Como comprobar que los supuestos factores primos realmente lo son solo requiere una multiplicación, este problema está en la clase NP, problemas que se resuelven con un algoritmo no determinista en coste polinómico y cuya solución se puede verificar con un algoritmo en la clase P.

Hay algo sorprendente con las matemáticas, son tan poderosas que se puede demostrar que hay una subclase de problemas NP, los llamados NP-completos, tales que todos los problemas NP se pueden reducir a un problema NP-completo de forma eficiente (con un sobrecoste polinómico). Determinar los factores primos de un número entero es un problema NP. Un problema muy útil porque se usa en el cifrado de clave pública (para enviar información segura por Internet).

No sabemos si todos los problemas NP (verificación eficiente) están en la clase P (solución eficiente). La mayoría de los expertos cree que NP ≠ P. Hay un millón de dólares para quien lo demuestre. Si un problema NP resulta estar en P no pasa nada; solo estaba mal clasificado. Pero si un problema NP-completo pasa a P, entonces NP = P. Ningún experto lo cree posible.

Dibujo20170924 slide 11-13 Superpoder Cuantico Ciencia Jot Down 2017

En 1994, Peter Shor encontró un algoritmo cuántico que resuelve el problema de factorización de números en coste polinómico (por cierto, los dos factores primos del número anterior acaban en 7). El algoritmo de Shor permite que un problema NP se clasifique en la clase P cuántica, llamada BQP (algoritmos cuánticos cuyo coste en número de operaciones cuánticas está acotado por un polinomio en el tamaño de la entrada, o su número de cúbits).

La clase NP tiene infinitos algoritmos, mientras que en la clase NP-completo solo conocemos un número finito (unos miles de algoritmos, muchos de ellos muy similares entre sí). Ningún experto en complejidad computacional cuántica cree que los problemas NP-completos se puedan resolver de forma eficiente en un ordenador cuántico (NP-c ≠ BQP). De hecho, la clase BQP contiene algunos algoritmos más allá de NP, por ejemplo, algunos algoritmos PSPACE y EXPTIME relacionados con la simulación de sistemas cuánticos. Todo indica que la clase BQP es un poco más grande que P, pero nadie espera que sea mucho más grande.

Dibujo20170924 slide 14-18 Superpoder Cuantico Ciencia Jot Down 2017

¿Qué es un ordenador cuántico? Un ordenador cuántico es un ordenador no determinista o probabilístico (que es reversible, trabaja a entropía constante y tiene otras propiedades en las que no entraré). Se prepara un estado inicial con ciertas probabilidades para todos los estados, se ejecutan instrucciones que cambian las probabilidades, haciendo que algunas crezcan y otras se reduzcan, al final, si todo va bien, las probabilidades del resultado correcto son más grandes y al medir el sistema se obtiene con gran probabilidad la respuesta correcta. La gran diferencia con los ordenadores clásicos no deterministas es que se usan “probabilidades negativas” (llamadas amplitudes de probabilidad) y que las operaciones son no locales (memorias cuánticas).

La unidad de información es el bit, un dígito 0/1, encendido/apagado, etc. En ordenadores no deterministas (o probabilísticos) la unidad de información es el próbit (bit probabilístico) que viene descrito por una probabilidad p ∈ [0,1] para el valor |0> y (1−p) para el valor |1>. La unidad de información cuántica es el cúbit (bit cuántico, a veces llamado qubit) que está descrito por dos amplitudes de probabilidad α y β (ambos números complejos) que determinan la superposición cuántica entre los estados |0> y |1>; el cúbit está determinado por dos números reales, que pueden ser positivos o negativos, mientras el próbit está determinado por un solo número real que tiene que ser positivo.

La gran diferencia entre la computación clásica (no determinista) y la computación cuántica es la localidad de las operaciones que se realizan sobre las memorias (registros de múltiples próbits o cúbits). En una memoria clásica las operaciones son locales y solo afectan a pocos próbits quedando inalterados el resto. En una memoria cuántica las operaciones que se ejecutan de forma local tienen efectos no locales; desde un punto de vista informático (obviando los detalles de física cuántica), las amplitudes de probabilidad negativa permiten un cambio local de las probabilidades que debe ser compensado con un efecto no local en el resto de los cúbits. De esta forma cada operación cuántica afecta a los 2^n estados de un registro de n cúbits.

Dibujo20170924 slide 19-22 Superpoder Cuantico Ciencia Jot Down 2017

Fabricar un ordenador cuántico es difícil por el efecto de la decoherencia cuántica. El entorno destruye el estado de superposición de los n cúbits y lo rompe en estados superpuestos de menor tamaño; así el poder cuántico se reduce a la superposición coherente más pequeña. La decoherencia tiene una escala de tiempo que depende de la tecnología del sistema y hay que realizar todas las operaciones cuánticas en un tiempo más corto para que su efecto se minimice.

Ahora mismo es imposible fabricar ordenadores cuánticos con decenas de cúbits con garantías de que se encuentren en un estado de superposición. Los ordenadores con 2048 cúbits de la compañía D-Wave Systems no son ordenadores cuánticos, ya que no garantizan el estado de superposición durante todo el cómputo ni siquiera en bloques de cuatro cúbits (al menos no lo han demostrado aún); dichos ordenadores son clásicos no deterministas aunque usen cúbits como fuente de aleatoriedad en sus próbits. Aún así, si durante el siglo XXI logramos fabricar un ordenador cuántico con 300 cúbits en superposición coherente tendríamos más estados que átomos hay en el universo visible. La potencia computacional del paralelismo cuántico es descomunal, pero luchar contra la decoherencia en una memoria cuántica de muchos cúbits es muy difícil, quizás imposible.

Mucha gente le tiene miedo a los futuros ordenadores cuánticos porque podrían desvelar las claves secretas que usamos en nuestras transacciones con tarjetas en Internet. Se usan técnicas de cifrado con clave pública que se basan en algoritmos de la clase NP (difíciles de resolver, pero fáciles de verificar), como la factorización de números. No hay que preocuparse, ya que se conocen algoritmos de cifrado en la clase NP-completo que son seguros incluso para los ordenadores cuánticos. Todos los algoritmos de cifrado seguros ante ataques cuánticos se llaman postcuánticos y cuando sean necesarios su uso será tan sencillo como tocar una tecla y cambiar de algoritmo.

Hay que tenerle miedo a que dichos algoritmos cuánticos del futuro descifren la información cifrada en la actualidad. No, de hecho, ya podemos descifrar casi toda la información cifrada antes de 1990 con los superordenadores actuales y a nadie parece preocuparle que se desvelen dichos secretos (cuyo único interés es histórico). La utilidad real de los ordenadores cuánticos no es descifrar claves secretas.

Dibujo20170924 slide 23-26 Superpoder Cuantico Ciencia Jot Down 2017

El superordenador que lidera el TOP 500 es el chino TaihuLight que alcanza una potencia punta de 93 petaflops por segundo; se estima que simular un sistema cuántico con 50 cúbits requiere un petaflop, luego con menos de 60 cúbits ya tendríamos un ordenador cuántico más poderoso que el líder mundial actual. Por ello una manera de demostrar que un ordenador cuántico es realmente cuántico es alcanzar la supremacía cuántica, resolver un problema hoy que es imposible de resolver con el TaihuLight a día de hoy. ¿Estamos lejos de la supremacía? Google, IBM, Microsoft y otras compañías más pequeñas quieren demostrar la supremacía cuanto antes (se ansía lograrla para principios de la década de los 2020). No parece fácil, pero la competencia entre gigantes y las inversiones multimillonarias podrían facilitar que se logre.

¿Para qué servirá un futuro ordenador cuántico? Para simular sistemas cuánticos (un problema PSPACE que está más allá de la potencia de los ordenadores clásicos actuales pero que está en BQP para un ordenador cuántico). Parece una tontería pero no lo es, ya que los sistemas cuánticos sufren mucho la decoherencia y no podemos estudiarlos mediante experimentos. Con un ordenador cuántico robusto ante la decoherencia se podrían simular muchos sistemas de interés aplicado y tecnológico: la acción de fármacos, el comportamiento de los sitios acivos de las proteínas, el diseño de nuevos materiales, e incluso el estudio de ciertas teorías cuánticas de campos con interés en física fundamental.

Dibujo20170924 slide 27-28 Superpoder Cuantico Ciencia Jot Down 2017

Por supuesto, fabricar ordenadores cuánticos es muy difícil y solo hemos logrado pequeñas máquinas con unos pocos cúbits. Hay muchas tecnologías en competencia y aún no sabemos cuáles serán las vencedoras; no tengo tiempo de entrar en detalles. Solo quisiera destacar la tecnología de átomos atrapados, que podría darle el Premio Nobel de Física a Juan Ignacio Cirac (junto a Peter Zoller). Ambos demostraron cómo implementar la puerta cuántica C-NOT mediante esta tecnología; junto con la puerta de Hadamard constituyen un sistema universal de puertas; sin embargo, los ordenadores cuánticos con estas puertas de una o dos entradas se pueden simular de forma eficiente mediante ordenadores clásicos, luego son poco útiles en la práctica; se requieren al menos puertas de tres entradas, como las puertas de Toffoli o Fredkin; que también se pueden implementar con la tecnología de átomos atrapados. Si esta tecnología es relevante dentro de 30 años, Cirac recibirá el Nobel.

En Sevilla me gustaría destacar el trabajo de un físico (madrileño) de la Universidad de Sevilla, Adán Cabello. Ha propuesto que el secreto de la computación cuántica no es el entrelazamiento cuántico (no he explicado lo que es), ni la superposición cuántica con efectos no locales, sino la contextualidad cuántica. Hoy en día los ordenadores cuánticos contextuales están en una fase muy primitiva, pero si en 30 años se ponen de moda y resultan ser una tecnología relevante en el área, Cabello podría recibir el Nobel de Física por su trabajo.

En resumen, España es una potencia en computación cuántica (sobre todo teórica, pero también experimental). No sabemos si algún día se podrán construir grandes ordenadores cuánticos, pero incluso si solo se fabrican ordenadores cuánticos pequeños, serán de gran utilidad como oráculos de ordenadores clásicos en centros de supercomputación. En mi opinión, ninguno tendremos un ordenador cuántico en casa, salvo que usemos la física cuántica como parte de nuestro trabajo.


4 Comentarios

Participa Suscríbete

Pedro MascarósPedro Mascarós

Dolorosa errata ” ha nadie”

Respecto al miedo, creo que hay que tenerle mucho más respeto, que no miedo, a la computación clásica; ya existen sistemas clásicos tomando decisiones importantes en la bolsa, y en menor medida en hospitales o laboratorios, que no son depurables, es decir, que no es un software al uso donde uno pueda depurar paso a paso y ver donde falla o realiza las acciones directamente, si no que sus acciones son resultado de distintas reglas de bajo nivel (redes neuronales) no explícitas a alto nivel, cuya forma de programación ha sido más por auto aprendizaje del propio sistema que por manipulación directa.
La computación clásica tiene mucho más que decir de lo que la gente cree, y va a deparar grandes sorpresas en el futuro.

Pedro MascarósPedro Mascarós

El problema básico es obviamente que queremos que la máquina pueda tomar decisiones particulares, pero que al mismo tiempo, no se escape de nuestro control, y eso tiene visos de ser imposible.

El software de Google capaz de indentificar un perro en una foto, cualquier foto, no sabemos cómo funciona, solo lo sabemos a grandes rasgos, el código no hace nada explícito respeto a la identificación.
El software que empezó a mandar a pacientes graves de asma a su casa, pues tampoco se pudo saber porqué hasta mucho tiempo después, y de forma indirecta, no a través de su código (imposible) si no percatándose cómo había llegado la máquina a esa conclusión a través de su experiencia.
Una de las IA de Facebook comenzó a usar abreviaturas para comunicarse entre sus distintos agentes, y como los programadores no lo entendían bien, prescindieron de ella.

El tema es que hablamos solo de software, es decir, no hablamos de intrincado hardware, es solo código, en máquinas de toda la vida…

Todo apunta a que decisión va a estar reñido con control, tal como parece intuitivo.

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>