El arte de Minor Embedding: Entendiendo su impacto y potencial en el mundo cuántico
Sumérgete en la apasionante técnica de Minor Embedding y cómo está redefiniendo las fronteras de la computación cuántica, soluciones más óptimas y coherencias para desafíos complejos
La computación cuántica nos ha permitido desarrollar proyectos increíbles, los cuales hace unos años atrás no serían posibles por las limitaciones de las computadoras clásicas. Hoy en día, la tecnología de Quantum Annealing se está volviendo muy requerida para resolver problemas de optimización. En el corazón de esta revolución tecnológica, encontramos Minor Embedding, una técnica crucial que ha sido fundamental para superar algunas de las limitaciones inherentes a la tecnología cuántica.
Minor Embedding es un enfoque que permite mapear un grafo del problema original a un grafo compatible con el hardware cuántico. Esto es especialmente relevante en problemas del Modelo Cuadrático Binario (BQM, por sus siglas en inglés), que son comunes en problemas de optimización. La razón por la cual Minor Embedding es esencial en este contexto radica en que, en muchas ocasiones, las funciones objetivo de estos problemas no pueden ser representadas directamente en una computadora cuántica, debido a restricciones topológicas en su arquitectura, como la limitada conectividad entre qubits. Al aplicar esta técnica, se pueden superar estas limitaciones, y al mismo tiempo, corrigiendo la coherencia de los resultados, mejorando así la calidad y precisión de los resultados obtenidos en la optimización.
Para ilustrar cómo funciona Minor Embedding en un contexto detallado, utilicemos la siguiente función objetivo o también llamado función de coste:
Cabe recalcar que estamos tratando de resolver un problema con variables binarias. Esta función de 3 variables también puede ser representada en una gráfica triangular, como se muestra a continuación:
Esta forma gráfica de representar las funciones nos permite dar una idea de cuándo necesitamos utilizar Minor Embedding. Esto se debe a que para implementar de manera correcta la función objetivo, este mismo gráfico cerrado debe de coincidir con los grafos que posee la topología de la QPU de la computadora cuántica. Para este ejemplo utilizaremos la topología Chimera de la QPU de la computadora cuántica 2000Q. A continuación, se muestra su topología:
Como podemos observar no hay forma de implementar la representación gráfica de la función objetivo. Es decir, no podemos tener un lazo cerrado de 3 nodos, las cuales representan las 3 variables de nuestro ejemplo en la topología Chimera. Para solucionar este inconveniente es necesario utilizar un nodo más para tener un lazo cerrado. Es ahí donde tenemos que aplicar Minor Embedding. Para ello tenemos que indicar cuales 2 nodos representarán una sola variable. Por ejemplo, podemos indicar que los nodos 0 y 4 representarán la variable “a”, el nodo 1 representará la variable “b” y el nodo 5 representará la variable “c”. El siguiente paso es reestructurar la representación gráfica de la función objetivo de la siguiente manera:
El siguiente paso es hallar los nuevos valores para la nueva representación gráfica del ejemplo que estamos utilizando. Los valores que teníamos anteriormente se mantienen, lo que tendremos que hallar ahora es el valor de la arista que une el nodo 0 y 4 y cuánto sería el valor de esos mismos nodos. Para ello se siguen los siguientes pasos:
Paso 1:
Se tiene que dividir de manera proporcional el valor del nodo “a” inicial con los nuevos nodos 0 y 4. En este caso el valor del nodo 0 y 4 tomarán un valor de -1/2 = -0.5 .
Paso 2:
Ahora tenemos que hallar el valor de la cadena, el cual es la arista que une los nodos 0 y 4. Este valor tiene que ser negativo y debe de ser un valor adecuado para que al momento de implementar el ejercicio se interprete que estos 2 nodos representan una sola variable. Si no se tiene un valor óptimo, se tendrá una ruptura de cadena, es decir no se reconocerá el nodo 0 y 4 como una sola variable y no se tendrán resultados coherentes. No hay un método exacto para hallar el mejor valor de cadena, sin embargo, se puede aproximar el valor que cumpla con el rango adecuado. Un primer paso podría ser aproximar su valor con el valor de las demás aristas. En este caso al tener que las demás aristas tienen un valor de 2, se puede probar con un valor de -2 para la cadena. En el caso de implementar el ejercicio y observar que ocurrió una ruptura de cadena, podemos ir aumentando o disminuyendo el valor poco a poco hasta encontrar un valor adecuado.
Paso 3:
El siguiente paso es compensar, de manera proporcional, el valor de cadena que hemos obtenido con el valor de los nodos 0 y 4. Para ello se divide el valor de la cadena entre 2 y luego se resta el resultado con los valores de cada nodo. Es decir, para el nodo 0 y 4 se tendrá un valor de -0.5-(-2/2) = 0.5 .
La nueva representación gráfica de nuestro ejemplo quedaría de la siguiente manera:
El siguiente paso es generar una nueva función objetivo con la nueva representación gráfica que hemos obtenido. Para ello tomaremos el nodo 0 como “a0” y el nodo 4 como “a1”, de lo cual obtenemos la siguiente función objetivo:
Ahora sí se podría implementar de manera correcta la nueva función objetivo. Cabe resaltar que debemos ignorar las soluciones en donde observemos que las variables “a0” y “a1” no tienen valores iguales, ya que estas están representando una sola variable. En el caso de querer observar de manera más rápida los mejores resultados, podemos agregar una restricción para penalizar las soluciones que contengan valores diferentes para las variables “a0” y “a1”. Para ello podemos utilizar la función “add_linear_equality_constraint” de la biblioteca “dimod” para agregar restricciones a nuestro modelo BQM.
Como hemos podido observar, Minor Embedding nos permite implementar de manera correcta las funciones objetivo que no presentan una cantidad adecuada de variables para ser representadas en la topología de la computadora cuántica. Sin embargo, realizar todo el procedimiento de manera manual podría ser un dolor de cabeza si es que se tiene una gran cantidad de variables. Por ello, D-Wave ha propuesto 3 opciones para implementar problemas BQM sin la necesidad de realizar Minor Embedding de manera manual.
Opción 1:
Como punto de partida para implementar un modelo BQM se puede utilizar la clase “EmbeddingComposite” de la biblioteca “dwave.system”. Es recomendable hacerlo cuando no se sabe sobre técnicas de Embedding para el problema y se desea que la clase automatice todo el proceso. La desventaja de automatizar todo el proceso es que se utiliza más recursos computacionales cada vez que se implemente algún modelo BQM. Además, no se podría añadir alguna corrección si es que el problema nos da algún valor que no tiene coherencia, el cual podría ser producto de una ruptura de cadena.
Opción 2:
Este segundo método para implementar un BQM es casi automatizado, ya que se tendrá que indicar algunos parámetros como el valor de cadena. Para este método utilizaremos la clase “LazyFixedEmbeddingComposite” de la biblioteca “dwave.system.composites”. Esta clase nos permite automatizar casi por completo el Embedding, ya que nos permitirá ingresar solo algunos parámetros necesarios.
Como sabemos, no hay un método exacto para hallar un valor de cadena adecuado. Sin embargo, D-Wave nos brinda 2 funciones para tener un valor referencial según nuestro modelo BQM. Estas funciones son “uniform_torque_compensation” y “scaled” de la biblioteca “dwave.embedding.chain_strength”. Estas funciones nos darán un punto de partida para el valor de cadena, ya que, si observamos que nuestra implementación está presentando una ruptura de cadena, podemos probar un valor distinto, pero cercano al valor inicial que hallamos con dichas funciones. Para saber si nuestra implementación presenta una ruptura de cadena, debemos de observar la columna del “chain” en los resultados que nos brinda la computadora cuántica. Todos los valores de la columna “chain” deben ser igual a 0. Si observamos un valor distinto de cero, quiere decir que la implementación de nuestro BQM está presentando una ruptura de cadena.
Opción 3:
La clase “ FixedEmbeddingComposite ” de la biblioteca “dwave.system”nos permite implementar un BQM indicando un Embedding fijo. Es decir, seremos nosotros quienes indiquemos qué variables estarán asociadas a los nodos de la topología de la computadora cuántica. Este método de implementación es útil cuando se desea realizar un Embedding específico. Esto podría ahorrar recursos y tiempo, ya que no se busca constantemente el Embedding cada vez que se implemente el modelo BQM en la computadora cuántica. Además, se podrá trabajar más a detalle y corregir errores más rápidos, ya que nosotros realizaremos todo el proceso de manera manual indicando los nodos que representarán las variables, indicando el valor de cadena, etc. A continuación, se muestra un ejemplo donde se indica que los nodos 0 y 1 representarán la variable “a”, el nodo 4 representa la variable “b” y el nodo 5 representa la variable “c”:
Estas 3 opciones nos permitirán implementar un modelo BQM utilizando la técnica de Minor Embedding. Se recomienda empezar con la opción 1 si es que no se conoce a detalle el Embedding que se podría aplicar al modelo BQM que deseamos implementar. La opción 2 sería la ideal si deseamos implementar un método algo más detallado o para corregir errores si es que es necesario. Finalmente, la opción 3 sería ideal cuando ya se tiene un estudio previo del modelo que se desea implementar. Además, esta opción nos permitirá ahorrar recursos si es que la aplicación lo amerita.
Como podemos observar Minor Embedding es una técnica fundamental en la computación cuántica. Actualmente, se está explorando cómo la inteligencia artificial y el aprendizaje automático pueden ser aplicados para generar embeddings con parámetros óptimos. Estos avances podrían conducir a soluciones más efectivas y de mayor impacto en la resolución de problemas de optimización.
En resumen, Minor Embedding es una técnica poderosa y esencial para Quantum Annealing, especialmente cuando se abordan problemas BQM y se enfrentan a restricciones topológicas. Al mejorar nuestra comprensión y habilidades en este campo, podemos desbloquear un potencial en la búsqueda de soluciones de problemas de optimización.
