量子コンピュータ

我々のコンピュータの理論は、最終的には実際のコンピュータと関連しなければなりません。そのためには、物理的に動作するコンピュータの計算を考えなければなりません。

現代の物理学では力学は相対論的量子力学によるとされています。そのため、コンピュータもそれを原理とした動作を前提としなければなりません。しかし、相対論的量子力学は日常的にはニュートン力学などの古典論で近似されます。そのため、現代コンピュータは半導体を使用してはいますが、基本的な計算原理は古典的な電磁気学などに基づいています。そして、現代コンピュータの動作速度はムーアの法則に従えず、徐々に限界へと近づいています。

ファインマンが提唱し、ドイチェが形式化した量子コンピュータは、量子力学に基づいたコンピュータです。そして、ショーアにより、素因数分解を行う高速なアルゴリズムと、グルーバーによる選択問題の高速なアルゴリズムが開発されたことにより、現在に至るまで、量子コンピュータの実現の研究が盛んに行われています。

14-1. 量子力学

概要

古典力学は原子レベルの微細な現象を説明できず破綻することが分かり、微細な現象を説明できる力学が必要となりました。そこで登場したのが量子力学です。しかし、従来の力学とは大きく異なるため、本質を理解するのはなかなか難しいです。さらに、物質の本質的な状態は正確に測定できない（不確定性原理）という性質があります。これは、従来の物理の根底にある、この世のものは目で見えたように存在するという素朴実在論という哲学をひっくり返しました。さらに、量子力学では仮定している本質を知る術がないという性質から、正当性を証明することを不可能にしています。但し、様々な実験結果を良く説明する理論の中ではもっともシンプルな理論であるため、支持されています。

なお、ヒルベルト空間とは完備な内積空間のことです。列ベクトル

|ψ⟩

に対して、エルミート転置行ベクトルを

{|ψ⟩}^{†} = ⟨ψ|

と書きます。そして、

⟨ψ|

|ψ'⟩

の内積を

⟨ψ | ψ'⟩

で表します。自己共役演算子とは複素ヒルベルト空間

H

の関数

h : H \to H

が

⟨h ψ | ψ'⟩ = ⟨ψ | h ψ'⟩

を満たすことです。例えば、転置複素行列が元の行列と等しい、エルミート行列は自己共役演算子になります。自己共役演算子の固有値はすべて実数になりますので、量子力学の枠組みでの観測値はすべて実数です。

ユニタリ行列Uとは

U U^{†} = \hat{1}

を満たす行列のことである。

さらに、列ベクトル

|ψ⟩

から作った行列

|ψ⟩ ⟨ψ|

は自己共役演算子になります。この自己共役演算子は

|ψ⟩

に平行な成分を取り出すため、

|ψ⟩

への射影演算子と呼ばれます。

なお、固有ベクトルは、相互に長さ1で直交するように正規化するものとする。

さらに、任意の自己共役演算子のすべての固有ベクトルを集めると、そのヒルベルト空間の任意のベクトルを線形結合で表せるという完全系をなすことが知られている。状態

ψ

に対して固有ベクトル

a

ごとの係数を返す関数(波動関数)

ψ (a) \in C

を仮定すると、状態ベクトルを次のように表現できる。

さらに、各固有ベクトル同士は直交するように選んでいるので、以下が導かれる。

⟨a| ψ⟩ = \sum_{a} ψ (a) ⟨a| a⟩ = ψ (a)

|ψ⟩ = \sum_{a} ⟨a| ψ⟩ |a⟩ = \sum_{a} |a⟩ ⟨a| |ψ⟩

\sum_{a} |a⟩ ⟨a| = \hat{1}

固有値 a に対応する固有ベクトルから得られる射影演算子の和を

\hat{P} (a)

で表す。

これを用いると、状態 ψ に対して a が観測される確率は次で表される。

古典論の破綻

熱源から放射される電磁波のスペクトル分布がプランクの法則で説明されることが分かり、電磁波のエネルギーがエネルギーの最小単位に振動数を掛けたもの

E = h ν

の整数倍であることを仮定することで導かれることも分かりました。

原子の構造が、原子核と電子からなるものと分かって来たとき、原子の大きさが定まらないことや、電子が粒子としたときに、軌道が存在することや、さらに、軌道に止まることが古典論では何も説明できないことが分かって来ました。

