物理ノート

サイエンス社「数理科学」SGCライブラリの読書メモ

量子コンピュータの基礎[第2版]

SGCライブラリ - 69

量子コンピュータの基礎[第2版]

Lectures on Quantum Computation

細谷暁夫 著

2009年9月25日 第2版発行

量子計算機とは何か

テューリングマシン

古典計算機は原理的にテューリングマシン(Turing machine)という概念的な計算機に帰着される。

テューリングマシンは  {TM = \{Q,\Sigma,\Gamma\}} から成り立つ。

  •  {Q = \{q_0,q_1,\dots\}}:動作命令のリスト
  •  {\Sigma}:入力テープ
  •  {\Gamma}:作業テープ

入力テープ  {\Sigma} には、左端を示す記号  {\vdash} と右端を示す記号  {\dashv} に挟まれた、 {0,\,1} の有限個の羅列が書き込まれている。

作業テープ  {\Gamma} には、 {\vdash} から始まって、 {0,\,1} とブランク  {B} の羅列が半無限に続いている。

計算はヘッドが動作命令  {q_0,q_1,\dots} に従って作業テープを書き換えることにより行われる。

入力ヘッドと作業ヘッドの次の動きが、右( {R})か左( {L}) かあるいはその位置にとどまるか( {S})を指定し、最後に  {Q} のどの項目に移行するかを命令する。

 {(q \in Q,\,b \in \Sigma,\,b_1 \in \Gamma) \mapsto (b_1^{\prime} \in \Gamma,\,X \in \{R,L,S\},\,Y \in \{R,L,S\},\,q^{\prime} \in Q)}

あるいは、計算を停止する。

 {(q \in Q,\,b \in \Sigma,\,b_1 \in \Gamma) \mapsto A} あるいは  {N}

 {A} は計算結果を受理して停止すること、 {N} は答え NO を得て停止することを意味する。

量子テューリングマシン

量子計算機においては、可能な状態として  {|0\rangle} {|1\rangle} だけではなく、それらの重ね合わせも許される。(キュービット)

 {|\psi\rangle = \alpha|0\rangle + \beta|1\rangle}

 {\alpha} {\beta} は規格化条件  {|\alpha|^2 + |\beta|^2 = 1} を満たす複素数。

古典計算機における  {0} {1} の書き換えは、量子計算機においては複素2次元空間のユニタリー変換にあたる。

量子計算は  {2^N} 次元のユニタリー変換を、ゲートと呼ばれる基本的なユニタリー変換の組み合わせで実行する。

このユニタリー変換は  {2^N} 個の並列計算と見なすことができる。

量子力学の公理

重ね合わせの原理

状態  {|\alpha\rangle} と状態  {|b\rangle} が可能な状態であれば、 {\alpha} {\beta} を複素数として、その重ね合わせ  {\alpha|a\rangle + \beta|b\rangle} も可能な状態である。

シュレーディンガー方程式

状態の時間発展は、シュレーディンガー方程式に従ってユニタリーな時間発展をする。

すなわち、 {|\psi\rangle \to U|\psi\rangle} と状態ベクトル  {|\psi\rangle} は発展し、時間発展の演算子  {U} はユニタリー演算子である。

波束の収縮と確率解釈

 {a,\,b} をある物理量  {Q} の固有値とし、それらの固有状態を各々  {|a\rangle,\,|b\rangle} とする。

重ね合わせの状態  {\alpha|a\rangle + \beta|b\rangle} にあるとき、物理量  {Q} を観測すると、状態は「波束の収縮」と呼ばれる遷移  {\alpha|a\rangle + \beta|b\rangle \to |a\rangle} あるいは  {\alpha|a\rangle + \beta|b\rangle \to |b\rangle} を起こす。

各々の確率は、状態  {|a\rangle} と状態  {|b\rangle} が規格化されているとして、 {|\alpha|^2} {|\beta|^2} で与えられる。

多粒子状態とテンソル積

多粒子の状態は、1粒子の状態の積の重ね合わせ、すなわちテンソル積になる。

量子論理ゲート

古典計算機における論理ゲート

  • NOT
    •  {|0\rangle \to |1\rangle}
    •  {|1\rangle \to |0\rangle}
  • OR
    •  {|0\rangle|0\rangle \to |0\rangle}
    •  {|0\rangle|1\rangle \to |1\rangle}
    •  {|1\rangle|0\rangle \to |1\rangle}
    •  {|1\rangle|1\rangle \to |1\rangle}
  • AND
    •  {|0\rangle|0\rangle \to |0\rangle}
    •  {|0\rangle|1\rangle \to |0\rangle}
    •  {|1\rangle|0\rangle \to |0\rangle}
    •  {|1\rangle|1\rangle \to |1\rangle}
  • XOR
    •  {|0\rangle|0\rangle \to |0\rangle}
    •  {|0\rangle|1\rangle \to |1\rangle}
    •  {|1\rangle|0\rangle \to |1\rangle}
    •  {|1\rangle|1\rangle \to |0\rangle}

量子計算機における論理ゲート

量子計算はユニタリー変換のことなので、逆変換のあるゲートしか使えない。

  • NOT は逆を持ち、ユニタリーである。
  • 他の古典ゲートは逆を持たない。

制御 NOT (controlled-NOT gate)は、古典計算における XOR の働きもできる2キュービットゲートで、2つの入力ビットのうち一方を制御ビット(control bit)、他方を標的ビット(target bit)と呼ぶ。

制御ビットが  {|a\rangle} と標的ビット  {|b\rangle} の入力があれば、標的ビットに  {|a + b \bmod 2\rangle} の出力がある。

量子回路では、制御 NOT と1ビットのユニタリー変換の組み合わせですべてのユニタリー変換が実行できる。

万能量子テューリングマシン(universal quantum Turing machine)

与えられたキュービットに対して、任意のユニタリー変換が実行できるゲートを持つテューリングマシンを万能量子テューリングマシンと呼ぶ。

任意の  {SU(2)} 行列  {U} に対して、制御 NOT 2個と1キュービットの3個の  {SU(2)} のユニタリー行列  {A,\,B,\,C} を使えば一般の制御– {U} が作れる。

制御– {U} は制御ビットが  {|1\rangle} のときにのみ標的ビットが変換  {U} を受ける量子論理ゲートである。

NOT は  {|0\rangle,\,|1\rangle} の基底では

$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

で表すことができるので、制御 NOT は制御– {U} の特別な場合である。

任意の  {SU(2)} 行列  {U} に対して行列  {A,\,B,\,C} を以下のように選ぶことができる。

  •  {ABC = 1}
  •  {AXBXC = U}

量子計算の実験

量子計算機を実現するための段階:

  1. 量子的な重ね合わせ状態を物理的に実現して、それを操作すること
  2. 2ビットの制御 NOT を実現すること
  3. 少なくとも  {10^6} 個程度にビット数を増加させて、意味のある計算が可能な計算機を作ること

実現するためのポイント:

  • デコヒーレンス時間が長いこと
  • クリーンで速い制御 NOT ができること
  • 拡張可能性

NMR 計算機

量子計算機はなぜ速いか

因数分解

離散対数問題に対するショアのアルゴリズム

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

ドイチ・ジョサの問題

群論的アプローチ

計算の複雑さと量子計算機

量子誤り訂正(quantum error correction)

一方向量子計算