Kodowanie korelacji Pauliego w celu redukcji wymagań Maxcut

Szacowany czas użycia: 30 minut na procesorze Eagle r3 (UWAGA: to jest tylko szacunek. Twój czas wykonania może się różnić.)

Tło

Ten samouczek przedstawia Kodowanie Korelacji Pauliego (PCE) [1], podejście zaprojektowane w celu kodowania problemów optymalizacyjnych w qubitach z większą wydajnością dla obliczeń kwantowych. PCE odwzorowuje klasyczne zmienne w problemach optymalizacyjnych na wielociałowe korelacje macierzy Pauliego, co skutkuje wielomianową kompresją wymagań przestrzennych problemu. Dzięki zastosowaniu PCE liczba qubitów potrzebnych do kodowania jest zmniejszona, co jest szczególnie korzystne dla bliskich terminu urządzeń kwantowych z ograniczonymi zasobami qubitowymi. Co więcej, analitycznie wykazano, że PCE inherentnie łagodzi efekt jałowych plateau, oferując super-wielomianową odporność na to zjawisko. Ta wbudowana funkcja umożliwia bezprecedensową wydajność w solverach optymalizacji kwantowej.

Przegląd

Podejście PCE składa się z trzech głównych kroków, jak pokazano na Rysunku 1 z [1] poniżej:

1. Zakodowanie problemu optymalizacyjnego w przestrzeń korelacji Pauliego.
2. Rozwiązanie problemu przy użyciu solvera optymalizacji kwantowo-klasycznej.
3. Zdekodowanie rozwiązania z powrotem do oryginalnej przestrzeni optymalizacyjnej. Podejście PCE jest adaptowalane do dowolnego solvera optymalizacji kwantowej zdolnego do przetwarzania macierzy korelacji Pauliego. Na Rysunku 1 z [1] problem Max-Cut jest używany jako przykład ilustrujący podejście PCE. Problem Max-Cut z $m=9$ węzłami jest zakodowany w przestrzeń korelacji Pauliego, reprezentując problem optymalizacyjny jako macierz korelacji, konkretnie 2-ciałowe korelacje macierzy Pauliego na $n=3$ qubitach $(Q_1, Q_2, Q_3)$. Kolory węzłów wskazują łańcuch Pauliego użyty dla każdego zakodowanego węzła. Na przykład węzeł 1, który odpowiada zmiennej binarnej $x_1$, jest zakodowany przez wartość oczekiwaną $Z_1 \otimes Z_2 \otimes I_3$, podczas gdy $x_8$ jest zakodowany przez $I_1 \otimes Y_2 \otimes Y_3$. Odpowiada to kompresji $m$ zmiennych problemu do $n = O(m^{1/2})$ qubitów. Ogólniej, korelacje $k$-ciałowe umożliwiają wielomianowe kompresje rzędu $k$. Wybrany zbiór Pauliego składa się z trzech podzbiorów wzajemnie komutujących łańcuchów Pauliego, co pozwala na eksperymentalne oszacowanie wszystkich $m$ korelacji za pomocą tylko trzech ustawień pomiarowych.

Funkcja strat $\mathcal{L}$ wartości oczekiwanych Pauliego, która imituje oryginalną funkcję celu Max-Cut, jest konstruowana. Następnie funkcja strat jest optymalizowana przy użyciu solvera optymalizacji kwantowo-klasycznej, takiego jak Variational Quantum Eigensolver (VQE).

Po zakończeniu optymalizacji rozwiązanie jest dekodowane z powrotem do oryginalnej przestrzeni optymalizacyjnej, dając optymalne rozwiązanie Max-Cut.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że masz zainstalowane następujące elementy:

• Qiskit SDK v1.0 lub nowszy, z obsługą wizualizacji
• Qiskit Runtime v0.22 lub nowszy (pip install qiskit-ibm-runtime)

Konfiguracja

# Added by doQumentation — required packages for this notebook
!pip install -q networkx numpy qiskit qiskit-ibm-runtime rustworkx scipy

from itertools import combinations

import numpy as np
import rustworkx as rx
from scipy.optimize import minimize

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

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

def calc_cut_size(graph, partition0, partition1):
    """Calculate the cut size of the given partitions of the graph."""

    cut_size = 0
    for edge0, edge1 in graph.edge_list():
        if edge0 in partition0 and edge1 in partition1:
            cut_size += 1
        elif edge0 in partition1 and edge1 in partition0:
            cut_size += 1
    return cut_size

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

