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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 量子コンピュータ へ行く。
  • 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)

概要 †

• ゲート型とアニーラ型がある
  • アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
• ある種の問題では古典コンピュータよりも早そうであると言われている
• 専門家ではないので僕が理解したと信じている範囲でのおきもち
  • 結局 qiskit で表示したり、テンソル積を手を動かしたりして、きちんと理解しないと意味がなさそう

参考 †

• https://sakumatcho.hatenablog.com/

アニーラ型 †

• バイナリ変数\( 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

数学的基礎 †

ユニタリ行列 †

• ユニタリ行列は実数での直交行列みたいなもの
  • 直交行列 \( M \in \mathbb{R}^{n \times n} \) は、行ベクトルのセットも列ベクトルのセットも正規直交基底になっており、\( x \) も \( Mx \) もノルムが変わらないようなやつ。回転行列や置換行列を含む。
  • ユニタリ行列 \( U \in \mathbb{C}^{n \times n} \) は直交行列の複素数版。重要な性質として
    • \( U \) の \( n \) 個の固有値のうち一つを \( \lambda \in \mathbb{C} \), その固有値に対応する固有ベクトルを \( x_{\lambda} \in \mathbb{C}^n \) とする（固有値の定義: \( U x_{\lambda} = \lambda x_\lambda \), つまり方向を変えずに \( U \) に伸ばされるベクトルが固有ベクトル、伸ばされる係数が固有値 \( \lambda \)）。この時、\( |\lambda| = 1 \)。複素数平面上の単位円にしか固有値がないということなので、\( \lambda = e^{i \theta}\ (\theta \in \mathbb{R}) \) と表記ができる。

テンソル積 †

• \( \mathbb{R^2} \)のベクトル空間と、\( \mathbb{R} \)のベクトル空間が、別の世界がある状態を考える。
  • これを一緒に扱いたい、自然な形でくっつけるように直和を考えると、\( \mathbb{R^3} \) を考えることができる。これを考えることで、別々の世界に居た住民を足すことができる。
  • \( v \in \mathbb{R^2} \) と \( w \in \mathbb{R} \) はそれぞれ、\( (v, 0) = v, (0, w) = 0 \) のように \( \mathbb{R^3} \) に移すことができる。
  • 直和の用語を使うと、\( v \in \mathbb{R^2} \) と \( w \in \mathbb{R} \) はそれぞれ、\( (v, 0) = v \oplus 0, (0, w) = 0 \oplus w \) のように \( \mathbb{R^2} \oplus \mathbb{R} \) の元として考えられる。
  • 集合 \( \mathbb{R^2}\oplus\mathbb{R} = {v \oplus w | v \in \mathbb{R^2}, w \in \mathbb{R}} \)
  • \( (v \oplus w) + (v' \oplus w') = (v + w) \oplus (v' + w') \)
  • \( r(v \oplus w) = (rv \oplus rw) \) スカラー \( r \) だけは両方の世界で共有される

• \( \mathbb{R} \) 代数のテンソル積
  • \( \mathbb{R}[X] \) を \( X \) を変数に持つ多項式環と、\( \mathbb{R}[Y] \) を \( Y \) を変数に持つ多項式環を考える。この別世界があるものと考える。
  • これを同じ箱の中に入れたい場合、\( \mathbb{R}[X,Y] = \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \) と考えると自然
  • 元の \( f(X) \in \mathbb{R}[X] \) は \( f(X) \otimes 1 \in \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \)
  • 元の \( g(X) \in \mathbb{R}[Y] \) は \( 1 \otimes g(Y) \in \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \)
  • 両方の世界で計算をしたいので、下記が成り立ってほしい（以下の条件は双線形写像と呼ばれる）
    • \( (f(X) \otimes g(X)) \cdot (f'(X) \otimes g'(Y)) = (f(X) f'(X)) \otimes (g(Y) g(Y)) \)。\( \cdot \) は \( \mathbb{R}[X] \otimes_{\mathbb{R}} \) 同士の積。それぞれの世界での積が適用される。
    • \( (f(X) + f'(X)) \times g(Y) = f(X) \otimes g(Y) + f'(X) \otimes g(Y) \)
    • \( (rf(X)) \times g(Y) = r (f(X) \otimes g(Y)) = f(X) \otimes (r g(Y)) \)
  • 環の直積と \( \mathbb{R} \) のテンソル積では環準同系ではないので異なる
  • \( \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}(Y) = \lbrace \sum_{i=1}^{N} f_i(X) \otimes g_i(Y) | f_i(X) \in \mathbb{R}[X], g_i(Y) \in \mathbb{R}[Y] \rbrace \)

• ベクトル空間のテンソル積
  • \( V, W \) をベクトル空間、\( V \) の基底が \( \lbrace v_1, \cdots, v_n \rbrace \), \( W \) の基底が \( \lbrace w_1, \cdots, w_m \rbrace \) とする。\( V \otimes_K W \) を \( \lbrace v_i \otimes w_j \rbrace\ (1 \le i \le n, 1 \le j \le m) \) を「形式的に」基底とする \( mn \) 次元ベクトルとする。
  • この時、\( - \otimes -: V \times W \rightarrow V \otimes_K W \) を \( v \otimes w = \sum_1^n \sum_1^m a_i b_j v_i \otimes w_j \) で定義する。
  • この時、\( (V \times W, - \otimes -) \) は \( V, W \) のテンソル積である。
  • ベクトル空間の線形写像のテンソル積
  • 写像 \( f: V \rightarrow V, g: W \rightarrow W \) について、\( f \otimes g \) を \( (f \otimes g)(v \otimes w) = f(v) \otimes g(w) \) で定義する。

ベクトル空間のテンソルの三表記とテンソル積の行列表現 †

• テンソル積の要素には以下の 3 つ（実際よく使うのは 2 つ）を意識することが重要
  • 1. 数学的な意味でのテンソル積。基底の総和として表現されるもの。
  • 2. 工学的な要請から「フラット化」されたテンソル積。多次元のテンソル積を一次元のベクトルに展開したもの。
  • 3. 2 階テンソルを行列のように表したもの（これをイメージしてもあまり意味がないが、これをイメージしても意味がないということを納得することは大切）

• 数学的な意味でのテンソル積
  • \( V \) を \( R^2 \)、\( W \) を \( R^3 \) とする。ここで、基底 \( e_{V0}, e_{V1} \in V, e_{W0}, e_{W1}, e_{W2} \in W \) とする。テンソル積 \( (V \times W, \otimes) \) の基底は \( e_{V0} \otimes e_{W0}, e_{V0} \otimes e_{W1}, e_{V0} \otimes e_{W2}, e_{V1} \otimes e_{W0}, e_{V1} \otimes e_{W1}, e_{V1} \otimes e_{W2} \) である。
  • ここで数学的な意味でのテンソル積は、\( a \otimes b = \sum_{ij} a_i b_j e_{Vi} \otimes e_{Wj} \) である。
  • 具体: \( a = \begin{pmatrix} -1 \\ 2 \\ \end{pmatrix} \in V, b = \begin{pmatrix} 3 \\ 4 \\ 5 \\ \end{pmatrix} \in W \)、\( V \) の基底を \( e_{V0} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \end{pmatrix}, e_{V1} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ \end{pmatrix}, e_{V2} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ \end{pmatrix} \)、\( W \) の基底を \( e_{W0} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \end{pmatrix}, e_{V1} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ \end{pmatrix} \) とする。この時、\( a \otimes b = -3 e_{V0} \otimes e_{W0} -4 e_{V0} \otimes e_{W1} -5 e_{V0} \otimes e_{W2} + 6 e_{V1} \otimes e_{W0} + 8 e_{V1} \otimes e_{W1} + 10 e_{V1} \otimes e_{W2} \)

• 工学的な要請から「フラット化」されたテンソル積
  • \( V \) を \( R^2 \)、\( W \) を \( R^3 \) とする。
  • ここで「フラット化」されたテンソル積は、\( a \otimes b = \begin{pmatrix} a_0 b_0 \\ a_0 b_1 \\ a_0 b_2 \\ a_1 b_0 \\ a_1 b_1 \\ a_1 b_2 \\ \end{pmatrix} \) である。ベクトルの要素の順序は、[右の添字, 左の添字] のリストの辞書順序が早い方から上から埋めていく。
  • 具体: \( a = \begin{pmatrix} -1 \\ 2 \\ \end{pmatrix} \in V, b = \begin{pmatrix} 3 \\ 4 \\ 5 \\ \end{pmatrix} \in W \) とすると、\( a \otimes b = \begin{pmatrix} -3 \\ -4 \\ -5 \\ 6 \\ 8 \\ 10 \\ \end{pmatrix} \)
    • 「2 階テンソルを行列のように表したもの」では、フラット化をせず、\( a \otimes b = \begin{pmatrix} -3 & -4 & -5 \\ 6 & 8 & 10 \\ \end{pmatrix} \) のような表記をすることも可能といえば可能だが、このような表記に対して線形写像を考えて行列演算の形式に落とし込むのは厳しいし、何より多次元拡張性がないので、このような表記は考えない。

• 「フラット化」されたテンソル積の行列表現
  • ここで、量子コンピュータは工学であるので、フラット化された演算を考えることとする。
  • \( V = R^2 \) とその基底 \( e_{V0}, e_{V1} \)、\( W = R^3 \) とその基底 \( e_{V0}, e_{V1}, e_{V2} \) を考える。
  • テンソル積 \( V \otimes W \) もまたベクトル空間となり、テンソル積の空間に閉じた線形写像 \( f: V \otimes W \rightarrow V \otimes W \) を考える。線形写像は一般に、それぞれの基底 \( i, j \) について、\( f(e_{Vi} \otimes e_{Wj}) = \sum_{k, l} T_{ij, kl} e_{Vk} \otimes e_{Wl} \) における \( T_{ij, kl} \) で必要十分に特徴づけることができる。
  • ここで、\( a \in V, b \in W \) について、\( f(a \otimes b) = \begin{pmatrix} T_{00,00} & T_{00,01} & T_{00,10} & T_{00,11} \\ T_{01,00} & T_{01,01} & T_{01,10} & T_{01,11} \\ T_{10,00} & T_{10,01} & T_{10,10} & T_{10,11} \\ T_{11,00} & T_{11,01} & T_{11,10} & T_{11,11} \end{pmatrix} \) と行列を辞書順に埋めた形になる（参考までに。証明しなくてもよい）
  • 一方、\( f \) の具体例として、\( V, W \) で定義される行列 \( A \in V^2, B \in W^2 \) を考え、\( f: a \otimes b \rightarrow (A a) \otimes (B b) \) となるような \( f \) の行列表現を \( A \otimes B \) と定義する。つまり、\( (A \otimes B)(a \otimes b) = (Aa) \otimes (Bb) \)である。
    • ここで、\( a \otimes b \) が「フラット化された」テンソル積だとすると、\( (A a) \otimes (B b) = M a \otimes b \) となるような \( M \) を具体的に構成することが可能である。これは、\( (A \otimes B)(e_{Ai} \otimes e_{Bj}) = \sum_{k, l} A_{ki} B_{lj} e_{Vi} e_{Wj} \) より（詳しく追わなくていい）、\( A \otimes B = \begin{pmatrix} A_{00} B & A_{01} B \\ A_{10} B & A_{11} B \\ \end{pmatrix} \) と表記可能である（重要！）

• 計算演習
  • \( \begin{align*} A &= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ a &= \begin{pmatrix} -1 \\ 2 \end{pmatrix}, \quad b = \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \end{align*} \)
  • これに対して、\( (A \otimes B)(a \otimes b) \) を 2 つの方法で計算する。
  • 先に \( (A \otimes B)(a \otimes b) = (A a) \otimes (B b) \) を計算したパターン
    • \( \begin{align*} Aa &= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} -1 \\ 2 \end{pmatrix} \\ &= \begin{pmatrix} 1(-1) + 2(2) \\ 3(-1) + 4(2) \end{pmatrix} \\ &= \begin{pmatrix} 3 \\ 5 \end{pmatrix} \\ Bb &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \\ &= \begin{pmatrix} 3 \\ 8 \\ 5 \end{pmatrix} \end{align*} \)
    • \( (A \otimes B)(a \otimes b) = (A a) \otimes (B b) = \begin{pmatrix} 3 \\ 5 \end{pmatrix} \otimes \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} = \begin{pmatrix} 9 \\ 24 \\ 15 \\ 15 \\ 40 \\ 25 \end{pmatrix} \)

• 先に \( A \otimes B \) を計算したパターン（フラット化されたテンソル積の表記での線形変換の合成）
  • \( \begin{align*} A \otimes B &= \begin{pmatrix} 1 \cdot B & 2 \cdot B \\ 3 \cdot B & 4 \cdot B \end{pmatrix} \\ &= \begin{pmatrix} 1 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} & 2 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ 3 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} & 4 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 0 & 4 & 0 \\ 0 & 0 & 1 & 0 & 0 & 6 \\ 3 & 0 & 0 & 4 & 0 & 0 \\ 0 & 6 & 0 & 0 & 8 & 0 \\ 0 & 0 & 9 & 0 & 0 & 4 \end{pmatrix} \end{align*} \)
  • \( \begin{align*} a \otimes b &= \begin{pmatrix} -1 \cdot \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \\ 2 \cdot \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \end{pmatrix} \\ &= \begin{pmatrix} -3 \\ -4 \\ -5 \\ 6 \\ 8 \\ 10 \end{pmatrix} \end{align*} \)
  • \( (A \otimes B)(a \otimes b) = \begin{pmatrix} 9 \\ 24 \\ 15 \\ 15 \\ 40 \\ 25 \end{pmatrix} \)

