■ 量子コンピュータ(基礎理論)


1994年にIEEE誌に発表された素因数分解に関するShorの論文は,高速な暗号解読を可能とする量子コンピュータの研究を推進する起爆剤となった。これらの画期的な量子技術の研究を推進させる元になっている基本原理は量子エンタングルメント(量子の絡み合い; entanglement)と呼ばれており,その代表的な例は電子のスピン一重項状態,すなわち全スピンがゼロの状態(スピン+1/2≡def|0>と,スピン-1/2≡def|1>の合成された状態)にある2電子系である。正確には,“複数の部分系からなる量子系において,個々の部分系の積では表されないような‘分離不能な状態’に現れる非局所的な相関”と定義される。古典系には存在しない,量子系特有の相関なので‘量子相関’と呼ばれることもある。
2電子系スピン一重項状態の量子エンタングルメントを|0>,|1>を用いて例示すると,(|0>電子1|1>電子2 - |1>電子1|0>電子2)/√2のように書ける。電子1,電子2をいちいち書くのは煩雑なので,今後はサフィックスをはずして(|0>|1> - |1>|0>)/√2と書くことにする。|0>|1>は電子1の|0>状態と電子2の|1>状態の複合状態であり,通常テンソル積と呼ばれ,テンソル記号をとすれば|0>|1>のようにも書く。誤解が生じない限りテンソル積の記号も省略されることが多い。(|0>|1> + |1>|0>),もまたエンタングルメント状態であるが,(|0> + |1>)|0>,はエンタングルメント状態ではない。電子1は(|0> + |1>)状態で,電子2が|0>状態であり,それぞれ分離・独立している。分離している状態がエンタングルメント状態になったり(その逆も)するには相互作用が必要である。相互作用がないと,分離した状態はいつまで経っても分離したままである。自然界は複雑であり,独立した状態よりもエンタングルメント状態に多くの特質が見られ,本当に調べたい問題が多く存在する。

分離している状態がエンタングルメント状態になる相互作用の例としては,方解石に入射し通過する光子がある。入射前の光子(状態はα|0>+β|1>,|0>,|1>は偏光状態)が経路W上を進む全体の系はΨ = (α|0>+β|1>)|w>と書ける。通過後には正常光|0>は経路Xを,異常光(屈折光)|1>は経路Yを進むので,全体の状態はΨ' = α|0>|X>+β|1>|Y>となる。通過後はエンタングルメント状態である。注意すべきなのが変換Ψ → Ψ'の性質である。この変換をUとすれば,Ψ'= UΨであるが,明らかに全体の系の大きさ(|α|2 + |β|2 )は変化していないので,方解石の通過の相互作用はユニタリー変換(UU = UU = 1)である。このユニタリー性を計算のアルゴリズムの中核に据えているのが量子コンピュータである。

(1)量子ゲート

古典的な情報の単位は“ビット(bit)”と呼ばれ2つの変数0と1で表されるが,対応する量子的な情報単位は“量子ビット(qubit)”と呼ばれる。量子系の状態が古典系と基本的に異なる点は,任意の重ね合わせ状態,例えばα|0>+β|1>,を考えることができることである。この重ね合わせ原理とユニタリー変換によって量子コンピュータが構成されるのだが,その前に現在のコンピュータ(古典計算機)の論理ゲートを整理しておく。
古典計算機はNOTANDORXORの4つの代表する論理ゲートで構成される。NOTは論理否定であり,働きは1ビットのフリップ(反転)である。即ち,
|0> → |1>,
|1> → |0>
ANDは2ビットの入力から1ビットの出力を行い,その働きは,
|0>|0> → |0>,
|0>|1> → |0>,
|1>|0> → |0>,
|1>|1> → |1>
ORも2ビットの入力から1ビットの出力を行い,その働きは,
|0>|0> → |0>,
|0>|1> → |1>,
|1>|0> → |1>,
|1>|1> → |1>
XORも2ビットの入力から1ビットの出力を行い,その働きは,
|0>|0> → |0>,
|0>|1> → |1>,
|1>|0> → |1>,
|1>|1> → |0>
であって,入力のうちどちらか1ビットのみ|1>の場合に|1>を出力する。別の言い方をすれば,XORは2を法とする足し算であって,|a>|b> → |a+b, mod2>である。詳細は省くが,古典チューリングマシンはNOTANDのみで構成されることが分かっている。つまり,古典計算機は2ビットを入力として,1ビットを出力することが基本原理である。

