Codificarea Pauli prin corelație pentru reducerea cerințelor de tăiere maximă

Estimare de utilizare: 35 de minute pe un procesor Eagle r3 (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Rezultate de învățare

• Înțelegerea principiilor teoretice din spatele Codificării Pauli prin Corelație (PCE), inclusiv modul în care șirurile Pauli multi-corp permit compresia polinomială a problemelor de optimizare clasice.

• Implementarea PCE în practică pentru a codifica și rezolva sarcini de optimizare la scară largă pe hardware cuantic de tip near-term.

Precondiții

• Algoritmi cuantici variționali

• QAOA și tăierea maximă

Fundal

Acest tutorial prezintă Codificarea Pauli prin Corelație (PCE) [1], o abordare concepută pentru a codifica probleme de optimizare în qubiți cu o eficiență mai mare pentru calculul cuantic. PCE mapează variabile clasice din problemele de optimizare la corelații multi-corp ale matricelor Pauli, rezultând o compresie polinomială a cerințelor de spațiu ale problemei. Prin utilizarea PCE, numărul de qubiți necesari pentru codificare este redus, ceea ce îl face deosebit de avantajos pentru dispozitivele cuantice pe termen scurt cu resurse limitate de qubiți. Mai mult, se demonstrează analitic că PCE atenuează în mod inerent platouri sterpe (barren plateaus), oferind reziliență super-polinomială față de acest fenomen. Această caracteristică integrată permite o performanță fără precedent în solvoarele de optimizare cuantică.

Prezentare generală

Abordarea PCE constă în trei pași principali, ilustrați în Figura 1 din [1] de mai jos:

1. Codificarea problemei de optimizare într-un spațiu de corelație Pauli.
2. Rezolvarea problemei folosind un solver de optimizare cuantico-clasic.
3. Decodificarea soluției înapoi în spațiul original de optimizare. Abordarea PCE este adaptabilă oricărui solver de optimizare cuantică capabil să proceseze matrici de corelație Pauli. În Figura 1 din [1], problema tăierii maxime este folosită ca exemplu pentru a ilustra abordarea PCE. Problema tăierii maxime cu $m=9$ noduri este codificată într-un spațiu de corelație Pauli, reprezentând problema de optimizare ca o matrice de corelație — mai precis corelații de două corpuri ale matricelor Pauli pe $n=3$ qubiți $(Q_1, Q_2, Q_3)$. Culorile nodurilor indică șirul Pauli utilizat pentru fiecare nod codificat. De exemplu, nodul 1, care corespunde variabilei binare $x_1$, este codificat prin valoarea de așteptare a lui $Z_1 \otimes Z_2 \otimes I_3$, în timp ce $x_8$ este codificat de $I_1 \otimes Y_2 \otimes Y_3$. Aceasta corespunde comprimării celor $m$ variabile ale problemei în $n = O(m^{1/2})$ qubiți. Mai general, corelațiile $k$-corp permit compresii polinomiale de ordin $k$, cu $k>1$. Setul Pauli ales cuprinde trei subseturi de șiruri Pauli mutual comutative, permițând estimarea experimentală a tuturor celor $m$ corelații cu doar trei configurații de măsurare.

O funcție de pierdere $\mathcal{L}$ a valorilor de așteptare Pauli care imită funcția obiectiv originală de tăiere maximă este construită. Funcția de pierdere este apoi optimizată folosind un solver de optimizare cuantico-clasic, cum ar fi Variational Quantum Eigensolver (VQE).

Odată ce optimizarea este completă, soluția este decodificată înapoi în spațiul original de optimizare, obținând soluția optimă de tăiere maximă.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalat următoarele:

• Qiskit SDK v1.0 sau mai nou, cu suport pentru vizualizare
• Qiskit Runtime v0.22 sau mai nou (pip install qiskit-ibm-runtime)
• Addon-ul Qiskit Optimization Mapper (pip install qiskit-addon-opt-mapper)

Configurare

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"networkx": "networkx", "numpy": "numpy", "qiskit": "qiskit", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime", "rustworkx": "rustworkx", "scipy": "scipy"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

from itertools import combinations

import numpy as np
import rustworkx as rx
import networkx as nx

from scipy.optimize import minimize, OptimizeResult

from qiskit.circuit.library import efficient_su2
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit.quantum_info import SparsePauliOp
from qiskit_ibm_runtime import EstimatorV2 as Estimator
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Session
from rustworkx.visualization import mpl_draw
from qiskit_aer import AerSimulator

from qiskit_addon_opt_mapper.applications import Maxcut

def make_cut_evaluator(problem):
    """Return a function that maps a 0/1 node assignment to its cut value.

    The objective of the max-cut ``OptimizationProblem`` is the cut value
    itself, and ``problem.objective.evaluate`` computes it for one
    assignment. The swap search in Step 4 evaluates one candidate
    assignment per edge, so pull the objective's coefficients out once
    and evaluate them as a sparse matrix product instead.
    """
    quadratic = problem.objective.quadratic.coefficients.tocsr()
    linear = problem.objective.linear.to_array()
    constant = problem.objective.constant

    def evaluate_cut(bits):
        x = np.asarray(bits, dtype=float)
        return int(round(constant + linear @ x + x @ (quadratic @ x)))

    return evaluate_cut

Exemplu la scară mică cu simulator

service = QiskitRuntimeService()
real_backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=156
)
backend = AerSimulator.from_backend(real_backend)
print(f"We are using the {backend.name}")