さらにシュテルン・ゲルラッハ(SternGerlach)の実験が行われました。これは、銀の蒸気を不均一な磁界の中に通す実験です。銀の蒸気は電気的に中性なので、ローレンツ力による影響は受けません。しかし、それでも銀の粒子に磁気モーメントがあれば、不均一な磁界においては磁気の不均一さによる影響を受けるはずです。つまり、この実験は銀の粒子の磁気モーメントを計測する実験となります。そして、実際に磁気モーメントの影響を調べたところ、一定の分布ではなく、たった 2種類に均等に分類されました。後に、ナトリウム、水素でも測定しましたが、同じ結果が得られました。これは、電子は2種類だけの磁気モーメントを等確率で持つことを示しています。

後に、平行な二本のスリットに電子を一個ずつ発射すると、スリットの後ろに干渉縞ができる実験が行われました。

また、アインシュタイン、ポドルスキー、ローゼンは一つの素粒子から生まれた二つの粒子を遠隔で観測した場合、（例えば、磁気モーメントの無い粒子から二つの電子が生まれた場合、二つの磁気モーメントは互いに逆になっているなどの）相関関係が生じるには観測の因果が光速を越えなければならないことを指摘しましたが、実際に測定すると相関関係が存在することが分かりました。また、ベル不等式という、古典論で仮定される局所実在論という目の前の物体はそのまま存在し、遠隔の物体とは因果律を越えないことを仮定することで得られる不等式が破られることも実験で分かりました。

量子論の基礎

シュテルン・ゲルラッハの実験により、電子に磁気モーメントがあることが分かりました。そして、そこから、電子に2種類の回転モーメントがあることが分かりました。これを電子のスピンと呼び、 +1, -1 や +1/2, -1/2　や +, - などと表します。ここではこの電子のスピンに話を絞って進めます。

電子の磁気モーメント内部状態を二次元複素数ベクトル空間の長さ1の列ベクトル

|ψ⟩ = (\begin{matrix} ξ \\ η \end{matrix})

ξ^{*} ξ + η^{*} η = 1

で表します。

これを観測して、 +1, -1 が得られるような自己共役演算子

\hat{A} = (\begin{matrix} a & b \\ c & d \end{matrix})

を求めます。つまり、これが二つの固有値 +1 と -1 を持つ条件を求めます。

\hat{A}

が固有値qを持つ場合、固有ベクトルpを用いると、次のように書けます。

これで、 qは +1 と -1 、また

\hat{A}

はエルミート転置行列ですから、 a, dは実数,

b = c^{*}

ですが、さらに次が得られます。

σ_{x} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})

σ_{y} = (\begin{matrix} 0 & -ⅈ \\ ⅈ & 0 \end{matrix})

σ_{z} = (\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix})

パウリの行列には様々な性質があります。例えば、これに単位行列を加えると、あらゆるエルミート行列がパウリ行列の実数倍の和で表されるなどです。

パウリ行列のそれぞれに対して、長さ 1 の固有ベクトルを求めると次の様になります。

σ_{x} の固有ベクトル = \frac{1}{\sqrt{2}} (\begin{matrix} 1 \\ \pm 1 \end{matrix}) = |\pm_{x}⟩ とおく

σ_{y} の固有ベクトル = \frac{1}{\sqrt{2}} (\begin{matrix} 1 \\ \pm ⅈ \end{matrix}) = |\pm_{y}⟩ とおく

σ_{z} の固有ベクトル = (\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \end{matrix}) = |\pm_{z}⟩ とおく

|ψ⟩ = (\begin{matrix} ξ \\ η \end{matrix})

を σ _x で観測すると、 +1, -1 が観測される確率はそれぞれ