ゲート型 †

• 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_2} = \ket{2_{10}} = (0, 0, 1, 0) \) (下付きの文字は基数。|14_10> = |1110_2>、自明な場合は省略される)
• \( \bra{i} = \ket{i}^* \)、ket の共役転置
  • なので、\( \bra{i} \ket{j} \) は i 行 j 列の要素だけ 1 でほかが 0 の行列
  • なので、\( \ket{i} \bra{j} \) は i = j なら 1, そうでなければ 0
• \( \ket{10_2} = \ket{1_2} \otimes \ket{0_2} \) のように分解できる。教科書によっては \( \ket{\psi} \) 間の直積を全部 \( \otimes \) でつなぐのが面倒になって、\( \otimes \) を省略するようなものもよく見られる。心の目で \( \otimes \) が見えるようになるまでは明示して勉強したほうがいい。

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

• 量子ビット \( \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_2} = \ket{01_2} \otimes \ket{1_2} = \ket{0_2} \otimes \ket{1_2} \otimes \ket{1_2}= \ket{3_{10}} \)
  • \( a \otimes b \in \mathbb{C} \otimes \mathbb{C} \) はテンソル積。\( a \otimes b = \begin{pmatrix} a_0 b \\ a_1 b \\ \end{pmatrix} \)
  • \( A \otimes B: \mathbb{C} \otimes \mathbb{C} \rightarrow \mathbb{C} \otimes \mathbb{C} \) はテンソル積の線形変換の行列表記。\( (A \otimes B) a \otimes b = (A a) \otimes (B b) \) で定義される。\( 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 b} = (U_0 \otimes U_1)(\ket{a} \otimes \ket{b}) = (U_0 \ket{a}) \otimes (U_1 \ket{b}) \) (テンソル積の双線型性の定義より)
