Rozwiązywanie problemu maksymalnego zbioru niezależnego z liczbą zmiennych większą niż liczba kubitów za pomocą SQOA Solver firmy JIJ

uwaga

Qiskit Functions to funkcja eksperymentalna dostępna tylko dla użytkowników planów IBM Quantum® Premium Plan, Flex Plan i On-Prem (przez IBM Quantum Platform API). Mają status wersji zapoznawczej i mogą ulec zmianie.

Szacowane zużycie: 10 sekund na procesorze Heron r2. (UWAGA: To tylko oszacowanie. Twój czas działania może się różnić.)

Tło

Ten samouczek pokazuje, jak użyć SQOA Solver, funkcji Qiskit Function firmy JIJ, do rozwiązania problemu maksymalnego zbioru niezależnego (MIS) z większą liczbą zmiennych binarnych, niż wybrany QPU ma kubitów. Podstawowe kroki to wczytanie instancji MIS z Quantum Optimization Benchmarking Library (QOBLIB) [1], sformułowanie jej w postaci kwadratowej optymalizacji binarnej bez ograniczeń (QUBO) za pomocą qiskit-addon-opt-mapper, przesłanie jej do SQOA Solver w celu wykonania na QPU IBM® oraz sprawdzenie zwróconego rozwiązania.

Problem maksymalnego zbioru niezależnego

Zbiór niezależny to podzbiór węzłów grafu, w którym żadne dwa wybrane węzły nie dzielą krawędzi. Maksymalny zbiór niezależny (MIS) to zbiór niezależny o największej możliwej liczbie węzłów. Zastosowania MIS obejmują harmonogramowanie, alokację zasobów i projektowanie sieci.

MIS jest NP-trudny. W przeszukiwaniu wyczerpującym każdy dodatkowy węzeł podwaja liczbę podzbiorów do rozważenia, więc to podejście jest niepraktyczne nawet dla grafów o umiarkowanej wielkości. QOBLIB zawiera MIS jako jedną ze swoich dziesięciu klas problemów, więc jest to użyteczny benchmark do oceny przepływów pracy optymalizacji kwantowej na prawdziwym sprzęcie.

Sformułowanie matematyczne

Dla danego grafu nieskierowanego $G = (V, E)$ przypisz zmienną binarną $x_v$ do każdego węzła $v$:

• $x_v = 1$, jeśli węzeł $v$ jest wybrany.

• $x_v = 0$ otherwise.

Binarne sformułowanie liniowe maksymalizuje liczbę wybranych węzłów, jednocześnie zapobiegając wybraniu obu końców dowolnej krawędzi:

$$\begin{aligned} \max_{x} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & x_v + x_w \leq 1 && \forall (v,w) \in E, \\ & x_v \in \{0,1\} && \forall v \in V. \end{aligned}$$

Funkcja celu zlicza wybrane węzły. Razem ograniczenia krawędziowe zapewniają, że wybrane węzły tworzą zbiór niezależny.

Ten samouczek używa binarnego sformułowania bez ograniczeń z QOBLIB, które zastępuje ograniczenia krawędziowe kwadratowymi karami:

$$\max_{x \in \{0,1\}^{|V|}} \quad \sum_{v \in V} x_v - 2 \sum_{(v,w) \in E} x_v x_w.$$

Za każdym razem, gdy oba końce krawędzi są wybrane, drugi składnik odejmuje dwa od funkcji celu. Ta kara sprawia, że wybór sprzeczny jest mniej korzystny niż zachowanie któregokolwiek z końców osobno. Powstała funkcja celu to QUBO, czyli format wejściowy akceptowany przez SQOA Solver.

Dlaczego warto używać SQOA Solver?

Wiele podejść do optymalizacji kwantowej przypisuje jeden kubit do każdej zmiennej binarnej, więc pojemność sprzętu kwantowego może bezpośrednio ograniczać rozmiar problemu. SQOA Solver łączy kilka technik redukcji i obliczeń hybrydowych, aby złagodzić to ograniczenie:

