注釈

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

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

Grover のアルゴリズムの例

このノートブックでは、 Qiskit の Grover 探索アルゴリズムを様々なオラクルで使用する方法を示しています。

import pylab
import numpy as np
from qiskit import BasicAer
from qiskit.tools.visualization import plot_histogram
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle, TruthTableOracle

3-SAT 問題の求解

3-Satisfiability (3-SAT) 問題の例を取り上げ、量子探索を用いて充足解を見つける方法を説明します。 3-SAT 問題は通常 Conjunctive Normal Forms (CNF) で表現され、DIMACS-CNF 形式で書かれています。例えば、以下のようになります。

input_3sat_instance = '''
c example DIMACS-CNF 3-SAT
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
'''

この 3-SAT インスタンスの CNF には、 3 つの変数と 5 つの節が含まれています。

\((\neg v_1 \vee \neg v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee v_3) \wedge (v_1 \vee v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee \neg v_3) \wedge (\neg v_1 \vee v_2 \vee v_3)\)

この 3-SAT 問題のインスタンスには、以下の 3 つの充足解があることが確認できます。

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((T, T, F)\)

あるいは、 DIMACS 表記を用いて表現すれば、以下のようになります。

1 -2 3, or -1 -2 -3, or 1 2 -3.

この例題を入力として、 Grover 探索に対応する oracle を作成します。特に DIMACS-CNF 形式の文字列を解析し、対応するオラクル回路を構築するために、 LogicalExpressionOracle コンポーネントを用います。

oracle = LogicalExpressionOracle(input_3sat_instance)

これで oracle を用い、 Grover のインスタンスを作成できるようになりました。

grover = Grover(oracle)

そしてバックエンドを設定し、 Grover インスタンスを実行して結果を得ることができます。

backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = grover.run(quantum_instance)
print(result.assignment)

[1, 2, -3]

上記のように、与えられた 3-SAT 問題の充足解が得られています。そして、それは確かに三つある充足解のうちの一つとなっています。

qasm_simulator を用いたので、以下に示すように完全な測定結果も返されます。三つの解に対応するバイナリ文字列 000, 011, 101 (それぞれの文字列のビット順に注意してください) は、全て高い確率ももっていることがわかります。

plot_histogram(result.measurement)

ブール論理表現

Qiskit の Grover は DIMACS 以外にも、他の手段で構築された oracle に基づいた量子探索を実行することが可能です。例えば LogicalExpressionOracle は、以下に示すように、任意のブール論理表現を用いて実際に設定することができます。

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

上の例では、^, ~, & がそれぞれブール論理における XOR, NOT, AND 演算を表しており、入力されたブール論理表現 '(w ^ x) & ~(y ^ z) & (x & y & z)' は非常にわかりやすいはずです。それぞれの部分を調べることで、充足解を見つけるのはとても簡単なはずです。 w ^ x は w と x が異なる値を取ることを、 ~(y ^ z) は y と z が同じであることを、x & y & z は三つが全て True であることをそれぞれ必要とします。これらを組み合わせると、充足解 (w, x, y, z) = (False, True, True, True) が得られ、これは Grover の結果と一致しています。

TruthTable オラクル

Qiskit を用いると、 Oracle は真理値表からも構築することができ、言い換えると真理値表に基づいて量子探索を実行することができます。これは本質的には、 \(1\) の値をもつ真理値表のエントリーを検索することになるので、意味がないように思えるかもしれませんが、実演のためには良い例となっています。

truthtable = '1000000000000001'

このように truthtable は表内の全てのエントリーの値を含むビット列で指定されます。この長さは \(16\) であるので、対応する真理値表は \(4\) の入力ビットで構成されます。最初と最後の値が \(1\) であるため、対応する真理値表のエントリは 0000` と 1111 です。

次に Oracle と Grover オブジェクトを設定して、従来通りに量子探索を実行します。

oracle = TruthTableOracle(truthtable)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

上のプロットに見られるように、探索結果は予想と一致しています。

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 17:26:36 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.