Optimització amb Recuita Quàntica

En aquest tutorial, explorarem com usar la Recuita Quàntica per resoldre un problema d’optimització simple usant QiliSDK.

Nota

Si encara no ho heu fet, pot ser útil consultar primer aquests tutorials: Quantum Basics, Quantum Circuits i Quantum Annealing.

El Problema

Suposem que tenim quatre persones i necessitem formar dos equips de dues persones cadascun. Tenim informació sobre com de bé treballen juntes cada parella de persones, i volem formar els equips de manera que la «compatibilitat» total dels equips sigui màxima. La informació sobre qui s’entén amb qui és la següent:

	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

Això significa que Alice preferiria treballar amb Dave, mentre que Bob preferiria treballar amb Carol, i així successivament.

Matemàticament, podem representar els nostres dos equips com a variables binàries, on \(x_i\) és 0 si la persona \(i\) està a l’equip 0, i 1 si està a l’equip 1. La compatibilitat de l’equip 0 es pot expressar llavors com:

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

On \(p_{ij}\) és la puntuació de compatibilitat entre la persona \(i\) i la persona \(j\). Cal observar que aquí cada terme només és diferent de zero si tant \(x_i\) com \(x_j\) són 0, la qual cosa significa que les dues persones estan a l’equip 0. Mentrestant, la compatibilitat de l’equip 1 es pot expressar com:

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

Per tant, volem maximitzar la compatibilitat total \(C = C_0 + C_1\), subjecte a la restricció que l’equip 1 (i per tant l’equip 0) tingui exactament dues persones:

\[\max_{x_i \in \{0, 1\}} C\]

\[\text{subjecte a} \quad x_{Alice} + x_{Bob} + x_{Carol} + x_{Dave} = 2\]

Un problema amb aquesta formulació és que té una restricció, la qual cosa la fa més difícil de resoldre usant algorismes d’optimització quàntica. Per solucionar això, podem usar algunes tècniques per convertir-la en un problema QUBO (Optimització Binària Quadràtica Sense Restriccions). En aquest cas, com que només tenim una restricció d’igualtat, podem afegir una versió al quadrat d’aquesta a la funció objectiu com a terme de penalització, de manera que el terme de penalització sigui zero quan es satisfà la restricció i positiu en cas contrari. Per a més detalls sobre aquest procés, consulteu la referència QUBO. Ara podem assumir que el problema s’ha reformulat en el següent problema d’optimització sense restriccions:

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

On \(c_{ij}\) són coeficients que codifiquen la funció objectiu així com la restricció.

La Solució

Ara que tenim el nostre problema formulat com un QUBO, podem usar la recuita quàntica per trobar una solució aproximada. La recuita quàntica és un algorisme d’optimització metaheurístic inspirat en el procés de recuita en metal·lúrgia, on un material s’escalfa i després es refreda lentament per eliminar defectes i trobar un estat de baixa energia. En la recuita quàntica, comencem amb un Hamiltonià simple el qual l’estat fonamental és fàcil de preparar i després l’evolucionem lentament cap a un Hamiltonià més complex que codifica el problema d’optimització que volem resoldre. L’esperança és que si fem això amb prou lentitud, el sistema romandrà en el seu estat fonamental durant tota l’evolució i així acabarà en l’estat fonamental del Hamiltonià final, que correspon a la solució òptima del nostre problema.

Assuming we have reformulated our problem into a QUBO, we can construct the problem Hamiltonian for quantum annealing, which is in the form:

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

Where \(Z(i)\) is the Pauli-Z operator acting on qubit \(i\), and \(c_{ij}\) are the coefficients from our QUBO formulation. Note that these variables \(Z(i)\) are related to the binary variables in our original problem by the transformation \(x_i = (1 - Z(i))/2\),

El nostre Hamiltonià de barreja s’escull típicament com el Hamiltonià de camp transversal, que ve donat per:

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

El Hamiltonià dependent del temps que evolucionem ve donat llavors per:

\[H(t) = A(t) H_{mix} + B(t) H_{prob}\]

On \(A(t)\) i \(B(t)\) són funcions que determinen com interpolem entre el Hamiltonià de barreja i el Hamiltonià del problema al llarg del temps. Per simplicitat, aquí assumirem que fem una interpolació lineal, de manera que \(A(t) = 1 - t/T\) i \(B(t) = t/T\), on \(T\) és el temps total de recuita.

La Implementació

Per simular l’evolució d’aquest Hamiltonià dependent del temps, primer necessitem formular el nostre problema:

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
)

Després usem el model per formar el nostre Hamiltonià del problema, i també podem definir el nostre Hamiltonià de barreja i l’esquema de la nostra evolució:

from qilisdk.analog import X
from qilisdk.analog import Schedule
from qilisdk.core import QTensor

problem_hamiltonian = model.to_hamiltonian()
mixer_hamiltonian = sum(-1.0 * X(i) for i in range(num_people))

We also need to define the schedule - how the coefficients of the problem and mixing Hamiltonians change over time. In this case we’ll just use a simple linear mixing:

schedule = Schedule.linear(mixer_hamiltonian, problem_hamiltonian, total_time=100.0, dt=0.1)

Començarem en l’estat fonamental del nostre Hamiltonià de barreja, que és l’estat de superposició uniforme sobre totes les assignacions possibles d’equips:

initial_state = QTensor.uniform(num_people)

Finalment, inicialitzem el nostre simulador quàntic, executem l’evolució i llegim els resultats:

from qilisdk.functionals import AnalogEvolution
from qilisdk.readout import Readout
from qilisdk.backends import QiliSim

backend = QiliSim()
evolution = AnalogEvolution(schedule=schedule, initial_state=initial_state)
readout = Readout().with_sampling(1000).with_expectation([problem_hamiltonian])
results = backend.execute(evolution, readout)
print("Results:", results)

Això imprimirà quelcom semblant a lo següent:

Functional Results: [

    Sampling Results: (
            nshots=1000,
            samples={'0110': 513, '1001': 487}
    )

    Expectation Value Results: (
            expectation_values=[-8.999696720325046],
    )

]

As you can see from these results, the samples satisfy the constraint (i.e. have exactly two 1’s). More specifically, the two samples «0110» and «1001» (corresponding to Alice/Dave on a team and Bob/Carol on the other team) are the optimal solutions to our problem, with 9 being the highest obtainable compatibility score.

Lectura Addicional

• QUBO

• Quantum Annealing