\Pr ({+1}_{x}) = {|⟨+_{x} | ψ⟩|}^{2} = {|({\frac{1}{\sqrt{2}}}^{*}  {\frac{1}{\sqrt{2}}}^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|\frac{1}{\sqrt{2}} (ξ + η)|}^{2} = \frac{1}{2} (ξ^{*} + η^{*}) (ξ + η) = \frac{1}{2} (ξ^{*} ξ + η^{*} η + ξ^{*} η + ξ η^{*}) = \frac{1}{2} (1 + ξ^{*} η + ξ η^{*})

\Pr ({-1}_{x}) = {|⟨-_{x} | ψ⟩|}^{2} = {|({\frac{1}{\sqrt{2}}}^{*}  {\frac{-1}{\sqrt{2}}}^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|\frac{1}{\sqrt{2}} (ξ - η)|}^{2} = \frac{1}{2} (ξ^{*} - η^{*}) (ξ - η) = \frac{1}{2} (ξ^{*} ξ + η^{*} η - ξ^{*} η - ξ η^{*}) = \frac{1}{2} (1 - ξ^{*} η - ξ η^{*})

|ψ⟩ = (\begin{matrix} ξ \\ η \end{matrix})

を σ _y で観測すると、 +1, -1 が観測される確率はそれぞれ

\Pr ({+1}_{y}) = {|⟨+_{y} | ψ⟩|}^{2} = {|({\frac{1}{\sqrt{2}}}^{*}  {\frac{ⅈ}{\sqrt{2}}}^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|\frac{1}{\sqrt{2}} (ξ - η ⅈ)|}^{2} = \frac{1}{2} (ξ^{*} + η^{*} ⅈ) (ξ - η ⅈ) = \frac{1}{2} (ξ^{*} ξ + η^{*} η - ξ^{*} η ⅈ + ξ η^{*} ⅈ) = \frac{1}{2} (1 - ξ^{*} η ⅈ + ξ η^{*} ⅈ)

\Pr ({-1}_{y}) = {|⟨-_{y} | ψ⟩|}^{2} = {|({\frac{1}{\sqrt{2}}}^{*}  {\frac{-ⅈ}{\sqrt{2}}}^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|\frac{1}{\sqrt{2}} (ξ + η ⅈ)|}^{2} = \frac{1}{2} (ξ^{*} - η^{*} ⅈ) (ξ + η ⅈ) = \frac{1}{2} (ξ^{*} ξ + η^{*} η + ξ^{*} η ⅈ - ξ η^{*} ⅈ) = \frac{1}{2} (1 + ξ^{*} η ⅈ - ξ η^{*} ⅈ)

|ψ⟩ = (\begin{matrix} ξ \\ η \end{matrix})

を σ _z で観測すると、 +1, -1 が観測される確率はそれぞれ

\Pr ({+1}_{z}) = {|⟨+_{z} | ψ⟩|}^{2} = {|(1^{*}  0^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|ξ|}^{2}

\Pr ({-1}_{z}) = {|⟨-_{z} | ψ⟩|}^{2} = {|(0^{*}  1^{*}) (\begin{matrix} ξ \\ η \end{matrix})|}^{2} = {|η|}^{2}

重ね合わせ

|ψ_{1}⟩ = (\begin{matrix} 1 \\ 0 \end{matrix})

|ψ_{2}⟩ = (\begin{matrix} 0 \\ 1 \end{matrix})

|ψ⟩ = \frac{1}{\sqrt{2}} |ψ_{1}⟩ + \frac{ⅈ}{\sqrt{2}} |ψ_{2}⟩

を

σ_{y}

で観測することを考える。それぞれ、 + か - が観測されるが、これは、それぞれの状態が+の状態と -の状態の重ね合わせになっていると考えられる。

σ_{y}

の固有ベクトルは、

|+_{y}⟩ = (\begin{matrix} \frac{1}{\sqrt{2}} \\ \frac{ⅈ}{\sqrt{2}} \end{matrix})

|-_{y}⟩ = (\begin{matrix} \frac{1}{\sqrt{2}} \\ \frac{-ⅈ}{\sqrt{2}} \end{matrix})

より、各状態は以下のように固有ベクトルの線形結合で書ける。

|ψ_{1}⟩ = \frac{1}{\sqrt{2}} |+_{y}⟩ + \frac{1}{\sqrt{2}} |-_{y}⟩

|ψ_{2}⟩ = \frac{-ⅈ}{\sqrt{2}} |+_{y}⟩ + \frac{ⅈ}{\sqrt{2}} |-_{y}⟩

|ψ⟩ = 1 |+_{y}⟩ + 0 |-_{y}⟩

観測確率は、観測値である固有値に対応する固有ベクトルの係数の和の二乗になるので、それぞれ以下のようになる。

このように、同じ確率が現象が観測される二つの状態の重ね合わせで、干渉により一つの現象が確率されないことが起こりうる。

|ψ⟩ = c_{1} |ψ_{1}⟩ + c_{1} |ψ_{2}⟩

に対して、 a が観測される確率を求めると、次のように、単純な足し算ではなく、干渉項が現れるのが分かる。

\Pr_{ψ} (a) = ⟨ψ| \hat{P} (a)| ψ⟩ = ⟨c_{1} ψ_{1} + c_{2} ψ_{2}| \hat{P} (a)| c_{1} ψ_{1} + c_{2} ψ_{2}⟩

= {c_{1}}^{*} c_{1} ⟨ψ_{1}| \hat{P} (a)| ψ_{1}⟩ + {c_{1}}^{*} c_{2} ⟨ψ_{1}| \hat{P} (a)| ψ_{2}⟩ + {c_{2}}^{*} c_{1} ⟨ψ_{2}| \hat{P} (a)| ψ_{1}⟩ + {c_{2}}^{*} c_{2} ⟨ψ_{2}| \hat{P} (a)| ψ_{2}⟩

= {|c_{1}|}^{2} \Pr_{ψ_{1}} (a) + {|c_{2}|}^{2} \Pr_{ψ_{2}} (a) + {c_{1}}^{*} c_{2} ⟨ψ_{1}| \hat{P} (a)| ψ_{2}⟩ + {c_{2}}^{*} c_{1} ⟨ψ_{2}| \hat{P} (a)| ψ_{1}⟩

ゆらぎ

状態

|ψ⟩

に対する物理量

A

とその平均値

⟨A⟩ = ⟨ψ| \hat{A}| ψ⟩

に対して、ばらつきを次のように定義する。

Δ A = A - ⟨A⟩

。分散と、標準偏差は次のように定義される。

⟨{(Δ A)}^{2}⟩

δ A = \sqrt{⟨{(Δ A)}^{2}⟩}

⟨ψ| {(Δ \hat{A})}^{2}| ψ⟩ = ⟨ψ| {(\hat{A} - ⟨A⟩ \hat{1})}^{2}| ψ⟩ = ⟨ψ| {\hat{A}}^{2} - 2 ⟨A⟩ \hat{A} + {⟨A⟩}^{2} \hat{1}| ψ⟩ = ⟨ψ| {\hat{A}}^{2}| ψ⟩ - 2 ⟨A⟩ ⟨ψ| \hat{A}| ψ⟩ + {⟨A⟩}^{2} \hat{1} = ⟨A^{2}⟩ - {⟨A⟩}^{2} = ⟨{(Δ A)}^{2}⟩ = {(δ A)}^{2}

不確定性原理

二つの演算子

\hat{A}

\hat{B}

に対して、交換子を次のように定義する。

ここで

[\hat{A}, \hat{B}] = ⅈ \hat{C}

と置くと、エルミート共役を取ることにより、以下のように

\hat{C}

は自己共役演算子になる。

{(ⅈ \hat{C})}^{†} = {([\hat{A}, \hat{B}])}^{†} = {(\hat{A} \hat{B} - \hat{B} \hat{A})}^{†} = \hat{B} \hat{A} - \hat{A} \hat{B} = - ⅈ \hat{C}

不確定性原理

自己共役演算子

\hat{A}

\hat{B}

が、ある実定数 k に対して、

[\hat{A}, \hat{B}] = ⅈ k \hat{1}

となるとき、

導出

まず、

[Δ \hat{A}, Δ \hat{B}] = [\hat{A}, \hat{B}] = ⅈ k \hat{1}

を示す。

[Δ \hat{A}, Δ \hat{B}] = [\hat{A} - ⟨A⟩ \hat{1}, \hat{B} - ⟨B⟩ \hat{1}] = (\hat{A} - ⟨A⟩ \hat{1}) (\hat{B} - ⟨B⟩ \hat{1}) - (\hat{B} - ⟨B⟩ \hat{1}) (\hat{A} - ⟨A⟩ \hat{1}) = \hat{A} \hat{B} - \hat{B} \hat{A}

さて、任意の実数 λ に対して、

Δ \hat{A} + ⅈ λ Δ \hat{B}

は自己共役演算子になります。したがって、任意の状態ベクトル

|ψ⟩

に対して、

(Δ \hat{A} + ⅈ λ Δ \hat{B}) |ψ⟩

のノルムは常に非負になります。つまり以下が任意の λ で成り立ちます。

この式を整理すると、以下のように λ に関する二次不等式が得られます。

⟨ψ| {(Δ \hat{A})}^{2}| ψ⟩ + ⅈ ⟨ψ| Δ \hat{A} Δ \hat{B} - Δ \hat{B} Δ \hat{A}| ψ⟩ λ + ⟨ψ| {(Δ \hat{B})}^{2}| ψ⟩ λ^{2} \geq 0

⟨ψ| {(Δ \hat{B})}^{2}| ψ⟩ λ^{2} - k λ + ⟨ψ| {(Δ \hat{A})}^{2}| ψ⟩ \geq 0

⟨ψ| {(Δ \hat{B})}^{2}| ψ⟩ \geq 0

より、この二次不等式が常に成立するのは判別式が非正の場合。つまり求める条件は以下の通り。

D = k^{2} - 4 ⟨ψ| {(Δ \hat{A})}^{2}| ψ⟩ ⟨ψ| {(Δ \hat{B})}^{2}| ψ⟩ \leq 0

⟨ψ| {(Δ \hat{A})}^{2}| ψ⟩ ⟨ψ| {(Δ \hat{B})}^{2}| ψ⟩ \geq \frac{k^{2}}{4}

時間発展

閉じた系において状態

|ψ_{t_{1}}⟩

から状態

|ψ_{t_{2}}⟩

に時間発展するとき、ユニタリ行列 Uにより、

|ψ_{t_{2}}⟩ = U |ψ_{t_{1}}⟩

となるとき、次のシュレディンガー方程式を導出できます。

14-2. 量子コンピュータ

qubit とテンソル積

量子コンピュータでは、1bitの情報、つまり、0または1のどちらかを保持する情報の単位をqubitと呼ぶ。具体的には0 を表す現象と 1 を表す現象のどちらかを観測できるような物理現象で情報を保持する。そのため、qubit は以下のように表される。

状態 0 を

|0⟩ = (\begin{matrix} 1 \\ 0 \end{matrix})

とし、

|1⟩ = (\begin{matrix} 0 \\ 1 \end{matrix})

とし、これをパウリの σ_zで観測すると、 0 を観測する確率が

{|a|}^{2}

, 1 を観測する確率が

{|b|}^{2}

となる。

複数の状態

ψ

φ

に対して、テンソル積

|ψ⟩ \otimes |φ⟩

を考える。これは、内積空間 V, W に対して、それぞれの正規直交基底が

\{|ξ_{1}⟩ ... |ξ_{n}⟩\}

\{|η_{1}⟩ ... |η_{m}⟩\}

である時、

|ψ⟩ = \sum_{i = 1}^{n} a_{i} |ξ_{i}⟩

|φ⟩ = \sum_{j = 1}^{m} b_{j} |η_{j}⟩

の時、

|ψ⟩ \otimes |φ⟩ = \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i} b_{j} |ξ_{i}⟩ \otimes |η_{j}⟩

なお、この場合、基底どうしのテンソル積は単なる直積として考える。また、テンソル積を

|ψ⟩ |φ⟩

や、

|ψ, φ⟩

や、

|ψ φ⟩

とも表す。

さらに、

|ψ^{'} φ^{'}⟩ = \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i}^{'} b_{j}^{'} |ξ_{i} η_{j}⟩

と

|ψ φ⟩

の内積を考える。

⟨ξ_{i} η_{j}| ξ_{k} η_{l}⟩ = ⟨ξ_{i}| ξ_{k}⟩ ⟨η_{j}| η_{l}⟩

と定義することにより、

⟨ψ φ| ψ^{'} φ^{'}⟩ = \sum_{i, j, k, l} a_{i}^{*} b_{j}^{*} a_{k}^{'} b_{l}^{'} ⟨ξ_{i}| ξ_{k}⟩ ⟨η_{j}| η_{l}⟩ = \sum_{i, j} a_{i}^{*} b_{j}^{*} a_{i}^{'} b_{j}^{'} = (\sum_{i} a_{i}^{*} a_{i}^{'}) (\sum_{j} b_{j}^{*} b_{j}^{'}) = ⟨ψ| ψ^{'}⟩ ⟨φ| φ^{'}⟩

また、

(\hat{A} \otimes \hat{B}) (|ψ⟩ \otimes |φ⟩) = (\hat{A} |ψ⟩) \otimes (\hat{B} |φ⟩)

状態が複素ヒルベルト空間の元であれば、テンソル積で得られた複合状態は次元が違うが複素ヒルベルト空間の元なので、量子力学の公理を満たすことができる。

非クローン化定理

観測されていない任意の量子状態をコピーすることはできないことを示します。これを示すには仮に二つの量子状態に対してコピーができたとき、必ず満たすべき状態が導かれるため、任意の状態のコピーにならないことを示します。まず、状態 ψ と φ のコピーができるとします。これは初期の任意状態 s があるユニタリ行列 U によって、 ψ や φ に遷移できることを意味します。

⟨U ψ s| U φ s⟩ = ⟨ψ ψ| φ φ⟩

⟨ψ s| U^{†} U| φ s⟩ = ⟨ψ ψ| φ φ⟩

⟨ψ| φ⟩ ⟨s| s⟩ = ⟨ψ| φ⟩ ⟨ψ| φ⟩

⟨ψ| φ⟩ = {⟨ψ| φ⟩}^{2}

⟨ψ| φ⟩ = 0, 1

つまり、どのようなユニタリ行列でもコピーができる状態は平行か直交かしかなく、任意の状態のコピーはできないということです。

量子コンピュータの基本構成

量子コンピュータは入力に対して、入力に対応した qubit を作り、さらにその入力の長さに対応したユニタリ行列を構成し、qubit にユニタリ行列を適用し、最終的に特定の qubit の観測を出力とします。ユニタリ行列の積はユニタリ行列なので、原理的には一つのユニタリ行列で最終状態にすることはできます。しかし、そのユニタリ行列の複雑度を考える上で、ユニタリ行列を基本的な操作の組み合わせに分解することを考えます。

さらに、基本的な操作の組み合わせで計算を定義する事自体が、量子計算のプログラミングとなります。

2状態系のBloch 球表示

観測すると2つの状態のうちの一つが観測される状態 ψ は、2つの正規直交基底

|0⟩

と

|1⟩

により、次で表される。

a を(広く使われている表記に合わせて)

a = e^{ⅈ α} cos \frac{θ}{2}

と置き、同じく bも

b = e^{ⅈ β} sin \frac{θ}{2}

と置く。すると、状態の表記を次のように表示できる。

|ψ⟩ = e^{ⅈ α} cos \frac{θ}{2} |0⟩ + e^{ⅈ β} sin \frac{θ}{2} |1⟩ = e^{ⅈ α} (cos \frac{θ}{2} |0⟩ + e^{ⅈ (β - α)} sin \frac{θ}{2} |1⟩)

ここで、全体の係数

e^{ⅈ α}

は、観測の確率と関係なく、また、

φ = β - α

と置くことで、2状態系の状態を二つの角度を表す実数

(θ, φ)

で表すことができる。これは、半径1の三次元球の表面の極座標になるので、この2状態系を2実数の極座標で表すことを Bloch 球表現と呼ぶ。

単一qubitに対するZ-Y変換(定理4.1)

単一qubitに対するユニタリ行列 U に対して、次の実数の α, β, γ, δ が存在する。

制御Not

ユニタリ行列の分解

量子Fourier変換

位数発見

量子探索

コンピュータとは、計算をさせる装置である以上、何らかの物理法則にしたがっています。我々の世界を支配している物理法則は相対論的量子力学ですから、この力学に基づいた計算原理を考える必要があります。現在の電子コンピュータは、シャノンが示したbool演算を実現する電子回路を原理として動作しています。しかし、これらと異なる原理による計算が不可能というわけではありません。ここでは、量子力学を原理とした計算について紹介します。

量子 bit

量子コンピュータで行う計算も情報処理に違いありませんので、情報の単位は bit になります。量子状態でbitを保持できるとします。量子状態は人間による観測によって確定して、情報を取り出すことができます。但し、量子状態は通常は確率的な値になります。つまり 1 bit を表す量子状態を観測すると、確率 a で 0 が取り出せ、確率 b で 1 が取り出せるということになります。この量子bit(q bit)の実現方法も色々議論されていますが、ここでは実現法ではなく、数学モデルについて説明します。

量子状態には、重ね合わせという概念があります。これは複数の状態が同時に重ね合わさっていて、人間が観測することにより、一つの状態に収束しそれが観測されるという概念です。これをコペンハーゲン解釈といいます。

量子力学の問題点を指摘するための、「シュレーディンガーの猫」という思考実験があります。これは、箱の中に猫を綴じ込め、α線の発生源、観測器、毒ガス発生器を仕組み、α線が観測されたら毒ガスが発生し、猫が死ぬように作られた装置を考えます。一時間以内にα線が観測される確率が 50% であるとします。すると、コペンハーゲン解釈によると、箱の中の猫は、生きている猫と死んでいる猫が量子状態で重ね合わさっていると考えることができます。この生きている猫と死んでいる猫の重ね合わせの状態というのは、人間の思考として俄に受け入れがたいものですが、コペンハーゲン解釈ではそう考えるもので、しかも、実際に見ようとすると一つの状態に収束してしまうので、決して重ね合わせ状態を観測することはできません。

ここで、Dirac の記号を導入します。行ベクトルを

⟨φ|

と書き、ブラベクトルと呼びます。一方、列ベクトルを

|ψ⟩

と書き、ケットベクトルと呼びます。すると、内積は

⟨φ| ψ⟩

と書けます。

さて、量子ビット(q bit) に関しての数学モデルを考えます。0 の状態と 1 の状態をそれぞれ線形代数の位置ベクトルとし、正規直交基底であるとします。 0状態の基底を

|0⟩

で表し、 1状態の基底を

|1⟩

で表すと、これは二次元の正規直交基底なので次が成り立ちます。

これの重ね合わせは

a |0⟩ + b |1⟩

と書けます(a,bは複素数)。状態ベクトルが常に大きさが１であるとすると、

{|a|}^{2} + {|b|}^{2} = 1

という制約が必要です。この時、 0, 1 がそれぞれ観測される確率は、

{|a|}^{2} ， {|b|}^{2}

になります。

多 q bit

さて、複数の量子ビットの取扱いをどうするかですが、基本的には同じ考え方をします。 2 bit の場合、取りうる状態は 00, 01, 10, 11 です。この 4 状態はそれぞれ別の状態なので、正規直交基底になります。 4次元の正規直交基底なので次のようになります。

|00⟩ = (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}), |01⟩ = (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}), |10⟩ = (\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}), |11⟩ = (\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix})