We are using the aer_simulator_from(ibm_pittsburgh)

Pasul 1: Maparea intrărilor clasice la o problemă cuantică

Problema tăierii maxime

Problema tăierii maxime este o problemă de optimizare combinatorială definită pe un graf $G = (V, E)$, unde $V$ este mulțimea vârfurilor și $E$ este mulțimea muchiilor. Scopul este de a partiția vârfurile în două mulțimi, $S$ și $V \setminus S$, astfel încât numărul de muchii dintre cele două mulțimi să fie maximizat. Pentru o descriere detaliată a problemei tăierii maxime, consultă tutorialul Algoritmul de optimizare cuantică aproximativă. Problema tăierii maxime este folosită, de asemenea, ca exemplu în tutorialul Tehnici avansate pentru QAOA. În acele tutoriale, algoritmul QAOA este utilizat pentru a rezolva problema tăierii maxime.

Graf → problemă de optimizare

Să considerăm mai întâi un graf aleatoriu cu 100 de noduri.

num_nodes = 100  # Number of nodes in graph
seed = 42
graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)
mpl_draw(graph)

Modelează problema max-cut cu clasa de aplicație Maxcut din addon-ul Qiskit Optimization Mapper. Ea returnează o OptimizationProblem cu o variabilă binară pentru fiecare nod, al cărei obiectiv este valoarea tăieturii de maximizat. În tutorialele QAOA, această problemă este convertită într-un QUBO și tradusă într-un hamiltonian de cost cu un qubit pe variabilă. PCE codifică în schimb fiecare variabilă binară în semnul unei valori de așteptare Pauli, așa că aici problema definește și evaluează obiectivul, iar codificarea în qubiți urmează mai jos.

maxcut = Maxcut(graph)
maxcut_problem = maxcut.to_optimization_problem()
evaluate_cut = make_cut_evaluator(maxcut_problem)

print(f"Binary variables: {maxcut_problem.get_num_vars()}")
print(
    "Quadratic terms (one per edge):",
    len(maxcut_problem.objective.quadratic.to_dict()),
)

Binary variables: 100
Quadratic terms (one per edge): 508

nx_graph = nx.Graph()
nx_graph.add_nodes_from(range(num_nodes))

for edge in graph.edge_list():
    nx_graph.add_edge(edge[0], edge[1])

curr_cut_size, partition = nx.approximation.one_exchange(nx_graph, seed=1)
print(f"Initial cut size: {curr_cut_size}")

Initial cut size: 345

