概要 †
- ゲート型とアニーラ型がある
- ある種の問題では古典コンピュータよりも早そうであると言われている
グローバーのアルゴリズム †
- 「f: 2^n -> bool を入力し、f(x) = true となるような x で全列挙する。ただし列挙内容は見れず、一回の観測ではその一例しか得られない」
- イメージとしては 3-SAT ソルバの論理式を設計する部分がオラクル設計と同じという理解。だから概ね 3-SAT と相性が良さそうな問題は解けそう（例: グラフ、スケジューリング、数独）に見えるが、実際には論理式を表現すると誤差で死ぬらしい (2022)
- 勝手に量子ゲートで作れることが AND の OR だけだと考えてしまいそうだが、実はもっと自由度があるはずであることには注意
ショアのアルゴリズム †
- 素因数分解 O(n^3 log n), 高速乗算を使うともうちょっと早くなる
- 手順
- N=15 を素因数分解したい
- Nと互いに素な整数aをいい加減に見つける。これは簡単に見つかる（簡単に見つかるなら素因数分解が進むので）。今回はa=7とする。
- ショアのアルゴリズムは、a^r=7^r=1 (mod 15) なる r を、観測された量子ビットの位相からランダムより高い確率で一例出力することができる（証明略、またランダムなので失敗することもあり何回も試行する必要があることに注意）。
- 正しくない r ならば再試行
- 偶数の r を再試行
- 奇数の r を見つけることができれば a^r-1 mod N = (a^{r/2}-1)(a^{r/2}+1) = 0 mod N となる。
- 例: r=4が出力された場合、7^4=1 mod 15 なので、(7^2+1)(7^2-1)=0 mod 15, 50 * 48 = 0 (mod 15)
- ここで現れた 50, 48 は何か素因数分解っぽくもあるが実際には素因数分解ではない。ここで、gcd(50, 15), gcd(48, 15) が N の素因数分解である可能性が高いことを示すことができる（証明略）
- 今回、3, 5 が出力されていたので幸せだった。
- メモ
- なお、rはショアのアルゴリズムを実行した結果として得られる量子ビットを観測した時の位相θが、数学的には有理数 p/q (q<15) として表される。量子の性質上、観測ごとに異なる実数が出力される可能性があることに注意。観測したθを有理数としてp/q (q<15) と表したときの q がショアのアルゴリズムの出力 (の一例) r である。
- 位相は実数値だけど有理数は有理数だから、N がでかくなると量子計算の位相推定誤差で有理数を推定することが難しくなりませんか？
- 既約分数であるという制約はありますか？なくて p/q (q<N/2) だった場合、一回の観測で r は複数出ませんか？
- 感想
- N がデカいと誤差で実数から有理数の変換が大変そうで r を見つけるのが難しそう
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
