第 14 回 量子コンピュータ

本日の内容

• 14-1. 量子コンピュータの基礎
• 14-2. 量子コンピュータ

量子 bit

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

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

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

ここで、Dirac の記号を導入します。 行ベクトルを $⟨\mathit{\phi }|$ と書き、ブラベクトルと呼びます。 一方、 列ベクトルを $|\mathit{\psi }⟩$ と書き、ケットベクトルと呼びます。 すると、内積は $⟨\mathit{\phi }|\mathit{\psi }⟩$ と書けます。

さて、量子ビット(q bit) に関しての数学モデルを考えます。0 の状態と 1 の状態をそれぞれ線形代数の位置ベクトルとし、正規直交基底であるとしま す。 0状態の基底を $|\mathit{0}⟩$ で表し、 1状態の基底を $|\mathit{1}⟩$ で表すと、これは二次元の正規直交基底なので次が成り立ちます。

これの重ね合わせは $a|\mathit{0}⟩+b|\mathit{1}⟩$ と書けます(a,bは複素数)。 状態ベクトルが常に大きさが１であるとすると、 ${\left|a\right|}^2+{\left|b\right|}^2=1$ という制約が必要です。 この時、 0, 1 がそれぞれ観測される確率は、 ${\left|a\right|}^2，{\left|b\right|}^2$ になります。

多 q bit

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

これらの状態の重ね合わせを次のように書きます。

つまり、これは4次元単位球の表面の位置ベクトルを意味します。 $|\mathit{\phi }⟩$ を観測して、 00, 01, 10, 11 が観測される確率は、それぞれ ${\left|{\alpha }_{00}\right|}^2,{\left|{\alpha }_{01}\right|}^2,{\left|{\alpha }_{10}\right|}^2,{\left|{\alpha }_{11}\right|}^2$ になります。

このように単純にビット数が増えると、次元が増えます。 これを演算として扱う、テンソル積を導入します。 これは、内積空間 V, W に対して、それぞれの基底が $\left\{|{\mathit{\xi }}_1⟩,...,|{\mathit{\xi }}_n⟩\right\}$ , $\left\{|{\mathit{\eta }}_1⟩,...,|{\mathit{\eta }}_m⟩\right\}$ である時、 $|\mathit{\phi }⟩\otimes |\mathit{\psi }⟩=|\mathit{\phi }\mathit{\phi }⟩$ の意味は前述した通り、次元を拡張するだけです。

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

量子計算

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

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

Hadamard

$\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

位相

$\left(\begin{array}{cc}1& 0\\ 0& \mathrm{i}\end{array}\right)$

制御NOT

$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

π/8ゲート

$\left(\begin{array}{cc}1& 0\\ 0& {\mathrm{e}}^{\mathrm{i}\mathrm{\pi }/4}\end{array}\right)$

従って、これらのユニタリ行列と対応した物理現象が起きるような装置を作 成すれば、量子コンピュータが実現できるようになります。 一つのq bit を実現するのに、2次元のベクトルが必要で、 上記のユニタリ行列が2または4次元なので、これは従来のコンピュータの概 念では論理ゲートにあたります。 つまり、ある q bit の列、 $|\mathit{\phi }⟩$ に対して上記のユニタリ行列 U1, U2,...,Un があって、 $U_1{U}_2...U_n|\mathit{\phi }⟩$ を計算するのに、実際は個々の特定の q bit に対して、上記の定めら れた演算を行う回路のようなものを考えれば良いことになります。

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

二次元複素ベクトル空間

また、複素数 $c=x+y\mathrm{i}$ に対して、共役 を $c^{*}=x-y\mathrm{i}$ で表します。 また、大きさは $\left|c\right|=\sqrt{a^2+b^2}$ とします。

行列 $\widehat{A}=\left(a_{ij}\right)$ に対して、転置行列を ${\hat{A}}^t=\left(a_{ji}\right)$ で表します。 また、エルミート行列 は ${\widehat{A}}^{*}=\left({a^{*}}_{ji}\right)$ で表します。 さらに、単位行列を I としたとき、ユニタリ行列 U は下記を満たす 正方行列です。