• 量子ビットは右から \( 0 \) 番目、\( 1 \) 番目と読む
• 「右から \( i \) 番目の量子ビットに作用させる量子ゲート」を \( Z_i \in \mathbb{C}^{2 \times 2} \) のように表記する。
  • 2 量子ビットの \( \ket{\psi} = \ket{01} = \ket{0} \otimes \ket{1} \) に右から \( 0 \) 番目の量子ビットに作用する量子ゲート \( Z_i \) を適用すると、作用後は \( \ket{0} \otimes (Z_0 \ket{1}) \) のように、該当する演算部分にのみ作用する。
  • 重要: \( Z_0 \) は \( \ket{01} \) 全体にかけるための行列ではなく、あくまで 0 ビット目の \( \ket{1} \) に局所的にかかるものである。
    • \( Z_0 \) を 0 ビット目に作用させる演算を \( \ket{0} \otimes (Z_0 \ket{1}) \) と同値な、\( \ket{01} \) 全体にかけるユニタリ行列を \( U_{Z_0} \) を考える。つまり、\( U_{Z_0} = \ket{0} \otimes (Z_0 \ket{1}) \) となるような \( U_{Z_0} \in \mathbb{C}^{2^2 \times 2^2} \) を考える。
    • これは、\( U_{Z_0} = I \otimes Z_0 \) で与えられ (ただし \( I \in \mathbb{C}^{2 \times 2} \) は単位行列)、具体的な表記はフラット化されたテンソル積の表記の行列の合成にしたがう。なぜかと言うと \( (I \otimes Z_0) (\ket{0} \otimes \ket{1}) = (I \ket{0}) \otimes (Z_0 \ket{1}) \) (テンソルの計算規則より) \( = \ket{0} \otimes (Z_0 \ket{1}) \)
    • 一般に、\( Z_i \) を \( n \) 量子ビットの状態ベクトル全体にかかるような行列表記することが一般にできる。これは \( I \otimes \cdots \otimes Z_i \otimes I \otimes \cdots \otimes I \) という線形変換を、テンソル積のフラット化された表記の行列の合成にしたがい構成することがすることで、長さ \( 2^n \) の縦ベクトルにフラット化された量子ベクトルに対する \( \mathbb{C}^{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 になるということがわかる。これを量子もつれといい、量子テレポーテーションを実現できる。

頻出ゲート †

Hadamard (アダマール) ゲート †

• H で表される 1 量子ゲート
• 対象の量子ビットに対して行列 \( H = 1/\sqrt{2} \begin{pmatrix} 1&1\\1&-1\\ \end{pmatrix} \) をかける。

• 計算練習の意味も兼ねて、式変形は非常に説明的にしています。
• 例1　(アダマールテストの第一段階)
  • \( \ket{0} \otimes \ket{\psi} \) の右から 1 ビット目 (0-indexed, 要するに \( \ket{0} \)）にかける
  • \( \begin{align*} (H \otimes I) (\ket{0} \otimes \ket{\psi}) \\ &= \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}\right) \otimes \ket{\psi} \\ &= \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \otimes \ket{\psi} \\ &= \left(\frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1}\right) \otimes \ket{\psi} \\ &= \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \\ &= \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \end{align*} \)
