グラフ彩色問題

グラフ彩色問題#

このチュートリアルでは、量子近似最適化アルゴリズム（QAOA）を用いてグラフ彩色問題を解きます。

まず、使用する主要なライブラリをインストールし、インポートしましょう。

# !pip install qamomile[qiskit, quri_parts]

import jijmodeling as jm
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import ommx.v1
import qiskit.primitives as qk_pr
import scipy.optimize as opt

import qamomile.core as qm
from qamomile.core.circuit.drawer import plot_quantum_circuit
from qamomile.qiskit import QiskitTranspiler

数理モデルの構築#

まず、JijModelingを用いてグラフ彩色問題の数理モデルを実装します。

def graph_coloring_problem() -> jm.Problem:
    # 変数を定義する
    V = jm.Placeholder("V")
    E = jm.Placeholder("E", ndim=2)
    N = jm.Placeholder("N")
    x = jm.BinaryVar("x", shape=(V, N))
    n = jm.Element("i", belong_to=(0, N))
    v = jm.Element("v", belong_to=(0, V))
    e = jm.Element("e", belong_to=E)
    # 問題を設定する
    problem = jm.Problem("Graph Coloring")
    # 各頂点がちょうど1つの色を持つようにする one-hot 制約を設定する
    problem += jm.Constraint("one-color", x[v, :].sum() == 1, forall=v)
    # エッジでつながれた頂点が同じ色になる数を最小化する目的関数を設定する
    problem += jm.sum([n, e], x[e[0], n] * x[e[1], n])
    return problem

problem = graph_coloring_problem()
problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Graph Coloring} & & \\& & \min \quad \displaystyle \sum_{i = 0}^{N - 1} \sum_{e \in E} x_{e_{0}, i} \cdot x_{e_{1}, i} & \\\text{{s.t.}} & & & \\ & \text{one-color} & \displaystyle \sum_{\ast_{1} = 0}^{N - 1} x_{v, \ast_{1}} = 1 & \forall v \in \left\{0,\ldots,V - 1\right\} \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}\end{split}\]

インスタンスデータの準備#

次に、この問題のインスタンスを作成します。

G = nx.Graph()
G.add_nodes_from([0, 1, 2, 3, 4])
G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 3), (3, 4), (2, 4)])
pos = {0: (-1, 1), 1: (-0.75, 0.75), 2: (-0.6, 0.3), 3: (-0.2, 0.5), 4: (0, 0)}
nx.draw_networkx(G, pos)
../../_images/0bc8c7983b5a5bc62a09d387395e6183d09b1a92c22ad917cde7068d89121ad8.png 
inst_E = [list(edge) for edge in G.edges]
color_num = 3
num_nodes = G.number_of_nodes()
instance_data = {"V": num_nodes, "N": color_num, "E": inst_E}
num_qubits = num_nodes * color_num

コンパイル済みインスタンスの作成#

では、QAOAを用いてグラフ彩色問題を解いてみましょう。QAOAを実行するには、数理モデルをイジングハミルトニアンに変換し、量子計算ライブラリを使って変分量子回路とハミルトニアンを作成する必要があります。しかし、QamomileはQAOAをサポートしており、比較的簡単に実行できます。

まず、JijModeling.Interpreterを用いて、JijModelingの数理モデルとインスタンスデータからommx.Instanceを作成します。

interpreter = jm.Interpreter(instance_data)
instance: ommx.v1.Instance = interpreter.eval_problem(problem)

Qamomileを用いたQAOA回路とハミルトニアンの生成#

次に、QAOAConverterを作成します。このConverterに制約に対する重みを設定することで、ハミルトニアンを作成できます。

qaoa_converter = qm.qaoa.QAOAConverter(instance)
qaoa_converter.ising_encode(multipliers={"one-color": 5})
qaoa_circuit = qaoa_converter.get_qaoa_ansatz(p=1)
qaoa_cost = qaoa_converter.get_cost_hamiltonian()

QAOA 回路の可視化#

plot_quantum_circuit(qaoa_circuit)
../../_images/1207c102a8afb9c1bcf878f1f30c58074b08c2cbfd9f104c47d4efc710a181c8.png

取得したQAOA回路とハミルトニアンをQiskit向けに変換#

変分量子回路とハミルトニアンの準備が整ったので、実際にQiskitを用いてQAOAを実行してみましょう。Qamomileの回路をQiskitの回路に変換し、シミュレーションを実行します。

qk_transpiler = QiskitTranspiler()
qk_circuit = qk_transpiler.transpile_circuit(qaoa_circuit)
qk_cost = qk_transpiler.transpile_hamiltonian(qaoa_cost)

QAOAの実行#

# 変分ステップ
estimator = qk_pr.StatevectorEstimator()

cost_history = []
def estinamate_cost(params):
    job = estimator.run([(qk_circuit, qk_cost, params)])
    job_result = job.result()
    cost = job_result[0].data['evs']
    cost_history.append(cost)
    return cost

result = opt.minimize(estinamate_cost, [0, 0], method="COBYLA", options={"maxiter": 1000})
result

 message: Optimization terminated successfully.
 success: True
  status: 1
     fun: 28.252167958276864
       x: [ 1.248e+00 -2.628e-01]
    nfev: 295
   maxcv: 0.0

結果の可視化#

plt.title("Change of Cost", fontsize=15)
plt.xlabel("Iteration", fontsize=15)
plt.ylabel("Cost", fontsize=15)
plt.xlim(1, result.nfev)
plt.plot(cost_history, label="Cost", color="#2696EB")
plt.show()
../../_images/4a164b5357498e9c1942c8049967f9119a841f8e841cf310a2fd872532d86049.png 
sampler = qk_pr.StatevectorSampler()
qk_circuit.measure_all()
plt.show()
job = sampler.run([(qk_circuit, result.x)], shots=10000)
job_result = job.result()

sampleset = qaoa_converter.decode(qk_transpiler, job_result[0].data['meas'])

解のプロット#

def plot_graph_coloring(graph: nx.Graph, sampleset: ommx.v1.SampleSet):
    # 実行可能解を抽出
    feasibles = [feas for feas in sampleset.feasible.values() if feas]
    if len(feasibles) == 0:
        print("No feasible solution found ...")
    else:
        lowest_sample = sampleset.best_feasible_unrelaxed()

        # x = 1のインデックスを取得
        indices = [subscripts for subscripts, value in lowest_sample.extract_decision_variables("x").items() if value == 1]
        # 頂点と色を取得
        # 頂点の色リストを初期化
        node_colors = [-1] * graph.number_of_nodes()
        # 可視化用の色リストを設定
        colorlist = ["gold", "violet", "limegreen", "darkorange"]
        # 頂点の色リストを設定
        for i, j in indices:
            node_colors[i] = colorlist[j]
        # 図を作成
        nx.draw_networkx(graph, pos=pos, node_color=node_colors, with_labels=True)
        plt.show()

# グラフ彩色の結果を可視化
plot_graph_coloring(G, sampleset)
../../_images/33cc3d608d6a0b17e0420322328a397814dce893f5dc3075f7ef527462159559.png
Contents