Codificăm graful cu 100 de noduri în corelații de două corpuri ale matricelor Pauli pe nouă qubiți (a se vedea explicația de mai jos). Graful este reprezentat ca o matrice de corelație, unde fiecare nod este codificat printr-un șir Pauli. Semnul valorii de așteptare a șirului Pauli indică partiția nodului. De exemplu, nodul 0 este codificat printr-un șir Pauli, $\prod_0 = I_{8} \otimes ... I_2 \otimes X_1 \otimes X_0$. Semnul valorii de așteptare a acestui șir Pauli indică partiția nodului 0. Definim o codificare Pauli prin corelație (PCE) relativ la $\prod$ ca

$x_i \coloneqq \textit{sgn}(\langle\prod_i \rangle),$

unde $x_i$ este partiția nodului $i$ și $\langle \prod_i \rangle \coloneqq \langle \psi |\prod_i| \psi \rangle$ este valoarea de așteptare a șirului Pauli care codifică nodul $i$ peste o stare cuantică $|\psi \rangle$. Acum, să codificăm graful într-un Hamiltonian folosind PCE. Împărțim nodurile în trei mulțimi: $S_1$, $S_2$, și $S_3$. Apoi, codificăm nodurile din fiecare mulțime folosind șirurile Pauli cu $X$, $Y$ și, respectiv, $Z$. Trebuie să extragem o relație între numărul de noduri și numărul de qubiți necesari pentru a codifica toate nodurile. Folosind toate permutările posibile pentru codificare, obținem:

$$m=3\binom{n}{k}.$$

În acest exemplu considerăm $k=2$, prin urmare,

$$m = \frac{3}{2} n(n-1).$$

Astfel, numărul de qubiți $n$ necesari pentru a exprima un anumit număr de noduri $m$ este:

$$n = \left\lceil \frac{1 + \sqrt{1 + \tfrac{8}{3}m}}{2} \right\rceil.$$

Observă că simbolul $\lceil \cdot \rceil$ reprezintă funcția plafon, care rotunjește orice număr real la cel mai mic întreg mai mare sau egal. Aceasta asigură că numărul de qubiți este un număr întreg.

num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))

list_size = num_nodes // 3
node_x = [i for i in range(list_size)]
node_y = [i for i in range(list_size, 2 * list_size)]
node_z = [i for i in range(2 * list_size, num_nodes)]

print(f"Number of qubits: {num_qubits}")
print("List 1:", node_x)
print("List 2:", node_y)
print("List 3:", node_z)

