注釈

このページは tutorials/algorithms/06_qaoa.ipynb から生成されました。

IBM Quantum lab でインタラクティブに実行します。

Quantum Approximate Optimization Algorithm

Qiskit には Quantum Approximate Optimization Algorithm QAOA の実装があり、このノートブックではグラフ分割問題への適用方法を実演します。

QAOA を直接的に用いることもできますが、最適化モジュールと組み合わせて使用すると便利です。詳細については、 Optimization チュートリアルを参照してください。

import numpy as np
import networkx as nx

from qiskit import BasicAer
from qiskit.aqua.algorithms import NumPyMinimumEigensolver
from qiskit.optimization.applications.ising import graph_partition
from qiskit.optimization.applications.ising.common import random_graph, sample_most_likely

まずランダムなグラフを作成し、可視化します。

num_nodes = 4
w = random_graph(num_nodes, edge_prob=0.8, weight_range=10, seed=48)
print(w)

[[ 0. -5. -6.  0.]
 [-5.  0. -2.  5.]
 [-6. -2.  0.  4.]
 [ 0.  5.  4.  0.]]

G = nx.from_numpy_matrix(w)
layout = nx.random_layout(G, seed=10)
colors = ['r', 'g', 'b', 'y']
nx.draw(G, layout, node_color=colors)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos=layout, edge_labels=labels);

総当たり法は以下の通りです。基本的には、あらゆる二進数の割り当てを網羅的に試します。それぞれの二進数の割り当てでは、頂点の値は 0 (その頂点が第一パーティションにあることを示す) か、 1 (その頂点が第二パーティションにあることを示す) のいずれかとなっています。グラフ分割の定義を満たし、パーティション間の辺の数が最小となる場合に対応する二進数の割り当てを表示します。

def brute_force():
    # use the brute-force way to generate the oracle
    def bitfield(n, L):
        result = np.binary_repr(n, L)
        return [int(digit) for digit in result]  # [2:] to chop off the "0b" part

    L = num_nodes
    max = 2**L
    minimal_v = np.inf
    for i in range(max):
        cur = bitfield(i, L)

        how_many_nonzero = np.count_nonzero(cur)
        if how_many_nonzero * 2 != L:  # not balanced
            continue

        cur_v = graph_partition.objective_value(np.array(cur), w)
        if cur_v < minimal_v:
            minimal_v = cur_v
    return minimal_v

sol = brute_force()
print(f'Objective value computed by the brute-force method is {sol}')

Objective value computed by the brute-force method is 3

The graph partition problem can be converted to an Ising Hamiltonian. Qiskit has different capabilities in the Optimization module to do this. Here, since the goal is to show QAOA, the module is used without further explanation to create the operator. The paper Ising formulations of many NP problems may be of interest if you would like to understand the technique further.

qubit_op, offset = graph_partition.get_operator(w)

では QAOA アルゴリズムを用いて、解を求めましょう。

from qiskit.aqua import aqua_globals
from qiskit.aqua.algorithms import QAOA
from qiskit.aqua.components.optimizers import COBYLA
from qiskit.circuit.library import TwoLocal

aqua_globals.random_seed = 10598

optimizer = COBYLA()
qaoa = QAOA(qubit_op, optimizer, quantum_instance=BasicAer.get_backend('statevector_simulator'))

result = qaoa.compute_minimum_eigenvalue()

x = sample_most_likely(result.eigenstate)
ising_sol = graph_partition.get_graph_solution(x)

print(ising_sol)
print(f'Objective value computed by QAOA is {graph_partition.objective_value(x, w)}')

[0. 0. 1. 1.]
Objective value computed by QAOA is 3.0

結果は、上記の総当たり法で計算された値に一致していることがわかります。一方、古典的な NumPyMinimumEigensolver によって計算を行うこともできます。この方法は、総当たり法を用いずに参照値を得る上で役に立つでしょう。

npme = NumPyMinimumEigensolver(qubit_op)
result = npme.compute_minimum_eigenvalue()

x = sample_most_likely(result.eigenstate)
ising_sol = graph_partition.get_graph_solution(x)

print(ising_sol)
print(f'Objective value computed by the NumPyMinimumEigensolver is {graph_partition.objective_value(x, w)}')

[0 0 1 1]
Objective value computed by the NumPyMinimumEigensolver is 3

また、以下のようにして VQE を用いることも可能です。

from qiskit.aqua.algorithms import VQE
from qiskit.circuit.library import TwoLocal

aqua_globals.random_seed = 10598

optimizer = COBYLA()
var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')
vqe = VQE(qubit_op, var_form, optimizer, quantum_instance=BasicAer.get_backend('statevector_simulator'))

result = vqe.compute_minimum_eigenvalue()

x = sample_most_likely(result.eigenstate)
ising_sol = graph_partition.get_graph_solution(x)

print(ising_sol)
print(f'Objective value computed by VQE is {graph_partition.objective_value(x, w)}')

[0. 1. 0. 1.]
Objective value computed by VQE is 3.0

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.23.0
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.0
IBM Q Provider	0.11.0
System information
Python	3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OS	Linux
CPUs	1
Memory (Gb)	5.827335357666016
Sun Nov 08 19:24:06 2020 EST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.