• 例2　(アダマールテストの第三段階)
  • \( \frac{1}{\sqrt{2}} (\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U\ket{\psi})) \) の右から 1 ビット目 (0-indexed) にかける
  • この時、全てのテンソル積の項（つまり、\( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} \) と \( \frac{1}{\sqrt{2}} \ket{1} \otimes (U\ket{\psi})) \) の両方）の右から 1 ビット目 (0-indexed) に H をかけることになることに注意
  • \( \begin{align*} &(H \otimes I) \left(\frac{1}{\sqrt{2}} (\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U\ket{\psi}))\right) \\ &= (H \otimes I) \left(\frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi}\right) + (H \otimes I)\left(\frac{1}{\sqrt{2}} \ket{1} \otimes (U\ket{\psi})\right) \\ &= \left(H \frac{1}{\sqrt{2}} \ket{0}\right) \otimes \ket{\psi} + \left(H \frac{1}{\sqrt{2}} \ket{1}\right) \otimes (U\ket{\psi}) \\ &= \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix}1 \\ 0 \end{pmatrix}\right) \otimes \ket{\psi} + \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix}0 \\ 1 \end{pmatrix}\right) \otimes (U\ket{\psi}) \\ &= \left(\frac{1}{2} \begin{pmatrix} 1 \\ 1 \end{pmatrix}\right) \otimes \ket{\psi} + \left(\frac{1}{2} \begin{pmatrix} 1 \\ -1 \end{pmatrix}\right) \otimes (U\ket{\psi}) \\ &= \frac{1}{2} (\ket{0} + \ket{1}) \otimes \ket{\psi} + \frac{1}{2} (\ket{0} - \ket{1}) \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes \ket{\psi} + \frac{1}{2} \ket{1} \otimes \ket{\psi} + \frac{1}{2} \ket{0} \otimes (U\ket{\psi}) - \frac{1}{2} \ket{1} \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes (I \ket{\psi}) + \frac{1}{2} \ket{1} \otimes (I \ket{\psi}) + \frac{1}{2} \ket{0} \otimes (U\ket{\psi}) - \frac{1}{2} \ket{1} \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes (I + U) \ket{\psi} + \frac{1}{2} \ket{1} \otimes (I - U) \ket{\psi} \end{align*} \)

