최대 절단 요구 사항을 줄이기 위한 파울리 상관 인코딩

예상 소요 시간: Eagle r3 프로세서 기준 35분 (참고: 이는 예상치에 불과합니다.) (실행 시간은 다를 수 있습니다.)

학습 성과

다체 파울리 스트링이 어떻게 고전적 최적화 문제의 다항식 차수 압축을 가능하게 하는지 포함하여, 파울리 상관 인코딩(PCE)의 이론적 원리를 이해한다.
실제 환경에서 PCE를 구현하여, 가까운 시일 내에 상용화될 양자 하드웨어에서 대규모 최적화 문제를 인코딩하고 해결한다.

전제조건

배경

이 튜토리얼에서는 최적화 문제를 양자 연산에 더 효율적으로 큐비트로 인코딩하도록 설계된 접근 방식인 폴리 상관관계 인코딩 (PCE) [1] 을 소개합니다. PCE는 최적화 문제의 기존 변수를 다항식 폴리 행렬 상관관계에 매핑하여 문제의 공간 요구 사항을 다항식으로 압축합니다. PCE를 사용하면 인코딩에 필요한 큐비트 수가 줄어들어 큐비트 리소스가 제한된 단기 양자 장치에 특히 유리합니다. 또한, PCE는 본질적으로 불모지를 완화하여 이러한 현상에 대한 초다항식 복원력을 제공한다는 것이 분석적으로 입증되었습니다. 이 기본 제공 기능을 통해 양자 최적화 솔버에서 전례 없는 성능을 구현할 수 있습니다.

개요

PCE 접근법은 아래 [1] 의 그림 1에 나와 있는 바와 같이 세 가지 주요 단계로 구성됩니다:

최적화 문제를 폴리 상관 관계 공간으로 인코딩합니다.
양자 고전 최적화 솔버를 사용하여 문제를 해결합니다.
솔루션을 원래 최적화 공간으로 다시 디코딩합니다. PCE 접근 방식은 폴리 상관 행렬을 처리할 수 있는 모든 양자 최적화 솔버에 적용할 수 있습니다.

[1] 의 그림 1에서는 PCE 접근법을 설명하기 위해 최대 절단 문제를 예시로 사용하였다. $m=9$ 개의 노드를 가진 최대 절단 문제는 파울리 상관 공간으로 인코딩되며, 이는 최적화 문제를 상관 행렬로 표현합니다. 구체적으로, 이는 $n=3$ 큐비트 간 2체 파울리 행렬 상관관계입니다. $(Q_1, Q_2, Q_3)$ . 노드의 색상은 각 인코딩된 노드에 사용된 파울리 문자열을 나타냅니다. 예를 들어, 이진 변수 $x_1$ 에 해당하는 노드 1은 $Z_1 \otimes Z_2 \otimes I_3$ 의 기대값으로 인코딩되는 반면, $x_8$ 는 $I_1 \otimes Y_2 \otimes Y_3$ 로 인코딩됩니다. 이는 문제의 $m$ 개 변수를 $n = O(m^{1/2})$ 개의 큐비트로 압축하는 것과 같습니다. 더 넓게 보면, $k$ -체 상관관계는 $k>1$ 인 경우, $k$ 차원의 다항식 압축을 가능하게 한다. 선택된 파울리 집합은 서로 교환하는 파울리 문자열의 세 부분집합으로 구성되어 있어, 단 세 가지 측정 설정만으로 모든 $m$ 상관관계를 실험적으로 추정할 수 있다.

원래의 최대 절단(max-cut) 목적 함수를 모방하는 파울리 기대값의 손실 함수 $\mathcal{L}$ 가 구성된다. 그런 다음 손실 함수는 변분 양자 고유값 해법기(VQE)와 같은 양자-고전 최적화 솔버를 사용하여 최적화됩니다.

최적화가 완료되면, 해는 원래의 최적화 공간으로 다시 디코딩되어 최적의 최대 절단 해를 산출합니다.

요구사항

이 튜토리얼을 시작하기 전에 다음이 설치되어 있는지 확인하세요:

Qiskit SDK v1.0 또는 이후 버전, 시각화 지원 기능 포함
Qiskit Runtime v0.22 또는 이후 (pip install qiskit-ibm-runtime)

설정

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

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

소규모 시뮬레이터 예시

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}")

Output:

We are using the aer_simulator_from(ibm_pittsburgh)

1단계: 고전적 입력을 양자 문제에 매핑하기

최대 절단 문제