Problem Max-Cut

Problem Max-Cut to kombinatoryczny problem optymalizacyjny zdefiniowany na grafie $G = (V, E)$, gdzie $V$ jest zbiorem wierzchołków, a $E$ jest zbiorem krawędzi. Celem jest podzielenie wierzchołków na dwa zbiory, $S$ i $V \setminus S$, tak aby liczba krawędzi między tymi dwoma zbiorami była zmaksymalizowana. Szczegółowy opis problemu Max-Cut znajdziesz w samouczku "Quantum approximate optimization algorithm". Ponadto problem Max-Cut jest używany jako przykład w samouczku "Advanced Techniques for QAOA". W tych samouczkach algorytm QAOA jest używany do rozwiązania problemu Max-Cut.

Graf -> Hamiltonian

Ten samouczek używa losowego grafu z 1000 węzłami.

Rozmiar problemu może być trudny do zwizualizowania, więc poniżej przedstawiono graf ze 100 węzłami. (Bezpośrednie renderowanie grafu z 1000 węzłami byłoby zbyt gęste, żeby cokolwiek widać!) Graf, z którym pracujemy, jest dziesięć razy większy.

mpl_draw(rx.undirected_gnp_random_graph(100, 0.1, seed=42))

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

import networkx as nx

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: 28075

Kodujemy graf z 1000 węzłami do 2-ciałowych korelacji macierzy Pauliego na 100 qubitach. Graf jest reprezentowany jako macierz korelacji, gdzie każdy węzeł jest zakodowany przez łańcuch Pauliego. Znak wartości oczekiwanej łańcucha Pauliego wskazuje na podział węzła. Na przykład węzeł 0 jest zakodowany przez łańcuch Pauliego $\prod_0 = I_{19} \otimes ... I_2 \otimes X_1 \otimes X_0$. Znak wartości oczekiwanej tego łańcucha Pauliego wskazuje na podział węzła 0. Definiujemy kodowanie korelacji Pauliego (PCE) względem $\prod$ jako

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

gdzie $x_i$ jest podziałem węzła $i$, a $\langle \prod_i \rangle \coloneqq \langle \psi |\prod_i| \psi \rangle$ jest wartością oczekiwaną łańcucha Pauliego kodującego węzeł $i$ nad stanem kwantowym $|\psi \rangle$. Teraz zakodujemy graf w Hamiltonian używając PCE. Dzielimy węzły na trzy zbiory: $S_1$, $S_2$ i $S_3$. Następnie kodujemy węzły w każdym zbiorze używając odpowiednio łańcuchów Pauliego $X$, $Y$ i $Z$.

num_qubits = 100

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("List 1:", node_x)
print("List 2:", node_y)
print("List 3:", node_z)

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, 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, 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, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332]
List 2: [333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665]
List 3: [666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999]

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
)

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

Circuit kwantowy

Tutaj stan $|\psi \rangle$ jest sparametryzowany przez $\mathbf{\theta}$, a my optymalizujemy te parametry $\mathbf{\theta}$ używając podejścia wariacyjnego. Ten samouczek używa ansatzu efficient_su2 dla naszego algorytmu wariacyjnego ze względu na jego ekspresywne możliwości i łatwość implementacji. Używamy również zrelaksowanej funkcji strat, która zostanie wprowadzona później w tym samouczku. Dzięki temu możemy rozwiązywać problemy na dużą skalę przy użyciu mniejszej liczby qubitów i płytszych głębokości Circuit.

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

# Optimize the circuit

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

Funkcja strat

Dla funkcji strat $\mathcal{L}$ używamy relaksacji funkcji celu Max-Cut opisanej w [1], która jest zdefiniowana jako $\mathcal{V}(\mathbf{x}) \coloneqq \sum_{(i, j) \in E} W_{i, j}(1-x_i x_j)$. Tutaj $W_{i, j}$ oznacza wagę krawędzi $(i, j)$, a $x_i$ reprezentuje podział węzła $i$. Funkcja strat $\mathcal{L}$ jest dana wzorem:

$\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})}$

gdzie funkcja celu Max-Cut jest zastąpiona przez gładkie tangensy hiperboliczne wartości oczekiwanych łańcuchów Pauliego kodujących węzły. Człon regularyzacyjny $\mathcal{L}^{(\text{reg})}$ i współczynnik przeskalowania $\alpha$, proporcjonalny do liczby qubitów, są wprowadzone w celu poprawy wydajności solvera.