制御ユニタリゲート †

• 2 入力 2 出力の量子ゲートで、制御ビットと標的ビットというものがある。「制御ビットが \( \ket{0} \) ならば標的ビットに変更なし、\( \ket{1} \) ならば標的ビットにユニタリ行列 \( U \) をかける」を行うもの（当然制御ビットも重ね合わせなので、変更のない世界線と行列がかけられた世界線は重なり合う）
  • ここですごいのは、「従来のコンピュータでは条件分岐は同時に実行することができないが、量子コンピュータでは状態の重ね合わせを利用して、条件分岐を同時並列的に実行することができる。」ところ！
  • 標的ビットは複数でもよい。
• 例1 (アダマールテストの第二段階)
  • \( \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \) の右から 1 ビット目を制御ビットとして、右から 0 ビット目を標的ビットにする。
  • \( \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \\ = \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \) において、1 項目 \( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} \) の 1 ビット目は \( \ket{0} \) なので、0 ビット目に対しては何もしない。2 項目 \( \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \) の 1 ビット目は \( \ket{1} \) なので、0 ビット目に対して \( U \) をかける。
  • その結果、制御ユニタリゲートを通したあとの量子状態は \( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes (U \ket{\psi}) \\ = \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U \ket{\psi}) \right) \) となる。

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