パウリ相関エンコーディングによる max-cut の要求リソース削減#
パウリ相関エンコーディングを使って、量子計算により効率よく最適化問題を量子ビットへ符号化します。
使用量の目安: Eagle r3 プロセッサで 35 分（注意: これはあくまで目安です。実際の実行時間は異なる場合があります。）
学習成果#
このチュートリアルを終えると、次の成果が得られます。
多体パウリ文字列によって古典的な最適化問題を多項式的に圧縮できる仕組みを含め、パウリ相関エンコーディング（PCE）の背後にある理論的な原理を理解する。
PCE を実際に実装し、近未来の量子ハードウェア上で大規模な最適化問題を符号化して解く。
前提知識#
このチュートリアルに進む前に、次のトピックについて理解しておくことをお勧めします。
背景#
このチュートリアルでは、量子計算においてより効率よく最適化問題を量子ビットへ符号化するために設計された手法である パウリ相関エンコーディング（PCE）[1] を紹介します。PCE は最適化問題における古典変数を多体パウリ行列の相関へ写像し、その結果として問題の空間要求量を多項式的に圧縮します。PCE を用いることで符号化に必要な量子ビット数が削減されるため、量子ビットのリソースが限られた近未来の量子デバイスにとって特に有利です。さらに、PCE が本質的にバレンプラトー（barren plateau）を緩和し、この現象に対して超多項式的な耐性をもつことが解析的に示されています。この組み込みの特性により、量子最適化ソルバーにおいてこれまでにない性能が可能になります。
概要#
PCE のアプローチは、以下に示す [1] の図 1 のとおり、3 つの主要なステップから成ります。
最適化問題をパウリ相関空間へ符号化する。
量子・古典ハイブリッドの最適化ソルバーを使って問題を解く。
解を元の最適化空間へ復号する。 PCE のアプローチは、パウリ相関行列を扱える任意の量子最適化ソルバーに適用できます。
[1] の図 1 では、PCE のアプローチを説明する例として max-cut 問題が使われています。\(m=9\) ノードの max-cut 問題がパウリ相関空間へ符号化され、最適化問題が相関行列として、具体的には \(n=3\) 量子ビット \((Q_1, Q_2, Q_3)\) にわたる 2 体のパウリ行列相関として表現されます。ノードの色は、符号化された各ノードに使われるパウリ文字列を示します。 たとえば、2 値変数 \(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\) 次（\(k>1\)）の多項式的な圧縮が可能になります。選ばれたパウリ集合は、互いに可換なパウリ文字列の 3 つの部分集合から成り、これにより \(m\) 個すべての相関をわずか 3 通りの測定設定で実験的に推定できます。
続いて、元の max-cut の目的関数を模倣する、パウリ期待値の損失関数 \(\mathcal{L}\) を構成します。この損失関数を 変分量子固有値ソルバー（VQE） などの量子・古典ハイブリッド最適化ソルバーで最適化します。
最適化が完了したら、解を元の最適化空間へ復号し、最適な max-cut の解を得ます。
要件#
このチュートリアルを始める前に、次のものがインストールされていることを確認してください。
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):
"""与えられたグラフの分割に対するカットサイズを計算する。"""
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"使用するバックエンド: {backend.name}")
We are using the aer_simulator_from(ibm_pittsburgh)
ステップ 1: 古典的な入力を量子問題へマッピングする#
max-cut 問題#
max-cut 問題は、グラフ \(G = (V, E)\) 上で定義される組合せ最適化問題です。ここで \(V\) は頂点の集合、\(E\) は辺の集合です。目標は、2 つの集合 \(S\) と \(V \setminus S\) の間の辺の数が最大になるように頂点を分割することです。 max-cut 問題の詳しい説明は、量子近似最適化アルゴリズム のチュートリアルを参照してください。 max-cut 問題は QAOA の高度な手法 のチュートリアルでも例として使われています。 これらのチュートリアルでは、max-cut 問題を解くために 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)
<Image src="/docs/images/tutorials/pauli-correlation-encoding-for-qaoa/extracted-outputs/37edb718-2bab-49d7-ad66-5f2f67d2aeff-0.avif" alt="Output of the previous code cell" />
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"初期のカットサイズ: {curr_cut_size}")
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\) の 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"量子ビット数: {num_qubits}")
print("リスト 1:", node_x)
print("リスト 2:", node_y)
print("リスト 3:", node_z)
Number of qubits: 9
List 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
List 2: [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65]
List 3: [66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
def build_pauli_correlation_encoding(pauli, node_list, n, k=2):
pauli_correlation_encoding = []
for idx, c in enumerate(combinations(range(n), k)):
if idx >= len(node_list):
break
paulis = ["I"] * n
paulis[c[0]], paulis[c[1]] = pauli, pauli
pauli_correlation_encoding.append(("".join(paulis)[::-1], 1))
hamiltonian = []
for pauli, weight in pauli_correlation_encoding:
hamiltonian.append(SparsePauliOp.from_list([(pauli, weight)]))
return hamiltonian
pauli_correlation_encoding_x = build_pauli_correlation_encoding(
"X", node_x, num_qubits
)
pauli_correlation_encoding_y = build_pauli_correlation_encoding(
"Y", node_y, num_qubits
)
pauli_correlation_encoding_z = build_pauli_correlation_encoding(
"Z", node_z, num_qubits
)
ステップ 2: 量子ハードウェア実行に向けて問題を最適化する#
量子回路#
ここでは状態 \(|\psi \rangle\) を \(\mathbf{\theta}\) でパラメーター化し、これらのパラメーター \(\mathbf{\theta}\) を変分的なアプローチで最適化します。
このチュートリアルでは、その表現力と実装の容易さから、変分アルゴリズムに efficient_su2 ansatz を採用します。
また、このチュートリアルで後ほど紹介する緩和された損失関数も使用します。
その結果、より少ない量子ビット数と浅い回路深さで、大規模な問題に取り組めます。
# 量子回路を構築する
qc = efficient_su2(num_qubits, su2_gates=["ry", "rz"], reps=2)
qc.draw("mpl")
<Image src="/docs/images/tutorials/pauli-correlation-encoding-for-qaoa/extracted-outputs/035f6b4a-4de0-452a-b60f-7260f9e3103a-0.avif" alt="Output of the previous code cell" />
# 回路を最適化する
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):
"""
与えられた ansatz、ハミルトニアン、グラフに対して、指定された損失関数を
計算する。
まず、量子バックエンド上で ansatz を実行して、ハミルトニアン内の各パウリ
文字列の期待値を求める。次に、それらの期待値を非線形関数
tanh(alpha * prod_i) に通す。損失関数は、こうして変換された値から
計算される。
"""
job = estimator.run(
[
(ansatz, hamiltonian[0], x),
(ansatz, hamiltonian[1], x),
(ansatz, hamiltonian[2], x),
]
)
result = job.result()
# 損失関数を計算する
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"反復 {len(experiment_result)}: {loss}")
experiment_result.append({"loss": loss, "exp_map": node_exp_map})
return loss
ステップ 3: Qiskit プリミティブを使って実行する#
このチュートリアルでは、デモンストレーションのために最適化ループで 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)
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: 後処理を行い、望ましい古典的形式で結果を返す#
各ノードの分割は、そのノードを符号化するパウリ文字列の期待値の符号を評価することで決まります。
# 最終的な期待値に基づいて分割を計算する
# 期待値が正であれば、そのノードは分割 0（par0）に属する
# そうでなければ、そのノードは分割 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)
{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}
ノードの分割を使って、max-cut 問題のカットサイズを計算できます。
cut_size = calc_cut_size(graph, par0, par1)
print(f"カットサイズ: {cut_size}")
Cut size: 268
学習が完了したら、古典的な後処理として、解を改善するために 1 ビットのスワップ探索を 1 巡実行します。 この処理では 2 つのノードの分割を入れ替えてカットサイズを評価します。カットサイズが改善されればそのスワップを採用します。これを、辺で結ばれたすべてのノードの組について繰り返します。
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)
[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]
# 分割を入れ替えてカットサイズを計算する
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)
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]
大規模なハードウェアでの例#
# -------------------------ステップ 1-------------------------
num_nodes = 1500 # グラフのノード数
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"使用する量子ビット数: {num_qubits}")
# -------------------------ステップ 2-------------------------
backend = real_backend
print(f"使用するバックエンド: {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)
# -------------------------ステップ 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]
)
# セッションを使って最適化を実行する。
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)
# -------------------------ステップ 4-------------------------
par0, par1, best_index = get_partitions(experiment_result)
cut_size = calc_cut_size(graph, par0, par1)
print(f"カットサイズ: {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(
f"{num_nodes} ノードのグラフに対して {num_qubits} 量子ビットで得られた "
f"最良の max-cut 値は {best_cut} です"
)
print(f"また、得られた具体的な分割は {best_bits} です")
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., 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.
チュートリアルアンケート#
このチュートリアルへのフィードバックのため、短いアンケートにご協力ください。いただいたご意見は、コンテンツとユーザー体験の改善に役立てられます。
© IBM Corp. 2024-2026
© IBM Corp., 2017-2026