• Może zajmować się problemami z większą liczbą zmiennych binarnych, niż QPU ma kubitów. Presolve stosuje reguły redukcji, które mogą ustalać wartości zmiennych i upraszczać pozostałe QUBO, zachowując co najmniej jedno rozwiązanie optymalne. Empirycznie presolve może także czynić pozostałe QUBO rzadszym, co pomaga następującemu po nim kodowaniu opartemu na QRAC.

  Następnie solver używa kodowania opartego na QRAC, wywodzącego się z Quantum Random Access Optimization (QRAO) [3], aby reprezentować na tym samym kubicie wiele zmiennych (do trzech) bez bezpośredniego oddziaływania w QUBO.

  Redukcje dzięki presolve i kodowaniu zależą od struktury problemu. Na przykład w tym samouczku problem o 200 zmiennych używa tylko 67 kubitów.

• Może być mniej wrażliwy na szum sprzętowy. Kwantowa diagonalizacja oparta na próbkach [4], [5] używa QPU do próbkowania ciągów bitów, ale diagonalizację wykonuje klasycznie. Pozwala to uniknąć powtarzanych ewaluacji na QPU przy aktualizacji parametrów wariacyjnych i może zmniejszyć wpływ szumu na przepływ pracy optymalizacji.

• Automatyzuje przepływ pracy od presolve po przetwarzanie końcowe. Podajesz poprawnie sformatowaną instancję QUBO i wybierasz Backend. SQOA Solver następnie automatycznie uruchamia cały przepływ pracy. Stosuje presolve, mapuje zmienne klasyczne na zrelaksowany problem kwantowy, konstruuje i transpiluje obwody próbkujące, wykonuje próbkowanie kwantowe i diagonalizację klasyczną, zaokrągla i udoskonala przypisanie oraz rekonstruuje i ocenia rozwiązanie klasyczne.

Wymagania

Zanim zaczniesz ten samouczek, upewnij się, że masz zainstalowane następujące pakiety:

• Klient Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, używany do sformułowania problemu (pip install qiskit-addon-opt-mapper).

• NetworkX i Matplotlib, używane do obsługi i rysowania grafu (pip install networkx matplotlib).

Potrzebujesz także dostępu do SQOA Solver z Qiskit Functions Catalog. Wypełnij formularz, aby poprosić o dostęp do tej funkcji.

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

_needed = {"matplotlib": "matplotlib", "networkx": "networkx", "ommx": "ommx", "ommx_quantum_benchmarks": "ommx-quantum-benchmarks", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog"}
_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")

# %pip install qiskit-ibm-catalog qiskit-addon-opt-mapper networkx matplotlib

Konfiguracja

Najpierw zaimportuj wymagane pakiety i narzędzia.

import urllib.request

import matplotlib.pyplot as plt
import networkx as nx
from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

SQOA Solver przyjmuje problem QUBO jako słownik współczynników w formacie krotek-ciągów używanym przez funkcje optymalizacji IBM®. Zdefiniuj funkcję pomocniczą, która konwertuje QUBO zwracane przez OptimizationProblemToQubo na ten format.

Konwerter zawsze zwraca problem minimalizacji, co odpowiada sposobowi, w jaki SQOA Solver traktuje problem w postaci słownika. Klucze używają indeksów zmiennych QUBO, a każda zmienna otrzymuje wpis liniowy, nawet o zerowym współczynniku, aby zwrócone rozwiązanie obejmowało wszystkie zmienne.

def to_problem_dict(qubo: OptimizationProblem) -> dict[str, float]:
    """Convert a QUBO from OptimizationProblemToQubo to the SQOA Solver dictionary format."""
    objective = qubo.objective
    payload = {"()": objective.constant}
    # Keep every variable in the problem, even with a zero linear coefficient.
    payload.update({f"({i},)": 0.0 for i in range(qubo.get_num_vars())})
    for i, coefficient in objective.linear.to_dict().items():
        payload[f"({i},)"] += coefficient
    for (i, j), coefficient in objective.quadratic.to_dict().items():
        # Fold a binary diagonal term x_i * x_i = x_i into the linear term.
        key = f"({i},)" if i == j else f"({i}, {j})"
        payload[key] = payload.get(key, 0.0) + coefficient
    return {key: float(value) for key, value in payload.items()}

Krok 1: Mapowanie klasycznych danych wejściowych na problem kwantowy

SQOA Solver przyjmuje problem QUBO i wykonuje mapowanie kwantowe wewnątrz funkcji. W tym samouczku pobierasz instancję MIS z QOBLIB i formułujesz ją jako QUBO za pomocą qiskit-addon-opt-mapper. Ten krok obejmuje następujące czynności:

• Połącz się z SQOA Solver.

• Zrozum framework SQOA.

• Wczytaj instancję problemu.

• Sformułuj QUBO i skonwertuj je do przesłania.

Połączenie z SQOA Solver

Połącz się z Qiskit Functions Catalog za pomocą swoich poświadczeń IBM Quantum Platform, a następnie wczytaj SQOA Solver. Poniższy kod zakłada, że zapisano już Twoje konto w lokalnym środowisku.

Jeśli połączenie się nie powiedzie, upewnij się, że administrator Twojego konta IBM Quantum Platform przyznał wybranej instancji usługi dostęp do SQOA Solver.

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
solver = catalog.load("jij/sqoa-solver")

Zrozumienie frameworku SQOA

Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] łączy Quantum Random Access Optimization (QRAO) z kwantową diagonalizacją opartą na próbkach:

