量子コンピュータ のバックアップ(No.4)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 量子コンピュータ へ行く。
  • 1 (2023-02-12 (日) 03:06:03)
  • 2 (2023-02-12 (日) 03:58:30)
  • 3 (2023-02-12 (日) 15:11:41)
  • 4 (2023-12-28 (木) 08:44:27)
  • 5 (2023-12-28 (木) 12:45:28)
  • 6 (2023-12-29 (金) 10:12:16)
  • 7 (2023-12-29 (金) 17:09:04)
  • 8 (2023-12-29 (金) 17:17:43)
  • 9 (2023-12-30 (土) 03:57:55)
  • 10 (2023-12-30 (土) 14:33:42)
  • 11 (2024-01-04 (木) 15:05:01)

概要 †

• ゲート型とアニーラ型がある
  • アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
• ある種の問題では古典コンピュータよりも早そうであると言われている
• 専門家ではないので僕が理解したと信じている範囲でのおきもち

アニーラ型 †

• バイナリ変数$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 が量子的効果を使っているのか、それが他のイジングモデルに比べて早いのか、そのあたりはかなり謎
  • 多分量子的効果を使ってはいそうだが、じゃあ GPU とか CMOS とかで実装したやつより早いの？と言われると超高速って感じじゃない気がする…（小並感）
  • 2022-10 くらいに、Amazon Braket から D-Wave が撤退するらしく、謎 https://blueqat.com/blueqat_official_news_ja/eff276c5-7c46-419e-8adf-7f45454ba2c2

ゲート型 †

• 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 を見ておくと良さそう（グローバーのアルゴリズムの説明としては不適切なので、そこを期待して見てはいけない）

基本 †

定義 †

• $\ket{i}$ は $i$ 要素目だけ 1 でほかが 0 の縦ベクトル
  • $\ket{0} = \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix}$ (|0>)
  • $\ket{0} = \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix}$ (|1>)
  • $\ket{10} = \ket{2} = (0, 0, 1, 0)$ (|3> = |10>)
• $\bra{i} = \ket{i}^*$、ket の共役転置
  • なので、$\bra{i} \ket{j}$ は i 行 j 列の要素だけ 1 でほかが 0 の行列
  • なので、$\ket{i} \bra{j}$ は i = j なら 1, そうでなければ 0

単一量子ビット・量子ゲート †

• 量子ビット $\ket{\psi} = \alpha \ket{0} + \beta \ket{1}$ where $|\alpha|^2 + |\beta|^2 = 1, \alpha, \beta \in \mathbb{C}$。
  • 量子ビットを「観測」すると、壊れて $|\alpha|^2$ の確率で 0 が、$|\beta|^2$ の確率で 1 が出力される。
• 演算子
  • 例えば演算子 $\bra{0}\ket{1}$ は量子ビット $\ket{\psi}$ に作用し、$\ket{\psi} = \alpha \ket{0} + \beta \ket{1}$ の $\ket{1}$ の係数 $\beta$ を使って $\beta \ket{0}$ を出力する。つまり、$\bra{0}\ket{1} \ket{\psi} = \beta \ket{0}$
• 量子ゲートは、演算子であって、対応する量子ビットへの操作が物理的に実現可能なもの
  • 逆操作が存在し、量子ビットから量子ビットへ移すようなものが量子ゲートであるという定義
  • 具体的には、ユニタリー行列であれば量子ゲート（有名なゲートとして X, Y, Z, H などがある）
  • 逆操作はエルミート共役
  • 演算子には、$\bra{0}\ket{0}, \bra{0}\ket{1}, \bra{1}\ket{0}, \bra{1}\ket{1}$ があったが、これは重ね合わせられる。単一量子ビットに作用する量子ゲートは、一般に $Z = \begin{bmatrix} \bra{0}\ket{0} & \bra{0}\ket{1} \\ \bra{1}\ket{0} & \bra{1}\ket{1} \\ \end{bmatrix}$ と表記され、状態ベクトル表記された $\ket{\psi}$ を与えて、$Z \ket{\psi}$ としてゲートの作用先を計算することができる。

複数量子ビット・量子ゲート †

• $n$ 個の量子ビットを並べた場合、複数量子ビットは $2^n$ 個の複素数 $c_i\ (\sum_i^{2^n - 1} |c_i|^2 = 1)$ で特徴づけられる。
  • 例えば $n=3$ では、$\ket{\psi} = \sum_{i, j, k \in 2^3} C_{ijk} \ket{ijk} = (c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7)^T$ と表現され、縦の状態ベクトルとして表記される。
• 定義
  • ket 表記は結合的: $\ket{011} = \ket{01} \otimes \ket{1} = \ket{0}\ket{1}\ket{1}= \ket{3}$
  • $a \otimes b$ はテンソル積。$a \otimes b = \begin{pmatrix} a_0 b \\ a_1 b \\ \end{pmatrix}$
  • $A \otimes B$ はテンソル積。$A \otimes B = \begin{pmatrix} a_{00} B & a_{01} B \\ a_{10} B & a_{11} B \\ \end{pmatrix}$
  • $(U_0 \otimes U_1)\ket{a_0 a_1} = U_0 \ket{a_0} U_1 \ket{a_1}$ https://quantum.riken.jp/pdf/ap2016_4.pdf