一様な磁場の中での陽子などの スピンを考えると、 特定の量子が重ね合わさっている状態で、観測すると 0 の情報か 1 の情報が 得られます。 このように、行列力学的な解釈として現象が二現象の重ね合わせになるような ものをデータの保存を行う単位として選びます。 この時、状態として、二つの現象を区別する単位ベクトルを $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ と $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ とし、これの重ね合わせを計算の単位(1bit)とすることとします。 これを Qbit と呼びます。 φ=φ0 (1,0) + φ1 (0,1) $\mathit{\psi }={\psi }_0\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_1\left(\begin{array}{c}0\\ 1\end{array}\right)={\psi }_0|0⟩+{\psi }_1|1⟩$ となっているような状態の時、 $\left(\begin{array}{c}1\\ 0\end{array}\right)$ に対応した現象が実際に観測される確率は、 $\frac{{{\psi }_0}^2}{{{\psi }_0}^2+{{\psi }_1}^2}$ |φ1^2/(φ1^2+φ2^2) となります。

さらにこの現象が複数存在し、直積的な関係のあるような状況を考える。 つまり、 $|{\mathit{\psi }}_1⟩={\psi }_{10}\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_{11}\left(\begin{array}{c}0\\ 1\end{array}\right)$ と $|{\mathit{\psi }}_2⟩={\psi }_{20}\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_{21}\left(\begin{array}{c}0\\ 1\end{array}\right)$ の直積 $|{\mathit{\psi }}_1⟩\otimes |{\mathit{\psi }}_2⟩=|{\mathit{\psi }}_1,{\mathit{\psi }}_2⟩$ を考える。

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

これは、

  |φ1> = φ10(1,0)+φ11(0,1) 
|φ2> = φ20(1,0)+φ21(0,1) 

これを |φ1,φ2> と書くと

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

n 個の 2x2 の正方行列 $A_1,...,A_n$ について、下記の様に積を定義する。特に $A_1\otimes ...\otimes A_n$ をテンソル積と言う。 (n Qbit に対して、 2ⁿ 個の計算があることに注意)

量子チューリング機械

