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:
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:
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:
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:
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.
Assumint que hem reformulat el nostre problema en un QUBO, podem construir el Hamiltonià del problema per a la recuita quàntica, que ve donat per:
On \(Z(i)\) és l’operador de Pauli-Z que actua sobre el qubit \(i\), i \(c_{ij}\) són els coeficients de la nostra formulació QUBO. Tingueu en compte que aquestes variables \(Z(i)\) estan relacionades amb les variables binàries del nostre problema original mitjançant la transformació \(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:
El Hamiltonià dependent del temps que evolucionem ve donat llavors per:
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.comparison import EQ
from qilisdk.core.variables import BinaryVariable
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))
També necessitem definir l’esquema: com canvien els coeficients dels Hamiltonians del problema i de barreja al llarg del temps. En aquest cas, simplement farem servir una barreja lineal senzilla:
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],
)
]
Com podeu veure d’aquests resultats, les mostres satisfan la restricció (és a dir, tenen exactament dos 1’s). Més concretament, les dues mostres «0110» i «1001» (corresponents a Alice/Dave en un equip i Bob/Carol en l’altre) són les solucions òptimes al nostre problema, amb 9 sent la puntuació de compatibilitat màxima assolible.
To help to visualize the evolution we just performed, we can re-run our simulation,
this time recording the full state at each timestep and then using
the Schedule.draw_eigenvalues() method
to plot how our state evolved versus the eigenvalues of the Hamiltonian over time:
evolution = AnalogEvolution(
schedule=schedule,
initial_state=initial_state,
store_intermediate_results=True
)
readout = Readout().with_state_tomography()
results = backend.execute(evolution, readout)
schedule.draw_eigenvalues(
intermediate_states=results.get_intermediate_states(),
show_overlaps=True
)
As we can see from this plot, the state started in the ground state of the mixing Hamiltonian (the bottom line, at the very left) and then evolved to the ground state of the problem Hamiltonian (at the very right). By moving slow enough we stayed in the ground state, with only a small percentage of our state leaking out to some of the excited states. A larger total time (and thus a slower evolution) would result in less state leaking out, at the cost of taking longer to run.