Algoritma optimasi perkiraan kuantum

Perkiraan penggunaan: 22 menit pada prosesor Heron r3 (CATATAN: Ini hanya perkiraan. Waktu aktual kamu bisa berbeda.)

Hasil pembelajaran

• Cara memetakan masalah optimasi kombinatorial klasik (max-cut) ke sebuah Hamiltonian kuantum

• Cara mengimplementasikan dan menjalankan Quantum Approximate Optimization Algorithm (QAOA) menggunakan session IBM Quantum Compute Service

• Cara menskalakan alur kerja QAOA dari contoh simulator kecil ke eksekusi perangkat keras skala utilitas

Prasyarat

• Dasar-dasar circuit kuantum

• Algoritma variasional

• QAOA secara mendalam — untuk pembahasan menyeluruh tentang algoritma QAOA dan penerapannya pada skala utilitas

Latar belakang

Quantum Approximate Optimization Algorithm (QAOA) adalah metode iteratif hibrida kuantum-klasik untuk memecahkan masalah optimasi kombinatorial. Dalam tutorial ini, kamu akan menggunakan QAOA untuk memecahkan masalah maximum-cut (max-cut) — sebuah masalah optimasi NP-hard dengan aplikasi dalam klasterisasi, ilmu jaringan, dan fisika statistik. Diberikan sebuah graf berisi simpul-simpul yang terhubung oleh sisi, tujuannya adalah membagi simpul-simpul ke dalam dua himpunan sedemikian rupa sehingga jumlah sisi yang melintasi partisi dimaksimalkan.

Optimasi kombinatorial juga muncul dalam tantangan keberlanjutan, seperti merencanakan rute pengiriman untuk mengurangi penggunaan bahan bakar dan mengalokasikan sumber daya untuk membatasi limbah material. Contoh max-cut memperkenalkan proses mengekspresikan objektif sebagai Hamiltonian biaya dan mengeksplorasi kandidat solusi dengan QAOA. Menerapkan pendekatan ini pada masalah keberlanjutan memerlukan fungsi objektif dan kendala yang merepresentasikan aplikasi yang dimaksud.

Dari optimasi klasik ke circuit kuantum

Max-cut dapat dinyatakan sebagai masalah optimasi biner klasik. Setiap simpul diberi sebuah variabel biner $x_i \in \{0, 1\}$ yang menunjukkan ia termasuk himpunan yang mana. Tujuannya adalah memaksimalkan jumlah sisi yang kedua ujungnya berada pada himpunan berbeda:

$$\max_{x \in \{0,1\}^n} \sum_{(i,j)} x_i + x_j - 2x_ix_j.$$

Ini secara ekuivalen merupakan masalah Quadratic Unconstrained Binary Optimization (QUBO) berbentuk $\min_x\, x^T Q x$. Melalui substitusi variabel standar ($x_i \to (1 - Z_i)/2$), QUBO dapat ditulis ulang sebagai sebuah Hamiltonian biaya yang keadaan dasarnya mengkodekan solusi optimal. Secara umum, Hamiltonian ini memiliki suku kuadratik maupun linier:

$$H_C = \sum_{ij} Q_{ij} \, Z_i Z_j + \sum_i b_i \, Z_i.$$

Dalam tutorial ini, kamu tidak melakukan substitusi ini secara manual. Optimization Mapper Qiskit addon (qiskit-addon-opt-mapper) menyediakan kelas aplikasi Maxcut yang memodelkan masalah langsung dari sebuah graf, sebuah konverter yang mengubah model menjadi QUBO, dan sebuah translator yang memetakan QUBO ke $H_C$. Untuk masalah max-cut tak berbobot yang dibahas di sini, koefisien linearnya lenyap ($b_i = 0$) dan setiap sisi menyumbang suku $\tfrac{1}{2} Z_i Z_j$, bersama offset konstan yang menghubungkan $\langle H_C \rangle$ dengan nilai potongan. Pipeline yang sama menangani graf berbobot dan masalah lain yang bisa dinyatakan sebagai QUBO tanpa mengubah bagian alur kerja lainnya.

Cara kerja QAOA