つまり、これは4次元単位球の表面の位置ベクトルを意味します。

|φ⟩

を観測して、 00, 01, 10, 11 が観測される確率は、それぞれ

{|α_{00}|}^{2}, {|α_{01}|}^{2}, {|α_{10}|}^{2}, {|α_{11}|}^{2}

になります。

このように単純にビット数が増えると、次元が増えます。これを演算として扱う、テンソル積を導入します。これは、内積空間 V, W に対して、それぞれの基底が

\{|ξ_{1}⟩ ... |ξ_{n}⟩\}

\{|η_{1}⟩ ... |η_{m}⟩\}

である時、

|φ⟩ \otimes |ψ⟩ = |φ φ⟩

の意味は前述した通り、次元を拡張するだけです。

n個の q bit はこの様に2n次元の基底の重ね合わせで表現されます。

量子計算

さて、この q bit を物理現象に基づいて計算させることを考えます。これは量子力学に従います。先ほども述べたように、大きさ 1 で正規化するので、実際にこの量子計算は q bit に対するユニタリ行列の積になります。

さらに、研究により、複雑なユニタリ行列は以下のような基本的なユニタリ行列を多次元に拡張(0を挿入)の積で表せることが分かっています。

従って、これらのユニタリ行列と対応した物理現象が起きるような装置を作成すれば、量子コンピュータが実現できるようになります。一つのq bit を実現するのに、2次元のベクトルが必要で、上記のユニタリ行列が2または4次元なので、これは従来のコンピュータの概念では論理ゲートにあたります。つまり、ある q bit の列、