Człon regularyzacyjny jest zdefiniowany jako:

$\mathcal{L}^{(\text{reg})}$ jest zdefiniowany jako $\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$

gdzie $\beta=1/2$, $\nu = |E|/2 + (m -1) /4$, a $m$ jest liczbą węzłów w grafie.

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

Krok 3: Wykonanie przy użyciu prymitywów Qiskit

W tym samouczku ustawiamy max_iter=50 dla pętli optymalizacyjnej w celach demonstracyjnych. Jeśli zwiększymy liczbę iteracji, możemy oczekiwać lepszych wyników.

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 Session

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

    experiment_result = []

    def loss_func(x):
        return loss_func_estimator(
            x, qc, [pce[0], pce[1], pce[2]], estimator, graph
        )

    np.random.seed(42)
    initial_params = np.random.rand(qc.num_parameters)
    result = minimize(
        loss_func, initial_params, method="COBYLA", options={"maxiter": 50}
    )
print(result)

Iter 0: 16659.649201600296
Iter 1: 12104.242957555361
Iter 2: 6541.137221994661
Iter 3: 6650.6188244671985
Iter 4: 7033.193518185085
Iter 5: 6743.687931793412
Iter 6: 6223.574718684094
Iter 7: 6457.3302709535965
Iter 8: 6581.316449107595
Iter 9: 6365.761052029896
Iter 10: 6415.872673527322
Iter 11: 6421.996561600348
Iter 12: 6636.372822791712
Iter 13: 6965.174320702346
Iter 14: 6774.236562696287
Iter 15: 6393.837617108355
Iter 16: 6234.311401676519
Iter 17: 6518.192237615901
Iter 18: 6559.933925068997
Iter 19: 6646.157979243488
Iter 20: 6573.726111605048
Iter 21: 6190.642092901959
Iter 22: 6653.06500163594
Iter 23: 6545.713700369988
Iter 24: 6399.996441760465
Iter 25: 6115.959687941808
Iter 26: 6665.915093554849
Iter 27: 6832.882201259893
Iter 28: 6541.392749578919
Iter 29: 6813.3456910443165
Iter 30: 6460.800944368402
Iter 31: 6359.635437029245
Iter 32: 6040.891641882451
Iter 33: 6573.930674936448
Iter 34: 6668.031753293785
Iter 35: 6450.002712889748
Iter 36: 6519.8298811058075
Iter 37: 6467.134502398199
Iter 38: 6655.284651397334
Iter 39: 6371.168353987336
Iter 40: 6480.337259347923
Iter 41: 6339.256786764425
Iter 42: 6588.635046825541
Iter 43: 6617.677964971322
Iter 44: 6469.0441600679205
Iter 45: 6567.874244906106
Iter 46: 6217.899975264532
Iter 47: 6783.481394627947
Iter 48: 6813.371853626112
Iter 49: 6506.5871531488765
 message: Maximum number of function evaluations has been exceeded.
 success: False
  status: 2
     fun: 6040.891641882451
       x: [ 1.375e+00  1.951e+00 ...  1.923e-01  4.087e-02]
    nfev: 50
   maxcv: 0.0

Krok 4: Przetwarzanie końcowe i zwrot wyniku w pożądanym formacie klasycznym

Podziały węzłów wyznaczane są poprzez ocenę znaku wartości oczekiwanych łańcuchów Pauliego kodujących węzły.

# Calculate the partitions based on the final expectation values
# If the expectation value is positive, the node belongs to partition 0 (par0)
# Otherwise, the node belongs to partition 1 (par1)

par0, par1 = set(), set()

for i in experiment_result[-1]["exp_map"]:
    if experiment_result[-1]["exp_map"][i] >= 0:
        par0.add(i)
    else:
        par1.add(i)
print(par0, par1)