QAOA menyiapkan solusi kandidat dengan menerapkan lapisan-lapisan berselang-seling dari dua operator pada sebuah keadaan superposisi awal $H^{\otimes n}|0\rangle$: operator biaya $e^{-i\gamma_k H_C}$ dan sebuah operator mixer $e^{-i\beta_k H_m}$. Sudut-sudut $\gamma_k$ dan $\beta_k$ dioptimalkan dalam loop umpan balik klasik; komputer kuantum mengevaluasi fungsi biaya, dan sebuah pengoptimal klasik memperbarui parameter sampai konvergen. Loop iteratif ini berjalan di dalam sebuah session Quantum Compute, yang menjaga perangkat kuantum tetap dipesan sepanjang iterasi untuk latensi yang lebih rendah.

Untuk pembahasan teori QAOA yang lebih mendalam, termasuk penurunan QUBO-ke-Hamiltonian lengkap, lihat modul kursus QAOA.

Dalam tutorial ini kamu pertama-tama akan memecahkan max-cut pada sebuah graf kecil lima-simpul, lalu menskalakan alur kerja yang sama ke masalah skala utilitas 100-simpul pada perangkat keras nyata. Catatan tentang akses paket: Tutorial ini menggunakan session Quantum Compute, yang hanya tersedia pada Premium Plan. Jika kamu menggunakan Open Plan, kamu tidak dapat menjalankan tutorial ini sebagaimana ditulis; sebagai gantinya, kamu perlu menukar Session dengan job mode (yaitu, kirim setiap iterasi sebagai job independen alih-alih membungkus loop optimasi dengan Session(...)). Alur kerja tetap berjalan, tetapi setiap iterasi menanggung latensi antrean penuh alih-alih menggunakan kembali perangkat yang dipesan. Lihat Gambaran umum paket yang tersedia untuk informasi lebih lanjut.

Persyaratan

Sebelum memulai tutorial ini, pastikan kamu telah menginstal hal-hal berikut:

• Qiskit SDK v2.0 atau lebih baru, dengan dukungan visualisasi

• Qiskit Runtime v0.22 atau lebih baru (pip install qiskit-ibm-runtime)

• Add-on Qiskit Optimization Mapper (pip install qiskit-addon-opt-mapper)

Selain itu, kamu memerlukan akses ke sebuah instance di IBM Quantum® Platform.

Setup

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

_needed = {"matplotlib": "matplotlib", "numpy": "numpy", "qiskit": "qiskit", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "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")

import matplotlib.pyplot as plt
import rustworkx as rx
from rustworkx.visualization import mpl_draw as draw_graph
import numpy as np
from scipy.optimize import minimize
from collections import defaultdict

from qiskit.quantum_info import SparsePauliOp
from qiskit.circuit.library import QAOAAnsatz
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Session, EstimatorV2 as Estimator
from qiskit_ibm_runtime import SamplerV2 as Sampler

from qiskit_addon_opt_mapper.applications import Maxcut
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_addon_opt_mapper.translators import to_ising

Contoh skala kecil

Bagian ini memandu kamu melalui setiap langkah alur kerja QAOA pada sebuah instance max-cut kecil lima-simpul. Meskipun berlabel "skala kecil", contoh ini tetap berjalan pada perangkat keras IBM Quantum nyata — kode memilih sebuah backend dengan 127 qubit atau lebih dan mengeksekusi circuit di sana. Inisialisasi masalahmu dengan membuat sebuah graf berisi $n=5$ simpul.

n_small = 5

graph = rx.PyGraph()
graph.add_nodes_from(np.arange(0, n_small, 1))
edge_list = [
    (0, 1, 1.0),
    (0, 2, 1.0),
    (0, 4, 1.0),
    (1, 2, 1.0),
    (2, 3, 1.0),
    (3, 4, 1.0),
]
graph.add_edges_from(edge_list)
draw_graph(graph, node_size=600, with_labels=True)

Langkah 1: Petakan input klasik ke masalah kuantum

Petakan graf klasik ke dalam circuit dan operator kuantum. Seperti dijelaskan dalam Latar belakang, max-cut adalah masalah QUBO yang Hamiltonian biaya $H_C$-nya memiliki keadaan dasar yang menyandikan potongan optimal, dan QAOA menggunakan sebuah circuit ansatz terparameterisasi untuk menyiapkan keadaan dasar kandidat dari $H_C$. Gunakan addon Optimization Mapper untuk beralih dari graf ke $H_C$ dalam tiga langkah: modelkan masalahnya, ubah menjadi QUBO, dan terjemahkan QUBO menjadi Hamiltonian Ising.