|φ⟩

に対して上記のユニタリ行列 U1, U2,...,Un があって、

U_{1} U_{2} ... U_{n} |φ⟩

を計算するのに、実際は個々の特定の q bit に対して、上記の定められた演算を行う回路のようなものを考えれば良いことになります。

14-3. 量子コンピュータの基礎

二次元複素ベクトル空間

また、複素数

c = x + y i

に対して、共役を

c^{*} = x - y i

で表します。また、大きさは

|c| = \sqrt{a^{2} + b^{2}}

とします。

行列

\hat{A} = (a_{i⁣ j})

に対して、転置行列を

{\hat{A}}^{t} = (a_{j⁣ i})

で表します。また、エルミート行列は

{\hat{A}}^{*} = ({a^{*}}_{j⁣ i})

で表します。さらに、単位行列を I としたとき、ユニタリ行列 U は下記を満たす正方行列です。

一様な磁場の中での陽子などのスピンを考えると、特定の量子が重ね合わさっている状態で、観測すると 0 の情報か 1 の情報が得られます。このように、行列力学的な解釈として現象が二現象の重ね合わせになるようなものをデータの保存を行う単位として選びます。この時、状態として、二つの現象を区別する単位ベクトルを

|0⟩ = (\begin{matrix} 1 \\ 0 \end{matrix})