최대 절단 문제(max-cut problem)는 그래프 $G = (V, E)$ 위에서 정의되는 조합 최적화 문제로, 여기서 $V$ 는 정점의 집합이고 $E$ 는 변의 집합이다. 목표는 정점들을 두 집합, $S$ 와 $V \setminus S$ 로 나누되, 두 집합 사이의 변의 개수가 최대가 되도록 하는 것이다. 맥스컷(max-cut) 문제에 대한 자세한 설명은 양자 근사 최적화 알고리즘 튜토리얼을 참고하시기 바랍니다. 최대 절단 문제(max-cut problem)는 QAOA(Quantum Annealing)를 위한 고급 기법 튜토리얼에서도 예시로 사용됩니다. 해당 튜토리얼에서는 QAOA 알고리즘을 사용하여 최대 절단 문제를 해결합니다.

그래프 -> 해밀턴 그래프

먼저 노드가 100개인 무작위 그래프를 생각해 보자.

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)

Output:

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}")

Output:

Initial cut size: 345

우리는 100개의 노드로 구성된 그래프를 9개의 큐비트에 걸친 2체 파울리 행렬 상관관계로 인코딩합니다(아래 설명 참조). 이 그래프는 상관 행렬로 표현되며, 각 노드는 파울리 문자열로 인코딩됩니다. 파울리 끈의 기대값의 부호는 노드의 분할을 나타낸다. 예를 들어, 노드 0은 파울리 문자열 $\prod_0 = I_{8} \otimes ... I_2 \otimes X_1 \otimes X_0$ 로 표현됩니다. 이 파울리 문자열의 기대값의 부호는 노드 0의 분할을 나타냅니다. 우리는 양자 얽힘( $\prod$ )에 대한 파울리 상관 인코딩 (PCE)을 다음과 같이 정의한다

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

여기서 $x_i$ 는 노드 $i$ 의 파티션이고 $\langle \prod_i \rangle \coloneqq \langle \psi |\prod_i| \psi \rangle$ 는 양자 상태 $|\psi \rangle$ 에 대한 폴리 문자열 인코딩 노드 $i$ 의 기대값입니다.

이제 PCE를 사용하여 그래프를 해밀턴으로 인코딩해 보겠습니다. 노드를 세 가지 세트로 나눕니다: $S_1$ , $S_2$ , $S_3$ 로 나눕니다. 그런 다음 각 세트의 노드를 각각 $X$ , $Y$ , $Z$ 로 폴리 문자열을 사용하여 인코딩합니다.

모든 노드를 인코딩하는 데 필요한 노드 수와 큐비트 수 간의 관계를 도출해야 합니다. 인코딩에 가능한 모든 순열을 적용하면 다음과 같은 결과가 나옵니다:

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

이 예제에서는 $k=2$ 를 고려하므로,

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

따라서, 특정 수의 노드 $m$ 를 표현하는 데 필요한 큐비트 수 $n$ 는 다음과 같이 계산됩니다:

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

$\lceil \cdot \rceil$ 기호는 천장 함수를 나타내며, 이는 모든 실수를 다음 정수로 올림합니다. 이를 통해 큐비트의 개수가 정수가 되도록 보장합니다.

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)

Output:

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
)

2단계: 양자 하드웨어 실행을 위한 문제 최적화

양자 회로

여기서 상태 $|\psi \rangle$ 는 $\mathbf{\theta}$ 로 매개변수화되고, 가변적 접근 방식을 사용하여 이러한 매개변수 $\mathbf{\theta}$ 를 최적화합니다. 이 튜토리얼에서는 표현력과 구현의 용이성 때문에 변형 알고리즘에 efficient_su2 ansatz를 사용합니다. 또한 이 튜토리얼의 뒷부분에서 소개할 완화된 손실 기능도 사용합니다. 그 결과, 더 적은 큐비트와 더 얕은 회로 깊이로 대규모 문제를 해결할 수 있습니다.

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

Output:

# Optimize the circuit

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

손실 함수

손실 함수 $\mathcal{L}$ 의 경우, [1] 에 설명된 대로 최대 절단(max-cut) 목적 함수의 완화 형태를 사용하며, 이는 $\mathcal{V}(\mathbf{x}) \coloneqq \sum_{(i, j) \in E} W_{i, j}(1-x_i x_j)$ 로 정의된다. 여기서 $W_{i, j}$ 는 변 $(i, j)$ 의 가중치를 나타내고, $x_i$ 는 노드 $i$ 의 분할을 나타낸다. 손실 함수 $\mathcal{L}$ 는 다음과 같이 주어진다:

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