Modelkan masalahnya

Kelas aplikasi Maxcut menerima graf rustworkx secara langsung dan mengembalikan sebuah OptimizationProblem yang fungsi objektifnya adalah nilai potongan yang akan dimaksimalkan. Setiap sisi $(i, j)$ menyumbang $x_i + x_j - 2 x_i x_j$ ke fungsi objektif, persis seperti di Latar belakang.

maxcut = Maxcut(graph)
maxcut_problem = maxcut.to_optimization_problem()
print(maxcut_problem.prettyprint())

Problem name: Max-cut

Maximize
  -2*x_0*x_1 - 2*x_0*x_2 - 2*x_0*x_4 - 2*x_1*x_2 - 2*x_2*x_3 - 2*x_3*x_4 + 3*x_0
  + 2*x_1 + 3*x_2 + 2*x_3 + 2*x_4

Subject to
  No constraints

  Binary variables (5)
    x_0 x_1 x_2 x_3 x_4

Bangun Hamiltonian biaya

Ubah masalah menjadi QUBO dengan OptimizationProblemToQubo, lalu terjemahkan QUBO menjadi Hamiltonian Ising dengan to_ising. Konverter mengubah maksimalisasi menjadi minimalisasi dari nilai potongan yang dinegasikan, dan translator menerapkan substitusi $x_i \to (1 - Z_i)/2$. Hasilnya adalah $H_C$ sebagai SparsePauliOp beserta offset skalar sehingga $\text{nilai QUBO} = \langle H_C \rangle + \text{offset}$. Karena QUBO meminimalkan nilai potongan yang dinegasikan, nilai potongan dari bitstring mana pun adalah $-(\langle H_C \rangle + \text{offset})$.

qubo = OptimizationProblemToQubo().convert(maxcut_problem)
cost_hamiltonian, offset = to_ising(qubo)
print("Cost Function Hamiltonian:", cost_hamiltonian)
print("Offset:", offset)

Cost Function Hamiltonian: SparsePauliOp(['IIIZZ', 'IIZIZ', 'ZIIIZ', 'IIZZI', 'IZZII', 'ZZIII'],
              coeffs=[0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j])
Offset: -3.0

Bangun circuit ansatz QAOA

Gunakan QAOAAnsatz untuk membangun circuit QAOA terparameterisasi dari Hamiltonian biaya. Di sini kita menggunakan reps=2 (dua lapisan QAOA, empat parameter: $\beta_0, \beta_1, \gamma_0, \gamma_1$).

circuit = QAOAAnsatz(cost_operator=cost_hamiltonian, reps=2)
circuit.measure_all()

circuit.draw("mpl")

circuit.parameters

ParameterView([ParameterVectorElement(β[0]), ParameterVectorElement(β[1]), ParameterVectorElement(γ[0]), ParameterVectorElement(γ[1])])

Langkah 2: Optimalkan masalah untuk eksekusi perangkat keras kuantum

Transpilasikan circuit abstrak menjadi instruksi native perangkat keras. Langkah ini menangani pemetaan qubit, dekomposisi gate, perutean, dan penekanan kesalahan. Lihat dokumentasi transpilasi untuk informasi lebih lanjut.

service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
print(backend)

# Create pass manager for transpilation. Level 3 is the most aggressive
# preset: slower to transpile, but produces shorter circuits that are
# more robust to hardware noise.
pm = generate_preset_pass_manager(optimization_level=3, backend=backend)

candidate_circuit = pm.run(circuit)
candidate_circuit.draw("mpl", fold=False, idle_wires=False)

<IBMBackend('ibm_pittsburgh')>

Langkah 3: Eksekusi menggunakan primitif Qiskit

Loop optimasi QAOA berjalan di dalam sebuah session Quantum Compute untuk menjaga perangkat tetap dipesan sepanjang iterasi. Sebuah Estimator mengevaluasi $\langle H_C \rangle$ pada setiap langkah, dan sebuah pengoptimal klasik (COBYLA) memperbarui parameter sampai konvergen.

Tentukan parameter awal dan jalankan loop optimasi:

# QAOA doesn't prescribe principled default angles — any bounded choice
# works as a warm start for problems this small. beta and gamma are
# periodic (beta in [0, pi] and gamma in [0, 2*pi] modulo the underlying
# Pauli-rotation periods), and pi/2 and pi are just midpoints of those
# ranges. For harder problems you would typically warm start from known
# good angles or transfer parameters from smaller instances.
initial_gamma = np.pi
initial_beta = np.pi / 2
init_params = [initial_beta, initial_beta, initial_gamma, initial_gamma]

def cost_func_estimator(params, ansatz, hamiltonian, estimator):
    # transform the observable defined on virtual qubits to
    # an observable defined on all physical qubits
    isa_hamiltonian = hamiltonian.apply_layout(ansatz.layout)

    pub = (ansatz, isa_hamiltonian, params)
    job = estimator.run([pub])

    results = job.result()[0]
    cost = results.data.evs

    objective_func_vals.append(cost)

    return cost

objective_func_vals = []  # Global variable
with Session(backend=backend) as session:
    # If using qiskit-ibm-runtime<0.24.0, change `mode=` to `session=`
    estimator = Estimator(mode=session)
    estimator.options.default_shots = 1000

    # Set simple error suppression/mitigation options
    estimator.options.dynamical_decoupling.enable = True
    estimator.options.dynamical_decoupling.sequence_type = "XY4"
    estimator.options.twirling.enable_gates = True
    estimator.options.twirling.num_randomizations = "auto"
    estimator.options.environment.job_tags = ["TUT_QAOA"]

    result = minimize(
        cost_func_estimator,
        init_params,
        args=(candidate_circuit, cost_hamiltonian, estimator),
        method="COBYLA",
        tol=1e-2,
    )
    print(result)

message: Return from COBYLA because the trust region radius reaches its lower bound.
 success: True
  status: 0
     fun: -1.0164225323839062
       x: [ 1.404e+00  1.174e+00  4.036e+00  2.969e+00]
    nfev: 30
   maxcv: 0.0

Pengoptimal berhasil mengurangi biaya dan menemukan parameter yang lebih baik untuk circuit.

Kurva yang menurun secara mulus dan kemudian mendatar adalah ciri khas konvergensi. Kurva yang berisik dan tidak monoton biasanya menunjukkan bahwa ada sesuatu di hulu yang perlu diperhatikan; penyebab umumnya adalah terlalu sedikit shot per evaluasi (varians estimator tinggi), parameter awal yang buruk, atau circuit yang kedalamannya didominasi oleh noise perangkat keras. COBYLA bebas turunan dan cukup tahan terhadap noise sedang, tetapi ketika noise menenggelamkan perbaikan biaya nyata per langkah, model aproksimasi liniernya tidak lagi dapat membedakan penurunan nyata dari jitter acak dan pengoptimal pun bergerak tanpa arah.

plt.figure(figsize=(12, 6))
plt.plot(objective_func_vals)
plt.xlabel("Iteration")
plt.ylabel("Cost")
plt.show()

Tetapkan parameter yang telah dioptimalkan dan ambil sampel distribusi akhir menggunakan primitif Sampler.

optimized_circuit = candidate_circuit.assign_parameters(result.x)
optimized_circuit.draw("mpl", fold=False, idle_wires=False)

# If using qiskit-ibm-runtime<0.24.0, change `mode=` to `backend=`
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10000

# Set simple error suppression/mitigation options
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XY4"
sampler.options.twirling.enable_gates = True
sampler.options.twirling.num_randomizations = "auto"

sampler.options.environment.job_tags = ["TUT_QAOA"]

pub = (optimized_circuit,)
job = sampler.run([pub], shots=int(1e4))
counts_int = job.result()[0].data.meas.get_int_counts()
counts_bin = job.result()[0].data.meas.get_counts()
shots = sum(counts_int.values())
final_distribution_int = {key: val / shots for key, val in counts_int.items()}
final_distribution_bin = {key: val / shots for key, val in counts_bin.items()}
print(final_distribution_int)

{22: 0.1003, 15: 0.008, 9: 0.0934, 4: 0.02, 31: 0.004, 17: 0.0288, 18: 0.0327, 14: 0.0305, 10: 0.0358, 28: 0.0128, 5: 0.0868, 20: 0.09, 11: 0.0908, 13: 0.0321, 19: 0.0298, 27: 0.0186, 8: 0.0077, 30: 0.0211, 23: 0.0098, 26: 0.0839, 12: 0.0254, 21: 0.0315, 16: 0.0082, 25: 0.01, 6: 0.0131, 1: 0.0205, 2: 0.0145, 29: 0.0137, 7: 0.0059, 3: 0.0101, 24: 0.0078, 0: 0.0024}

Langkah 4: Pasca-proses dan kembalikan hasil dalam format klasik yang diinginkan

Ekstrak bitstring yang paling mungkin dari distribusi yang telah diambil sampelnya. Ini merepresentasikan potongan terbaik yang ditemukan oleh QAOA. Metode interpret dari kelas Maxcut mendekode bitstring menjadi dua himpunan node dari partisi tersebut.

# auxiliary functions to sample most likely bitstring
def to_bitstring(integer, num_bits):
    result = np.binary_repr(integer, width=num_bits)
    return [int(digit) for digit in result]

keys = list(final_distribution_int.keys())
values = list(final_distribution_int.values())
most_likely = keys[np.argmax(np.abs(values))]
most_likely_bitstring = to_bitstring(most_likely, len(graph))
most_likely_bitstring.reverse()

print("Result bitstring:", most_likely_bitstring)

partition = maxcut.interpret(np.array(most_likely_bitstring))
print("Partition:", partition)

Result bitstring: [0, 1, 1, 0, 1]
Partition: [[0, 3], [1, 2, 4]]

plt.rcParams.update({"font.size": 10})
final_bits = final_distribution_bin
values = np.abs(list(final_bits.values()))
top_4_values = sorted(values, reverse=True)[:4]
positions = []
for value in top_4_values:
    positions.append(np.where(values == value)[0])
fig = plt.figure(figsize=(11, 6))
ax = fig.add_subplot(1, 1, 1)
plt.xticks(rotation=45)
plt.title("Result Distribution")
plt.xlabel("Bitstrings (reversed)")
plt.ylabel("Probability")
ax.bar(list(final_bits.keys()), list(final_bits.values()), color="tab:grey")
for p in positions:
    ax.get_children()[int(p[0])].set_color("tab:purple")
plt.show()

Visualisasikan potongan terbaik

Dari bitstring optimal, kamu kemudian dapat memvisualisasikan potongan ini pada graf asli.

# auxiliary function to plot graphs
def plot_result(G, x):
    colors = ["tab:grey" if i == 0 else "tab:purple" for i in x]
    pos, _default_axes = rx.spring_layout(G), plt.axes(frameon=True)
    rx.visualization.mpl_draw(
        G, node_color=colors, node_size=100, alpha=0.8, pos=pos
    )

plot_result(graph, most_likely_bitstring)

Sekarang, hitung nilai potongan. Fungsi objektif dari OptimizationProblem adalah nilai potongan itu sendiri, jadi evaluasi langsung pada bitstring. Kamu juga bisa membandingkannya dengan nilai potongan yang diimplikasikan oleh biaya akhir optimizer, $-(\langle H_C \rangle + \text{offset})$, yang merupakan rata-rata atas seluruh distribusi sampel, bukan nilai dari satu bitstring.

cut_value = maxcut_problem.objective.evaluate(np.array(most_likely_bitstring))
print("The value of the cut is:", cut_value)
print("Cut value implied by the optimized cost:", -(result.fun + offset))

The value of the cut is: 5.0
Cut value implied by the optimized cost: 4.016422532383906

Untuk graf sekecil ini, optimum sebenarnya mudah dicari dengan brute-force, sehingga kamu dapat memeriksa ulang hasilnya dengan membandingkan hasil QAOA terhadap jawaban eksak.

# Classical baseline: enumerate all 2**n_small bitstrings and take the best cut.
def brute_force_max_cut(problem) -> tuple[int, list[int]]:
    n = problem.get_num_vars()
    best_cut = -1
    best_x: list[int] = []
    for i in range(2**n):
        x = np.array([(i >> k) & 1 for k in range(n)])
        cut = problem.objective.evaluate(x)
        if cut > best_cut:
            best_cut = int(cut)
            best_x = x.tolist()
    return best_cut, best_x

classical_best, classical_x = brute_force_max_cut(maxcut_problem)
print(f"Classical optimum (brute force): {classical_best}")
print(f"QAOA cut value:                  {cut_value}")

Classical optimum (brute force): 5
QAOA cut value:                  5.0

Contoh perangkat keras skala besar

Kamu memiliki akses ke banyak perangkat dengan lebih dari 100 qubit di IBM Quantum Platform. Pilih salah satu untuk memecahkan max-cut pada sebuah graf berbobot 100-simpul. Ini adalah masalah "skala utilitas". Alur kerjanya mengikuti langkah-langkah yang sama seperti di atas, diterapkan pada graf yang jauh lebih besar.

Alur kerja menyeluruh pada skala utilitas

Keempat langkah ditunjukkan di bawah, diterapkan pada graf 100-simpul. Strukturnya sama dengan panduan skala kecil: petakan, transpilasi, eksekusi, pasca-proses — tetapi dengan masalah yang lebih besar dan dibagi ke dalam empat sel di bawah agar lebih jelas.

# Precomputed parity lookup table: _PARITY[b] = +1 if popcount(b) is even, else -1.
# We use this to vectorize expectation-value evaluation across all Pauli terms.
_PARITY = np.array(
    [-1 if bin(i).count("1") % 2 else 1 for i in range(256)],
    dtype=np.complex128,
)

def evaluate_sparse_pauli(state: int, observable: SparsePauliOp) -> complex:
    """Expectation value of a SparsePauliOp on a single computational-basis state.

    For a Z-only observable (which QAOA cost Hamiltonians are, after the
    QUBO-to-Hamiltonian mapping), the eigenvalue of each Pauli term on a
    computational-basis state is simply (-1)**popcount(z_mask AND state),
    i.e., the parity of the bitwise-AND of the term's Z-support and the
    measured bitstring.

    This routine packs the Z-support of every Pauli term into bytes, ANDs
    them against the measured state in a single vectorized op, and looks up
    the parity in _PARITY. For a 100-qubit / ~hundreds-of-terms Hamiltonian
    over 10_000 samples, this is dramatically faster than calling
    SparsePauliOp.expectation_value per sample.
    """
    packed_uint8 = np.packbits(observable.paulis.z, axis=1, bitorder="little")
    state_bytes = np.frombuffer(
        state.to_bytes(packed_uint8.shape[1], "little"), dtype=np.uint8
    )
    reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)
    return np.sum(observable.coeffs * _PARITY[reduced])

def best_solution(samples, hamiltonian):
    """Return the sampled bitstring (as int) with the lowest Hamiltonian cost."""
    min_cost = float("inf")
    min_sol = None
    for bit_str in samples.keys():
        candidate_sol = int(bit_str)
        fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real
        if fval <= min_cost:
            min_cost = fval
            min_sol = candidate_sol
    return min_sol

def _plot_cdf(objective_values: dict, ax, color):
    x_vals = sorted(objective_values.keys(), reverse=True)
    y_vals = np.cumsum([objective_values[x] for x in x_vals])
    ax.plot(x_vals, y_vals, color=color)

def plot_cdf(dist, ax, title):
    _plot_cdf(dist, ax, "C1")
    ax.vlines(min(list(dist.keys())), 0, 1, "C1", linestyle="--")
    ax.set_title(title)
    ax.set_xlabel("Objective function value")
    ax.set_ylabel("Cumulative distribution function")
    ax.grid(alpha=0.3)

def samples_to_objective_values(samples, hamiltonian):
    """Convert the samples to values of the objective function."""
    objective_values = defaultdict(float)
    for bit_str, prob in samples.items():
        candidate_sol = int(bit_str)
        fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real
        objective_values[fval] += prob
    return objective_values

Langkah 1: Bangun graf dari coupling map Backend, lalu petakan ke Hamiltonian biaya dengan addon Optimization Mapper dan bangun ansatz.

# Step 1: build the 100-node graph, cost Hamiltonian, and QAOA ansatz.
n_large = 100
graph_100 = rx.PyGraph()
graph_100.add_nodes_from(np.arange(0, n_large, 1))
elist = set()
for u, v in backend.coupling_map:
    # The coupling map lists both directions of each coupler, so sort
    # the endpoints to avoid adding the same edge twice.
    if u < n_large and v < n_large:
        elist.add((min(u, v), max(u, v), 1.0))
graph_100.add_edges_from(sorted(elist))

maxcut_100 = Maxcut(graph_100)
maxcut_problem_100 = maxcut_100.to_optimization_problem()
qubo_100 = OptimizationProblemToQubo().convert(maxcut_problem_100)
cost_hamiltonian_100, offset_100 = to_ising(qubo_100)

circuit_100 = QAOAAnsatz(cost_operator=cost_hamiltonian_100, reps=1)
circuit_100.measure_all()

Langkah 2: Transpilasikan untuk backend perangkat keras yang dipilih.

# Step 2: transpile for hardware.
pm = generate_preset_pass_manager(optimization_level=3, backend=backend)
candidate_circuit_100 = pm.run(circuit_100)

Langkah 3: Jalankan loop optimasi QAOA di dalam sebuah session, lalu ambil sampelnya.

# Step 3: run the QAOA optimization loop on the device, then sample the
# final distribution with the optimized parameters.
initial_gamma = np.pi
initial_beta = np.pi / 2
init_params = [initial_beta, initial_gamma]

objective_func_vals = []  # Global variable
with Session(backend=backend) as session:
    estimator = Estimator(mode=session)
    estimator.options.default_shots = 1000

    # Set simple error suppression/mitigation options
    estimator.options.dynamical_decoupling.enable = True
    estimator.options.dynamical_decoupling.sequence_type = "XY4"
    estimator.options.twirling.enable_gates = True
    estimator.options.twirling.num_randomizations = "auto"
    estimator.options.environment.job_tags = ["TUT_QAOA"]

    result = minimize(
        cost_func_estimator,
        init_params,
        args=(candidate_circuit_100, cost_hamiltonian_100, estimator),
        method="COBYLA",
    )
    print(result)

# Assign optimal parameters and sample the final distribution.
optimized_circuit_100 = candidate_circuit_100.assign_parameters(result.x)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10000

# Set simple error suppression/mitigation options
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XY4"
sampler.options.twirling.enable_gates = True
sampler.options.twirling.num_randomizations = "auto"

# Add a unique tag to the job execution
sampler.options.environment.job_tags = ["TUT_QAOA"]

pub = (optimized_circuit_100,)
job = sampler.run([pub], shots=int(1e4))

counts_int = job.result()[0].data.meas.get_int_counts()
shots = sum(counts_int.values())
final_distribution_100_int = {
    key: val / shots for key, val in counts_int.items()
}

message: Return from COBYLA because the trust region radius reaches its lower bound.
 success: True
  status: 0
     fun: -4.214640355142735
       x: [ 2.586e+00  4.161e+00]
    nfev: 26
   maxcv: 0.0

Langkah 4: Pasca-proses distribusi yang diambil sampelnya untuk mengekstrak potongan terbaik.

# Step 4: find the best-cost sample and evaluate its cut value.
best_sol_100 = best_solution(final_distribution_100_int, cost_hamiltonian_100)
best_sol_bitstring_100 = to_bitstring(int(best_sol_100), len(graph_100))
best_sol_bitstring_100.reverse()

print("Result bitstring:", best_sol_bitstring_100)

cut_value_100 = maxcut_problem_100.objective.evaluate(
    np.array(best_sol_bitstring_100)
)
print("The value of the cut is:", cut_value_100)

Result bitstring: [1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1]
The value of the cut is: 78.0

Periksa bahwa biaya yang diminimalkan dalam loop optimasi telah konvergen, dan visualisasikan hasilnya.

# Plot convergence
plt.figure(figsize=(12, 6))
plt.plot(objective_func_vals)
plt.xlabel("Iteration")
plt.ylabel("Cost")
plt.show()

# Visualize the cut
plot_result(graph_100, best_sol_bitstring_100)

# Plot cumulative distribution function
result_dist = samples_to_objective_values(
    final_distribution_100_int, cost_hamiltonian_100
)
fig, ax = plt.subplots(1, 1, figsize=(8, 6))
plot_cdf(result_dist, ax, backend.name)

Langkah selanjutnya

Jika kamu merasa karya ini menarik, kamu mungkin tertarik dengan materi berikut:

Rekomendasi

• Teknik lanjutan untuk QAOA — mengeksplorasi strategi lanjutan untuk meningkatkan performa QAOA
• Tantangan optimasi multi-objektif — uji kemampuanmu dengan tantangan komunitas tentang optimasi kuantum multi-objektif ini
• Dokumentasi transpilasi untuk penyetelan halus optimasi circuit
• Penekanan dan mitigasi kesalahan untuk meningkatkan hasil perangkat keras