{0, 1, 4, 8, 9, 10, 12, 13, 14, 15, 16, 18, 25, 27, 31, 32, 34, 36, 38, 39, 40, 41, 44, 46, 47, 48, 49, 50, 51, 52, 57, 60, 61, 62, 63, 64, 65, 66, 68, 71, 79, 81, 82, 86, 88, 91, 92, 93, 94, 95, 96, 99, 100, 105, 106, 107, 112, 114, 115, 121, 123, 129, 133, 134, 145, 147, 161, 165, 166, 168, 171, 173, 184, 185, 187, 188, 192, 193, 194, 196, 197, 198, 202, 205, 206, 207, 208, 209, 210, 211, 215, 217, 218, 219, 220, 221, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 238, 241, 242, 243, 244, 246, 247, 248, 249, 251, 252, 253, 255, 256, 257, 258, 259, 261, 262, 264, 265, 266, 268, 269, 270, 272, 273, 275, 276, 277, 278, 279, 281, 283, 284, 285, 286, 288, 292, 293, 294, 299, 300, 303, 305, 306, 307, 308, 310, 312, 313, 314, 316, 317, 319, 321, 326, 327, 328, 333, 336, 338, 340, 341, 342, 344, 345, 346, 349, 351, 352, 353, 356, 357, 360, 361, 362, 363, 364, 366, 368, 370, 374, 378, 379, 380, 381, 382, 383, 384, 386, 387, 388, 389, 390, 391, 393, 394, 395, 396, 397, 398, 404, 405, 406, 409, 411, 413, 415, 416, 418, 421, 425, 426, 427, 428, 429, 433, 434, 435, 437, 444, 450, 456, 457, 458, 459, 462, 463, 465, 467, 469, 470, 472, 476, 479, 484, 487, 489, 492, 493, 497, 498, 499, 502, 506, 508, 513, 516, 517, 518, 519, 521, 523, 526, 527, 528, 531, 532, 533, 535, 536, 537, 539, 540, 541, 542, 543, 544, 545, 547, 549, 550, 552, 557, 562, 563, 564, 565, 567, 568, 569, 570, 571, 572, 573, 576, 578, 579, 580, 583, 585, 587, 588, 589, 591, 595, 596, 597, 600, 602, 603, 604, 605, 606, 607, 608, 609, 610, 612, 618, 619, 623, 624, 625, 626, 627, 628, 630, 632, 636, 637, 640, 644, 646, 649, 652, 656, 657, 658, 659, 661, 662, 663, 664, 667, 669, 670, 671, 672, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 692, 693, 694, 695, 696, 698, 700, 701, 703, 706, 707, 708, 709, 712, 713, 714, 716, 717, 718, 719, 721, 722, 723, 724, 725, 726, 728, 730, 731, 733, 734, 735, 737, 739, 740, 741, 743, 744, 746, 748, 750, 751, 752, 753, 754, 758, 760, 761, 762, 763, 764, 765, 766, 774, 778, 780, 782, 787, 795, 800, 802, 803, 808, 809, 812, 818, 822, 825, 827, 834, 836, 840, 843, 845, 847, 850, 853, 854, 857, 858, 863, 864, 865, 866, 867, 868, 869, 870, 872, 873, 874, 875, 876, 878, 880, 881, 882, 883, 884, 885, 887, 888, 889, 890, 891, 893, 894, 895, 896, 898, 901, 902, 903, 904, 905, 907, 908, 910, 911, 912, 913, 914, 915, 916, 917, 918, 920, 921, 923, 925, 926, 928, 929, 930, 932, 934, 935, 936, 938, 939, 941, 943, 945, 946, 947, 948, 949, 953, 955, 956, 957, 958, 959, 961, 966, 975, 978, 980, 983, 988, 990, 996, 999} {2, 3, 5, 6, 7, 11, 17, 19, 20, 21, 22, 23, 24, 26, 28, 29, 30, 33, 35, 37, 42, 43, 45, 53, 54, 55, 56, 58, 59, 67, 69, 70, 72, 73, 74, 75, 76, 77, 78, 80, 83, 84, 85, 87, 89, 90, 97, 98, 101, 102, 103, 104, 108, 109, 110, 111, 113, 116, 117, 118, 119, 120, 122, 124, 125, 126, 127, 128, 130, 131, 132, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 146, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 162, 163, 164, 167, 169, 170, 172, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 186, 189, 190, 191, 195, 199, 200, 201, 203, 204, 212, 213, 214, 216, 222, 223, 224, 237, 239, 240, 245, 250, 254, 260, 263, 267, 271, 274, 280, 282, 287, 289, 290, 291, 295, 296, 297, 298, 301, 302, 304, 309, 311, 315, 318, 320, 322, 323, 324, 325, 329, 330, 331, 332, 334, 335, 337, 339, 343, 347, 348, 350, 354, 355, 358, 359, 365, 367, 369, 371, 372, 373, 375, 376, 377, 385, 392, 399, 400, 401, 402, 403, 407, 408, 410, 412, 414, 417, 419, 420, 422, 423, 424, 430, 431, 432, 436, 438, 439, 440, 441, 442, 443, 445, 446, 447, 448, 449, 451, 452, 453, 454, 455, 460, 461, 464, 466, 468, 471, 473, 474, 475, 477, 478, 480, 481, 482, 483, 485, 486, 488, 490, 491, 494, 495, 496, 500, 501, 503, 504, 505, 507, 509, 510, 511, 512, 514, 515, 520, 522, 524, 525, 529, 530, 534, 538, 546, 548, 551, 553, 554, 555, 556, 558, 559, 560, 561, 566, 574, 575, 577, 581, 582, 584, 586, 590, 592, 593, 594, 598, 599, 601, 611, 613, 614, 615, 616, 617, 620, 621, 622, 629, 631, 633, 634, 635, 638, 639, 641, 642, 643, 645, 647, 648, 650, 651, 653, 654, 655, 660, 665, 666, 668, 673, 691, 697, 699, 702, 704, 705, 710, 711, 715, 720, 727, 729, 732, 736, 738, 742, 745, 747, 749, 755, 756, 757, 759, 767, 768, 769, 770, 771, 772, 773, 775, 776, 777, 779, 781, 783, 784, 785, 786, 788, 789, 790, 791, 792, 793, 794, 796, 797, 798, 799, 801, 804, 805, 806, 807, 810, 811, 813, 814, 815, 816, 817, 819, 820, 821, 823, 824, 826, 828, 829, 830, 831, 832, 833, 835, 837, 838, 839, 841, 842, 844, 846, 848, 849, 851, 852, 855, 856, 859, 860, 861, 862, 871, 877, 879, 886, 892, 897, 899, 900, 906, 909, 919, 922, 924, 927, 931, 933, 937, 940, 942, 944, 950, 951, 952, 954, 960, 962, 963, 964, 965, 967, 968, 969, 970, 971, 972, 973, 974, 976, 977, 979, 981, 982, 984, 985, 986, 987, 989, 991, 992, 993, 994, 995, 997, 998}