여기서 최대 절단(max-cut) 목적 함수는 노드를 인코딩하는 파울리 스트링의 기대값에 대한 부드러운 쌍곡 탄젠트 함수로 대체된다. 해법기의 성능을 향상시키기 위해 정규화 항 $\mathcal{L}^{(\text{reg})}$ 과 큐비트 수에 비례하는 재스케일링 계수 $\alpha$ 를 도입한다.

정규화 용어는 다음과 같이 정의됩니다:

$\mathcal{L}^{(\text{reg})}$ 는 다음과 같이 정의됩니다 $\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$

여기서 $\beta=1/2$ , $\nu = |E|/2 + (m -1) /4$ , $|E|$ 는 변의 개수이며, $m$ 는 그래프의 정점 개수이다.

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

3단계: `Qiskit primitives` 명령어로 실행합니다

이 튜토리얼에서는 설명을 위해 최적화 루프에서 를 설정합니다 max_iter=50 . 반복 횟수를 늘리면 더 나은 결과를 기대할 수 있습니다.

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)

Output:

Iter 0: 159.88755362682548
Iter 1: 113.46202580636677
Iter 2: 56.76494226400048
Iter 3: 32.63357946896002
Iter 4: 21.517837239610117
Iter 5: 30.96034960483569
Iter 6: 20.780475923938027
Iter 7: 24.54251816279811
Iter 8: 27.834486461763042
Iter 9: 16.705460776812693
Iter 10: 18.020587887236864
Iter 11: 12.252379762741352
Iter 12: 5.253885750886939
Iter 13: 6.985984759592262
Iter 14: 6.908717244584757
Iter 15: 12.915466016863858
Iter 16: 4.105776920457279
Iter 17: 11.707504530740305
Iter 18: 7.154360511076546
Iter 19: 10.3890865704735
Iter 20: 10.376147647857252
Iter 21: 2.533430195296697
Iter 22: 3.8612421907795462
Iter 23: 6.103735057461906
Iter 24: -1.1190368234312347
Iter 25: 6.125915279494738
Iter 26: 11.086280445482455
Iter 27: 10.102569882302827
Iter 28: -0.02664415648133822
Iter 29: 7.621887727398785
Iter 30: 5.967346615554497
Iter 31: 3.85345716014828
Iter 32: 4.5494846149011
Iter 33: 10.006668112637232
Iter 34: -3.1927138938527877
Iter 35: 2.8829882366285116
Iter 36: 3.3130087521654144
Iter 37: -4.907566569808272
Iter 38: -4.980134722109894
Iter 39: -2.990457463896541
Iter 40: -5.938401817344579
Iter 41: -2.1807712386469724
Iter 42: -1.0945774380342126
Iter 43: -4.7548102593556685
Iter 44: -3.8762362299208144
Iter 45: -4.9348321021624
Iter 46: -6.487722842864011
Iter 47: 0.7064210113389331
Iter 48: -2.3428323031772216
Iter 49: -2.626032270380895
 message: Return from COBYLA because the objective function has been evaluated 50 times.
 success: False
  status: 3
     fun: -2.626032270380895
       x: [ 1.375e+00  1.951e+00 ...  9.395e-01  8.948e-01]
    nfev: 50

4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환

노드의 파티션은 노드를 인코딩하는 폴리 문자열의 기대 값의 부호를 평가하여 결정됩니다.

# 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)
def get_partitions(experiment_result):
    par0, par1 = set(), set()
    best_index = min(
        range(len(experiment_result)),
        key=lambda i: experiment_result[i]["loss"],
    )
    for i in experiment_result[best_index]["exp_map"]:
        if experiment_result[best_index]["exp_map"][i] >= 0:
            par0.add(i)
        else:
            par1.add(i)
    return par0, par1, best_index


par0, par1, best_index = get_partitions(experiment_result)
print(par0, par1)

Output:

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

노드의 분할을 활용하여 최대 절단 문제의 절단 크기를 계산할 수 있습니다.

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

Output:

Cut size: 268

훈련이 완료되면 고전적인 후처리 단계로 솔루션을 개선하기 위해 한 차례의 단일 비트 스왑 검색을 수행합니다. 이 과정에서 두 노드의 파티션을 교체하고 잘라낸 크기를 평가합니다. 컷 크기가 개선되면 스왑을 유지합니다. 에지로 연결된 모든 가능한 노드 쌍에 대해 이 과정을 반복합니다.

