Optimización con QAOA

En este tutorial, exploraremos cómo usar el Algoritmo de Optimización Aproximada Cuántica (QAOA) para resolver un problema de optimización simple usando QiliSDK.

Nota

Si aún no lo has hecho, puede ser útil revisar primero estos tutoriales: Quantum Basics, Quantum Circuits y Quantum Annealing.

El Problema

Supongamos que tenemos cuatro personas y necesitamos formar dos equipos de dos personas cada uno. Tenemos información sobre lo bien que trabajan juntos cada par de personas, y queremos formar los equipos de modo que la «compatibilidad» total de los equipos sea máxima. La información sobre quién se lleva bien con quién es la siguiente:

Alice

Bob

Carol

Dave

Alice

N/A

1

3

4

Bob

1

N/A

5

2

Carol

3

5

N/A

6

Dave

4

2

6

N/A

Esto significa que Alice preferiría trabajar con Dave, mientras que Bob preferiría trabajar con Carol, y así sucesivamente.

Matemáticamente, podemos representar nuestros dos equipos como variables binarias, donde \(x_i\) es 0 si la persona \(i\) está en el equipo 0, y 1 si está en el equipo 1. La compatibilidad del equipo 0 puede expresarse entonces como:

\[C_0 = \sum_{i=0,j=0}^3 p_{ij} (1 - x_i) (1 - x_j)\]

Donde \(p_{ij}\) es la puntuación de compatibilidad entre la persona \(i\) y la persona \(j\). Nótese que aquí cada término solo es distinto de cero si tanto \(x_i\) como \(x_j\) son 0, lo que significa que ambas personas están en el equipo 0. Mientras tanto, la compatibilidad del equipo 1 puede expresarse como:

\[C_1 = \sum_{i=0,j=0}^3 p_{ij} x_i x_j\]

Por lo tanto, queremos maximizar la compatibilidad total \(C = C_0 + C_1\), sujeto a la restricción de que el equipo 1 (y por tanto el equipo 0) tenga exactamente dos personas:

\[\max_{x_i \in \{0, 1\}} C\]
\[\text{sujeto a} \quad x_{Alice} + x_{Bob} + x_{Carol} + x_{Dave} = 2\]

Un problema con esta formulación es que tiene una restricción, lo que la hace más difícil de resolver usando algoritmos de optimización cuántica. Para solucionar esto, podemos usar algunas técnicas para convertirla en un problema QUBO (Optimización Binaria Cuadrática Sin Restricciones). En este caso, dado que solo tenemos una restricción de igualdad, podemos añadir una versión al cuadrado de esta a la función objetivo como término de penalización, de modo que el término de penalización sea cero cuando se satisface la restricción y positivo en caso contrario. Para más detalles sobre este proceso, consulta la referencia QUBO. Ahora podemos asumir que el problema se ha reformulado en el siguiente problema de optimización sin restricciones:

\[\min_{x_i \in \{0, 1\}} \sum_{i=0,j=0}^4 c_{ij} x_i x_j\]

Donde \(c_{ij}\) son coeficientes que codifican la función objetivo así como la restricción.

La Solución

Ahora que tenemos nuestro problema formulado como un QUBO, podemos usar QAOA para encontrar una solución aproximada. QAOA es un algoritmo híbrido cuántico-clásico que utiliza un circuito cuántico parametrizado para encontrar soluciones aproximadas a problemas de optimización combinatoria. Funciona alternando entre la aplicación de un Hamiltoniano del problema (que codifica el problema de optimización) y un Hamiltoniano de mezcla (que ayuda a explorar el espacio de soluciones), con los parámetros del circuito siendo optimizados mediante un algoritmo de optimización clásico. Piénsalo como hacer recocido cuántico, excepto que es una versión digital que alterna entre Hamiltonianos, en lugar de un algoritmo analógico que evoluciona un Hamiltoniano genérico variable en el tiempo.

Asumiendo que hemos reformulado nuestro problema en un QUBO, podemos construir el Hamiltoniano del problema para QAOA, que viene dado por:

\[H_{prob} = \sum_{i,j} c_{ij} Z(i) Z(j)\]

Donde \(Z(i)\) es el operador de Pauli-Z que actúa sobre el cúbit \(i\), y \(c_{ij}\) son los coeficientes de nuestra formulación QUBO.

Nuestro Hamiltoniano de mezcla se elige típicamente como el Hamiltoniano de campo transverso, que viene dado por:

\[H_{mix} = - \sum_i X(i)\]

Dado que estos son Hamiltonianos (en lugar de puertas unitarias), necesitamos transformarlos en unitarios, lo cual está determinado por los parámetros de nuestro circuito:

\[U_{prob}(\gamma) = e^{-i \gamma H_{prob}}\]
\[U_{mix}(\beta) = e^{-i \beta H_{mix}}\]

Donde \(\gamma\) y \(\beta\) son los parámetros de nuestro circuito sobre los que optimizaremos.

A continuación, realizamos aplicaciones alternadas de estos unitarios, comenzando con el unitario de mezcla y terminando con el unitario del problema. También debemos comenzar en el estado fundamental del Hamiltoniano de mezcla, que en este caso es el estado de superposición uniforme. Como circuito, esto se ve de la siguiente manera:

../../_images/qaoa_circuit_light.svg ../../_images/qaoa_circuit_dark.svg

Aquí solo hemos realizado dos repeticiones, pero podríamos hacer más o menos dependiendo del problema.

Los parámetros \(\gamma\) y \(\beta\) se optimizan entonces mediante un algoritmo de optimización clásico, con el objetivo de minimizar el valor esperado del Hamiltoniano del problema. Esto significa que ejecutamos el circuito cuántico, medimos la salida y luego usamos los resultados para ajustar los parámetros y obtener una mejor solución.

La Implementación

In QiliSDK, a variety of classes are available to help streamline the implementation. Starting with the problem Hamiltonian, we can use the QUBO class to represent our QUBO problem, and then use the QAOA class to construct the QAOA circuit and perform the optimization.

Para crear nuestro modelo:

from qilisdk.core.model import QUBO, ObjectiveSense
from qilisdk.core.variables import BinaryVariable, EQ

num_people = 4
vars = [BinaryVariable(f"x{i}") for i in range(num_people)]
preferences = [[0, 1, 3, 4],
              [1, 0, 5, 2],
              [3, 5, 0, 6],
              [4, 2, 6, 0]]

model = QUBO("team_formation_example")

team_1 = sum(
    preferences[i][j] * vars[i] * vars[j]
    for i in range(num_people)
    for j in range(i+1, num_people)
)

team_0 = sum(
    preferences[i][j] * (1 - vars[i]) * (1 - vars[j])
    for i in range(num_people)
    for j in range(i+1, num_people)
)

model.set_objective(
    team_0 + team_1,
    label="obj",
    sense=ObjectiveSense.MAXIMIZE
)

model.add_constraint(
    "team_size_constraint",
    EQ(sum(vars[i] for i in range(num_people)), 2),
    lagrange_multiplier=10
)

Luego usamos el modelo para formar nuestro ansatz QAOA (el circuito que vamos a optimizar):

from qilisdk.digital import QAOA

problem_hamiltonian = model.to_hamiltonian()
ansatz = QAOA(
    problem_hamiltonian=problem_hamiltonian,
    layers=2,
)

A continuación, construimos un problema variacional (combinando un optimizador clásico y un circuito cuántico) y lo simulamos:

from qilisdk.functionals.variational_program import VariationalProgram
from qilisdk.functionals import DigitalPropagation
from qilisdk.optimizers.scipy_optimizer import SciPyOptimizer
from qilisdk.cost_functions.observable_cost_function import ObservableCostFunction
from qilisdk.readout import Readout
from qilisdk.backends import QiliSim

vqa = VariationalProgram(functional=DigitalPropagation(ansatz),
                        optimizer=SciPyOptimizer(method="cobyla", tol=1e-7),
                        cost_function=ObservableCostFunction(problem_hamiltonian))

backend = QiliSim()
result = backend.execute(vqa, readout=Readout().with_sampling(nshots=1000))
print("VQA Result:", result)

Esto da algo parecido al siguiente resultado:

samples={
    '0000': 8,
    '0001': 31,
    '0010': 11,
    '0011': 42,
    '0100': 13,
    '0101': 200,
    '0110': 226,
    '0111': 18,
    '1000': 16,
    '1001': 173,
    '1010': 131,
    '1011': 2,
    '1100': 56,
    '1101': 18,
    '1110': 16,
    '1111': 39
}

Como puedes ver en estos resultados, las muestras más comunes son aquellas que satisfacen la restricción (es decir, tienen exactamente dos 1’s), y entre ellas, las más comunes son las que tienen un valor objetivo alto.

Lectura Adicional