Groverのアルゴリズムを実装する

```math
\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さんの[常微分方程式数値計算メモ](https://qiita.com/_LISA0/items/dfbd63b828f6a0941f5f)です。

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

### 作業

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

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

### Oracle

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

```math
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

### オラクル

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

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

```python
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回作用させるといった説明がされています。

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


```python
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}))$である証明が記されています。

```python
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)
```

## 動かしてみる


```bash
------------------------------
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
```


```bash
------------------------------
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$をあえて大きくとってみましょう。

```bash
------------------------------
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)