1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

求めたかった期待値

サイモンのアルゴリズムについては、
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$の範囲でプロットした。
expectation.png
おおお!大体$O(n)$か?
古典計算における試行回数$2^{n-1}+1$と比較。驚いたのは、$n=2$のとき完全一致。
まず$n=2から5$の範囲。赤が古典計算、青が量子計算。
序盤は古典コンピュータが優勢かもしれないが、終盤劣勢。
exp_and_bin.png
そして$n=2から100$の範囲。古典計算のほうには壁がそそり立っているかのように見える。
exp_and_bin2.png

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?