量子チューリング機械はテープとして、 Qbit が連続してあるようなものを考 えます。 また、状態遷移関数は $\delta (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-2. 量子コンピュータ

qubit とテンソル積

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

状態 0 を $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ とし、 $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ とし、 これをパウリの σ_zで観測すると、 0 を観測する確率が ${\left|a\right|}^2$ , 1 を観測する確率が ${\left|b\right|}^2$ となる。

複数の状態 $\mathit{\psi }$ , $\mathit{\phi }$ に対して、テンソル積 $|\mathit{\psi }⟩\otimes |\mathit{\phi }⟩$ を考える。 これは、内積空間 V, W に対して、それぞれの正規直交基底が $\left\{|{\mathit{\xi }}_1⟩,...,|{\mathit{\xi }}_n⟩\right\}$ , $\left\{|{\mathit{\eta }}_1⟩,...,|{\mathit{\eta }}_m⟩\right\}$ である時、 $|\mathit{\psi }⟩=\sum _{i=1}^n{a}_i|{\mathit{\xi }}_i⟩$ , $|\mathit{\phi }⟩=\sum _{j=1}^m{b}_j|{\mathit{\eta }}_j⟩$ の時、 $|\mathit{\psi }⟩\otimes |\mathit{\phi }⟩=\sum _{i=1}^n\sum _{j=1}^m{a}_i{b}_j|{\mathit{\xi }}_i⟩\otimes |{\mathit{\eta }}_j⟩$ なお、この場合、基底どうしのテンソル積は単なる直積として考える。 また、テンソル積を $|\mathit{\psi }⟩|\mathit{\phi }⟩$ や、 $|\mathit{\psi },\mathit{\phi }⟩$ や、 $|\mathit{\psi }\mathit{\phi }⟩$ とも表す。

さらに、 $|{\mathit{\psi }}^{\text{'}}{\mathit{\phi }}^{\text{'}}⟩=\sum _{i=1}^n\sum _{j=1}^m{a}_i^{\text{'}}{b}_j^{\text{'}}|{\mathit{\xi }}_i{\mathit{\eta }}_j⟩$ と $|\mathit{\psi }\mathit{\phi }⟩$ の内積を考える。 $⟨{\mathit{\xi }}_i{\mathit{\eta }}_j|{\mathit{\xi }}_k{\mathit{\eta }}_l⟩=⟨{\mathit{\xi }}_i|{\mathit{\xi }}_k⟩⟨{\mathit{\eta }}_j|{\mathit{\eta }}_l⟩$ と定義することにより、 $⟨\mathit{\psi }\mathit{\phi }|{\mathit{\psi }}^{\text{'}}{\mathit{\phi }}^{\text{'}}⟩=\sum _{i,j,k,l}{a}_i^{*}{b}_j^{*}{a}_k^{\text{'}}{b}_l^{\text{'}}⟨{\mathit{\xi }}_i|{\mathit{\xi }}_k⟩⟨{\mathit{\eta }}_j|{\mathit{\eta }}_l⟩=\sum _{i,j}{a}_i^{*}{b}_j^{*}{a}_i^{\text{'}}{b}_j^{\text{'}}=\left(\sum _i{a}_i^{*}{a}_i^{\text{'}}\right)\left(\sum _j{b}_j^{*}{b}_j^{\text{'}}\right)=⟨\mathit{\psi }|{\mathit{\psi }}^{\text{'}}⟩⟨\mathit{\phi }|{\mathit{\phi }}^{\text{'}}⟩$ また、 $\left(\widehat{A}\otimes \widehat{B}\right)\left(|\mathit{\psi }⟩\otimes |\mathit{\phi }⟩\right)=\left(\widehat{A}|\mathit{\psi }⟩\right)\otimes \left(\widehat{B}|\mathit{\phi }⟩\right)$

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

非クローン化定理

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

この二つの内積を取ります。

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

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

量子コンピュータの実現性を示すためには、基本的には論理回路の構成と同 様にします。 論理回路の構成を示すには、基本ゲートを定め、入力長を固定します。 そして、任意の入力長に対して、基本ゲートのみで回路の構成の仕方のアル ゴリズムを与えます。 （なお、回路の非存在を示すような場合、入力長毎のアルゴリズムを与えら れないような回路列も想定できるため、 uniformity, non-uniformity とい う区分を考えることがあります）。 通常の論理回路では、任意の2入力論理ゲートや、多入力 and, or, nand 回 路などを想定します。

しかし量子コンピュータでは、and, or, nand ゲートなど、入力数と出力数 が異なったり、逆演算ができないようなゲートは実現できません。 そこで、入出力ゲート数が同じで、可逆計算可能で、あらゆる計算を実現で きる Toffoli Gate をユニタリ行列で実現できることを示します。

Toffoli Gate は controlled-Controlled-not (CCNOT)とも呼ばれ、次の論 理式で与えられます

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

さらに、基本的な操作の組み合わせで計算を定義する事自体が、 量子計算のプログラミングとなります。 以下は量子コンピュータの構成の流れになります：

1. qubit を2つの角度で表す Bloch球表現
2. qubit への任意のユニタリ行列演算が、3つの基本ユニタリ行列の積で表せ る
3. 制御NOT
4. Tofforiゲートのユニタリ行列による構成

2状態系のBloch 球表示

観測すると2つの状態のうちの一つが観測される状態 ψ は、2つの正規直交基底 $|0⟩$ と $|1⟩$ により、次で表される。

a を(広く使われている表記に合わせて) $a={\mathrm{e}}^{\mathrm{i}\alpha }cos\frac{\theta }{2}$ と置き、同じく bも $b={\mathrm{e}}^{\mathrm{i}\beta }sin\frac{\theta }{2}$ と置く。すると、状態の表記を次のように表示できる。

ここで、全体の係数 ${\mathrm{e}}^{\mathrm{i}\alpha }$ は、観測の確率と関係なく、また、 $\phi =\beta -\alpha$ と置くことで、2状態系の状態を二つの角度を表す実数 $\left(\theta \phi \right)$ で表すことができる。 これは、半径1の三次元球の表面の極座標になるので、この2状態系を2実数 の極座標で表すことを Bloch 球表現と呼ぶ。

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

パウリ行列について次の関数を定義する

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

補題

以下のユニタリ行列もパウリ行列の積で表せる

Hadamard

$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

π/8 ゲート

$T=\left(\begin{array}{cc}1& 0\\ 0& {\mathrm{e}}^{\mathrm{i}\mathrm{\pi }/4}\end{array}\right)$

位相ゲート

$S=\left(\begin{array}{cc}1& 0\\ 0& \mathrm{i}\end{array}\right)$

制御Not

$\mathrm{CNOT}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

Toffoli Gate の構成