量子アルゴリズム③ Groverのアルゴリズム

かなり空きましたが，今回はGroverのアルゴリズムについてです．

概要

L. K. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings, 28th ACM Symposium on Theory of Computation, 212 (1996).

整列されていないデータベースの探索を効率よく行うアルゴリズムです．$N$ 個の要素のリストがあったとき，特定の要素を $O(\sqrt{N})$ の計算量で探索することができます．古典だと，事前に昇順（降順）にソートを仮定して，2分探索を行なったときの計算量と同じですが，こちらの場合はソートの仮定は不要です．
例えば，128 bit長の全探索を行うのに $2^{64}$ 回の探索で済むことから，このアルゴリズムにより，公開鍵暗号でも共通鍵暗号でも、実用的な量子計算機の登場以降は、従来と同じ安全性を保つには鍵長を2倍にする必要があります．

Groverのアルゴリズム

＊今回は簡単のため，1要素を見つける場合のみ考えます

Input : $N = 2^n$ で，関数 $f : ${$0, 1$}$^n \rightarrow ${$ 0, 1 $}
Output : $f(x_0) = 1$ なる解 $x_0 \in ${$0, 1$}$^n$
(i) 初期状態 $ | 0^n \rangle | 0 \rangle $ に対して， 末尾1bitに X gate，先頭$n$bitに Hadamard gate を作用させ，$ \displaystyle \left( \frac{1}{\sqrt{2^n}} \sum_{x \in {0, 1}^n} | x \rangle \right) | 1 \rangle $ を得る．
(ii) 量子オラクル $O_f$ に対応する unitary 演算子 $U_f$ をbit全体に作用させ，$ \displaystyle \frac{1}{\sqrt{2^n}} \sum_{x \in {0, 1}^n} | x \rangle | 1 \oplus f(x) \rangle $ を得る．
(iii) 先頭$n$bitに Diffuser を作用させる．
(iv) (ii) と (iii) の処理を十分回繰り返す
(v) 先頭$n$bitを測定する

＊(iv)の繰り返す回数は $ \displaystyle \left \lfloor \frac{\pi}{4 \mathrm{arcsin}(\sqrt{\frac{1}{N}})} \right \rfloor $ 回で十分です．
＊理論的なことは後で載せます，今回は実装のみで

実装

今回もQiskit Textbook を参考にしています．
＊和訳

以下，$n = 2^7$ で $w = 117 \in [1, n]$ とします（さっきまで$N$としていたのを$n$で置き換えています）．

Grover_import.py

import matplotlib.pyplot as plt
import numpy as np

# Qiskit関連のパッケージをインポート
from qiskit import IBMQ, Aer, QuantumCircuit, ClassicalRegister, QuantumRegister, execute
from qiskit.providers.ibmq import least_busy
from qiskit.quantum_info import Statevector
from qiskit.visualization import plot_histogram
from qiskit.tools.monitor import job_monitor
from qiskit.circuit.library import MCMT

上のステップを順に実装していきます．

(i)

参考：量子コンピューティング・ワークブック

Grover_initialize.py

def initialize_s(qc, qubits):
    # 回路のqubitsにHゲートを適用
    for q in qubits:
        qc.h(q)

    return qc

(ii)

$w$のマーク付として，$w$の2進展開で要素が0のqubitに$X$ゲートを置くと，一旦$w$の2進展開の要素が全て1になります．
その際に全体に$Z$ゲートを掛ける（$CZ$ゲートや$CCZ$ゲートの一般化と思ってください）と，$w$のみにマークが付けられます（(i)の重ね合わせで$|w\rangle$のみ符号が負になる）．
「全体に$Z$ゲートを掛ける」はMCMTを使えばできます．

Grover_oracle.py

def oracle(n, w):
    # オラクルを作成して、回路に実装
    oracle = QuantumCircuit(n)

    bin_w = bin(w)[2:]
    if len(bin_w) < n:
        for _ in range(n - len(bin_w)):
            bin_w.insert(0, 0)

    # w を２進展開した際に，要素が0の箇所をbit反転する
    # 要素が全て1の場合のみに符号を反転させる
    for index in range(len(bin_w)):
        if bin_w[index] == '0':
            oracle.x((n - 1) - index)
    oracle = MCMT('cz', n - 1, 1)
    for index in range(len(bin_w)):
        if bin_w[index] == '0':
            oracle.x((n - 1) - index)

    oracle_gate = oracle.to_gate()
    oracle_gate.name = "U_w"
    
    return oracle_gate

(iii)

参考：Qiskit Textbook

Grover_diffuser.py

def diffuser(n):
    qc = QuantumCircuit(n)

    # Hゲートで |s> -> |00..0> に変換
    for qubit in range(n):
        qc.h(qubit)
    # Xゲートで |00..0> -> |11..1> に変換
    for qubit in range(n):
        qc.x(qubit)
    # マルチ制御Zゲートをかけます
    qc.h(n - 1)
    qc.mct(list(range(n - 1)), n - 1)  # マルチ制御トフォリ
    qc.h(n - 1)
    # |11..1> -> |00..0> に変換
    for qubit in range(n):
        qc.x(qubit)
    # |00..0> -> |s> に変換
    for qubit in range(n):
        qc.h(qubit)

    U_s = qc.to_gate()
    U_s.name = "U_s"
    
    return U_s

(v)

Grover_measure.py

def show_distribution(answer):
    # 横軸を整数でプロットする
    n = len(answer)
    x = [int(key,2) for key in list(answer.keys())]
    y = list(answer.values())

    fig, ax = plt.subplots()
    rect = ax.bar(x,y)

    def autolabel(rects):
        for rect in rects:
            height = rect.get_height()
            ax.annotate('{:.3f}'.format(height/sum(y)),
                        xy=(rect.get_x()+rect.get_width()/2, height),xytext=(0,0),
                        textcoords="offset points",ha='center', va='bottom')
    autolabel(rect)
    plt.ylabel('Probabilities')
    plt.show()

まとめ

Grover.py

def main(n, w):
    grover_circuit = QuantumCircuit(n)
    grover_circuit = initialize(grover_circuit, list(range(n)))
    grover_circuit.append(oracle(n, w), list(range(n)))
    grover_circuit.append(diffuser(n), list(range(n)))
    grover_circuit.measure_all()
    grover_circuit.draw('mpl')
    backend = Aer.get_backend('qasm_simulator')
    results = execute(grover_circuit, backend=backend, shots=1024).result()
    answer = results.get_counts()
    show_distribution(answer)

出力される画像（めちゃくちゃわかりづらいですが・・・117だけ突出しています）

まとめ

古典の暗号理論に関しては冒頭で書いたような脅威があるのですが，
今やっている研究分野だと，McEliece暗号を効率良く解読する（攻撃手法）で ISD(Information-Set Decoding) というのがあって，

Daniel J Bernstein. Grover vs. McEliece. In International Workshop on PostQuantum Cryptography, pages 73–80. Springer, 2010.

上記の論文でGroverのアルゴリズムと組み合わせることで，古典の場合よりも速く解読できることが知られています．

次回はQuantum walkをやろうと思います．理由は上記の Quantum ISD を更に発展させるために，Quantum walkの知識が必要なためです．

参考文献

$ \bullet $ 石坂 智, 小川 朋弘, 河内 亮周, 木村 元, 林 正人, 『量子情報科学入門』, 共立出版, 2012年
$ \bullet $ 中山 茂, 『量子アルゴリズム』, 技報堂出版, 2014年
$ \bullet $ 縫田 光司，『耐量子計算機暗号』，森北出版，2020年