注釈

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

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

Grover のアルゴリズムと振幅増幅

Grover のアルゴリズムは、 1996 年に Lov Grover によって提案された、最も有名な量子アルゴリズムの一つです [1] 。最初は非構造検索問題、すなわち非構造化データベース内のマークされた要素を見つける問題のために提案されました。しかし Grover のアルゴリズムは、現在 Grover Adaptive Search [2] のような他のいくつかのアルゴリズムのサブルーチンとなっています。 Grover のアルゴリズムの詳細については、 Qiskit textbook の Grover’s Algorithm を参照してください。

Qiskitは、 Grover クラスにGroverのアルゴリズムを実装します。 このクラスには、一般化されたバージョンである振幅増幅 [3] も含まれており、個々の反復やその他のメタ設定をグローバーのアルゴリズムに設定できます。

**参考文献: **

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

Grover のアルゴリズム

Grover のアルゴリズムは、 Grover 演算子 \(\mathcal{Q}\) を用いて、所望の状態の振幅を増幅します。

\[\mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^\dagger \mathcal{S_f}\]

ここで * \(\mathcal{A}\) はアルゴリズムの初期探索状態であり、教科書的な Grover 探索におけるアダマール \(H^{\otimes n}\) に同じですが、 振幅増幅のためにはより複雑なものとすることができます。 * \(\mathcal{S_0}\) は ゼロ状態に関する反転です。

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rangle, &x = 0\end{cases}\end{split}\]

* \(\mathcal{S_f}\) は適用するオラクルです。

\[|x\rangle \mapsto (-1)^{f(x)}|x\rangle\]

\(f(x)\) は \(x\) が所望の状態の場合 1 となり、それ以外の場合は 0 になります。

一言で言えば、グローバーのアルゴリズムは異なる \(\mathcal{Q}\) の累乗を適用し、各実行後に適切な解が見つかったかどうかをチェックします。

Grover のアルゴリズムの実行

Grover クラスでGroverのアルゴリズムを実行するには、まず、Groverのアルゴリズムの回路にオラクルを指定する必要があります。次の例では、グローバーのアルゴリズムのオラクルとして QuantumCircuit を使用しています。 ただし、グローバーのアルゴリズムのオラクルとして使用できるクラスは他にもいくつかあります。 これらについては、このチュートリアルの後半で説明します。

Grover のアルゴリズムのためのオラクルは、 位相反転 オラクルであることに注意してください。つまり 「所望の状態」 の振幅に \(-1\) の係数を乗じています。 ビット反転 オラクルを位相反転オラクルに変換する方法については後述します。