と

|1⟩ = (\begin{matrix} 0 \\ 1 \end{matrix})

とし、これの重ね合わせを計算の単位(1bit)とすることとします。これを Qbit と呼びます。 φ=φ0 (1,0) + φ1 (0,1)

ψ = ψ_{0} (\begin{matrix} 1 \\ 0 \end{matrix}) + ψ_{1} (\begin{matrix} 0 \\ 1 \end{matrix}) = ψ_{0} |0⟩ + ψ_{1} |1⟩

となっているような状態の時、

(\begin{matrix} 1 \\ 0 \end{matrix})

に対応した現象が実際に観測される確率は、

\frac{{ψ_{0}}^{2}}{{ψ_{0}}^{2} + {ψ_{1}}^{2}}

|φ1^2/(φ1^2+φ2^2) となります。

さらにこの現象が複数存在し、直積的な関係のあるような状況を考える。つまり、

|ψ_{1}⟩ = ψ_{1⁣ 0} (\begin{matrix} 1 \\ 0 \end{matrix}) + ψ_{1⁣ 1} (\begin{matrix} 0 \\ 1 \end{matrix})

と

|ψ_{2}⟩ = ψ_{2⁣ 0} (\begin{matrix} 1 \\ 0 \end{matrix}) + ψ_{2⁣ 1} (\begin{matrix} 0 \\ 1 \end{matrix})