Number of qubits: 9
List 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
List 2: [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65]
List 3: [66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

def build_pauli_correlation_encoding(pauli, node_list, n, k=2):
    pauli_correlation_encoding = []
    for idx, c in enumerate(combinations(range(n), k)):
        if idx >= len(node_list):
            break
        paulis = ["I"] * n
        paulis[c[0]], paulis[c[1]] = pauli, pauli
        pauli_correlation_encoding.append(("".join(paulis)[::-1], 1))

    hamiltonian = []
    for pauli, weight in pauli_correlation_encoding:
        hamiltonian.append(SparsePauliOp.from_list([(pauli, weight)]))

    return hamiltonian

pauli_correlation_encoding_x = build_pauli_correlation_encoding(
    "X", node_x, num_qubits
)
pauli_correlation_encoding_y = build_pauli_correlation_encoding(
    "Y", node_y, num_qubits
)
pauli_correlation_encoding_z = build_pauli_correlation_encoding(
    "Z", node_z, num_qubits
)

Pasul 2: Optimizarea problemei pentru execuția pe hardware cuantic

Circuit cuantic

Aici, starea $|\psi \rangle$ este parametrizată cu $\mathbf{\theta}$, iar acești parametri $\mathbf{\theta}$ sunt optimizați folosind o abordare varațională. Acest tutorial folosește ansatz-ul efficient_su2 pentru algoritmul nostru variațional datorită capacităților sale expresive și ușurinței de implementare. Folosim, de asemenea, funcția de pierdere relaxată, care va fi introdusă mai târziu în acest tutorial. Ca rezultat, putem aborda probleme la scară largă cu mai puțini qubiți și adâncimi de circuit mai mici.

# Build the quantum circuit
qc = efficient_su2(num_qubits, su2_gates=["ry", "rz"], reps=2)
qc.draw("mpl")

# Optimize the circuit

pm = generate_preset_pass_manager(optimization_level=3, backend=backend)
qc = pm.run(qc)

Funcția de pierdere

Pentru funcția de pierdere $\mathcal{L}$, folosim o relaxare a funcției obiectiv de tăiere maximă descrisă în [1], care este definită ca $\mathcal{V}(\mathbf{x}) \coloneqq \sum_{(i, j) \in E} W_{i, j}(1-x_i x_j)$. Aici, $W_{i, j}$ denotă ponderea muchiei $(i, j)$, iar $x_i$ reprezintă partiția nodului $i$. Funcția de pierdere $\mathcal{L}$ este dată de:

$\mathcal{L}\coloneqq \sum_{(i, j) \in E} W_{i, j} \text{tanh} (\alpha \langle\prod_i \rangle) \text{tanh} (\alpha \langle\prod_j \rangle) + \mathcal{L}^{(\text{reg})}$,

unde funcția obiectiv de tăiere maximă este înlocuită de tangentele hiperbolice netede ale valorilor de așteptare ale șirurilor Pauli care codifică nodurile. Termenul de regularizare $\mathcal{L}^{(\text{reg})}$ și factorul de rescalare $\alpha$, proporțional cu numărul de qubiți, sunt introduși pentru a îmbunătăți performanța solverului.

Termenul de regularizare este definit ca:

$\mathcal{L}^{(\text{reg})}$ este definit ca $\mathcal{L}^{(\text{reg})} \coloneqq \beta \nu \lbrack \frac{1}{m} \sum_{i \in V} \text{tanh} (\alpha \langle\prod_i \rangle)^2 \rbrack ^2$

unde $\beta=1/2$, $\nu = |E|/2 + (m -1) /4$, $|E|$ este numărul de muchii, iar $m$ este numărul de noduri din graf.

def loss_func_estimator(x, ansatz, hamiltonian, estimator, graph):
    """
    Calculates the specified loss function for the given ansatz, Hamiltonian,
    and graph.

    The expectation values of each Pauli string in the Hamiltonian are first
    obtained by running the ansatz on the quantum backend. These
    expectation values are then passed through the nonlinear function
    tanh(alpha * prod_i). The loss function is
    subsequently computed from these transformed values.
    """
    job = estimator.run(
        [
            (ansatz, hamiltonian[0], x),
            (ansatz, hamiltonian[1], x),
            (ansatz, hamiltonian[2], x),
        ]
    )
    result = job.result()

    # calculate the loss function
    node_exp_map = {}
    idx = 0
    for r in result:
        for ev in r.data.evs:
            node_exp_map[idx] = ev
            idx += 1

    loss = 0
    alpha = num_qubits
    for edge0, edge1 in graph.edge_list():
        loss += np.tanh(alpha * node_exp_map[edge0]) * np.tanh(
            alpha * node_exp_map[edge1]
        )

    regulation_term = 0
    for i in range(len(graph.nodes())):
        regulation_term += np.tanh(alpha * node_exp_map[i]) ** 2
    regulation_term = regulation_term / len(graph.nodes())
    regulation_term = regulation_term**2
    beta = 1 / 2
    v = len(graph.edges()) / 2 + (len(graph.nodes()) - 1) / 4
    regulation_term = beta * v * regulation_term

    loss = loss + regulation_term

    global experiment_result
    print(f"Iter {len(experiment_result)}: {loss}")
    experiment_result.append({"loss": loss, "exp_map": node_exp_map})
    return loss

Pasul 3: Execuție folosind primitivele Qiskit

În acest tutorial, setăm max_iter=50 în bucla de optimizare în scop demonstrativ. Dacă mărim numărul de iterații, putem obține rezultate mai bune.

pce = []
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]
)
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]
)
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]
)

max_iter = 50
counter = {"i": 0}
last_x = {"value": None}
last_fun = {"value": None}