一方,量子計算はユニタリー変換が基本であり,逆変換が必ず存在しなければならない。NOTは|0>を|1>,|1>を|0>に変換するので,明らかに逆変換が存在し,それは自分自身である。NOT・NOT = 1だからである。
もう一つ,古典でのANDのような働きをする論理ゲートが必要であるが,それは制御NOT(Controlled NOT, c-NOT)ゲートと呼ばれ,2ビットを入力し2ビットを出力する。その働きは,
|0>|0> → |0>|0>,
|0>|1> → |0>|1>,
|1>|0> → |1>|1>,
|1>|1> → |1>|0>
である。最初のビットは制御ビット2番目のビットは標的ビットと呼ばれている。機能的には,制御ビットが|0>なら標的ビットは変化しない,即ち,
|0>|0>|0>|0>
|0>|1>|0>|1>
ということ,及び,制御ビットが|1>なら標的ビットは反転する,即ち,
|1>|0>|1>|1>
|1>|1>|1>|0>
ということが特徴である。NOT制御NOTがあれば全てのユニタリー変換が構成されることが証明されており,万能量子チューリングマシンが作れることが分かっている。しかし,様々な試みはなされているが,現在に至るまで制御NOTゲートを物理的に構成することは達成されていない。 制御NOTは古典でのXORのような機能に似ているともいえる。
制御NOTゲートはエンタングルメント状態を作ることと同じであることは容易に分かる。
(|0> + |1>)|0> → |0>|0> + |1>|0>c-NOT|0>|0> + |1>|1>
つまり,制御NOTゲートはユニタリー相互作用の量子計算での表現であるとも考えることができるのである。制御NOTゲートが量子計算にとって本質的であることが理解できると思う。制御NOTゲートの量子回路図を図1で示す。

(2)量子アルゴリズム

NOT制御NOTがあれば任意のユニタリー変換が構成されることを証明し,量子コンピュータの基本原理を述べる。構成されたユニタリー変換回路は制御-U(Control-U)と呼ばれている。制御NOT制御-Uの特別な場合である。

