概要 †
- ゲート型とアニーラ型がある
- アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
- ある種の問題では古典コンピュータよりも早そうであると言われている
- 専門家ではないので僕が理解したと信じている範囲でのおきもち
ゲート型 †
- 2^n の論理符号を並列で扱うような説明をされがちだが、ほとんどの有用そうなアルゴリズムはどちらかというとアナログな計算をしている
- qubits の冪集合は実数値である位相を保持するメモリである。観測すると、|sin θ| の確率で 1, 1-|sin θ| の確率で 0 が出る
- 量子もつれによって、qubit 同士に拘束条件を加えることで、qubits の冪集合の確率分布を操作する
- 例: 00: 0度、01: 30度, 10: 0度, 11: 30度 ならば、観測すると 01, 11 だけが 50% ずつの確率で出現する
- メンタルモデルとしては https://www.youtube.com/watch?v=_b_yEgZh3BE&ab_channel=QuantumTokyo を見ておくと良さそう（グローバーのアルゴリズムの説明としては不適切なので、そこを期待して見てはいけない）
グローバーのアルゴリズム †
- 「f: 2^n -> bool を入力し、f(x) = true となるような x を量子状態として全列挙する。ただし量子状態なので全列挙内容は見れず、一回の観測ではその一例しか得られない」
- イメージとしては 3-SAT ソルバの論理式を設計する部分がオラクル設計と同じという理解。だから概ね 3-SAT と相性が良さそうな問題は解けそう（例: グラフ、スケジューリング、数独）に見えるが、実際には論理式を表現すると誤差で死ぬらしい (2023)
- 勝手に量子ゲートで作れることが AND の OR だけだと考えてしまいそうだが、実はもっと自由度があるはずであることには注意
- ということを理解していると巷で言われているデータベース検索が容易というのもかなり語弊があって、データベースのフルスキャン後に量子回路の構造を決定しないといけない気がしていて、フルスキャンの時点で計算量が O(n) になるんですがそれは…という気持ちに
ショアのアルゴリズム †
- 素因数分解ならし 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]")