cur_bits = []

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

Output:

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

# Swap the partitions and calculate the cut size


def swap_partitions(graph, cur_bits):
    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],
        )

        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
    return best_cut, best_bits


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

Output:

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

대규모 하드웨어 예시

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

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="Return from COBYLA because the objective function "
            "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-------------------------

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

best_bits = []
cur_bits = []
for i in experiment_result[best_index]["exp_map"]:
    if experiment_result[best_index]["exp_map"][i] >= 0:
        cur_bits.append(1)
    else:
        cur_bits.append(0)
best_cut, best_bits = swap_partitions(graph, cur_bits)
# 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}")

Output:

We are using 33 qubits
We are using the ibm_pittsburgh
Iter 0: 57399.57543902076
Iter 1: 56458.787143794
Iter 2: 40778.45608998947
Iter 3: 35571.58511146131
Iter 4: 33861.6835761173
Iter 5: 39697.22637736274
Iter 6: 34984.77893767163
Iter 7: 32051.882157096858
Iter 8: 26134.153216063707
Iter 9: 24914.322627065787
Iter 10: 24030.21227315425
Iter 11: 23047.463945514
Iter 12: 22629.42866110748
Iter 13: 17374.859132614685
Iter 14: 18020.11637762458
Iter 15: 17924.7066364044
Iter 16: 15825.1992250984
Iter 17: 16553.346711978447
Iter 18: 12393.565736512377
Iter 19: 11994.021456089155
Iter 20: 11199.994322735669
Iter 21: 9624.895532927634
Iter 22: 9073.811130188606
Iter 23: 9836.721241931278
Iter 24: 10555.925186133794
Iter 25: 9179.1179493286
Iter 26: 8495.394826965305
Iter 27: 8913.688189840399
Iter 28: 7830.448471810181
Iter 29: 7757.430542422075
Iter 30: 6796.187594518731
Iter 31: 7307.985913766867
Iter 32: 7340.225833330675
Iter 33: 7064.731899380469
Iter 34: 7632.270657372515
Iter 35: 7049.154710767935
Iter 36: 7486.118442084411
Iter 37: 6302.12602219333
Iter 38: 6244.934230209166
Iter 39: 7154.9748739261395
Iter 40: 6482.109600054041
Iter 41: 5718.475169152395
Iter 42: 5693.008457857462
Iter 43: 4869.782667921923
Iter 44: 4957.625304450959
Iter 45: 5582.240637063214
Iter 46: 4983.90082772116
Iter 47: 5416.268575648202
Iter 48: 4809.98398457807
Iter 49: 5092.527306646118
 message: Return from COBYLA because the objective function has been evaluated 50 times.
 success: False
  status: 3
     fun: 5092.527306646118
       x: [ 1.375e+00  1.951e+00 ...  7.259e-01  8.971e-01]
    nfev: 50
Cut size: 56152
The best max-cut value achieved for a graph with 1500 nodes on 33 qubits is 56219
and the specific partition we obtained is [1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 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, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

다음 단계

권장사항

이 글이 흥미로웠다면, 다음 자료도 관심 있게 읽어보시기 바랍니다:

참조

[1] Sciorilli, M., 보르헤스, L., 패티, T. L., 가르시아-마르틴, D., 카밀로, G., 아난드쿠마르, A., & 아올리타, L. (2024). 소수의 큐비트를 활용한 대규모 양자 최적화 솔버를 향하여. arXiv 사전 출판본 arXiv:2401.09421.

튜토리얼 설문조사

이 튜토리얼에 대한 피드백을 제공하려면 간단한 설문조사에 참여해 주세요. 여러분의 인사이트는 콘텐츠 제공과 사용자 경험을 개선하는 데 도움이 됩니다.

설문조사 링크

이 페이지가 도움이 되었습니까?

GitHub에서 버그, 오타를 보고하거나 컨텐츠를 요청하십시오.

최대 절단 요구 사항을 줄이기 위한 파울리 상관 인코딩

학습 성과

전제조건

배경

개요

요구사항

설정

소규모 시뮬레이터 예시

1단계: 고전적 입력을 양자 문제에 매핑하기

최대 절단 문제

그래프 -> 해밀턴 그래프

2단계: 양자 하드웨어 실행을 위한 문제 최적화

양자 회로

손실 함수

3단계: Qiskit primitives 명령어로 실행합니다

4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환

대규모 하드웨어 예시

다음 단계

참조

튜토리얼 설문조사

3단계: `Qiskit primitives` 명령어로 실행합니다