簡単な例として,2行2列のユニタリー行列で,行列式が1であるSU(2)を考える。行列A,B,C,UをSU(2)の元とし,制御NOTをXで表すと,任意のUに対して,
ABC=1
U = AXBXC
となるように行列A,B,Cを選ぶことができる。図2に量子回路を示す。制御ビットが|0>の時は制御NOTであるXは働かないので,標的ビットはABCの変換を受けるが,これは定義により恒等変換である。また,変換A,B,Cは標的ビットにのみ作用するので1キュービットのユニタリー変換であるという。制御ビットが|1>の時はXがNOT変換として働くのでAXBXC(=U)の変換が働く。Uは制御ビットの値により標的ビットに作用するので2キュービット制御-Uという。このようなA,B,CとUの例としては,
U = Rz(α)Ry(β)Rz(γ)
(オイラー角(α,β,γ)を用いた任意の回転)及び,
A = Rz((α-γ)/2
B = Rz(-(α+γ)/2)Ry(-β/2
C = Ry(β/2)Rz(γ)
と採れば上記の条件ABC = 1,U = AXBXCを満たすことができる。Rξ(α)= Exp(iασξ/2)を用いてこれを確認する計算は単純であり省略する。ここでσξ(= σxまたはσyまたはσz)は通常のパウリ行列を表す。

次に,一般的な2キュービットの場合でも,
〔a〕任意のユニタリー変換である制御-U
〔b〕制御NOT(上記X)と
〔c〕1キュービットのユニタリー変換(例えば上記A,B,C)
で構成されることを証明する。3キュービット以上に拡張することは比較的容易である。

以下の手順で証明する。
[1].任意の2キュービットのユニタリー変換をSとすると,Sがユニタリーであるということは,Sの固有状態を|Ψm>として,

S|Ψm> = e mm>

が成立することである。従ってSは,この固有状態を用いて,

S = Σm=03e mm><Ψm|

と書くことができる。

[2].|0>,|1>を直交状態とする2キュービットの任意の重ねあわせ状態|Ψn>を直交基底の|n>に変換するユニタリー変換G(Ψn)は,〔b〕制御NOTと〔c〕1キュービットのユニタリー変換で構成される(〔証明〕)。ここに,|n>のnは,|0>=|0>|0>,|1>=|0>|1>,|2>=|1>|0>,|3>=|1>|1>の,0から3までを表す。従って,

n> = Σm=03Cm|m>

G(Ψn)|Ψn> = |n>

が成立する。

[3].上記G(Ψn)を用いて作るユニタリー行列S',

S’= Πm=03G(Ψm)-1mG(Ψm)

を考える。ここに,Xm

0 = e 0|0><0| + |1><1| + |2><2| + |3><3|
1 = |0><0| + e 1|1><1| + |2><2| + |3><3|
2 = |0><0| + |1><1| + e 2|2><2| + |3><3|
3 = |0><0| + |1><1| + |2><2| + e 3|3><3|

であり,これは特別な制御-U(後述)を用いて作ることができ,制御NOTと1キュービットのユニタリー変換で構成される。

S’はG(Ψm)とXmで構成されており,従って,〔b〕制御NOTと〔c〕1キュービットのユニタリー変換で構成される,ということができる。

[4].S’はSそのものに等しい(〔証明〕)。故に,任意の2キュービットのユニタリー変換Sは,〔b〕制御NOTと〔c〕1キュービットのユニタリー変換で構成されることが証明できた。

(3)量子コンピュータはなぜ速いか?

量子コンピュータがなぜ速いか,という理由は以下のように説明される。

まず第一が重ね合わせを使った量子並列計算である,

ということである。これはNキュービットの量子コンピュータでは,2次元のユニタリー変換を,(2)で説明した量子ゲートと呼ばれる基本的なユニタリー変換の組み合わせで,並列実行するからである。例えば,N個のキュービットを一斉に回転して,0から2N- 1までの数を表す重ね合わせ状態を瞬時につくることができる。これを,2進数表示によってラベルした状態
Σn=02N-1|a)で表し,このaが奇数であるラベルの状態を反転させる変換(マイナス符号を付けるに等しい)を考える。古典計算では,状態一つ一つにあたる作業が必要なので2N個の計算セットを必要とする。一方,量子計算では,単にN番目のキュービットで,
|0> → |0>,|1> → -|1>を行うだけでよい。たった1回の操作が2N個の操作と等しい結果を生じることができるのである。

第二の理由が,普通の高速フーリエ変換にも出てくる,テンソル積による計算の高速化である。

フーリエ変換といっても,量子状態は有限個のキュービットで表されるので,離散的フーリエ変換である。また,関数ではなく,状態をフーリエ変換するので,単に量子力学における表示の変換と言ったほうが適切かもしれない。2n項の離散的フーリエ変換を実行するのに,逐次的にわずかn回程度の制御-Uで実現できることが売りである。量子フーリエ変換については後述する。
テンソル積による計算の例として,マトリックスMをベクトルvに演算することを考える。Mを2n行2n列のマトリックスとし,vを2n次元ベクトルとすると,w  =  Mvの素朴な計算には(2n2 回の掛け算が必要になる。
Mとvをn個のテンソル積に分解できたとする。

M   = S(1)(2)(n)
v   = v(1)(2)(n)

ここに,S(i)はi番目のビット(v(i))にのみ働く2行2列のマトリックスである。w  =  Mvを具体的に書けば,

w = S(1)(1)(2)(2)(n)(n)

j1…jn=   Σi1…in(1)j1i1…S(n)jnini1…in

となる。S(1)(1)の演算には4回の掛け算が必要であり,従って,S(1),S(2),…,S(n)全部の演算を行うには4n回必要になる。テンソル積の計算は量子並列計算により1回で行うことができるので合計4n+1回の掛け算で計算が完了する。任意のマトリックスがテンソル積に分解できるわけではないので,量子計算が有効なアプリケーションは限定されることになる。

(4)量子フーリエ変換

量子フーリエ変換は,テンソル積で計算できるアプリケーションの代表例である。2n項の離散的フーリエ変換を実行するのに,逐次的にわずかn回程度の制御-Uで実現できることが売りである。以下に量子フーリエ変換の原理を示す。

量子暗号で述べたマッハ・ツエンダー干渉計(MZ干渉計)を使うと,
|0>   →   (eB|0> + ieA|1>)/√2
= ei(φA + φB)/2*(ei(φB - φA)/2|0> + ie-i(φB - φA)/2|1>)/√2
がハーフビームスピリッタBS2への入力状態となる。最終出力としては, |0>   →  ei(φA + φB)/2*{ei(φB - φA)/2(|0> + i|1>)+ ie-i(φB - φA)/2(i|0> + |1>)}/2
= iei(φA + φB)/2*{sinB - φA)/2*|0> + cosB - φA)/2*|1>}

