|QC-5> Puchero de átomos
Hasta ahora hemos visto el fundamento y funcionamiento de un computador cuántico generalista, universal o también conocido como “basado en puertas”, pero hay otro tipo de computadores cuánticos que son más específicos, es decir, sólo resuelven un tipo muy concreto de problemas pero que, por contra, son más sencillos de construir y, en cierto modo, de escalar.
Pero, para entender cómo funcionan este tipo de computadores cuánticos, es necesario entender cómo se formulan los problemas que resuelven, y ello nos lleva a hablar de la optimización.
El problema de la optimización
En términos generales, la optimización aplica tanto a computadores cuánticos como clásicos. Se trata de diseñar los algoritmos adecuados para resolver problemas extremadamente complejos o, dicho de otro modo, computacionalmente muy complejos.
No vamos a tratar en profundidad el dominio de la optimización porque es un campo muy extenso, aunque sí intentaremos describir algunos fundamentos y centrarnos en un tipo de problemas de optimización característicos, que son los que pueden resolverse con un tipo específico de computadores cuánticos, que luego introduciremos.
Tampoco vamos a entrar en la teoría de complejidad computacional, pero te dejamos unas referencias para que profundices en el tema si tienes interés:
- Para empezar: Wikipedia
- Si quieres profundizar un poco: Teoría De La Complejidad Computacional Y Teoría De La Computabilidad
En ciencias de la computación, como en otras disciplinas científicas, un problema a resolver se representa mediante una expresión matemática, que se llama modelo matemático, y la creación de este modelo matemático se llama formulación.
Por lo tanto, es necesario formular el problema a resolver como un problema de optimización y describir en qué medida se ha logrado el propósito requerido por el problema. Esto se denomina función objetivo y las variables determinadas para lograr este objetivo se denominan variables de decisión.
Como hemos visto, existen problemas cuya formulación puede ser sencilla, pero son imposibles de resolver en un tiempo razonable, ni aún disponiendo de un supercomputador del tamaño de nuestro planeta. Muchos de los problemas de optimización entran dentro de esta categoría.
Hay muchos problemas de este tipo en el mundo de la ciencia, de la ingeniería o de la industria, que podríamos usar para ilustrar los conceptos que queremos presentar, pero usaremos el muy conocido problema del viajante, o también llamado del vendedor ambulante, que seguro te resulta familiar. Este problema fue formulado por primera vez como un problema matemático en 1930 y se trata de uno de los problemas más intensamente estudiados en optimización.
El problema del viajante
El problema del viajante responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?
La aproximación tradicional para resolver este problema y obtener el resultado óptimo, sería explorar, una a una, a fuerza bruta, todas las posibles combinaciones, ordenarlas y seleccionar aquella en la que la distancia es menor. Fácil, si, pero la dificultad reside en que el número de combinaciones crece de modo factorial en función del número de ciudades a considerar.
Para que te hagas una idea, para 30 ciudades, el problema, resuelto de este modo, requeriría explorar ½(n-1)! = 4x1030 combinaciones diferentes (4 quintillones de combinaciones). Incluso con el supercomputador más potente del mundo hasta la fecha (noviembre del 2021), el FUGAKU, construido por FUJITSU y capaz de realizar 442.000 billones de operaciones en un segundo, necesitaríamos más de 300.000 años para explorar todas estas combinaciones. Ahora, eso sí, seríamos clientes VIP de nuestra compañía eléctrica, porque ¡le habríamos pagado más de 15 billones de euros! Y todo ello para encontrar la ruta óptima entre 30 ciudades…creo que no nos va a merecer la pena o, como dirían mis hijos: ¡No nos renta!
Este tipo de problemas se encuadra en la categoría de problemas de optimización combinatoria…. Pero no vamos a profundizar en este tema. Lo que sí vamos a subrayar es que, dentro del dominio de las ciencias de la computación, se han desarrollado infinidad de técnicas para resolver este tipo de problemas e implementarlos en algoritmos de búsqueda, recomendación, clasificación, …
Estas técnicas se denominan metaheurísticas. Una metaheurística es un método heurístico (basado en la experiencia), para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos, de una manera que se espera eficiente.
Muchos de estos algoritmos están, como no podía ser de otro modo, inspirados en la sabia naturaleza, como es el caso de los algoritmos de colonia de hormigas, algoritmos genéticos, algoritmos basados en inteligencia de enjambre o algoritmos basados en inteligencia colectiva.
Recocido simulado (Simulated Annealing)
Uno de los algoritmos metaheurísticos más antiguos, pero más populares, es el Recocido Simulado (Simulated Annealing o SA), que es una técnica de búsqueda aleatoria de optimización. Imita el proceso de recocido en el procesamiento de materiales metálicos. En el recocido, los átomos se separan de su estado inicial y cambian a un estado de mayor energía. El enfriamiento lento en este estado, aumenta la probabilidad de recristalizar en configuraciones con menor energía que la inicial (mínimo global)
Las características mecánicas de un material dependen tanto de su composición química como de la estructura cristalina que tenga. Estas características pueden ser la resistencia al desgaste, resistencia al impacto o la dureza. Los tratamientos térmicos modifican esa estructura cristalina sin la composición química, mediante un proceso de calentamientos y enfriamientos sucesivos hasta conseguir la estructura cristalina deseada.
El Recocido Simulado imita el proceso de recocido en el procesamiento de materiales metálicos. En el recocido, los átomos se separan de su estado inicial y cambian a un estado de mayor energía (se calienta). El enfriamiento lento en este estado aumenta la probabilidad de recristalizar en configuraciones con menor energía que la inicial (alcanzar un mínimo global)
Modelo de Ising
Para resolver un problema con una computadora de Von Neumann (que es la arquitectura en que se basan todos los computadores digitales convencionales), se considera una solución correspondiente al problema (algoritmo), el algoritmo se describe como una secuencia de instrucciones para la CPU y la CPU ejecuta secuencialmente las instrucciones. Aunque también se utilizan técnicas para ejecutar simultáneamente múltiples instrucciones y acelerar el proceso, es una característica de las computadoras convencionales ejecutar instrucciones secuenciales.
Antes de la computadora Von Neumann, hubo una era en la que se resolvía una ecuación diferencial con un circuito electrónico compuesto principalmente por una parte electrónica llamada amplificador operacional. Es un dispositivo llamado computadora analógica, el origen del nombre no es solo porque usa circuitos electrónicos analógicos, sino también porque se basa en la analogía entre los dos. Esto se basa en el hecho de que la relación entre el problema de las ecuaciones diferenciales y el comportamiento de los circuitos electrónicos por los amplificadores operacionales es similar.
Utilizando este conocimiento, nos preguntamos si las computadoras que manejan de manera eficiente los problemas de optimización combinatoria podrían fabricarse sobre la base de la idea de las computadoras analógicas.
Describimos el problema de optimización combinatoria en el modelo de física estadística llamado modelo de Ising y realizamos la operación llamada recocido (o annealing), para encontrar la condición óptima. En lugar de resolver estas acciones con base en programas, estamos tratando de resolver estos comportamientos con el hardware de una estructura que imita el modelo de Ising.
El modelo de Ising es un modelo físico propuesto para estudiar el comportamiento de materiales ferromagnéticos. Se trata de un modelo paradigmático de la Mecánica Estadística, en parte porque fue uno de los primeros en aparecer, pero sobre todo porque es de los pocos modelos útiles que tiene solución analítica exacta (esto es, sin resultados aproximados).
El progreso más innovador en el campo de la investigación del recocido cuántico es su implementación de hardware, es decir, el llamado recocido cuántico que utiliza espines artificiales. Los annealers implementados en HW también son llamados máquinas de Ising.
Esta implementación HW se puede realizar de varias formas. Una de ellas es a partir de circuitos digitales expresamente diseñados para este propósito o circuitos CMOS, o circuitos realizados por medio de FPGAs. Se trata, en esencia de emular el funcionamiento de los átomos por medio de circuitos electrónicos digitales. El trabajo necesario para diseñar y fabricar este tipo de dispositivos, podría parecer a priori, un trabajo innecesario, pero los resultados indican lo contrario. Una máquina de Ising puede resolver un problema de optimización combinatoria 300 veces más rápido que con otros métodos.
Recocido cuántico (Quantum Annealing)
Ya estamos preparados para presentar el último concepto que habíamos previsto que es el del recocido cuántico o quantum annealing, y que nos ayudará a entender la clasificación de computadores cuánticos que veremos más adelante.
El recocido cuántico (QA) es el equivalente cuántico del recocido simulado empleando fluctuaciones cuánticas. En este caso se tiene en cuenta el efecto túnel, presente en las fluctuaciones cuánticas, para aproximarse al mínimo global de energía. El recocido cuántico se utiliza principalmente en problemas en los que el espacio de búsqueda es discreto (problemas de optimización combinatoria), con muchos mínimos locales; como en el caso del problema del viajante.
Curiosidad: El término quantum annealing o annealing a secas, se ha traducido en algunas referencias como “Temple cuántico” o “Temple”, pero su traducción correcta sería “Recocido” porque se ajusta a su equivalente en la metalurgia, que es el que ha inspirado este concepto y le ha dado su nombre, es decir primero calentar el material por debajo de su temperatura crítica y luego enfriarlo lentamente con el propósito de alterar sus propiedades físicas. En el temple (en inglés tempering), la segunda parte del proceso es a la inversa, es decir, el material se enfría rápidamente y no lentamente.
En algunas referencias podemos encontrar el término Adiabatic Quantum Computation (ó AQC). Quantum Annealing y Adiabatic Quantum Computation están estrechamente relacionados. Son formas de computación cuántica similares que se basan en el teorema adiabático para realizar cálculos.
Teorema adiabático: Un sistema mecano cuántico sujeto a condiciones externas que cambian gradualmente, puede adaptar su forma, y por tanto permanece en un estado que le es propio, durante todo el proceso adiabático (o cuasiestático). El término “adiabático” no es el mismo que se usa en termodinámica (un proceso adiabático en termodinámica es aquel en el que no hay intercambio de calor entre el sistema y su ambiente), más bien la definición mecánico-cuántica está más relacionada con el concepto de proceso cuasiestático de termodinámica, es decir que el proceso se hace con suficiente lentitud que cada una de sus partes permanece en equilibrio.
La ventaja principal de este tipo de computación cuántica es que está sujeta a menos complejidad técnica que la basada en puertas y, aunque se limite a un tipo muy específico de problemas, puede resolverlos con menor índice de errores. Por contra es necesario formular el problema de una forma muy determinada (modelo de Ising o QUBO), antes de enviarlo al computador cuántico en sí. Este trabajo de descripción físico/matemática del problema es la parte más complicada. Una vez hecha, el computador cuántico (o máquina de Ising en caso de annealing digital), puede encontrar los mínimos de la función objetivo, es decir la solución al problema, en cuestión de minutos o segundos.
Esta tecnología cuántica, la computación adiabática, se podría decir que es un paso intermedio entre el computador clásico digital y el cuántico universal. La empresa canadiense D-Wave lleva fabricando (y comercializando) este tipo de computadores cuánticos desde el 2010, ya hace más de una década y muchos son los que han usado esta tecnología para explorar y desarrollar tecnologías cuánticas generalistas. Algunos de los primeros clientes de D-Wave incluyen a compañías tan relevantes como Google, la NASA o Lockheed Martin.
Por su parte FUJITSU ha conseguido desarrollar una máquina de Ising, llamada Digital Annealer que permite resolver problemas de optimización combinatoria, a través de un servicio perimetral (Edge) o en la Nube. A través de este servicio permite realizar casos de uso empresariales o industriales, reales, para sus clientes.
Pero, no nos adelantemos…
En el siguiente artículo, y penúltimo de esta serie introductoria a la computación cuántica, “|QC-6> La mesa está puesta”, exploraremos los diferentes tipos de computadores cuánticos existentes en la actualidad y sus principales fabricantes.
Artículos de esta serie:
