囲碁と素数

Igo and prime number

第三部、量子コンピュータのその2

前々回に続いて、

量子とは

重ね合わせ

ビット、量子ビット

ドイチュのアルゴリズム

 量子3ビット

量子転送

 ベルの不等式の破れ

グローバー、ショアのアルゴリズム

等々についての説明が必要になるが、遠回りになるようでも、これらを既に説明してきたアルゴリズムの誕生から、ソフトウェア、AIへと続いたこれまでのコンピュータ世界と区別して、明確に対比させることを目指して話を始めたい。

 

これまで話が専門的になることから半導体の物理にはふれずに来たが、半導体LSIの動作の基礎には半導体の物理がある。半導体の物理とは、半導体を流れる電流、半導体キャリアによる電流が、他の金属や絶縁体などの材料とどう異なるかを説明するもので、これも量子力学の初期の成果による理論である。しかし、そのような半導体を流れる電流をトランジスタという半導体素子でスイッチさせる制御方式が生まれ、確立されるとそこから先は、量子力学の理論の必要性はほとんど無くなる。電流のスイッチのオン/オフの0, 1のビットの世界である。しかし、量子力学的には、0, 1の(単純にいえば) 重ね合わせの状態が本来的に存在する。量子力学自体も初期のアインシュタインの頃から発展して、ベルの不等式の理論、実験的な検証(ベルの不等式の破れ)へとつながり70年余りが経過している。そんな中で量子ビットを用いた、従来の古典コンピュータと全く異なる量子コンピュータが生まれて来た。量子ビットトランジスタ素子に対応する量子コンピュータの素子、量子ゲートはどんなものかが問題になる。

量子ビットの現在、最も実用化研究が進んでいる方式は、半導体超電導状態にして電荷を量子状態にして蓄える方式である。この量子ビットマイクロ波を送り、状態を変化させるのが量子回路。アダマールゲートと呼ばれるのは、その中で重ね合わせの状態を作りだせる。

|0>が入力すると、|+>=(|0>+|1>)/\sqrt{2}\ が出力、

|1>が入力すると、|->=(|0> - |1>)/\sqrt{2}\ が出力される。

具体的に量子コンピュータの素子、量子ゲートがどのように実現されているかは、後回しにして、ここでは超電導状態やスピン、光の量子光学による制御で実現されている(当然ながら、量子力学に基づいている)ことだけ紹介して、ドイチュのアルゴリズムという具体例で説明を進めたい。

 

ドイチュのアルゴリズム―均等と一定 (あるいは、等分と均一)―

ここでの説明は、量子3ビットを用いた場合の例を用いる。そもそも、なぜ、量子コンピュータを開発するかというと、このビット数を3ビットから4, 5, 6ビット…と増やしていった時に、重ね合わせの状態を利用したある種の並列性から従来の古典コンピュータによる処理速度を量子コンピュータが追い抜ける可能性があるからである。

そこで、ドイチュ、正確にはドイチュ-ジョサの問題は、[「量子コンピュータ」竹内 繁樹、講談社ブルーバックス 2005年から引用]

上図の?位置のブラックボックスに入力された3ビットの数が均等か一定かを判定することである。均等とは上図の例の[00101101]のように0, 1の数が等しい場合、一定は文字通り0か1のみが8連続した場合である。2進関数的に表すと、変数を簡単化して2ビットに減らし考えると、変数は4通り、関数は均等か一定かのどちらかしかないので、8通りの組み合わせ

f(00)=f(01)=f(10)=f(11)=0 か f(00)=f(01)=f(10)=f(11)=1 の一定、2通り

f(00)=f(01)=0 で f(10)=f(11)=1 の均等

f(00)=f(01)=1 で f(10)=f(11)=0 の均等

f(00)=f(10)=0 で f(01)=f(11)=1 の均等

f(00)=f(01)=1 で f(01)=f(11)=0 の均等

f(00)=f(11)=0 で f(01)=f(10)=1 の均等

f(00)=f(11)=1 で f(01)=f(10)=0 の均等、6通り

合計8通りしかない、問題設定になっている。

ドイチュ-ジョサの実現したアルゴリズムでは、これを図5-4の観測のところで、もしすべてが状態|0>であれば、その結果ブラックボックスに入力された3ビットの数が一定であることが言える。ビット数を元の3ビットに戻して話を進める。このビット数nが2, 3, 4と増えるに従い、従来のコンピュータでは2nのような処理ステップ数を用いて均等か一定かを判定することができるが、ドイチュ-ジョサのアルゴリズムでは処理ステップ数の増加はnに比例している。

図5-4でステップAのHの記号はアダマール(Hadamard)ゲートをさす。

3つのアドレスビットは|0>と|1>の重ね合わせ状態へと変化する。一方、|b>は|0>のまま。4つの量子ビットの状態を具体的に書くと、

 (|0,0,0,0> + |0,0,1,0> + |0,1,0,0> + |0,1,1,0> + |1,0,0,0> + |1,0,1,0> + |1,1,0,0> + |1,1,1,0>)/2\sqrt{2}\         (1)

