概要 †
- ゲート型とアニーラ型がある
- アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
- ある種の問題では古典コンピュータよりも早そうであると言われている
- 専門家ではないので僕が理解したと信じている範囲でのおきもち
アニーラ型 †
- バイナリ変数\( s_i \)を最適化する。設計した \( H_i, G_{ij} \) と (V, E) のグラフを考え、イジングモデル \( \sum_V H_i s_i + \sum_E G_{ij} s_i s_j \)を最小化する \( s_i \) を求めることができる（近似解）
- 数の分割問題、グラフの分割問題、クリーク判定問題、整数計画問題、精密被覆問題、集合パッキング問題（最大独立集合問題、MIS）、頂点被覆問題、充足可能性問題（SAT）、最小極大マッチング問題、整数重みナップサック問題、グラフ彩色問題、クリークカバー問題、整数長ジョブスケジューリング問題、ハミルトン閉路問題、巡回セールスマン問題、シュタイナー木問題、次数制約付き最小全域木問題、有向帰還頂点集合問題、無向帰還頂点集合問題、最小帰還辺集合問題、グラフ同型性判定問題などがこのイジングモデルに変換できる（まあ自由度が高いモデルだからそりゃそうという気持ち）
- 数学的にはそうだけど、実はマシンによってはイジング模型のグラフに対する制約もある。イジングマシンはイジングモデルを解くためのものなので別に量子である必要はない（CMOS, GPU, 量子など実装はまちまち）。
- 例えば、Fixstars Amplify AE, 富士通 Digital Annealer, 東芝 SQBM+ は量子ではなく完全グラフを扱える。D-Wave 2000Q は Chimera グラフ、D-Wave Advantage は Pegasus グラフであり、日立製作所によるイジングマシンの CMOS アニーリングは King's グラフを採用している。グラフ形状への落とし込みが一番の問題点となりそう。
- D-Wave 2000Q/Advantage は 2000~5000 くらいの変数を扱える。
- 係数パラメータも、D-Wave だと 5 bits くらいしかない。デジタルのものでも 3~64 までまちまち
- King's graph で完全グラフを表現するための埋め込みアルゴリズムが知られており、最新の D-Wave 2000Q では、2048 量子ビットを 16×16 のユニットセルで構築しています。そのため完全グラフ換算では 4×16=64 量子ビットに相当します。
- D-Wave が量子的効果を使っているのか、それが他のイジングモデルに比べて早いのか、そのあたりはかなり謎
ゲート型 †
- 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]")
