注釈

このページは tutorials/optimization/4_grover_optimizer.ipynb から生成されました。

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

グローバーオプティマイザー

はじめに

グローバー適応探索（Grover Adaptive Search、GAS）は、変分量子固有ソルバー（Variational Quantum Eigensolver、VQE）や量子近似最適化アルゴリズム（Quantum Approximate Optimization Algorithm、QAOA）などの変分アルゴリズムとともに、組み合わせ最適化問題における可能な解決策として検討されてきました。アルゴリズムは、グローバー検索を繰り返し適用し、直前の実行までで最もよいと思われる値をしきい値として使用して、目的関数の最適値を見つけます。GASで使用されるアダプティブオラクルは、現在のしきい値より上または下のすべての値（それぞれ最大および最小）を認識し、最適値が見つかるまで、しきい値が更新されるたびに検索スペースのサイズを縮小します。

このノートブックでは、 [1] に記載されているように、制約なし二値変数二次計画問題(QUBO)を最小化することで、GASで記述されている手法を活用した GroverOptimizer の各コンポーネントを探索します。

参考文献

[1] A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization, arXiv preprint arXiv:1912.04088 (2019).

グローバー適応探索

GASのコア要素であるグローバー探索には、3つの材料が必要です:

1. 探索スペース内の全ての状態を重ね合わせるための状態準備演算子 \(A\) 。

2. 関心のある状態を認識し、その振幅を-1で乗算するオラクル演算子 \(O\) 。

3. \(|0\rangle_n\) 状態の振幅に -1 を掛けるグローバー拡散演算子 \(D\) 。

GASの実装は特定のユースケースによって異なりますが、一般的なフレームワークは、以下で説明する手順に大まかに従います。

GroverOptimizer は QuadraticProgramToNegativeValueOracle を使用して \(A_y\) を構築し、 \(n\)-qubitレジスタを準備し、 \(|x\rangle_n\) と \(m\)-qubitレジスタは対応する \(|Q(x)-y\rangle_m\) を表します。 次に、 \((Q(x) - y)\) 負のすべての状態に \(O_y\) のフラグが付けられます。 実装では、オラクル演算子は \(y\) から独立していますが、これは必須ではありません。 明確にするために、オラクルが \(y\) から独立している場合は、オラクルを \(O\) として参照します。

正式に言えば、 QuadraticProgramToNegativeValueOracle は、次のような \(A_y\) と \(O\) を構成します。

ここで、 \(|x\rangle\) は整数 \(x\) のバイナリーエンコーディングです。

閾値 \(y\) が更新される毎に、関数値が（それぞれ最小値と最大値に対して）上または下に \(y\) だけシフトするように \(A_y\) を適応させます。 たとえば、最小値を見つけるコンテキストでは、\(y\) の値が減少すると、最小値のみが残るまで、探索空間（負の値）も減少します。 具体的な例については、次のセクションで説明します。

GroverOptimizerを使用してQUBO問題の最小値を見つける

以下は最小化問題のおもちゃの例です。

\begin{eqnarray} \min_{x \in \{0, 1\}^3} -2x_1x_3 - x_2x_3 - 1x_1 + 2x_2 - 3x_3. \end{eqnarray}

最初のステップでは、上記の問題を定義するdocplexモデルを作成します。 そして、from_docplex() 関数を使用してモデルを QuadraticProgram に変換し、Qiskit Optimization で QUBO を表すために使用できます。

from qiskit.aqua.algorithms import NumPyMinimumEigensolver
from qiskit.optimization.algorithms import GroverOptimizer, MinimumEigenOptimizer
from qiskit.optimization.problems import QuadraticProgram
from qiskit import BasicAer
from docplex.mp.model import Model

backend = BasicAer.get_backend('statevector_simulator')

model = Model()
x0 = model.binary_var(name='x0')
x1 = model.binary_var(name='x1')
x2 = model.binary_var(name='x2')
model.minimize(-x0+2*x1-3*x2-2*x0*x2-1*x1*x2)
qp = QuadraticProgram()
qp.from_docplex(model)
print(qp.export_as_lp_string())

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: docplex_model1

Minimize
 obj: - x0 + 2 x1 - 3 x2 + [ - 4 x0*x2 - 2 x1*x2 ]/2
Subject To

Bounds
 0 <= x0 <= 1
 0 <= x1 <= 1
 0 <= x2 <= 1

Binaries
 x0 x1 x2
End

次に、6 qubit で値をエンコードする GroverOptimizer を作成します。 そして、進行なしでGASが10回繰り返された後に終了します (つまり \(y\) の値は変化しません) 。 solve() 関数は先ほど作成した QuadraticProgram を受け取り、実行に関する情報を含む結果オブジェクトを返します。

grover_optimizer = GroverOptimizer(6, num_iterations=10, quantum_instance=backend)
results = grover_optimizer.solve(qp)
print("x={}".format(results.x))
print("fval={}".format(results.fval))

x=[1 0 1]
fval=-6.0

この結果、最適解 \(x_0=1\) 、 \(x_1=0\) 、\(x_2=1\) および、 \(-6\) の最適な目的値となる（ほとんどの時間は、ランダム化されたアルゴリズムによる）。 以下の例では、量子状態のカスタム可視化は、このQUBOに適用される GroverOptimizer の実行可能性が示されています。

各グラフはGASの単一の反復を示しており、 \(r\) (= 反復カウンター) と \(y\) (= 閾値 / オフセット) の現在の値がタイトルに示されています。X軸は入力に相当する整数 (例: 『101』 \(\rightarrow\) 5) を表示し、Y軸は可能な関数値を表示します。3つのバイナリ変数があるため、 \(2^3=8\) の可能な解決策があり、各グラフに示されています。色の強度は特定の結果を測定する確率を示し (明るい強度が最も高い) 、実際の色は対応するフェーズを示します (以下のフェーズのカラーホイールを参照) 。 \(y\) が減少すると、すべての値がその量だけ上にシフトすることに注意してください。つまり、1つだけが残る (最小) まで、分布内の負の値はますます少なくなります。

GroverOptimizerが正しい値を見つけることの確認

Qiskitの MinimumEigenOptimizer を使用してアルゴリズムが正しく動作していることを確認できます。

exact_solver = MinimumEigenOptimizer(NumPyMinimumEigensolver())
exact_result = exact_solver.solve(qp)
print("x={}".format(exact_result.x))
print("fval={}".format(exact_result.fval))

x=[1. 0. 1.]
fval=-6.0

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.20.0
Terra	0.15.1
Aer	0.6.1
Ignis	0.4.0
Aqua	0.7.5
IBM Q Provider	0.8.0
System information
Python	3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)]
OS	Darwin
CPUs	2
Memory (Gb)	8.0
Wed Aug 12 19:54:42 2020 JST

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.