Możemy obliczyć rozmiar cięcia problemu Max-Cut, korzystając z podziałów węzłów.

cut_size = calc_cut_size(graph, par0, par1)
print(f"Cut size: {cut_size}")

Cut size: 24682

Po zakończeniu treningu wykonujemy jedną rundę wyszukiwania z zamianą pojedynczych bitów w celu poprawy rozwiązania jako klasyczny etap przetwarzania końcowego. W tym procesie zamieniamy podziały dwóch węzłów i oceniamy rozmiar cięcia. Jeśli rozmiar cięcia się poprawia, zachowujemy zamianę. Powtarzamy ten proces dla wszystkich możliwych par węzłów połączonych krawędzią.

best_bits = []
cur_bits = []

for i in experiment_result[-1]["exp_map"]:
    if experiment_result[-1]["exp_map"][i] >= 0:
        cur_bits.append(1)
    else:
        cur_bits.append(0)
print(cur_bits)

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

# Swap the partitions and calculate the cut size
best_cut = 0
for edge0, edge1 in graph.edge_list():
    swapped_bits = cur_bits.copy()
    swapped_bits[edge0], swapped_bits[edge1] = (
        swapped_bits[edge1],
        swapped_bits[edge0],
    )

    cur_partition = [set(), set()]
    for i, bit in enumerate(swapped_bits):
        if bit > 0:
            cur_partition[0].add(i)
        else:
            cur_partition[1].add(i)
    cut_size = calc_cut_size(graph, cur_partition[0], cur_partition[1])
    if best_cut < cut_size:
        best_cut = cut_size
        best_bits = swapped_bits

print(best_cut, best_bits)

24733 [1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1]

Odniesienia

[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.

Ankieta dotycząca samouczka

Wypełnij tę krótką ankietę, aby podzielić się opinią na temat tego samouczka. Twoje spostrzeżenia pomogą nam udoskonalić ofertę treści i doświadczenia użytkownika.

Link do ankiety

Note: This survey is provided by IBM Quantum and relates to the original English content. To give feedback on doQumentation's website, translations, or code execution, please open a GitHub issue.