Optimització amb QAOA

En aquest tutorial, explorarem com usar l’Algorisme d’Optimització Aproximada Quàntica (QAOA) 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 QAOA per trobar una solució aproximada. QAOA és un algorisme híbrid quàntic-clàssic que utilitza un circuit quàntic parametritzat per trobar solucions aproximades a problemes d’optimització combinatòria. Funciona alternant entre l’aplicació d’un Hamiltonià del problema (que codifica el problema d’optimització) i un Hamiltonià de barreja (que ajuda a explorar l’espai de solucions), amb els paràmetres del circuit sent optimitzats mitjançant un algorisme d’optimització clàssic. Penseu-hi com fer recuita quàntica, excepte que és una versió digital que alterna entre Hamiltonians, en lloc d’un algorisme analògic que evoluciona un Hamiltonià genèric variable en el temps.

Assumint que hem reformulat el nostre problema en un QUBO, podem construir el Hamiltonià del problema per a QAOA, que ve donat per:

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

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.

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)\]

Com que aquests són Hamiltonians (en lloc de portes unitàries), necessitem transformar-los en unitaris, la qual cosa està determinada pels paràmetres del nostre circuit:

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

On \(\gamma\) i \(\beta\) són els paràmetres del nostre circuit sobre els quals optimitzarem.

A continuació, fem aplicacions alternades d’aquests unitaris, començant amb el unitari de barreja i acabant amb el unitari del problema. També hem de començar en l’estat fonamental del Hamiltonià de barreja, que en aquest cas és l’estat de superposició uniforme. Com a circuit, això té l’aspecte següent:

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

Aquí només hem fet dues repeticions, però podríem fer-ne més o menys depenent del problema.

Els paràmetres \(\gamma\) i \(\beta\) s’optimitzen llavors mitjançant un algorisme d’optimització clàssic, amb l’objectiu de minimitzar el valor esperat del Hamiltonià del problema. Això significa que executem el circuit quàntic, mesurem la sortida i després usem els resultats per ajustar els paràmetres i obtenir una millor solució.

La Implementació

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.

Per crear el nostre model:

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 ansatz QAOA (el circuit que anem a optimitzar):

from qilisdk.digital import QAOA

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

A continuació, construïm un problema variacional (combinant un optimitzador clàssic i un circuit quàntic) i el simulem:

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)

Això dona quelcom semblant al resultat següent:

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
}

Com podeu veure d’aquests resultats, les mostres més comunes són aquelles que satisfan la restricció (és a dir, tenen exactament dos 1’s), i entre elles, les més comunes són les que tenen un valor objectiu alt.

Lectura Addicional