from qiskit import QuantumCircuit
from qiskit.aqua.algorithms import Grover

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
grover = Grover(oracle=oracle, good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
grover.grover_operator.draw(output='mpl')

<matplotlib.figure.Figure at 0x7f359572eba8>

次にバックエンドを指定し、 Grover の run メソッドを呼び出して回路を実行します。返される結果の型は GroverResult です。

探索が成功した場合は、 oracle_evaluation 属性が True となります。この場合、最も多くサンプリングされた測定値である top_measurement が「所望の状態」の一つであることを示します。そうでなければ、 oracle_evaluation は False となります。

from qiskit import Aer
from qiskit.aqua import QuantumInstance

qasm_simulator = Aer.get_backend('qasm_simulator')
result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.aqua.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

この例では、 top_measurement の結果が 11 となっており、これは「所望の状態」の一つとなっています。このように、 Grover を用いて解を見つけることに成功しました。

Grover オラクルとしての様々なクラスの使用

上の例では、 Grover のオラクルとして QuantumCircuit を用いました。しかし、 qiskit.aqua.components.oracles.Oracle や qiskit.quantum_info.Statevector をオラクルとして用いることも可能です。以下の例は全て、\(|11\rangle\) が「所望の状態」である場合です。

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
grover = Grover(oracle=oracle, good_state=['11'])

result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.aqua.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

内部的には、状態ベクトルが量子回路にマッピングされています。

grover.grover_operator.oracle.draw(output='mpl')

Qiskit Aqua の Oracle コンポーネントを用いれば、より複雑なオラクルを簡単に構築することが可能です。 Oracle 型には興味深いサブクラスがあります。 * LogicalExpressionOracle: '~a | b' のような論理式を解析するためのものです。これは特に 3-SAT 問題を解くのに便利で、 Grover Examples チュートリアルで説明されています。 * TrutheTableOracle: 真理値表を回路に変換するための関数です。

ここでは LogicalExpressionOracle を用い、'a & b' に対応する状態である \(|11\rangle\) を見つける、簡単な例を示します。

from qiskit.aqua.components.oracles import LogicalExpressionOracle

# `Oracle` (`LogicalExpressionOracle`) as the `oracle` argument
expression = '(a & b)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle=oracle)
grover.grover_operator.oracle.draw(output='mpl')

このオラクルは、実際には二つではなく三つの量子ビットで実装されていることがわかります。

これは、 LogicalExpressionOracle が位相反転オラクル (所望の状態の位相を判定させる) ではなく、ビット反転オラクルだからです。これは他のビットが条件を満たしていれば、補助ビットの状態を反転させることというを意味しています。しかし、 Grover のアルゴリズムでは、位相反転オラクルが必要です。ビット反転オラクルを位相反転オラクルに変換するために、上記の回路で見られるように、 \(X\) ゲートと \(H\) ゲートでCNOT ゲートを挟みます。

**注: ** このビット反転から位相反転への変換は一般的なものであり、これを用いてオラクルを正しい表現に変換することができます。

振幅増幅

Grover のアルゴリズムでは、 Grover 演算子 \(\mathcal{Q}\) の最初において、全ての状態の一様な重ね合わせをアダマールゲートによって用意します。所望の状態に関する情報がある際には、一様な重ね合わせから始めるのではなく、特定の状態だけを初期化する方が便利な場合があります。 Grover のアルゴリズムがこのように一般化されたものは、 振幅増幅(Amplitude Amplification) と呼ばれています。

Qiskit では state_preparation 引数を設定することで、重ね合わせの初期状態を簡単に調整することができます。

状態の準備

A state_preparation argument is used to specify a quantum circuit that prepares a quantum state for the start point of the amplitude amplification. By default, a circuit with \(H^{\otimes n}\) is used to prepare uniform superposition (so it will be Grover’s search). The diffusion circuit of the amplitude amplification reflects state_preparation automatically.

import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.h(2)
oracle.ccx(0,1,2)
oracle.h(2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
grover = Grover(oracle=oracle, state_preparation=state_preparation, good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
grover.grover_operator.state_preparation.draw(output='mpl')

state preparation circuit:

result = grover.run(quantum_instance=qasm_simulator)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

完全な柔軟性

より高度な使用法としては、 grover_operator 引数を設定することで、 Grover 演算子全体を指定することもできます。これはゼロ状態まわりの反転、オラクル、状態準備を介したデフォルトの構成よりも、 \(\mathcal{Q}\) のより効率的な実装がわかっている場合に便利かもしれません。

The qiskit.circuit.library.GroverOperator can be a good starting point and offers more options for an automated construction of the Grover operator. You can for instance

• set the mcx_mode

• ignore qubits in the zero reflection by setting reflection_qubits

• explicitly exchange the \(\mathcal{S_f}, \mathcal{S_0}\) and \(\mathcal{A}\) operations using the oracle, zero_reflection and state_preparation arguments

例えば、所望の状態は三量子ビットの \(|111\rangle\) ですが、補助量子ビットとして二量子ビットを追加するとします。

from qiskit.circuit.library import GroverOperator, ZGate

oracle = QuantumCircuit(5)
oracle.append(ZGate().control(2), [0, 1, 2])
oracle.draw(output='mpl')

デフォルトでは、 Grover 演算子は五つの量子ビット全てにゼロ状態まわりの反射を実装します。

grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.draw(output='mpl')

しかし、最初の三つだけを考えればよいということがわかっています。

grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.draw(output='mpl')

Grover の他の引数について

Grover には oracle と state_prepartion 以外にも引数があります。このセクションでは、それらについて説明します。

good_state の指定

good_state は測定結果が正しいかどうかを内部的にチェックするために使用します。これは、バイナリ文字列のリスト、整数のリスト、 Statevector 、 Callable のいずれかになります。入力がビット列のリストの場合、リスト内の各ビット列が所望の状態を表します。入力が整数のリストならば、それぞれの整数は所望の状態で \(|1\rangle\) となる桁のインデックスを表します。 Statevector の場合は、全ての所望の状態の重ね合わせを表します。

# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.is_good_state('11'))

True

# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=callable_good_state)
print(grover.is_good_state('11'))

True

iterations の数

Grover 演算子のアルゴリズムで正しい結果を得るためには、 Grover 演算子を適用する際の繰り返し回数が重要です。繰り返し回数は Grover の引数 iterations で設定することができます。次の入力がサポートされています。入力が整数ならば、適用される Grover 演算子 の指数を表します。入力が整数のリストならば、 Grover 演算子がそれらの回数だけ連続して適用され、各回の実行後に正しい解が見つかったかどうかチェックされます。

これらに加えて、 sample_from_iterations という引数もあります。これが True になっている場合、 iterations で指定された指数の代わりに、 0 と iterations の間のランダムな整数を Grover 演算子の指数として用いることができます。この方法は、解の個数すら分からない場合に有用です。

sample_from_iterations を用いたアルゴリズムの詳細は [4] を参照してください。

**参考文献: **

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=1)

# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=[1, 2, 3])

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], iterations=[1, 2, 3], sample_from_iterations=True)

解の個数がわかっている場合には、静的メソッド optimal_num_iterations を用いて最適な反復回数を求めることもできます。出力される反復回数は、近似値であることに注意してください。量子ビット数が少ない場合には、出力される反復回数が最適でない可能性があります。

iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations

12

post_processing の適用

読みやすさのために、最も多く得られた測定値に後処理を適用することができます。これは例えば、測定値のビット表現 [1, 0, 1] を DIMACS CNF 形式 [1, -2, 3] に変換するために使用可能です。

def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'],post_processing=to_DIAMACS_CNF_format)
grover.post_processing([1, 0, 1])

[1, -2, 3]

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:30:57 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.