with Session(backend=backend) as session:
    estimator = Estimator(mode=session)

    experiment_result = []

    def loss_func(x):
        last_x["value"] = x.copy()
        if counter["i"] + 1 > max_iter:
            return last_fun["value"]
        counter["i"] += 1
        val = loss_func_estimator(
            x, qc, [pce[0], pce[1], pce[2]], estimator, graph
        )
        last_fun["value"] = val
        return val

    np.random.seed(seed)
    initial_params = np.random.rand(qc.num_parameters)

    result = minimize(
        loss_func, initial_params, method="COBYLA", options={"rhobeg": 1.0}
    )

    if counter["i"] >= max_iter:
        result = OptimizeResult(
            message=f"Return from COBYLA because the objective function "
            f"has been evaluated {max_iter} times.",
            success=False,
            status=3,
            fun=last_fun["value"],
            x=last_x["value"],
            nfev=counter["i"],
        )

print(result)

Iter 0: 152.06331779109445

Iter 1: 126.93132569244693

Iter 2: 55.00651109478942

Iter 3: 33.21667439735082

Iter 4: 19.167189700765054

Iter 5: 30.426875553389127

Iter 6: 13.906354614925815

Iter 7: 27.668686100172614

Iter 8: 28.194600411380772

Iter 9: 24.899677141564936

Iter 10: 22.10858041608358

Iter 11: 8.096210209030176

Iter 12: 8.761240650022913

Iter 13: 9.43332962472133

Iter 14: 7.559669820210062

Iter 15: 13.023860357384214

Iter 16: 11.953653163007987

Iter 17: 10.434221292269214

Iter 18: 4.871246922225549

Iter 19: 10.303826533395856

Iter 20: 16.40225843511339

Iter 21: 10.852469442638652

Iter 22: 9.314666066331633

Iter 23: 6.082358010011717

Iter 24: 10.982893700414476

Iter 25: 4.575556036893407

Iter 26: 6.844995727798197

Iter 27: 8.695229718011293

Iter 28: 3.730227705075576

Iter 29: 4.285479467758721

Iter 30: 4.219714169314187

Iter 31: 0.21125608131726548

Iter 32: 4.22820465672552

Iter 33: 13.67513152473414

Iter 34: 10.388838701884863

Iter 35: -0.5400153834163355

Iter 36: 5.310281742761159

Iter 37: -0.5430772019249082

Iter 38: -4.47820293096989

Iter 39: -3.4832056790567467

Iter 40: -0.5087341672330172

Iter 41: -2.488777859669888

Iter 42: 0.34945469121089356

Iter 43: -0.8544299675507805

Iter 44: -3.5902371208579344

Iter 45: 2.6609573847203216

Iter 46: -4.336467834641085

Iter 47: 0.10158504073828034

Iter 48: -1.3506458813942084

Iter 49: -2.1794894170194192

message: Return from COBYLA because the objective function has been evaluated 50 times.
 success: False
  status: 3
     fun: -2.1794894170194192
       x: [ 1.375e+00  1.951e+00 ...  9.395e-01  8.948e-01]
    nfev: 50

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

Partițiile nodurilor sunt determinate evaluând semnul valorilor de așteptare ale șirurilor Pauli care codifică nodurile. O valoare de așteptare nenegativă atribuie nodului valoarea 1, iar una negativă atribuie 0. Metoda interpret a lui Maxcut decodează apoi această atribuire în cele două mulțimi de noduri.

# Decode the node assignment from the iteration with the lowest loss.
# If the expectation value is non-negative, the node is assigned 1,
# otherwise it is assigned 0.
def get_bits(experiment_result):
    best_index = min(
        range(len(experiment_result)),
        key=lambda i: experiment_result[i]["loss"],
    )
    exp_map = experiment_result[best_index]["exp_map"]
    bits = [1 if exp_map[i] >= 0 else 0 for i in range(len(exp_map))]
    return bits, best_index

cur_bits, best_index = get_bits(experiment_result)
partition = maxcut.interpret(np.array(cur_bits))
print("Partition 0:", partition[0])
print("Partition 1:", partition[1])

