2011年12月06日

JavaScriptでつくる量子コンピューター

はてなブックマークに登録

KLab Advent Calendar 2011 「DSAS for Social を支える技術」の4日目です。
「DSAS for Socialは量子コンピューターつかってるのかよ」という声が聞こえてきそうですが、すいません、単にタイミングの問題です。


■古典計算脳の恐怖

JavaScriptで量子コンピューターがつくれるのか?もちろん無理です。本物は。古典的計算機の上で動くブラウザの上で量子コンピューターが動くはずはありません。


しかしシミュレーターならば話は別です。たとえば本来なら並列で計算すべきところを、順番に計算すればよいだけ。非決定性チューリングマシンだって、何だってつくれます。
何のためにJavaScriptで量子コンピューターをつくる必要があるのか。NO REASON! ですが、強いていえば「新しい計算パラダイムを学ぶため」です。古典計算機に憑かれた頭をリフレッシュして、量子計算で考えられる頭をつくりましょう。


ただし、以下は、専門家ではないわたしが教科書を読んでシミューレーターをつくっているだけですので、まちがいなどが含まれているかもしれません。まちがいに気がついた方は遠慮なくご指摘頂けるとありがたいです。
なお今回使用したコードを含め、シミュレーターのコードはすべて以下にpushしてあります
https://github.com/takada-at/quantum.js

参考文献:
量子コンピュータ (ブルーバックス)
一冊目。ブルーバックスですが、内容がつめこまれてます。

マーミン 量子コンピュータ科学の基礎
二冊目。物理の知識は前提されておらず、比較的読みやすいです。


■古典ビットと量子ビット

古臭い古典的なコンピューターでは、1ビットは、{0, 1} どちらかの値だけを取ります。0 or 1。つねにそのどちらか一方だけ。
量子コンピューターでは、1ビットははるかに自由な値を取ります。0、1、またはその重ね合わせ。
重ね合わせとは何か? ひとまず「2つの状態が半透明になって重なりあっている」という絵でもイメージしておいてください。


一般的には、1ビットの量子ビットの状態は以下のように書けます。


$a\left|0\right\rangle + b\left|1\right\rangle$


$\left|0\right\rangle$と$\left|1\right\rangle$はビットの状態であるベクトル。量子力学ではしばしばこの$\left|\right\rangle$の記号を使ってベクトルを表記します。
aとbは「振幅」と呼ばれますが、ひとまず二乗すると確率になる値だと思ってください。
このビットが、$\left|0\right\rangle$である確率は、
$|a|^2$

$\left|1\right\rangle$である確率は
$|b|^2$

です。
確率なので以下の制限があります。
$|a|^2 + |b|^2 = 1$

実際のところ、この制限以外の制限は何もなく、aとbは複素数になることもありえます。
また古典ビットが取る{0, 1}の状態は、この重ね合わせの特殊な事例と見なすことができます。
0の場合
$1*\left|0\right\rangle + 0*\left|1\right\rangle$
1の場合
$0*\left|0\right\rangle + 1*\left|1\right\rangle$


これをnビットに拡張したときに何が起きるか?
n個のビットがあるとき、古典ビットは、$2^n$通りの可能性の内のいずれか1つとなります。
2ビットなら、0から3までの4通り。
00
01
10
11

量子ビットでは、n個のビットを使って、$2^n$の可能性の重ね合わせを表現できます。
$a_0\left|00\right\rangle + a_1\left|01\right\rangle + a_2\left|10\right\rangle + a_3\left|11\right\rangle$

1ビットの場合と同様に、平方の合計は1になります。また、$a_0$から$a_3$までの値は二乗すると確率を表わす値となります。
$|a_0|^2 + |a_1|^2 + |a_2|^2 + |a_3|^2 = 1$

このように少ないリソースで大量の状態を表現でき、しかもそれらのビットに並列に作用できるというのが量子コンピューターの強みと言えるでしょう(後述するようにこれには罠がありますが)。
また、思うに、量子ビットの複雑さは、この「n個のビットで」「$2^n$の状態を表現する」という部分にあります。k番目のビットを変化させると、$2^n$個の状態はどのように変化するか? 「ビット」と「状態」という2つの側面を念頭に置きつつ考えないとすぐ頭が混乱してしまいます。

以上のように、長さnのビット列に対し、量子ビットクラスは$2^n$の状態を保持し、それぞれの状態は係数を持ちます。シミュレーターを実装するにあたって、量子ビットクラスのコンストラクターは以下のようにつくりましょう。ビットの長さをlengthで保持し、各状態の振幅をthis.statesの配列で持つことにします。
初期状態では、$\left|0\right\rangle$の確率が1になるように初期化しておきます。


function Qubits(length){
    this.length = length;
    var statelen = Math.pow(2, length);
    this.states = new Array(statelen);
    this.states[0] = 1.0;
    this.state_length = statelen;
    for(var i=1;i<statelen;++i){
        this.states[i] = 0.0;
    }
}

■「観測」を実装する

