양자 근사 최적화 알고리즘 (Quantum Approximate Optimization Algorithm)¶

키스킷에는 양자 근사 최적화 알고리즘 QAOA 이 구현되어 있다. 이 노트북은 그래프 분할 (graph partition) 문제에 이를 적용하는 방법을 시연할 것이다.

QAOA는 직접 사용할 수도 있지만, 최적화 모듈과 함께 사용하는 것이 더 편리하다. 자세한 내용은 최적화 사용 지침서를 참조하라.

[1]:

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

먼저 무작위 그래프를 생성하고 이를 그려서 확인해보자.

[2]:

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

[3]:

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);

../../_images/tutorials_algorithms_06_qaoa_4_0.png

무차별 대입(brute-force) 방법은 다음과 같다. 기본적으로 철저히 모든 경우의 수에 대하여 바이너리 할당(binary assignment) 을 시도한다. 각 바이너리 할당에서 꼭짓점의 항목은 0 (꼭짓점이 첫 번째 분할 영역에 있음을 의미) 또는 1 (꼭짓점이 두 번째 분할 영역에 있음을 의미) 이다. 그래프 분할의 정의를 충족하면서 모서리 교차횟수가 최소인 바이너리 할당 결과를 출력한다.

[4]:

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.

[5]:

qubit_op, offset = graph_partition.get_operator(w)

QAOA를 사용하여 솔루션을 찾아보자.

[6]:

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 를 사용하여 계산을 수행할 수 있는데, 이는 무차별 대입을 수행하지 않는 다는 점에서 참조하면 유용할 것이다.

[7]:

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를 사용할 수도 있다.

[8]:

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

[9]:

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

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.