Partition 0: [0, 1, 3, 5, 6, 7, 9, 11, 12, 14, 15, 17, 22, 24, 25, 28, 31, 32, 33, 35, 37, 38, 39, 40, 41, 43, 49, 53, 54, 56, 59, 61, 63, 65, 67, 68, 69, 77, 78, 79, 80, 88, 92, 93, 94, 95]
Partition 1: [2, 4, 8, 10, 13, 16, 18, 19, 20, 21, 23, 26, 27, 29, 30, 34, 36, 42, 44, 45, 46, 47, 48, 50, 51, 52, 55, 57, 58, 60, 62, 64, 66, 70, 71, 72, 73, 74, 75, 76, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 96, 97, 98, 99]

Putem calcula dimensiunea tăieturii pentru problema tăierii maxime evaluând obiectivul OptimizationProblem pe această atribuire.

cut_size = evaluate_cut(cur_bits)
print(f"Cut size: {cut_size}")

Cut size: 278

Odată ce antrenamentul este finalizat, efectuăm o rundă de căutare prin schimbul unui singur bit pentru a îmbunătăți soluția ca pas de post-procesare clasică. În acest proces, schimbăm partițiile a două noduri și evaluăm dimensiunea tăieturii. Dacă dimensiunea tăieturii se îmbunătățește, păstrăm schimbul. Repetăm acest proces pentru toate perechile posibile de noduri conectate printr-o muchie.

# Swap the partitions and calculate the cut size

def swap_partitions(graph, cur_bits, evaluate_cut):
    best_cut = 0
    best_bits = []
    for edge0, edge1 in graph.edge_list():
        swapped_bits = cur_bits.copy()
        swapped_bits[edge0], swapped_bits[edge1] = (
            swapped_bits[edge1],
            swapped_bits[edge0],
        )
        cut_size = evaluate_cut(swapped_bits)
        if best_cut < cut_size:
            best_cut = cut_size
            best_bits = swapped_bits
    return best_cut, best_bits

best_cut, best_bits = swap_partitions(graph, cur_bits, evaluate_cut)
print(best_cut, best_bits)

287 [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]

Exemplu la scară largă pe hardware real

# -------------------------Step 1-------------------------

num_nodes = 1500  # Number of nodes in graph
graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)
nx_graph = nx.Graph()
nx_graph.add_nodes_from(range(num_nodes))
for edge in graph.edge_list():
    nx_graph.add_edge(edge[0], edge[1])

maxcut = Maxcut(graph)
maxcut_problem = maxcut.to_optimization_problem()
evaluate_cut = make_cut_evaluator(maxcut_problem)

num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))

list_size = num_nodes // 3
node_x = [i for i in range(list_size)]
node_y = [i for i in range(list_size, 2 * list_size)]
node_z = [i for i in range(2 * list_size, num_nodes)]

pauli_correlation_encoding_x = build_pauli_correlation_encoding(
    "X", node_x, num_qubits
)
pauli_correlation_encoding_y = build_pauli_correlation_encoding(
    "Y", node_y, num_qubits
)
pauli_correlation_encoding_z = build_pauli_correlation_encoding(
    "Z", node_z, num_qubits
)
print(f"We are using {num_qubits} qubits")

# -------------------------Step 2-------------------------
backend = real_backend
print(f"We are using the {backend.name}")
qc = efficient_su2(num_qubits, ["ry", "rz"], reps=2)
pm = generate_preset_pass_manager(optimization_level=3, backend=backend)
qc = pm.run(qc)
# -------------------------Step 3-------------------------
pce = []
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]
)
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]
)
pce.append(
    [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]
)

# Run the optimization using a session.
max_iter = 50
counter = {"i": 0}
with Session(backend=backend) as session:
    estimator = Estimator(mode=session)
    estimator.options.environment.job_tags = ["TUT_PCEFQ"]
    experiment_result = []

    def loss_func(x):
        last_x["value"] = x.copy()
        if counter["i"] + 1 > max_iter:
            return last_fun["value"]
        counter["i"] += 1
        val = loss_func_estimator(
            x, qc, [pce[0], pce[1], pce[2]], estimator, graph
        )
        last_fun["value"] = val
        return val

    np.random.seed(seed)
    initial_params = np.random.rand(qc.num_parameters)
    result = minimize(
        loss_func, initial_params, method="COBYLA", options={"rhobeg": 1.0}
    )
    if counter["i"] >= max_iter:
        result = OptimizeResult(
            message=f"Return from COBYLA because the objective function "
            f"has been evaluated {max_iter} times.",
            success=False,
            status=3,
            fun=last_fun["value"],
            x=last_x["value"],
            nfev=counter["i"],
        )