重ね合わせ状態の量子ビットは、「観測」されることで、古典的な状態のいずれかに収縮します。
「観測」後の量子ビットは、もはや重ね合わせの状態ではなく、$\left|0\right\rangle$から$\left|2^n-1\right\rangle$の状態のいずれかに落ちついています。

量子コンピューター上の「観測」は単にビットを観察することではなく、独自の演算と考えた方がよいでしょう。観測は不可逆な演算であり、ビット列は観測されることで重ね合わされた状態の内のただ一つに収束してしまいます。シミュレーター上ならば、計算の途中経過を知ることも可能ですが、実際には、状態を収束させることなく、計算結果を知ることはできません。
map/reduceの比喩で言えば、量子コンピューターは、mapにあたる超並列計算を実現するが、結果を観測しようとすると、ランダムにそのなかのただひとつの計算結果に収束してしまいます。そこで実用的な目的に供するにはreduceの段階でさまざまなトリックを弄する必要があります。

ともあれ、1ビットを観測するコードは以下のようになります。
イメージとしては、n番目のビットについて確率判定を行なって、n番目のビットのみ状態を確定させる感じです。
Qubits.prototype.measure = function(n){
    var bit = 1<<n;
    var sumprod = 0;
    var val = 0; var prob;
    for(var i=0;i<this.state_length;++i){
        //標的ビットがたっている状態の係数の平方を足します
        if(i&bit){
            sumprod += square(this.states[i]);
        }
    }
    //確率による判定
    if(Math.random() < sumprod){
       //該当ビットが1だった場合
        prob = Math.sqrt(sumprod);
        val = 1;
        for(i=0;i<this.state_length;++i){
            if(i&bit){
                cdiv(this.states[i], prob);
            }else{
                //該当ビットが0であるような状態はすべて確率0にする
                this.states[i] = 0.0;
            }
        }
    }else{
       ....
    }
    return val;
};


■重ね合わせで計算する

ここで改めて考えてほしいんですが、観測した時点で結果が1つに収束するというのは、コップのなかでサイコロを振って、コップを開くまでは結果がわからないというのとは何が違うんでしょう?コップを開くまで結果がわからないというだけのことであれば「状態の重ね合わせ」という概念は必要ないように思われます。

いろいろな答えがありえると思いますが、ひとつ重要な違いは、「重ね合わせ状態」は関数のインプットになりえるということです。

たとえば、単純に、ビットを反転させるという作用を考えてみましょう。以下の4つのビットに対してこの変換を作用させるとすべて違う結果を生み出します。なお下2つは、$\left|0\right\rangle$と$\left|1\right\rangle$の重ね合わせ状態にあるビットです。
$\left|0\right\rangle$
$\left|1\right\rangle$
$\frac{1}{\sqrt2}(\left|0\right\rangle + \left|1\right\rangle$)
$\frac{1}{\sqrt2}(\left|0\right\rangle - \left|1\right\rangle$)

結果はそれぞれ以下のようになります。
$\left|1\right\rangle$
$\left|0\right\rangle$
$\frac{1}{\sqrt2}(\left|0\right\rangle + \left|1\right\rangle$)
$-\frac{1}{\sqrt2}(\left|0\right\rangle - \left|1\right\rangle$)
注目すべきは4つめの結果で、$\left|0\right\rangle$の係数と$\left|1\right\rangle$の係数が逆転しています。あたかも重ね合った状態のそれぞれに対し、ビットの反転という操作を作用させたかのようになっているのです。
「コップを開くまでわからない状態」というのは実際には、サイコロの目はいずれかに確定している状態です。従って、それ独自の状態として関数のインプットになることはありえません。一方、重ね合わせの状態は独自の状態として関数のインプットとなります。

ちなみに、1ビットの量子ビットに対する操作は、ベクトルと行列のかけ算で書けるのですが、n番目のビットに作用するコードは以下のようになります。
n番目のビットがたっている状態とたっていない状態の係数をベクトルと見なして、行列をかけています。

Qubits.prototype.op = function(n, mat){
    var bit = 1 << n;
    for(var i=0;i<this.states.length;++i){
        if(i&bit){
            var r = mvprod(mat, [this.states[i^bit],
                                 this.states[i]]);
            this.states[i^bit] = r[0];
            this.states[i]     = r[1];
        }
    }
};
たとえば以下のような行列をかけると、ビットの反転と同じ効果となります。
[[0, 1],
 [1, 0]]
残念ながら、量子コンピューターのアルゴリズムの具体的内容にはまったく入れなかったのですが、とりあえず以上で終わります。どれくらいのペースで書けるかわかりませんが、少しずつつづけて書きたいと思います。

takada-at
klab_gijutsu2 at 22:10│Comments(2)

この記事へのコメント

1. Posted by cocoatomo   2011年12月07日 23:45
楽しく読ませてもらいました. 続きを楽しみにしています.

理論の間違いではないのですが, 最初の式に誤植があります. 第2項のベクトルは |1> だと思います.
2. Posted by takada-at   2011年12月08日 20:16
ありがとうございます。修正しました!

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント