サイモンのアルゴリズムの試行回数の期待値求めてみた

3209 ワード
量子コンピュータ 量子アルゴリズム 量子コンピュータ テキストリンク

求めたかった期待値

サイモンのアルゴリズムについては、
https://qiskit.org/textbook/ja/ch-algorithms/simon.html
このサイトを見ていただければ一番わかりやすいです(丸投げ)
このアルゴリズムについて私が知りたかったのは、
およそ何回繰り返せば$n$個のデータが得られるのか、という点です。

まず確率を求めてみた

$n$量子ビットのオラクルについて考えます。
取り出したいデータが$x_1,\cdots ,x_n$の$n$個あるとします。一回の試行でどのデータを取り出すかは等確率です。
$k$を$k\geq n$なる整数として$k$回の試行ではじめてすべてのデータが取り出される確率を求めます。
$1\leq l\leq n$なる整数$l$に対して次の命題を定めます。

A_l:「k-1回の試行で少なくとも一回x_lを取り出す」\\
B_l:「k回目の試行でx_lを取り出す」

$A_l,B_l$は独立な試行によるものですから求める確率$p_k$は

p_k = P(\bar{A_1}\cap A_2\cap \cdots A_n)P(B_1) + P(A_1\cap \bar{A_2}\cap \cdots A_n)P(B_2) +\cdots + P(A_1\cap A_2\cap \cdots \bar{A_n})P(B_n)

まず第1項について考えましょう。データ$x_2,\cdots,x_n$に関する対称性と包除原理より

P(\bar{A_1}\cap A_2\cap \cdots \cap A_n)\\
=P(\bar{A_1}\cap \overline{\overline{A_2\cap \cdots \cap A_n}})\\
=P(\bar{A_1}\cap \overline{\bar{A_2}\cup \cdots \cup \bar{A_n}})\\
=P(\bar{A_1})-P(\bar{A_1}\cap (\bar{A_2}\cup \cdots \cup \bar{A_n}))\\
=P(\bar{A_1})-\sum_{m=1}^{n-1} (-1)^{m-1}{}_{n-1}\text{C}_m P(\bar{A_2}\cap\cdots\cap\bar{A_{m+1}})\\
=\left(\frac{n-1}{n}\right)^{k-1}+\sum_{m=1}^{n-1}(-1)^m{}_{n-1}\text{C}_m \left(\frac{n-m-1}{n}\right)^{k-1}\\
=\sum_{m=1}^n (-1)^{m-1}\left(1-\frac{m}{n}\right)^{k-1}.

また明らかに$P(B)=\frac{1}{n}$です。
これについてほかの項についても考えれば

p_k = \sum_{m=1}^n (-1)^{m-1}\left(1-\frac{m}{n}\right)^{k-1}.

期待値を求めてみた

期待値$E_n$は

E_n = \sum_{k=n}^\infty kp_k\\
=(級数計算は省略)\\
=\sum_{m=1}^n(-1)^{m-1}{}_{n-1}\text{C}_{m-1}\frac{n}{m}\left(1-\frac{m}{n}\right)^{n-1}\left(n+\frac{n}{m}-1\right)

Maximaでプロットしてみた

ゴリゴリ計算して出たはいいものの...あまり意味が分からない。ということでMaximaでプロットしてみる。
$n=2から100$の範囲でプロットした。

おおお！大体$O(n)$か？
古典計算における試行回数$2^{n-1}+1$と比較。驚いたのは、$n=2$のとき完全一致。
まず$n=2から5$の範囲。赤が古典計算、青が量子計算。
序盤は古典コンピュータが優勢かもしれないが、終盤劣勢。

そして$n=2から100$の範囲。古典計算のほうには壁がそそり立っているかのように見える。