の直積

|ψ_{1}⟩ \otimes |ψ_{2}⟩ = |ψ_{1}, ψ_{2}⟩

を考える。

最初の2現象と次の2現象に関して、起きうる現象は最初が　　で、次が最初が　で、次がなど4通りの組み合わせがある。これに対して、それぞれ単位ベクトルを用意し、と単位ベクトル同士の直積を定義する。

|0⟩ \otimes |1⟩ = |0, 1⟩

などと定義します。

これは、 |φ1> = φ10(1,0)+φ11(0,1) |φ2> = φ20(1,0)+φ21(0,1) 単位ベクトル (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)

(\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix})

(\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix})

(\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix})

(\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix})

に対して、

を意味します。同様の意味で以下を |φ1,...,φn> のような表記をします。

n 個の 2x2 の正方行列

A_{1}, ..., A_{n}

について、下記の様に積を定義する。特に

A_{1} \otimes ... \otimes A_{n}

をテンソル積と言う。 (n Qbit に対して、 2ⁿ 個の計算があることに注意)

(A_{1} \otimes ... \otimes A_{n}) |ψ_{1} ... ψ_{n}⟩ = ∑_{i_{1} ... i_{n} = 0}^{1} ψ_{1, i_{1}} ... ψ_{n, i_{n}} (A_{1} |i_{1}⟩ \otimes ... \otimes A_{n} |i_{n}⟩)

量子チューリング機械

量子チューリング機械はテープとして、 Qbit が連続してあるようなものを考えます。また、状態遷移関数は

δ (p, a, b, q, d) = c

δ(p,a,b,q,d)=c という状態が p, ヘッドが a を読んでいるとき(観測ではなく)、新たに b を書き込み、状態を q に移し、ヘッドの方向を d に移動する事象の確率振幅を |c|² と定義する。このとき、行列 M_δ のc1 行 c2 列は、 c2 から c1 への 1 ステップの遷移と対応したδの値になる。ただし、ここでも M_δ はユニタリ行列になる。

14-4. 量子コンピュータのプログラミング

NOT

(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) |ψ⟩ = ψ_{1, 0} (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 \\ 0 \end{matrix}) + ψ_{1, 1} (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 0 \\ 1 \end{matrix})

|x> → |1-x>

AND

|0> <0| x |0> <0| x I + |0> <0| x |1> <1| x I + |1> <1| x |0> <0| x I + |1> <1| x |1> <1| x (0 1 ; 1 0)

14-5. 有名なアルゴリズム

Shor のアルゴリズム

実は、 n Qbit のベクトルに対して、離散フーリエ変換を行ったときの nQbit の関数表は量子多項式時間で求めることができます。

Shor は量子コンピュータを使って、多項式時間で高い確率で、因数分解と、離散対数問題が解けることを示しました。

y^r = 1 mod n となるようなもっとも小さい r を y の mod n のオーダーと言います。もし、非自明な r が求まると、 n の素因数分解ができます。

Groover の選択問題

関数 f(x) が特定の x=x0 で f(x0)=1 になり、他の x では f(x)=0 となるようなことを考えます。

$\Pr_{ψ_{1}} (+) = \frac{1}{2}$ ,	$\Pr_{ψ_{1}} (-) = \frac{1}{2}$
$\Pr_{ψ_{2}} (+) = \frac{1}{2}$ ,	$\Pr_{ψ_{2}} (-) = \frac{1}{2}$
$\Pr_{ψ} (+) = 1$ ,	$\Pr_{ψ} (-) = 0$

第 14 回量子コンピュータ

本日の内容

14-1. 量子力学

概要

古典論の破綻

量子論の基礎

重ね合わせ

ゆらぎ

不確定性原理

不確定性原理

導出

時間発展

14-2. 量子コンピュータ

qubit とテンソル積

非クローン化定理