2019-09-08 (Sun.)
\[\newcommand{\ket}[1]{\left|#1\right\rangle} \newcommand{\true}{\mathrm{true}} \newcommand{\false}{\mathrm{false}} \newcommand{\exact}{\mathrm{EXACT}} \newcommand{\threshold}{\mathrm{THRESHOLD}} \newcommand{\concat}{+\!\!\!+}\]
ここではあくまでも計算モデルとして量子計算を眺め, なにが実現出来るかを調べる. 物理学的な視点にはあまり興味がない.
まず量子計算を支える qbit (量子ビット) がどのような性質を持つかを説明する. 次にどのようなゲート (回路) が実現可能で qbit を操作できるかを紹介する. ただしいずれも物理的原理までは立ち入らず紹介するだけに留める.
古典コンピュータにおける計算にはbitを用いる. これは \(0\) または \(1\) のいずれかの状態を取るものである. 対して qbit はこの2つの状態を確率的に持つ. 具体的には2つの状態の線型結合として記述される.
qbit が \(0\) である状態を \(\ket{0}\), qbit が \(1\) である状態を \(\ket{1}\) と書く (bra-ket 記法という) ことにし, 一般の状態はこの2つの重ねあわせ (線型結合): \[\alpha \ket{0} + \beta \ket{1}\] で表される. ここで \(\alpha, \beta\) は複素数を取り \((\alpha, \beta \in \mathbb C)\), また物理学の要請から \[|\alpha|^2 + |\beta|^2 = 1\] という制約を要請される.
復習: 複素数 \(z \in \mathbb C\) は, 実数 \(x, y \in \mathbb R\) によって \(z = x + y i\) で一意に表現される値で, これについて共役数 \(\bar{z} = x - y i (\in \mathbb C)\) と \(|z|^2 = \bar{z} \cdot z = x^2 + y^2 (\in \mathbb R)\) を定めるのだった.
補足: 係数の制約を無視すれば, qbit の取り得る空間というのは 2つの基底 \(\ket{0}, \ket{1}\) からなる二次元の複素数上のベクトル空間である. 制約があるので実際にはこれの部分空間であっても, 部分ベクトル空間ではないが.
qbit は状態の重ね合わせだと言ったが実は実際に観測をすると, \(\ket{0}\) または \(\ket{1}\) のどちらかに見える.
先程, 係数には制約 \(|\alpha|^2 + |\beta|^2 = 1\) があると述べたが, 実はこれらはどちらに観測されるかの確率になっている.
すなわち, ある qbit, \(\alpha \ket{0} + \beta \ket{1}\) を実際に観測すると, 確率 \(|\alpha|^2\) で \(\ket{0}\) を得, 確率 \(|\beta|^2\) で \(\ket{1}\) を得る. (確率の和はちょうど \(1\) になっており不都合はない.)
そして観測という行為は qbit に干渉する. 一度状態が確定すると, 以降何度観測をしても初めに得た結果を得るだけである. 即ち, 一度 \(\ket{0}\) を観測したならば, その qbit は \(\ket{0} = 1 \cdot \ket{0} + 0 \cdot \ket{1}\) に 収束 したと言える.
bit を \(n\) 個並べたものを \(n\) bit と言うように, qbit を \(n\) 個並べたものを \(n\) qbit と呼ぶことにする.
特に 並べる という操作を二項演算子 \(\otimes\) で表すことにする. \(n\) qbit \(x\) と \(m\) qbit \(y\) を並べることで \(n+m\) qbit \(x \otimes y\) を得る. ここで並べる場合には順序があるので \(x \otimes y \ne y \otimes x\) であることに註意.
簡単に \(2\) qbit について考える. \(\ket{0}\) の右に \(\ket{1}\) を並べて得る 2 qbit を \[\ket{01} := \ket{0} \otimes \ket{1}\] と書くことにする. すると 2 qbitは \[\ket{00}, \ket{01}, \ket{10}, \ket{11}\] の4通りの状態を取り得る. 実際にはそれぞれの qbit は重ね合わせであるから, 2 qbit はこの4通りの重ね合わせになる: \[\alpha_{00} \ket{00} + \alpha_{01} \ket{01} + \alpha_{10} \ket{10} + \alpha_{11} \ket{11}\]
2 qbit のそれぞれが \(\beta_0 \ket{0} + \beta_1 \ket{1}\) と \(\gamma_0 \ket{0} + \gamma_1 \ket{1}\) だったとするとき, 形式的に
\[(\beta_0 \ket{0} + \beta_1 \ket{1}) \otimes (\gamma_0 \ket{0} + \gamma_1 \ket{1}) = \beta_0 \gamma_0 \ket{00} + \beta_0 \gamma_1 \ket{01} + \beta_1 \gamma_0 \ket{10} + \beta_1 \gamma_1 \ket{11}\]
という掛け算をすればよい. 係数はただの掛け算で \(\ket{\cdot}\) は横に結合させるだけ. 実際, \(\ket{00}\) を観測する確率は, 同時確率なので \(|\beta_0|^2 |\gamma_0|^2 = |\beta_0 \gamma_0|^2\) となっていて, \(\alpha_{00} = \beta_0 \gamma_0\) とすれば都合がよい. 同様に \(\alpha_{ij} = \beta_i \gamma_j\) とすればよく, \(\ket{ij}\) を観測する確率は \(|\alpha_{ij}|^2\) だと言える. \(\sum_{i,j} |\alpha_{ij}|^2 = 1\) は各 qbit の係数の制約から従う.
\(n\) qbit の内 1 qbit だけを観測した結果, その qbit の状態は先述したとおり, 観測された状態に確定して固定されるが, 残りの \(n-1\) qbit についてはなおも重ね合わせの状態を保ったままで観測が干渉することはない.
例として, 2 qbit \[\alpha_{00} \ket{00} + \alpha_{01} \ket{01} + \alpha_{10} \ket{10} + \alpha_{11} \ket{11}\] を考える. これの 1 qbit 目を観測した結果 \(\ket{0}\) を得たとする. 1 qbit 目は \(0\) で固定されるので, 観測しうる状態は \(\ket{00}\) または \(\ket{01}\) だけであるので, 観測後の 2 qbit は, \[\alpha_{00}' \ket{00} + \alpha_{01}' \ket{01}\] で表される.
\(\alpha_{00}'\), \(\alpha_{01}'\) はどうなるかと言うと, これらは結局, 2 qbit 目が \(\ket{0}\), \(\ket{1}\) で観測される確率 (の平方根) であって, (それは観測の前後で変化しない)
元の 2 qbit が \(\beta_0 \ket{0} + \beta_1 \ket{1}\) と \(\gamma_0 \ket{0} + \gamma_1 \ket{1}\) だったとすると, 観測後の事後確率なので
と言える. また先程見たように \(\alpha_{00} = \beta_0 \gamma_0\) なので, \(\alpha_{00} = \beta_0 \alpha_{00}'\). 同様に \(\alpha_{01} = \beta_0 \alpha_{01}'\).
従って \(\beta_0\) の逆数を単に定数 \(\kappa\) と書くことにすると, 事後の 2 qbit は \[\kappa \alpha_{00} \ket{00} + \kappa \alpha_{01} \ket{01}\] と書ける.
さて係数の自乗和が \(1\) である性質から実は \(\kappa\) は決まる. 即ち, \[|\kappa|^2 (|\alpha_{00}|^2 + |\alpha_{01}|^2) = 1\] があるので \(\kappa\) の大きさは決まる.
qbit に対する実現可能な操作で次のようなゲートを作成することが理論上可能である.
次のような操作 \(X\) が存在する:
この操作 \(X\) は線形写像のように働く. 即ち, \[X (\alpha \ket{0} + \beta \ket{1}) = \alpha \ket{1} + \beta \ket{0}\] となる.
次のような 2 qbit に対する操作 \(X\) が存在する:
ここで \(\oplus\) は排他的論理和で, \(0 \oplus j = j\), \(1 \oplus j = 1 - j\).
次のような \(H\) が存在する:
\(H\) は二回通すことで恒等写像になる.
\(H \ket{0}\) のことを \(\ket{+}\), \(H \ket{1}\) のことを \(\ket{-}\) と書くことにする. この符号はもちろん2つの状態が和になってるか差になってるかを意味している.
補足: これも重ね合わせの状態については線形写像のように働く. ところで, 重ね合わせられてない状態というのは, 実際に観測すれば容易に手に入る. それをアダマールゲートに通すと, 2つの状態が同確率で観測されるような状態の qbit が手に入る. また \(H\) を組み合わせることで, 全ての \(2^n\) 状態が等確率で観測できる \(n\) qbit を作ることができる.