量子コンピュータの基礎[第2版]
SGCライブラリ - 69
量子コンピュータの基礎[第2版]
Lectures on Quantum Computation
細谷暁夫 著
2009年9月25日 第2版発行
量子計算機とは何か
テューリングマシン
古典計算機は原理的にテューリングマシン(Turing machine)という概念的な計算機に帰着される。
テューリングマシンは から成り立つ。
- :動作命令のリスト
- :入力テープ
- :作業テープ
入力テープ には、左端を示す記号 と右端を示す記号 に挟まれた、 の有限個の羅列が書き込まれている。
作業テープ には、 から始まって、 とブランク の羅列が半無限に続いている。
計算はヘッドが動作命令 に従って作業テープを書き換えることにより行われる。
入力ヘッドと作業ヘッドの次の動きが、右()か左() かあるいはその位置にとどまるか()を指定し、最後に のどの項目に移行するかを命令する。
あるいは、計算を停止する。
あるいは
は計算結果を受理して停止すること、 は答え NO を得て停止することを意味する。
量子テューリングマシン
量子計算機においては、可能な状態として と だけではなく、それらの重ね合わせも許される。(キュービット)
と は規格化条件 を満たす複素数。
古典計算機における と の書き換えは、量子計算機においては複素2次元空間のユニタリー変換にあたる。
量子計算は 次元のユニタリー変換を、ゲートと呼ばれる基本的なユニタリー変換の組み合わせで実行する。
このユニタリー変換は 個の並列計算と見なすことができる。
量子力学の公理
重ね合わせの原理
状態 と状態 が可能な状態であれば、 と を複素数として、その重ね合わせ も可能な状態である。
シュレーディンガー方程式
状態の時間発展は、シュレーディンガー方程式に従ってユニタリーな時間発展をする。
すなわち、 と状態ベクトル は発展し、時間発展の演算子 はユニタリー演算子である。
波束の収縮と確率解釈
をある物理量 の固有値とし、それらの固有状態を各々 とする。
重ね合わせの状態 にあるとき、物理量 を観測すると、状態は「波束の収縮」と呼ばれる遷移 あるいは を起こす。
各々の確率は、状態 と状態 が規格化されているとして、 と で与えられる。
多粒子状態とテンソル積
多粒子の状態は、1粒子の状態の積の重ね合わせ、すなわちテンソル積になる。
量子論理ゲート
古典計算機における論理ゲート
- NOT
- OR
- AND
- XOR
量子計算機における論理ゲート
量子計算はユニタリー変換のことなので、逆変換のあるゲートしか使えない。
- NOT は逆を持ち、ユニタリーである。
- 他の古典ゲートは逆を持たない。
制御 NOT (controlled-NOT gate)は、古典計算における XOR の働きもできる2キュービットゲートで、2つの入力ビットのうち一方を制御ビット(control bit)、他方を標的ビット(target bit)と呼ぶ。
制御ビットが と標的ビット の入力があれば、標的ビットに の出力がある。
量子回路では、制御 NOT と1ビットのユニタリー変換の組み合わせですべてのユニタリー変換が実行できる。
万能量子テューリングマシン(universal quantum Turing machine)
与えられたキュービットに対して、任意のユニタリー変換が実行できるゲートを持つテューリングマシンを万能量子テューリングマシンと呼ぶ。
任意の 行列 に対して、制御 NOT 2個と1キュービットの3個の のユニタリー行列 を使えば一般の制御– が作れる。
制御– は制御ビットが のときにのみ標的ビットが変換 を受ける量子論理ゲートである。
NOT は の基底では
$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$
で表すことができるので、制御 NOT は制御– の特別な場合である。
任意の 行列 に対して行列 を以下のように選ぶことができる。
量子計算の実験
量子計算機を実現するための段階:
- 量子的な重ね合わせ状態を物理的に実現して、それを操作すること
- 2ビットの制御 NOT を実現すること
- 少なくとも 個程度にビット数を増加させて、意味のある計算が可能な計算機を作ること
実現するためのポイント:
- デコヒーレンス時間が長いこと
- クリーンで速い制御 NOT ができること
- 拡張可能性