• 量子ビットは右から $0$ 番目、$1$ 番目と読む
• 「右から $i$ 番目の量子ビットに作用させる量子ゲート」を $Z_i$ のように表記する。
  • 2 量子ビットの $\ket{\psi} = \ket{01}$ の場合、$Z_0 \ket{\psi} = Z_0 \ket{01} = Z_0 (\ket{0} \otimes \ket{1}) = \ket{0} \otimes (Z_0 \ket{1})$ のように、該当する演算部分にのみ作用する。
  • $Z_0$ は、$n$ 量子ビットの状態ベクトルの長さ $2^n$ に対して、$\mathbb{R}^{2^n \times 2^n}$ の行列演算としても表記できる。

• 「右から $i$ 番目の量子ビットを観測」する場合、そこだけをくくりだした状態にして、その量子ビットがどちらの状態になるかを判定し、その後そうでなかった項を削除して状態ベクトルの二乗和が 1 になるように調整する。
  • 例: $\sqrt{2}/4 \ket{00} + \sqrt{3}/4 \ket{01} + \sqrt{5}/4 \ket{10} + \sqrt{6}/4 \ket{11}$ の $0$ ビット目を観測
    • $(\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0} + (\sqrt{3}/4 \ket{0} + \sqrt{6}/4 \ket{1}) \otimes \ket{1}$ なので、$0$ は $(\sqrt{2}/4)^2 + (\sqrt{5}/4)^2$, $1$ は $( \sqrt{3} / 4)^2 + (\sqrt{6}/4) ^ 2$ の確率で出力される。
    • $0$ が出力された場合、$\ket{1} = 0$ を代入した後に量子条件を満たすように変更する。$(\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0}$ と $0$ ビット目が $0$ のものだけを取り出したが、これでは係数が合わず量子ビットとして成立していないので、$4/\sqrt{7}$ をかけて補正する。すると、$4\sqrt{7}(\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0} = \sqrt{2}/sqrt{7} \ket{00} + \sqrt{5}/\sqrt{7} \ket{10}$ となり、正しい量子ビットになる。また、0 ビット目の量子ビットが 0 で確定していることがわかる。
• 量子もつれ
  • $1/\sqrt{2} \ket{0} \otimes \ket{0} + 1/\sqrt{2} \ket{1} \otimes \ket{1}$ を考えると、0 ビット目が 0 と観測されれば 1 ビット目は必ず 0 だし、0 ビット目が 1 と観測されれば 1 ビット目は必ず 1 になるということがわかる。これを量子もつれといい、量子テレポーテーションを実現できる。
• 制御ユニタリゲート
  • 2 入力 2 出力の量子ゲートで、制御ビットと標的ビットというものがある。「制御ビットが $\ket{0}$ ならば標的ビットに変更なし、$\ket{1}$ ならば標的ビットに何らかのユニタリ行列をかける」を行うもの（当然制御ビットも重ね合わせなので、変更のない世界線と行列がかけられた世界線は重なり合う）

• CNOT ゲート
  • 制御ユニタリゲートの一種で、「制御ビットが $\ket{0}$ ならば標的ビットに変更なし、$\ket{1}$ ならば標的ビットの係数を入れ替える」。実はこれと 1 量子ビットに対するユニタリゲートを合わせると任意の制御ユニタリゲートを実現できる。Controlled-NOT ゲート。
  • 例: 制御ビットが $\ket{0}$ (0 確定)、標的ビットが $1/sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1}$ → $\ket{0}\otimes(1/sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1})$
  • 例: 制御ビットが $\ket{1}$ (1 確定)、標的ビットが $1/sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1}$ → $\ket{0}\otimes(2/sqrt{5} \ket{0} + 1/\sqrt{5} \ket{1})$
  • 面白い例: 制御ビットが $1 / \sqrt{2} (\ket{0} + \ket{1})$、標的ビットが $\ket{0})$ (0 確定) → $\ket{00} + \ket{11}$ でもつれる（理由: 制御ビットが 0 だった世界線では標的ビットは 0 になり、制御ビットが 1 だった世界線では標的ビットが反転して 1 になるから）
  • CNOT $\ket{00}$ = $\ket{00}$, CNOT $\ket{01}$ = $\ket{01}$, CNOT $\ket{10}$ = $\ket{11}$, CNOT $\ket{11}$ = $\ket{10}$ より、CNOT = $\begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \\ \end{pmatrix}$

グローバーのアルゴリズム †

• 「f: 2^n -> bool を入力し、f(x) = true となるような x を量子状態として全列挙する。ただし量子状態なので全列挙内容は見れず、一回の観測ではその一例しか得られない」
• イメージとしては 3-SAT ソルバの論理式を設計する部分がオラクル設計と同じという理解。だから概ね 3-SAT と相性が良さそうな問題は解けそう（例: グラフ、スケジューリング、数独）に見えるが、実際には論理式を表現すると誤差で死ぬらしい (2023)
• 勝手に量子ゲートで作れることが AND の OR だけだと考えてしまいそうだが、実はもっと自由度があるはずであることには注意
• ということを理解していると巷で言われているデータベース検索が容易というのもかなり語弊があって、データベースのフルスキャン後に量子回路の構造を決定しないといけない気がしていて、フルスキャンの時点で計算量が O(n) になるんですがそれは…という気持ちに

ショアのアルゴリズム †

• 素因数分解ならし O(n^3 log n), 高速乗算を使うともうちょっと早くなる
  • 2014 bit RSA だと、2000 万個 qubits があれば 7.44 時間くらいで解けそう、くらいの感じらしい https://zenn.dev/hk_ilohas/articles/shor_algorithm#fnref-131d-2

• 手順
  • 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 を見つけるのが難しそう