1. Introducción.#
En este apartado se va a abordar un enfoque especial de optimización de funciones basado enla computación cuántica, hoy en día en proceso de madurez pero con grandes esperanzas de cara al futuro para poder resolver con ellas problemas presentes hoy en día con la computación tipo bit existente.
Existen diferentes enfoque de implementación de la computación cuántica, liderando estos enfoques diversas empresas punteras en la matería.
En este sentido, el modelo de circuitos cuánticos es el que está recibiendo más atención por parte de diversas empresas como IBM, Google o Riggeti para construir un computador cuántico capaz de resolver problemas con aplicación real.
Estos computadores están basados en puertas cuánticas, similares a las puertas lógicas que se usan en la computación tradicional, pero que en vez de usar lógica booleana, manipulan los estados de superposición de los cúbits que pasan por esas puertas.
Sin embargo, el computador que se va a utilizar en este trabajo utiliza otro paradigma, el llamado quantum anneling (recocido cuántico) o computación adiabática cuántica.
Antes de hablar de este paradigma de computación, hay que entender algunos conceptos básicos como por ejemplo el cúbit que es la unidad mínima de información en este tipo de máquinas, y sus propiedades, que son las que brindan a estas máquinas su capacidad masiva de computación.
1.1. El qubit.#
En la informática tradicional, un bit es la unidad mínima de información. Los bits tienen dos estados: el 0 y el 1. Estos estados vienen representados por distintos niveles de voltaje.
En informática cuántica, los qúbits, al igual que los bits tienen dos estados (los cuales pueden ser tomados con probabilidades ciertas probabilidades); pero estos se representan con propiedades cuánticas tales como el “spin” de una partícula o el campo magnético de un superconductor en temperaturas cercanas al cero absoluto. Sin embargo, los cúbits al estar representados con estos fenómenos, la información que codificamos en ellos goza de propiedades cuánticas como la superposición y el entrelazamiento.
La superposición es el fenómeno por el cual un cúbit está en un estado indeterminado de sus dos estados básicos. Este estado se puede describir como la combinación lineal de sus estados básicos. Matemáticamente se describe así :
Los coeficientes a y b son las denominadas amplitudes de probabilidad. Para saber con cuanta probabilidad se medirá cada estado en el cúbit, se obtiene el cuadrado de cada término. De esta manera, \(a^2\) es la probabilidad de medir el estado \(|0 \rangle\) (más bien que colapse hacia el estado \(|0\rangle\)) en el cúbit y \(b^2\) la probabilidad de medir \(|1\rangle\).
Como es evidente, ambos valores tienen que obedecer la expresión \(a^2 +b^2 = 1\). Esto es así porque la suma de la probabilidad de todos los sucesos posibles debe ser exactamente igual a 1. De esta forma, se puede definir el cúbit que tiene el 50% de medir \(|0\rangle\) y 50% de medir \(|1\rangle\) sería \(\frac{1}{\sqrt{2}}|0\rangle +\frac{1}.{\sqrt{2}}|1\rangle \)
Un sistema de mútiples cubits, supongamos 2 cubits similares al de arriba descrito, se definiría como el producto tensorial de ambos cubits:
Pero para verlo de forma más clara se escribe con la siguiente notación donde se perciben todos los estados posibles del sistema:
Si en este sistema midiésemos el primer cúbit, recibiríamos \(|0\rangle\) o \(|1\rangle\) con la misma probabilidad. Después de esta acción, medir el segundo cúbit sería totalmente igual que en el cúbit anterior, recibiríamos un resultado aleatorio. En este sistema los cúbits son independientes y no se afectan los unos a los otros.
Usando la superposición de cúbits se pueden crear sistemas de N cúbits donde se representan \(2^N\) estados con los que operar todos a la vez. Es la superposición la que encierra la potencia de estas máquinas.
El entrelazamiento es un caso particular de superposición entre objetos cuánticos. Supongamos el siguiente sistema:
En este caso los cúbits están entrelazados. Si midiésemos el primer cúbit, automáticamente determinaríamos el estado del cúbit siguiente.
Otra forma de saber si un sistema de cúbits están entrelazados es intentando factorizar el sistema en sus cúbits fundamentales. Es decir, si ese sistema es posible construirlo a través del producto tensorial entre cúbits. Si no es el caso, el sistema es un sistema entrelazado.
1.2. DWave.#
DWave es una empresa canadiense dedicada exclusivamente a la investigación y comercialización de computadores cuánticos. Al contrario que otras empresas, que intentan mediante puertas cuánticas lograr un computador cuántico general, DWave tras unos intentos poco exitosos, centró su investigación en este paradigma de computación adiabática. Tras esa decisión, la empresa ha conseguido grandes logros; como ofrecer al público el primer omputador cuántico de 7000 cúbits.
Esta empresa ha desarrollado un software denominado SDK (software development kit) que permite a los usuarios interactuar con los ordenadores de esa empresa (conocidos como QPUs, es decir quantum processing units) así como con los solvers híbridos, utilizando para ello programas escritos en python.
La api a utilizar para realizar estas tareas la podemos encontrar en este enlace .
1.3. Modelos soportados por Ocean.#
Como puede verse en la documentación que ofrece D-Wave Ocean, son soportados cuatro modelos básicos para expresar el problema a optimizar como una función objetivo y submitirlo para encontrar la solución buscada.
Binary Quadratic Models . Conocidos también por la iniciales BQM, y son modelos sin restricciones (aunque las restricciones se pueden añadir mediante funciones de penalización) construidos en base a variables binarias. Este tipo de modelos, tienen dos subcategorías: Modelos Ising ( cuyas variables binarias pueden tomar los valores -1 ó 1, y los modelos QUBO, cuyas variables pueden tomar los valores 0 ó 1).
Constrained Quadratic Models . Conocidos también con las iniciales CQM pueden tener restricciones y las variables pueden ser de tipo real (aunque en la actualidad este tipo de variables no están soportadas para interacciones cuadráticas), entero o binario.
Este tipo de modelos, son normalmente utilizados para aplicaciones sobre problemas de optimización que pueden incluir variables de tipo entero y/o binario así como una o más restricciones.
Discrete Quadratic Models . También conocidos por las siglas DQM de tal manera que no admiten restricciones ( por regla general estas restricciones se introducen mediante funciones de penalización).
NOTA. Ocean también ofrece soporte para los modelos denominados de orden superior y son modelos que no están restringidos a interacciones cuadráticas.