1. Relaksacja kwantowa i kodowanie: SQOA Solver konwertuje QUBO na minimalizowaną funkcję celu Isinga postaci $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, gdzie $z_i \in \{-1, +1\}$. QRAO [3] mapuje następnie każdą zmienną spinową na obserwablę Pauliego. Dla użytego tu kodowania $(3,1)$-QRAC zrelaksowany hamiltonian ma postać

   $$\widetilde{H} = cI + \sum_i \sqrt{k_i} h_i P_{f(i)} + \sum_{i<j} \sqrt{k_i k_j} J_{ij} P_{f(i)} P_{f(j)},$$

   gdzie $I$ jest operatorem tożsamościowym, $f(i)$ przypisuje zmienną $i$ do kubitu i jednego z $X$, $Y$ lub $Z$, a $k_i \in \{1,2,3\}$ to liczba zmiennych odwzorowanych na ten sam kubit co $i$. Gdy oba istotne kubity zawierają trzy zmienne, współczynniki skalowania liniowy i kwadratowy stają się odpowiednio $\sqrt{3}$ i $3$.

   Zmiennym dzielącym kubit przypisywane są różne, nieprzemienne obserwable Pauliego. Zmienne oddziałujące w QUBO są trzymane na różnych kubitach, natomiast zmienne bez bezpośredniego oddziaływania w QUBO mogą dzielić kubit. Zmniejszenie liczby kubitów zależy zatem od struktury problemu.

2. Próbkowanie kwantowe: Procesor kwantowy próbkuje ciągi bitów z obwodów zaprojektowanych do badania stanów o niskiej energii zrelaksowanego hamiltonianu.

3. Diagonalizacja oparta na próbkach: Solver rzutuje zrelaksowany hamiltonian na podprzestrzeń rozpiętą przez stany bazowe uzyskane z próbkowanych ciągów bitów i diagonalizuje zrzutowany hamiltonian klasycznie [4], [5]. Dla ustalonego zbioru próbkowanych ciągów bitów niech $\mathcal{S}_r$ będzie podprzestrzenią rozpiętą przez $r$ różnych stanów bazowych, więc $\dim(\mathcal{S}_r) \leq r$. Jej szacowana energia stanu podstawowego wynosi:

   $$E_r = \min_{\substack{|\psi\rangle \in \mathcal{S}_r \\ \langle\psi|\psi\rangle=1}} \langle\psi|\widetilde{H}|\psi\rangle, \qquad \mathcal{S}_r \subseteq \mathcal{S}_{r'} \Longrightarrow E_{\mathrm{exact}} \leq E_{r'} \leq E_r \quad (r' \geq r),$$

   gdzie $E_{\mathrm{exact}}$ jest energią stanu podstawowego pełnego zrelaksowanego hamiltonianu. Zatem większa zachowana podprzestrzeń nie może zwiększyć szacowanej energii stanu podstawowego.

   To uporządkowanie zakłada ten sam wynik próbkowania i dotyczy energii zrelaksowanego hamiltonianu przed zaokrągleniem. Nie gwarantuje teoretycznie lepszego zwróconego rozwiązania klasycznego. Jednak w QRAO heurystycznie oczekuje się, że stan o niższej energii da lepsze rozwiązanie klasyczne.

4. Zaokrąglanie: Zrelaksowany stan uzyskany z diagonalizacji jest konwertowany na klasyczne przypisanie binarne.

SQOA Solver otacza ten framework przetwarzaniem klasycznym. Przed mapowaniem kwantowym presolve stosuje reguły redukcji, które mogą ustalać wartości zmiennych i upraszczać pozostałe QUBO, zachowując co najmniej jedno rozwiązanie optymalne. Po diagonalizacji i zaokrągleniu klasyczne przeszukiwanie lokalne udoskonala przypisanie, a OMMX rekonstruuje i ocenia pełne rozwiązanie.

Wczytanie instancji

QOBLIB rozpowszechnia każdą instancję MIS jako graf w formacie DIMACS .gph, liniowym formacie, w którym wiersz zaczynający się od p podaje liczby węzłów i krawędzi, a każdy wiersz zaczynający się od e definiuje krawędź.

QOBLIB publikuje też optymalne lub najlepsze znane rozwiązanie referencyjne dla każdej instancji. Poniższe funkcje pobierają oba z repozytorium QOBLIB. DIMACS numeruje węzły od 1, więc graf jest przenumerowywany tak, aby zaczynał się od 0.

Jeśli wolisz zacząć od własnego grafu, pomiń pobieranie i sformułuj problem na podstawie swojego grafu NetworkX w taki sam sposób.

QOBLIB_URL = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Download a QOBLIB independent-set instance as a NetworkX graph."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/instances/{name}.gph"
    ) as response:
        lines = response.read().decode().splitlines()
    graph = nx.Graph()
    for fields in map(str.split, lines):
        if fields and fields[0] == "p":
            # Header: p edge <number of nodes> <number of edges>
            graph.add_nodes_from(range(int(fields[2])))
        elif fields and fields[0] == "e":
            # DIMACS labels nodes from 1; relabel them to start from 0.
            graph.add_edge(int(fields[1]) - 1, int(fields[2]) - 1)
    return graph