を得ることができる(〔MZ干渉計〕)。 ここで,ビームスピリッタ(BS1,BS2)の役割をゲート記号〔〕(Hadamard Gate)で表し,位相変化(φB - φA)/2をもたらす機能をゲートとして〔Θ〕で表すと,MZ干渉計は量子ゲートとして以下のように表すことができる。

入力○―〔〕―〔Θ〕―〔〕―○出力

また,最終出力前の状態は,全体にかかる位相は無視し,θ=φA - φBとおくと,

(ei(φB - φA)/2|0> + ie-i(φB - φA)/2|1>)/√2
= (e‐iθ/2|0> + ieiθ/2|1>)/√2

であり,これは量子ゲート表示では,

入力○―〔〕―〔Θ〕―○出力

と同値である。〔Θ〕を2回続けると(e2*iθ/2|0> + ie2*iθ/2|1>)/2となることは容易に分かる。〔Θ〕をn回続けると同様にして,
(en*iθ/2|0> + ien*iθ/2|1>)/2n/2
を得る。従って,以下のような量子ゲートを作成すれば,nキュービットの量子フーリエ変換ができる。

入力|0>○―〔〕―〔Θ〕―○出力
入力|0>○―〔〕―〔Θ〕〔Θ〕―○出力
入力|0>○―〔〕―〔Θ〕〔Θ〕〔Θ〕―○出力



入力|0>○―〔〕―〔Θ〕〔Θ〕…〔Θ〕(n個のΘゲート)―○出力

何故なら,上記の量子ゲートは,以下の変換を表すからである。

|0>|0>…|0> → (en*iθ/2|0> + ien*iθ/2|1>)…
(e2*iθ/2|0> + ie2*iθ/2|1>) (e‐iθ/2|0> + ieiθ/2|1>)
= Σa=02n-1eiaθ|a)

最後の形がフーリエ変換であることを示している。量子フーリエ変換はショアの因数分解の主要なアルゴリズムを占めており,因数分解の時間がnの多項式の程度でおさまることが証明されている。これは,現在のRSA方式が数分で解読されることを意味し,このことにより量子コンピュータの研究が多いに加速されることになった。


(2002年5月18日;第一版 Copyright 寒泉)