🔗概要

• ゲート型とアニーラ型がある

  • アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
  • ゲートは「ある種の問題では古典コンピュータよりも早そうであると言われている」くらいの気持ち。現在は量子メモリと誤り訂正が全然できていなくて、見た目、実用レベルには 1000 年以上かかりそう

• なので、僕はゲートもアニーラもあまり勉強したいと思わない（というか、「量子すごいよ、面白いよ」という発信をするのは、優秀な頭脳が実現可能性と公益性の低い量子コンピュータに集まってしまうため、社会的に悪だと思っている）

• 専門家ではないので僕が理解したと信じている範囲でのおきもち

  • 結局 qiskit で表示したり、テンソル積を手を動かしたりして、きちんと理解しないと意味がない。
  • アルゴリズムを考えるときに、何でもかんでも離散フーリエ変換とユニタリ行列の固有値・固有ベクトル計算を介さないといけなくてつらすぎる。。

• 自作したシミュレータ

🔗参考

• https://sakumatcho.hatenablog.com/

🔗目次

• アニーラ型
• 数学的基礎
  • ユニタリ行列
  • テンソル積
  • ベクトル空間のテンソルの三表記とテンソル積の行列表現
• ゲート型
  • 基本
    • 定義
    • 単一量子ビット・量子ゲート
    • 複数量子ビット・量子ゲート
  • 頻出ゲート
    • Hadamard (アダマール) ゲート
    • 制御ユニタリゲート
  • 具体的なアルゴリズムに入っていく前に
  • 疑似乱数生成
  • アダマールテスト
    • CNOT ゲート
  • グローバーのアルゴリズム
  • ショアのアルゴリズム
• qiskit
  • Quickstart (CLI)
  • Quickstart (Jupyter Notebook)

🔗アニーラ型

• バイナリ変数$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^{\prime }\oplus w^{\prime })=(v+w)\oplus (v^{\prime }+w^{\prime })$
  • $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^{\prime }(X)\otimes g^{\prime }(Y))=(f(X)f^{\prime }(X))\otimes (g(Y)g(Y))$。$\cdot$ は $\mathbb{R}[X]{\otimes }_{\mathbb{R}}$ 同士の積。それぞれの世界での積が適用される。
    • $(f(X)+f^{\prime }(X))\times g(Y)=f(X)\otimes g(Y)+f^{\prime }(X)\otimes g(Y)$
    • $(rf(X))\times g(Y)=r(f(X)\otimes g(Y))=f(X)\otimes (rg(Y))$
  • 環の直積と $\mathbb{R}$ のテンソル積では環準同系ではないので異なる
  • $\mathbb{R}[X]{\otimes }_{\mathbb{R}}\mathbb{R}(Y)=\{{\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]\}$

• ベクトル空間のテンソル積

  • $V,W$ をベクトル空間、$V$ の基底が $\{v_1,\cdots ,v_n\}$, $W$ の基底が $\{w_1,\cdots ,w_m\}$ とする。$V{\otimes }_{K}W$ を $\{v_i\otimes w_j\}(1\le i\le n,1\le j\le m)$ を「形式的に」基底とする $mn$ 次元ベクトルとする。
  • この時、$-\otimes -:V\times W\to 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\to V,g:W\to W$ について、$f\otimes g$ を $(f\otimes g)(v\otimes w)=f(v)\otimes g(w)$ で定義する。