今回は，Simonのアルゴリズムについてです．
概要
Simon, Daniel R. "On the power of quantum computation." SIAM journal on computing 26.5 (1997): 1474-1483.
一見すると何に応用できるんだって感じですが，特定の共通鍵暗号方式はこのアルゴリズム（を使える量子計算機を仮定して）で破られることが知られています．
＊「特定の共通鍵暗号方式」とは，例えば，Feistel構造が挙げられます
前回のShorのアルゴリズムが公開鍵暗号方式に影響を及ぼしていることを考えると，量子コンピュータが既存の暗号方式に与える影響は絶大なものだと分かりますね．
追記
原論文を詳細に理解したい方は こちら
問題
正整数 $ n, m $ が $ n \leq m $ で，{$0, 1$}$^n \rightarrow$ {$0, 1$}$^m $ なる $f$ について，ある $ s \in$ {$0, 1$}$^n $ があって，$ f(x) = f(x^{\prime}) \Leftrightarrow x^{\prime} \in $ {$x , x \oplus s$} なる $s$ を見つけよ．
＊$f$ が1対1対応か2対1対応かを判定する問題か，とも解釈できます（個人的な感覚ではこっちの方が計算量の見積もりなどは分かりやすいです）
Simonのアルゴリズム
初めに以下の4ステップを十分な回数（今回は1,024回）繰り返す．
i). Hadamard変換を作用させて $ x \in $ {$ 0, 1 $}$^n$ に対して，$ \displaystyle \frac{1}{\sqrt{2^n}} \sum_x | x \rangle $ なる状態を作る
ii). i)を使った合成 $ \displaystyle \frac{1}{\sqrt{2^n}} \sum_x | x \rangle \otimes | 0 \rangle $ なる状態を量子オラクルへ与えることで $ \displaystyle \frac{1}{\sqrt{2^n}} \sum_x | x \rangle \otimes | x \oplus s \rangle $ なる状態を得る
iii). ii) の前半 $n$ ビットにもう一度Hadamard変換を作用させることで，$ \displaystyle \frac{1}{2^n} \sum_y \sum_x (-1)^{xy} | x \rangle \otimes | y \oplus s \rangle $ なる状態を得る
iv). iii) を測定する
上記の測定値が生成するベクトル空間 $V$ の次元を $ \ell $ とするとき，
$ \ell = n \Rightarrow s = 0^n $
$ \ell < n \Rightarrow s = $ ($V$の任意の元と直交するベクトル)
＊初めのループ回数は実は定量化できます，具体的には $ 3n $ 回以上実行すればOKです
＊ii)の冒頭は「$ \displaystyle \frac{1}{\sqrt{2^n}} \sum_x | x \rangle \otimes | 0 \rangle $ なる状態」を入力として「$ \displaystyle \frac{1}{\sqrt{2^n}} \sum_x | x \rangle \otimes | x \oplus s \rangle $ なる状態」を返す量子オラクルがあってi)を使った・・・，が適切な表現な気がします
実装
今回もQiskit Textbook を参考にしています．
＊和訳
以下，$b = 11000$ とします（本来はコマンドライン引数で与えるのが良いんでしょうが，面倒なので値を直接与えています）．
初めに以下をインポートすることを仮定します（最後の１行はどっちでもいい）．
# Qiskit をインポートする
from qiskit import IBMQ, BasicAer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, execute
# 基本的なプロットツールをインポートする
from qiskit.visualization import plot_histogram
from qiskit_textbook.tools import simon_oracle # 内部モジュールを使いたい場合はインポートする
前回と同様？，実は，量子オラクルの部分はQiskitに予め実装されています．
b = "11000"
n = len(b)
simon_circuit = QuantumCircuit(n*2, n)
# i) オラクルに入力する前にアダマールゲートを適用する
simon_circuit.h(range(n))
# ii) オラクルに入力する
simon_circuit = quantum_simon_oracle(b, simon_circuit)
# iii) 入力レジスターにアダマールゲートを適用する
simon_circuit.h(range(n))
# iV) ローカルシミュレーターを利用して測定する
backend = BasicAer.get_backend('qasm_simulator')
shots = 1024
results = execute(simon_circuit, backend=backend, shots=shots).result()
counts = results.get_counts()
# 測定値との内積の計算結果が0になるか検証する
for z in counts:
print( '{}.{} = {} (mod 2)'.format(b, z, bdotz(b,z)) )
検証結果の出力は次のようになります．
11000.00101 = 0 (mod 2)
11000.11010 = 0 (mod 2)
11000.11011 = 0 (mod 2)
11000.00111 = 0 (mod 2)
11000.00011 = 0 (mod 2)
11000.00001 = 0 (mod 2)
11000.11111 = 0 (mod 2)
11000.11110 = 0 (mod 2)
11000.00000 = 0 (mod 2)
11000.11000 = 0 (mod 2)
11000.00110 = 0 (mod 2)
11000.11101 = 0 (mod 2)
11000.11001 = 0 (mod 2)
11000.00010 = 0 (mod 2)
11000.00100 = 0 (mod 2)
11000.11100 = 0 (mod 2)
測定値の妥当性も大丈夫だということが分かりました．
上記で用いた量子オラクルはブラックボックスっぽく見えますが，以下のように実装できます（こうするならインポート文の最後の1行は不要）．
def quantum_simon_oracle(b: str, circuit: list) -> list:
"""
nビット列 x に対して， |x>|0> を 入力として |x> |x \oplus b> を出力する関数
ただし， x \oplus b で x と b の排他的論理和を表す
|x>|0> → |x>|x> と，初めに１つめのレジスタの内容を2つめにコピーする
次に， 後半 n ビットと b との排他的論理和で与える
"""
n = len(b)
# |x>|0> → |x>|x>
for index in range(n):
circuit.cx(index, index+ n)
# |x>|x> → |x>|x \oplus b>
for index in range(n):
if b[n - 1 - index] == '1':
target_index = index
break
for index in range(n):
if b[index] == '1':
circuit.cx(target_index, 2 * n - 1 - index)
return circuit
まとめ
理論的なことはまとめ終わったら追記します．
冒頭でも書いたように，このアルゴリズムを応用すると，特定の共通鍵暗号方式を破れるのがすごいですね．
次回はGroverの探索アルゴリズムです．これも非常に強力なアルゴリズム（らしい）です．
参考文献
$ \bullet $ 縫田光司. 耐量子計算機暗号. 森北出版 株式会社, 2020.