def fetch_reference_objective(name: str) -> float:
    """Read the objective value of the QOBLIB reference solution."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/solutions/{name}.opt.sol"
    ) as response:
        for line in response.read().decode().splitlines():
            if line.startswith("# Objective value"):
                return float(line.split("=")[1])
    raise ValueError(f"No objective value found for {name}.")

INSTANCE_NAME = "gen200_p0-9_44"
G = fetch_qoblib_graph(INSTANCE_NAME)
reference_objective = fetch_reference_objective(INSTANCE_NAME)

Wartości funkcji celu rozwiązania referencyjnego użyjesz później do oceny wyniku z SQOA Solver. Ten samouczek rozwiązuje ten problem na urządzeniu ze 156 kubitami.

print(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
print(f"Reference objective: {reference_objective:g}")

gen200_p0-9_44: 200 nodes, 1990 edges
Reference objective: 44

Zwizualizuj graf. Później użyjesz go także do sprawdzenia, czy węzły zwrócone przez SQOA Solver tworzą zbiór niezależny.

layout = nx.forceatlas2_layout(
    G, max_iter=500, scaling_ratio=3.0, gravity=1.0, seed=7
)
node_size = max(8, min(60, 4000 / max(G.number_of_nodes(), 1)))

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G, layout, node_size=node_size, node_color="lightgray", ax=ax
)
ax.set_title(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
ax.set_axis_off()
plt.show()

Sformułowanie QUBO

Zbuduj binarne sformułowanie liniowe z sekcji Tło jako OptimizationProblem z jedną zmienną binarną na węzeł, funkcją celu zliczającą wybrane węzły i jednym ograniczeniem na krawędź. Następnie skonwertuj je za pomocą OptimizationProblemToQubo.

Przy wadze kary równej 2 konwerter zastępuje każde ograniczenie krawędziowe składnikiem kary $2 x_v x_w$ i zamienia maksymalizację na minimalizację, więc skonwertowany problem to binarne sformułowanie bez ograniczeń z QOBLIB z odwróconym znakiem. Indeksy zmiennych QUBO to etykiety węzłów grafu. Klasa aplikacyjna IndependentSet w qiskit_addon_opt_mapper.applications buduje ten sam model z ograniczeniami za pomocą IndependentSet(G).to_optimization_problem().

Na koniec skonwertuj QUBO do formatu słownika za pomocą to_problem_dict(). Ponieważ problem jest binarnym QUBO, żądanie w kroku 2 deklaruje domenę jego zmiennych jako "binary". Funkcja wykonuje presolve, mapowanie kwantowe i konstrukcję obwodów po przesłaniu.

mis = OptimizationProblem(INSTANCE_NAME)
mis.binary_var_list(G.number_of_nodes(), name="x")
mis.maximize(linear={v: 1 for v in G.nodes})
for u, v in G.edges:
    mis.linear_constraint({u: 1, v: 1}, "<=", 1)

converter = OptimizationProblemToQubo(penalty=2)
qubo = converter.convert(mis)
problem_dict = to_problem_dict(qubo)

print(f"QUBO variables: {qubo.get_num_vars()}")
print(f"Dictionary entries: {len(problem_dict)}")

QUBO variables: 200
Dictionary entries: 2191

Krok 2: Optymalizacja problemu pod kątem wykonania na sprzęcie kwantowym

SQOA Solver wykonuje mapowanie kwantowe i przygotowanie do pracy na sprzęcie wewnątrz funkcji. Najpierw stosuje presolve do QUBO, a następnie mapuje pozostałe zmienne na zrelaksowany hamiltonian, używając kodowania opartego na QRAC.

Na potrzeby próbkowania kwantowego konstruuje obwody oparte na zrelaksowanym hamiltonianie i transpiluje je dla wybranego Backend. Redukcje rozmiaru problemu i liczby kubitów dzięki presolve i kodowaniu zależą od problemu, więc skonfiguruj solver bez zakładania stałego współczynnika redukcji.

Konfiguracja danych wejściowych solvera

SQOA Solver wymaga dwóch danych wejściowych:

• problem, słownik z kroku 1.

• variable_type, które dla tego QUBO wynosi "binary".

Akceptuje też dwa opcjonalne dane wejściowe:

• backend_name wybiera QPU. Gdy zostanie pominięte lub ma wartość None, funkcja wybiera najmniej obciążony działający QPU dostępny dla Twojej instancji.

• options to słownik kontrolujący budżet próbkowania (shots), ziarno klasyczne (seed), użycie sesji (session), klasyczne przeszukiwanie lokalne (postprocessing_level) i tagi zadań (job_tags). Jeśli zwiększysz shots, statystyki próbkowania mogą się poprawić.

Wszystkie dane wejściowe, ich wartości domyślne i reguły walidacji znajdziesz w dokumentacji API.

Ten samouczek jawnie podaje nazwę Backend, używa wartości domyślnych dla shots, session i postprocessing_level oraz ustawia ziarno klasyczne. Zbierz dane wejściowe w słowniku, aby móc przekazać je do solver.run() w kroku 3.

# ibm_fez has 156 qubits
backend_name = (
    "ibm_fez"  # Omit this key or pass None for automatic selection.
)

sqoa_input = {
    "problem": problem_dict,
    "variable_type": "binary",
    "backend_name": backend_name,
}

sqoa_input["options"] = {
    "shots": 4096,
    "seed": 42,
    "session": False,
    "postprocessing_level": 1,
}

Krok 3: Wykonanie z użyciem prymitywów

Prześlij zadanie, używając połączenia z SQOA Solver utworzonego w kroku 1. Funkcja uruchamia prymityw IBM Quantum Sampler na wybranym Backend, zbiera zmierzone ciągi bitów i kontynuuje klasyczną diagonalizacją oraz przetwarzaniem końcowym. Masz do czynienia z jednym zadaniem funkcji.

job = solver.run(**sqoa_input)
print(f"Job ID: {job.job_id}")

Job ID: dcee8e26-b8ac-4dd7-a76e-5adb5bc388e5

Aby sprawdzić stan obciążenia, zobacz Sprawdzanie stanu zadania. Wewnętrznie funkcja przechodzi przez fazy mapowania, optymalizacji sprzętowej, oczekiwania w kolejce, wykonania na QPU i przetwarzania końcowego.

job.status()

'INITIALIZING'

job.result() blokuje do zakończenia zadania i zwraca słownik z rozwiązaniem, jego wartością funkcji celu i dopuszczalnością oraz metadanymi zawierającymi informacje o solverze i zużyciu zasobów. Pełną definicję danych wejściowych i wyjściowych znajdziesz w dokumentacji API.

result = job.result()

Krok 4: Przetwarzanie końcowe wyniku i konwersja do formatu klasycznego

Przejrzyj pełne wyjście funkcji, zmapuj zwrócone przypisanie z powrotem na graf, zweryfikuj wybrane węzły i zwizualizuj wynik.

Przegląd wyniku

Słownik wyniku zawiera cztery pola najwyższego poziomu:

• solution to pełne przypisanie zmiennych, z kluczami x_i, gdzie i jest indeksem zmiennej (na przykład x_17). W tym samouczku indeks zmiennej to etykieta węzła.

• objective_value to wartość funkcji celu tego przypisania obliczona na przesłanym słowniku, czyli na minimalizowanym QUBO.

• feasible odnosi się tylko do domeny zmiennych, ponieważ słownik nie zawiera ograniczeń.

• metadata zawiera solver_info i resource_usage. solver_info zapisuje efektywne seed uruchomienia. Jeśli wykonano klasyczne przeszukiwanie lokalne, solver_info zapisuje też w solution_before_postprocessing zaokrąglone przypisanie sprzed tego udoskonalenia.

solver_info = result["metadata"]["solver_info"]

print(f"Result fields: {list(result)}")
print(f"Solution entries: {len(result['solution'])}")
print(f"First entries: {dict(list(result['solution'].items())[:3])}")
print(f"Objective value: {result['objective_value']}")
print(f"Feasible: {result['feasible']}")
print(f"Solver-info fields: {list(solver_info)}")
print(f"Effective seed: {solver_info['seed']}")
print(f"Resource-usage phases: {list(result['metadata']['resource_usage'])}")

Result fields: ['solution', 'objective_value', 'feasible', 'metadata']
Solution entries: 200
First entries: {'x_0': 0.0, 'x_1': 0.0, 'x_2': 1.0}
Objective value: -35.0
Feasible: True
Solver-info fields: ['seed', 'solution_before_postprocessing']
Effective seed: 42
Resource-usage phases: ['RUNNING: MAPPING', 'RUNNING: OPTIMIZING_FOR_HARDWARE', 'RUNNING: WAITING_FOR_QPU', 'RUNNING: EXECUTING_QPU', 'RUNNING: POST_PROCESSING']

Mapowanie rozwiązania na graf

Zbierz zwrócone wartości w kolejności indeksów zmiennych i zmapuj je z powrotem na zmienne oryginalnego problemu za pomocą interpret(). Wybrane węzły to zmienne o wartości 1, a is_feasible() sprawdza przypisanie względem ograniczeń krawędziowych oryginalnego problemu.

x_qubo = [result["solution"][f"x_{i}"] for i in range(qubo.get_num_vars())]
x = converter.interpret(x_qubo)
selected_nodes = [node for node, value in enumerate(x) if value > 0.5]

print(f"Selected nodes: {len(selected_nodes)}")
print(f"Satisfies every edge constraint: {mis.is_feasible(x)}")

Selected nodes: 35
Satisfies every edge constraint: True

Porównanie z rozwiązaniem sprzed przetwarzania końcowego

Ponieważ postprocessing_level wynosi 1, solver_info zapisuje też w solution_before_postprocessing zaokrąglone przypisanie sprzed klasycznego przeszukiwania lokalnego. Używa ono tych samych kluczy co solution.

Oblicz je na QUBO, aby zobaczyć, o ile udoskonalenie poprawiło wynik. Obie wartości są wartościami funkcji celu przesłanego minimalizowanego QUBO, więc niższa wartość jest lepsza. Pole jest pomijane, gdy przeszukiwanie lokalne się nie wykonuje, na przykład gdy presolve ustala wszystkie zmienne.

before = solver_info.get("solution_before_postprocessing")
if before is None:
    print("The classical local search did not run for this problem.")
else:
    x_before = [before[f"x_{i}"] for i in range(qubo.get_num_vars())]
    changed = sum(
        before[key] != value for key, value in result["solution"].items()
    )
    print(
        f"Objective before local search: {qubo.objective.evaluate(x_before)}"
    )
    print(f"Objective after local search: {result['objective_value']}")
    print(f"Variables changed by local search: {changed}")

Objective before local search: -12.0
Objective after local search: -35.0
Variables changed by local search: 19

Weryfikacja ograniczenia niezależności

Ponieważ QUBO reprezentuje sąsiedztwo za pomocą składników kary, a nie jawnych ograniczeń, wynik heurystyczny nadal może wybierać sąsiednie węzły. Sprawdź zwrócone węzły bezpośrednio względem grafu. Na potrzeby porównania i wizualizacji w kolejnych sekcjach skopiuj zwrócony zbiór i zachłannie usuń jeden koniec każdego wykrytego konfliktu.

returned_set = set(selected_nodes)
conflicts = [
    (u, v) for u, v in G.edges if u in returned_set and v in returned_set
]
print(f"Conflicting edges in the returned set: {len(conflicts)}")

independent_set = returned_set.copy()
for u, v in conflicts:
    if u in independent_set and v in independent_set:
        # Drop the endpoint that has more selected neighbors.
        drop = max(
            (u, v),
            key=lambda node: sum(nb in independent_set for nb in G[node]),
        )
        independent_set.remove(drop)

assert all(
    not (u in independent_set and v in independent_set) for u, v in G.edges
)
print(f"Independent set size after repair: {len(independent_set)}")

Conflicting edges in the returned set: 0
Independent set size after repair: 35

Porównanie z rozwiązaniem referencyjnym

W kroku 1 pobrano wartość funkcji celu rozwiązania referencyjnego QOBLIB. Rozwiązania referencyjne QOBLIB mogą być optymalne lub najlepsze znane, więc porównuj z referencyjną wartością funkcji celu, nie zakładając, że jest ona zawsze certyfikowanym optimum.

W tym problemie maksymalizacji współczynnik 1.0 oznacza, że naprawiony wynik odpowiada referencyjnej wartości funkcji celu.

ratio_to_reference = len(independent_set) / reference_objective

print(f"Reference objective: {reference_objective:g}")
print(f"Ratio to reference: {ratio_to_reference:.3f}")

Reference objective: 44
Ratio to reference: 0.795

Wizualizacja wyniku

Narysuj graf ponownie z wyróżnionym naprawionym zbiorem niezależnym. Żadne dwa wyróżnione węzły nie dzielą krawędzi.

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=[v for v in G if v not in independent_set],
    node_size=node_size,
    node_color="lightgray",
    ax=ax,
)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=sorted(independent_set),
    node_size=node_size * 1.4,
    node_color="tab:blue",
    ax=ax,
)
ax.set_title(
    f"Independent set size: {len(independent_set)} "
    f"(reference: {reference_objective:g})"
)
ax.set_axis_off()
plt.show()

Odczyt zużycia zasobów

Metadane wyniku zawierają CPU_TIME dla faz innych niż RUNNING: EXECUTING_QPU, gdy jest dostępny. Faza RUNNING: EXECUTING_QPU może zgłaszać QPU_TIME, czyli zużycie QPU zwrócone przez Quantum Compute, jeśli końcowe zużycie jest dostępne dla każdego zadania Quantum Compute.

usage = result["metadata"]["resource_usage"]

for phase, metrics in usage.items():
    line = f"{phase:36s}"
    if "CPU_TIME" in metrics:
        line += f" CPU {metrics['CPU_TIME']:8.1f} s"
    if "QPU_TIME" in metrics:
        line += f" QPU {metrics['QPU_TIME']:8.1f} s"
    print(line)

RUNNING: MAPPING                     CPU     11.8 s
RUNNING: OPTIMIZING_FOR_HARDWARE     CPU     15.4 s
RUNNING: WAITING_FOR_QPU             CPU     16.5 s
RUNNING: EXECUTING_QPU               QPU      3.0 s
RUNNING: POST_PROCESSING             CPU     55.8 s

Podsumowanie

W tym tutorialu pobrano instancję MIS z QOBLIB, sformułowano ją jako QUBO za pomocą qiskit-addon-opt-mapper, połączono się z SQOA Solver, skonfigurowano i przesłano zadanie, zmapowano zwrócone przypisanie z powrotem na graf oraz sprawdzono wybrane węzły względem oryginalnego grafu.

Porównano też wynik z rozwiązaniem referencyjnym z QOBLIB, zbadano wkład klasycznego przetwarzania końcowego i przeanalizowano zużycie zasobów w każdej fazie wykonania.

SQOA Solver łączy presolve, QRAO z kodowaniem opartym na QRAC, konstrukcję obwodów próbkujących, transpilację uwzględniającą sprzęt, diagonalizację opartą na próbkach, zaokrąglanie i klasyczne dopracowanie rozwiązania. Ten przepływ pracy może zmapować więcej zmiennych binarnych, niż pozwoliłoby kodowanie typu jedna zmienna na kubit. Stopień redukcji dzięki presolve i kodowaniu zależy od struktury problemu, a jakość rozwiązania zależy od uzyskanych próbek.

Ustawienia shots i postprocessing_level kontrolują odpowiednio budżet próbkowania kwantowego i klasyczne dopracowanie, bez zmiany przepływu przesyłania zadania.

Dodatek: prześlij problem jako instancję OMMX

SQOA Solver akceptuje również ommx.v1.Instance z SDK OMMX. Pakiet OMMX Quantum Benchmarks dystrybuuje problemy QOBLIB jako instancje OMMX wraz z ich rozwiązaniami referencyjnymi, dzięki czemu możesz wczytać to samo QUBO bez samodzielnego formułowania go.

Przy wejściu OMMX objective_value jest obliczana w sensie instancji, a wynik zawiera także kanoniczne ommx.v1.Solution. Zainstaluj pakiet, który instaluje również SDK OMMX:

# %pip install ommx-quantum-benchmarks

Wczytaj model binary_unconstrained tej samej instancji. Loader zbioru danych wypisuje komunikaty o postępie, więc kod przechwytuje je, aby wynik był zwięzły.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

ommx_instance, _ = IndependentSet()("binary_unconstrained", INSTANCE_NAME)

SQOA Solver otrzymuje instancję OMMX jako standardowy ciąg Base64 z dopełnieniem i zwraca kanoniczne rozwiązanie w tym samym formacie. Zdefiniuj dwie funkcje pomocnicze do tej konwersji:

• to_problem_payload() serializuje ommx.v1.Instance do ciągu, który przekazujesz jako problem.

• to_ommx_solution() dekoduje kanoniczne ommx.v1.Solution z wyniku.

import base64

from ommx.v1 import Instance, Solution

def to_problem_payload(instance: Instance) -> str:
    """Serialize an OMMX instance into the `problem` string for SQOA Solver."""
    return base64.b64encode(instance.to_bytes()).decode()

def to_ommx_solution(result: dict) -> Solution:
    """Decode the canonical OMMX solution from a SQOA Solver result."""
    payload = result["metadata"]["solver_info"]["ommx_solution"]
    return Solution.from_bytes(base64.b64decode(payload, validate=True))

Prześlij instancję z tymi samymi danymi wejściowymi co wcześniej, zmieniając tylko problem. Następnie zdekoduj kanoniczne rozwiązanie i odczytaj wybrane węzły według nazwy zmiennej.

ommx_job = solver.run(
    **{**sqoa_input, "problem": to_problem_payload(ommx_instance)}
)
ommx_result = ommx_job.result()

ommx_solution = to_ommx_solution(ommx_result)
x_values = ommx_solution.extract_decision_variables("x")
ommx_nodes = sorted(
    node for (node,), value in x_values.items() if value > 0.5
)

print(f"Objective value: {ommx_result['objective_value']}")
print(f"Selected nodes: {len(ommx_nodes)}")

Objective value: 35.0
Selected nodes: 35

Kolejne kroki

Rekomendacje

• Zastosuj ten przepływ pracy do własnych problemów QUBO. Zbuduj OptimizationProblem, jak pokazano w przewodniku po SQOA Solver. Kroki konwersji i przesyłania pozostają te same, ale dostosuj walidację do struktury swojego problemu.
• Prześlij problem jako instancję OMMX, jak pokazano w dodatku. Akceptowane formaty problemów i zwracane pola znajdziesz w dokumentacji API.
• Poznaj inne instancje zbioru niezależnego w repozytorium QOBLIB lub za pośrednictwem OMMX Quantum Benchmarks.
• Dowiedz się więcej o modelowaniu za pomocą qiskit-addon-opt-mapper lub JijModeling oraz o wymianie problemów z OMMX.

Bibliografia

[1] Koch, T., Bernal Neira, D. E., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Gomez Cadavid, A., Huang, R., Itoko, T., et al. (2026). Quantum optimization benchmarking library: The intractable decathlon. Nature Computational Science, 6, 653–671. DOI, arXiv:2504.03832

[2] Matsuyama, H., & Yamashiro, Y. (2025). Sampling-based quantum optimization algorithm with quantum relaxation. 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 1, 2323–2333. DOI, arXiv:2504.12629

[3] Fuller, B., Hadfield, C., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M. M., Blom-Schieber, A. W., Raymond, R., et al. (2024). Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5, 1–15. DOI, arXiv:2111.03167

[4] Kanno, K., Kohda, M., Imai, R., Koh, S., Mitarai, K., Mizukami, W., & Nakagawa, Y. O. (2026). Quantum-selected configuration interaction: Classical diagonalization of Hamiltonians in subspaces selected by quantum computers. Physical Review Research, 8(2), 023268. DOI, arXiv:2302.11320

[5] Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., et al. (2025). Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25), eadu9991. DOI, arXiv:2405.05068