print(result)

# -------------------------Step 4-------------------------

cur_bits, best_index = get_bits(experiment_result)
cut_size = evaluate_cut(cur_bits)
print(f"Cut size: {cut_size}")

best_cut, best_bits = swap_partitions(graph, cur_bits, evaluate_cut)
# Print final solution

print(
    f"The best max-cut value achieved for a graph with {num_nodes} nodes "
    f"on {num_qubits} qubits is {best_cut}"
)
print(f"and the specific partition we obtained is {best_bits}")

We are using 33 qubits
We are using the ibm_pittsburgh

Iter 0: 62192.56098951446

Iter 1: 54325.76340818571

Iter 2: 42933.215216568526

Iter 3: 35721.92960658595

Iter 4: 35947.69927402131

Iter 5: 38563.731543582166

Iter 6: 32552.97070835923

Iter 7: 34730.314616527576

Iter 8: 27032.920190652876

Iter 9: 27126.107795624957

Iter 10: 25268.853826648774

Iter 11: 23521.1489346676

Iter 12: 21658.585394613096

Iter 13: 15154.765728388778

Iter 14: 14826.985321939152

Iter 15: 16199.811009055386

Iter 16: 14328.589985020852

Iter 17: 13542.67789354434

Iter 18: 11737.341026421902

Iter 19: 10986.431644208033

Iter 20: 9780.61657788984

Iter 21: 8555.757154943312

Iter 22: 10465.489221259657

Iter 23: 8577.158776664453

Iter 24: 8950.176436175909

Iter 25: 7395.8803219317215

Iter 26: 7228.1129297581765

Iter 27: 6881.076354027118

Iter 28: 6626.8983738084835

Iter 29: 7302.433279572058

Iter 30: 6995.735525608492

Iter 31: 6176.828001182083

Iter 32: 6299.8061884979725

Iter 33: 6498.921256598082

Iter 34: 6184.684072713035

Iter 35: 5707.720358527108

Iter 36: 5414.328928670104

Iter 37: 5771.80573980932

Iter 38: 5620.64903695431

Iter 39: 6285.735849503706

Iter 40: 5894.367571492991

Iter 41: 6079.275064349491

Iter 42: 5267.448536682269

Iter 43: 4789.7281459863325

Iter 44: 5109.106057200384

Iter 45: 5060.248865782273

Iter 46: 5064.786713246322

Iter 47: 5474.433264995371

Iter 48: 4675.6138719238015

Iter 49: 5081.660754434205

message: Return from COBYLA because the objective function has been evaluated 50 times.
 success: False
  status: 3
     fun: 5081.660754434205
       x: [ 1.375e+00  1.951e+00 ...  7.260e-01  8.971e-01]
    nfev: 50
Cut size: 55507

The best max-cut value achieved for a graph with 1500 nodes on 33 qubits is 55567
and the specific partition we obtained is [1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1]

Pași următori

Recomandări

Dacă ți s-a părut interesant acest material, s-ar putea să te intereseze și:

• Tehnici avansate pentru QAOA
• Combinarea opțiunilor de atenuare a erorilor cu primitiva Estimator

Referințe

[1] Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2024). Towards large-scale quantum optimization solvers with few qubits. arXiv preprint arXiv:2401.09421.

Sondaj tutorial

Te rog să completezi acest scurt sondaj pentru a oferi feedback despre acest tutorial. Observațiile tale ne vor ajuta să îmbunătățim conținutul și experiența utilizatorilor.

Notă: Acest sondaj este realizat de IBM Quantum și acoperă conținutul tutorialului (scris de IBM). doQumentation oferă site-ul web, traducerile și execuția codului — pentru feedback despre acestea, te rugăm deschide un issue pe GitHub.

Link către sondaj © IBM Corp. 2024-2026