次に、ステップBのブラックボックス回路では、上の例えば|0,0,0>が入力されると、量子ビット|b>はブラックボックスのビット列の最初の値に応じて出力される。その値が0なら|b>は|0>のまま。1なら|b>は|0>から反転して|1>に変わる。

 今、ブラックボックス回路に蓄えられているビット列が均等の[10110100]だとしよう。上に述べたことから(1)式の|b>の変化を反映させると

(|0,0,0,1> + |0,0,1,0> + |0,1,0,1> + |0,1,1,1> + |1,0,0,0> + |1,0,1,1> + |1,1,0,0>+ |1,1,1,0>)/2\sqrt{2}\         (2)

(2)式のそれぞれの項の最終ビット|b>は、蓄えられていた[10110100]そのものになっていることが分かる。一度の操作で(ステップBの段階で) ビット列の情報を読み出せている訳である。この状態から特徴を抽出するための操作が次のステップCである。

レジスタビット|b>に制御位相シフトと呼ばれるゲート操作を行う。これは、対象とするビットが|1>の時だけ、その位相をプラスからマイナスへ変化させる。この操作の結果は、

(-|0,0,0,1> + |0,0,1,0> - |0,1,0,1> - |0,1,1,1> + |1,0,0,0> - |1,0,1,1> + |1,1,0,0> + |1,1,1,0>)/2\sqrt{2}\         (3)

次のステップDでは、Bと同じブラックボックス回路を通るので、|b>の状態はもとの|0>に戻ることになり、

(-|0,0,0,0> + |0,0,1,0> - |0,1,0,0> - |0,1,1,0> + |1,0,0,0> - |1,0,1,0> + |1,1,0,0> + |1,1,1,0>)/2\sqrt{2}\         (4)

となる。元の|0>に戻ったアドレスビット|b>を分けて書くと

(-|0,0,0> + |0,0,1> - |0,1,0> - |0,1,1> + |1,0,0> - |1,0,1> + |1,1,0> + |1,1,1,0>)|0>/2\sqrt{2}\         (5)

次のステップEでは、これら3つのアドレスビットに再度、アダマールゲートを作用させる。アダマールゲートは|0>に作用させると(|0>+|1>)/\sqrt{2}\

|1>に作用させると(|0> - |1>)/\sqrt{2}\ と変化する。(5)式のそれぞれに作用させる。

|0,0,0> については、左側のビットが(|0>+|1>)/\sqrt{2}\となり、次に真ん中のビットに作用させて、

{|0> (|0>+|1>) |0> + |1> (|0>+|1>) |0>}/2

=(|0,0,0> + |0,1,0> + |1,0,0> + |1,1,0>)/2

となる。最後に右側のビットに作用させると

(|0,0,0> + |0,0,1> + |0,1,0> + |0,1,1> + |1,0,0> + |1,0,1> + |1,1,0> + |1,1,1>)/\sqrt{2}\

となる。

|0,0,1> については、左側のビットに作用させて(|0,0,1>+|1,0,1>)/\sqrt{2}\となり、次に真ん中のビットに作用させて、

(|0,0,1>+|0,1,1>+|1,0,1>+|1,1,1>)/2 となる。

最後に右側のビットに作用させると

(|0,0,0>-|0,0,1>+|0,1,0>-|0,1,1>+|1,0,0>-|1,0,1>+|1,1,0>-|1,1,1>)/2\sqrt{2}\となる。

同様に、残り6項の状態に作用させて、全てを足し合わせると、プラスマイナスで打ち消しあう状態があり、(5)式の8つの状態に対する作用後の結果が

(|0,0,1> + |0,1,1> - |1,0,0> + |1,1,0>)/2  (6)

となる。

さて、この3つのアドレスビットの結果(6)を観測すると、もし、全てが状態|0>であれば、一定。もし、全て|0>以外の結果が得られれば均等と断定できる。今の結果(6)の重ね合わせ状態は明らかに全て|0>以外であるから、このブラックボックスに入力された3ビットの数が均等であることが言える。確かに、今の場合[10110100]の均等のビット列が入力されたので正しい結果である。

 別の一定のビット列[00000000]や[11111111]を入力させた場合には、今度は、全てが状態|0>である観測結果になるハズである。

例えば、ビット列[00000000]が入力されると、前式の

ステップBの(2)式では、どの項においてもレジスタビット|b>は|0>になっている。この状態に、ステップCで制御位相シフトを作用させたとしても、レジスタビット|b>は|0>のため、位相シフトは生じず、状態は変化しない。つまり|a_{0}>、|a_{1}>、|a_{2}>がすべて|0>と|1>の重ね合わせの(|0>+|1>)/\sqrt{2}\状態となり、|b>は|0>という状態となる。

次のステップEのアダマール変換は(|0>+|1>)/\sqrt{2}\に作用させると

|0>に変化させる。したがって、3つの量子ビット|a_{2},a_{1},a_{0}>、にアダマールゲートが作用されると、それぞれの量子ビットは|0>状態に戻る。つまり|0,0,0>。前式(6)に相当。この3つのアドレスビットの結果(6)を観測すると、全て|0>の結果であるから、一定と判定される。

 

このような量子ブラックボックス回路を演算回路U_{f}と書き、上で述べたことと等価なことだが、2進関数的に表すfの問題関数を実現する演算回路U_{f}が、

量子力学風に書くと入・出力のブラ、ケットを用いて

                                    |φ> = U_{f} |ψ>

と表記されることになる。