Searching（探索問題） 〜Quantum Zooやっていく〜

Dec. 30, 2021, 8:42 a.m. edited Dec. 31, 2021, 2:26 p.m.

#Quantum Zoo  #量子情報  #量子力学 

$$ \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}} $$

一応、 Quantum Zoo やっていく企画の第三回だけれど、 Grover's algorithm はどこを調べても載ってるので、ほんと自分のためのメモ程度。

背景

\(N\) 個の入力があり、その中に \(M\) 個の正解があるとする。この正解判定がオラクルによりおこなわれるとき、古典計算においては \(\Omega(N/M)\) 回のオラクル呼び出し回数（クエリ計算量）が必要となる。一方で、 Lov Grover により \(O(\sqrt{N/M})\) のクエリ計算量で解決できる量子アルゴリズムが得られた [L. Grover, 1996]。

問題

\(N\) 個の入力 \(x\) をオラクル \(f\) に入力し、正解判定ができるとする。このとき、正解となる \(x\in W\) (\(W\) を正解集合とする) を見つける。

アルゴリズム

\(n\) ビット（\(2^n=N\)。 \(N\) がもともと 2 のベキでないことも多いだろうが、 2 のベキとなるように \(f\) の定義域をはみ出た部分は不正解にするなどして拡張してやる）の量子ビットを用意し、アダマール \(H^{\otimes n}\) を作用させる。

$$ \begin{align} &\frac{1}{\sqrt{N}}\sum_{x=1}^{N}\ket{x}\\ =&\frac{1}{\sqrt{N}}\left(\sum_{x\notin W}\ket{x}+\sum_{x\in W}\ket{x}\right)\\ =&\sqrt{\frac{N-M}{N}}\frac{1}{\sqrt{N-M}}\sum_{x\notin W}\ket{x}+\sqrt{\frac{M}{N}}\frac{1}{\sqrt{M}}\sum_{x\in W}\ket{x}\\ =&\sqrt{\frac{N-M}{N}}\ket{\alpha}+\sqrt{\frac{M}{N}}\ket{\beta}\\ =&\cos\frac{\theta}{2}\ket{\alpha}+\sin\frac{\theta}{2}\ket{\beta}=:\ket{s} \end{align} $$

3 番目の等号では \(\ket{\alpha}:=\frac{1}{\sqrt{N-M}}\sum_{x\notin W}\ket{x}\), \(\ket{\beta}:=\frac{1}{\sqrt{M}}\sum_{x\in W}\ket{x}\) として定義した（\(\|\ket{\alpha}\|^2=\|\ket{\beta}\|^2=1\) を満たす）。4 番目の等号では \(\cos\frac{\theta}{2}=\sqrt{\frac{N-M}{N}}\), \(\sin\frac{\theta}{2}=\sqrt{\frac{M}{N}}\) を満たすように \(\theta\) を定義した。

オラクルを呼んで正解ならば符号を反転させるような量子回路を実装し¹、作用させる（このユニタリを \(U_w\) とする）。

$$\cos\frac{\theta}{2}\ket{\alpha}-\sin\frac{\theta}{2}\ket{\beta}$$

次に拡散行列 \(U_s:=2\ket{s}\bra{s}-I\) を作用させる。これは量子回路としては \(U_s=H^{\otimes n}X^{\otimes n}(MCZ)X^{\otimes n}H^{\otimes n}\) となる（ただし \(MCZ\) は \(n-1\) 番目までを制御とし \(n\) 番目に作用させるマルチ制御 \(Z\) ゲート）。なぜ成り立つのかは Qiskit テキストの項目 反転 \(U_s\) および Qiskit での実装内にある「詳細：一般的なDiffuserの作成（クリックして展開）」を参照。

$$\cos\frac{3\theta}{2}\ket{\alpha}+\sin\frac{3\theta}{2}\ket{\beta}$$

ここまでの \(U_s U_w\) を \(\ket{s}\) に \(k\) 回作用させると、

$$\cos\frac{(2k+1)\theta}{2}\ket{\alpha}+\sin\frac{(2k+1)\theta}{2}\ket{\beta}$$

となる。ゆえに、 \(\frac{(2k+1)\theta}{2}\) が最も \(\frac{\pi}{2}\) に近づくような \(k\) の回数だけ繰り返せば良い。その回数はここ見て。

Qiskit による実装

実装は、 Qiskit テキストにて実装が既にあるけれど、一応実装した。オラクルとしては本当にシンプルに 11 が奇数個存在したら正解とするものを使用した。この際、補助ビットとして 1 ビット使用しているが、使用後はちゃんと 0 に戻している。完全なコードは GitHub に載せている・・といつものように書いたが、 Shor のアルゴリズムと違って、以下で完結していて本当にシンプルで楽。

from typing import Optional

import matplotlib.pyplot as plt
from qiskit import QuantumCircuit, Aer, transpile
from qiskit.visualization import plot_histogram
from qiskit.circuit import Gate


def grover(N_len: int, oracle_gate: Gate, oracle_qubits_len: int, k_time: int, show_hist: Optional[bool] = True) -> int:
    qc = QuantumCircuit(N_len + oracle_qubits_len, N_len)

    qc.h(range(N_len))

    for _ in range(k_time):
        qc.append(oracle_gate, range(N_len + oracle_qubits_len))

        qc.h(range(N_len))
        qc.x(range(N_len))

        # MCZ
        qc.h(N_len - 1)
        qc.mct(list(range(N_len - 1)), N_len - 1)
        qc.h(N_len - 1)

        qc.x(range(N_len))
        qc.h(range(N_len))

    qc.measure(range(N_len), range(N_len))

    backend = Aer.get_backend('aer_simulator_matrix_product_state')
    qc = transpile(qc, backend)
    job = backend.run(qc, shots=10000)
    hist = job.result().get_counts()

    if show_hist:
        plot_histogram(hist)
        plt.show()

    return int(max(hist.items(), key=lambda x: x[1])[0], 2)


def sample_oracle(N_len: int) -> Gate:
    """
    An oracle which inverts the sign if the number of 11 is odd.
    11 が奇数個あるなら符号を反転するオラクル
    """

    qc = QuantumCircuit(N_len + 1)

    for qubit in range(N_len - 1):
        qc.ccx(qubit, qubit + 1, N_len)

    qc.z(N_len)

    for qubit in reversed(range(N_len - 1)):
        qc.ccx(qubit, qubit + 1, N_len)

    return qc.to_gate()


if __name__ == '__main__':
    print(grover(3, sample_oracle(3), 1, 1))

結果は以下のようになった。

確かに \(011=3\) および \(110=6\) が得られている。ここで、他の不正解の値が完全に消失しているが、これは正解の数が \(M=2\) であるために \(\cos \frac{\theta}{2}=\sqrt{\frac{N-M}{N}}=\sqrt{\frac{6}{8}}=\frac{\sqrt{3}}{2}\) より \(\theta=\frac{\pi}{3}\)、つまり一度 \(U_s U_w\) を適用するだけで \(\cos \frac{3\theta}{2}=\cos \frac{\pi}{2}=0\) となって \(\ket{\alpha}\) の振幅が \(0\) となるためである²。