\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}

これは木更津高専アドベントカレンダー20日目の記事です！

19日目は @_LISA0さんの常微分方程式数値計算メモです。

20日目も @_LISA0さんの記事です！

Groverのアルゴリズム

解決される課題

N個のファイルの中からある一つのデータを探索したいときに使えます。

古典的だと$O(N)$回の探索が必要ですが、Groverのアルゴリズムだと$O(\sqrt{N})$回で探索可能になります。

量子コンピュータ上で動くアルゴリズムなので量子アルゴリズムとも呼ばれています。

アルゴリズムについて

手順

材料

n個のqubits
1個の補助qubit
量子ゲート
- MCX(Multi Controlled X)ゲート
- MCZ(Multi Controlled Z)ゲート
- X　ゲート
- H　ゲート
Oracle

作業

すべてのqubitsを重ね合わせ状態にする
次の操作を適当な回数k回繰り返す
1. Oracleを作用させる
2. 振幅増幅回路を作用させる
測定を行う

2で行う操作をGrover operatorと呼びます。

Oracle

解が入力されたときのみ位相を反転させます。

U_f \ket{x} = \left\{
\begin{array}{ll}
\ket{x} & (x \ is\ not\ solution)\\
-\ket{x} & (x \ is\ solution)
\end{array}
\right.

すなわち、以下の操作と同じになります。
$$
U_f \ket{x} = (-1)^{f(x)} \ket{x}
$$

これはMCZ(Multi Controlled Z)ゲートとXゲートを使えば、あるビット列に対してだけ-1を作用させることが可能になります。

実装

環境
- Python 3.8
- Cirq

実装は https://gist.github.com/Chizuchizu/69a9428f35a5bd6959efdd752e6bf183

オラクル

入力のbitに0があれば、そのbitのみXゲートを作用させる
MCZゲートを作用させる
1.と同じことをしてbitを元に戻す

MCZゲートは制御bit、ターゲットbitそれぞれが1のときのみ位相が反転します。

def make_oracle(input_qubits, output_qubit, x_bits):
    return [
        [cirq.X(q) for (q, bit) in zip(input_qubits, x_bits) if not bit],  # bitが0のときのみXを作用
        cirq.Z.controlled(len(input_qubits) - 1)(*input_qubits),
        [cirq.X(q) for (q, bit) in zip(input_qubits, x_bits) if not bit]
    ]

Grover operator

Oracleを作用させ、入力のbitだけ位相を反転させてから拡散変換（Inversion about meanとも呼ばれる）を作用させます。

拡散変換は本来の状態ベクトルを軸として対称移動させる変換です。

なんで拡散変換はこのように対称移動できるのかについては、「量子情報科学入門」のp.66~67にわかりやすく書かれています。

概略だけ書いておきます。

拡散変換$D_N$は以下のように書けることが知られています。ここの$\phi_0(=\frac{1}{\sqrt{N}} \Sigma \ket{x})$ はすべてが0のqubitにアダマールゲートを作用させたものです。

$$
D_N = - I + \ket{\phi_0} \bra{\phi_0}
$$

この式を用いてオラクルによって位相が反転した$\phi_0'$から$\phi_0$に射影する射影演算子が$ \ket{\phi_0} \bra{\phi_0}$に相当し、折り返したいので2回作用させるといった説明がされています。

本書ではこれらの説明をベクトルの図示や丁寧な式変形と共に記されています。

def make_grover_operator(input_qubits, output_qubit, oracle):
    return [
        oracle,
        cirq.H.on_each(*input_qubits),
        cirq.X.on_each(*input_qubits),
        cirq.Z.controlled(len(input_qubits) - 1)(*input_qubits),
        cirq.X.on_each(*input_qubits),
        cirq.H.on_each(*input_qubits)
    ]

回路

Grover Operatorをある回数だけ作用させるのですが、一般的にはビット数$n$個に対して $\lfloor (\pi / 4) \sqrt{n} \rfloor$回の作用が望ましいと言われています。「量子情報科学入門」という本では$k$回作用させたときの成功確率が$sin^2((2k + 1)arcsin(\sqrt{N}))$である証明が記されています。

def make_grover_circuit(input_qubits, output_qubit, oracle, grover_operator):
    c = cirq.Circuit()

    # 初期設定
    c.append(
        [
            cirq.H.on_each(*input_qubits),
        ]
    )

    # Grover operatorを適当な回数、作用させる
    [c.append(grover_operator) for _ in range(num_loop)]

    # 結果を測定
    c.append(cirq.measure(*input_qubits, key='result'))

    return c


circuit = cirq.Circuit()

oracle = make_oracle(qubits, None, target_bits)
grover_operator = make_grover_operator(qubits, None, oracle)

circuit = make_grover_circuit(qubits, None, oracle, grover_operator)

動かしてみる

------------------------------
parameters
Target bits: 100
num_loop: 2
repetitions: 1000
------------------------------

Sampled results:
Counter({'100': 943, '001': 11, '000': 10, '101': 9, '111': 8, '011': 8, '010': 6, '110': 5})
Most common bitstring: 100 (94.3 %)
Found a match: True

------------------------------
parameters
Target bits: 1000
num_loop: 3
repetitions: 1000
------------------------------

Sampled results:
Counter({'1000': 962, '0010': 6, '1011': 6, '0000': 5, '1111': 4, '0111': 3, '1100': 3, '0110': 2, '1110': 2, '1001': 2, '1010': 2, '0011': 1, '0001': 1, '0101': 1})
Most common bitstring: 1000 (96.2 %)
Found a match: True

いいですね。ちゃんと正解のビットが見つかってますね。

試しに、$k$をあえて大きくとってみましょう。

------------------------------
parameters
Target bits: 100
num_loop: 4
repetitions: 1000
------------------------------

Sampled results:
Counter({'001': 154, '000': 151, '111': 149, '010': 139, '110': 132, '101': 130, '011': 130, '100': 15})
Most common bitstring: 001 (15.4 %)
Found a match: False

想定通り、正解のビットが得られませんでした。良かった。

参考文献

Qiskit グローバーのアルゴリズム (https://qiskit.org/textbook/ja/ch-algorithms/grover.html)
Quantum Native Dojo グローバーのアルゴリズム (https://dojo.qulacs.org/ja/latest/notebooks/8.2_Grovers_algorithm.html)
量子コンピュータ授業 #4　グローバーのアルゴリズム(慶應義塾大学) (https://youtu.be/U6HszEyIuEw)