1+1を量子コンピュータで計算するには?

量子コンピュータと普通(ノイマン型)のコンピュータと特徴の違いについては別の note で説明します。　ここでは、プログラミング初心者を対象に、ごく単純な例で違いを説明ます。

実は、1 + 1 のような単純な一つの演算だけだと量子コンピュータの出番はありません。　それをスカラー演算と言いますが、普通の加算器を使えば良いでだけです。

少なくとも並列計算をして、速く解ける問題でなければ、量子コンピュータを使うメリットはありません。

しかし、二つの数の合計が2になる組み合わせを例に、量子コンピュータではどのように計算するのか、ものすごく大雑把ですが、簡単な例示を試みます。

量子ビットを配列で表現

今二つの観測のできない量子ビットがあったとします。　観測できないとは、それぞれのビットが二つの向きを持っており、どちらの向きが 0 か 1 か分からないとします。　

ちょうど、サイズが2の配列 x[ 0 ], x[ 1 ] と y[ 0 ], y[ 1 ] の中にそれぞれ値として 0, 1が入っており、同じ配列には必ず異なる値が入っているが、どちらに 0 / 1 が入っているか分からない状態であるとも言えます。 ここでは、x が第一ビット, y が第二ビットとしています。　

ただし、少し注意が要ります。　ノーマルな配列では、二つの状態を保持するのに、第一ビットや第二ビットを表す x や y はサイズが 2 の配列でなければならないのですが、量子ビットでは同時の状態を保てるので、それぞれ、一つずつで良いのです。

問題設定

次に、両方とものビットの和が 2 になった時の、ビットの向きの組み合わせが正解だと言う問題を解きたいといます。　

配列の例に言い換えると、x[ i ] + y[ j ] = 2 になる インデックス( i,  j )の組合せを求めると言う問題です。　なお、配列の中に 0 か 1 の数値しか入らなのですが、どちらが入っているか分からないものとします。

解き方

普通のコンピュータのスカラー演算では

1. 第一のビットをある向きにし(0 / 1 は分からない)、次に第二のビットをある向き(こちらも 0 / 1 が不明)にします。　これで和を求め値を調べます。　
   配列の例では x[ 0 ] + y[ 0 ] を計算します。

2. 次に第一ビットを別の状態にして、第二はそのまま、そして和を求めます。　
   配列の例では x[ 1 ] + y[ 0 ] を計算します。

3. 次に第一ビットを最初の状態にして、第二は最初と別の状態にします。　そして和を求めます。
   配列の例では x[ 0 ] + y[ 1 ] を計算します。

4. 最後に第一ビットとを第二を両方とも別の状態にして、和を求めます。
   配列の例では x[ 1 ] + y[ 1 ] を計算します。
   

と言うようにすべてのビットの状態を試すには、4通りの計算が必要です。　この問題では両ビットの( i,  j )組み合わせで、和が2になる正解は一つだけです。

普通のコンピュータで並列計算するには

今時のPCは複数コアお持ち、マルチスレッド計算できるのは当たり前です。　ただし、異なったプログラムを同時に実行(コンカレント)するのではなく、一つのプログラムの独立に計算できる部分を並行して計算(パラレル)するには、プログラミングで特別の指示と仕組みが必要です。　その仕組みの一つとして有名なものとして、MPI(Message Passing Interface)があります。　c言語をはじめ多くのプログラミング言語で利用可能です。

要は、 上記の1,2,3,4 は独立して計算できるので、4つのノード(独立した加算機)で計算するのです。　同時に計算すると短ければ1回の計算時間で済みます。　ただし、計算を振り分けたり、集計したりするオーバーヘッドの時間が必要になるので1回の計算時間よりは少し長くなります。　それでも、スカラー演算の4回分の計算時間より短く、i,jの範囲や変数が増えると圧倒的に並列計算が速くなります。　なお、このような単純なものはベクトル型の並列計算と呼ばれ、MPIのような指示がなくとも、コンパイラの最適化機能で自動的になされる場合が多いです。

正解が得られる組み合わせの確率が高くなるように操作する

一つの量子ビットに二値が同時に持てる量子コンピュータでは、二つの量子ビットがあれば、一回の計算ですみます。　何故なら、二つの状態を同時に持てるので、和が 2 になる組み合わせの向きの確率が最も高くなるように操作して、一回の計算で ( i,  j )の組みを知ります。

この、確率の操作の部分が結構キモなのです。　量子コンピュータと言えばこの部分の説明がよく語られるのですが、並列計算の前提が分かっていないとタイトルのような疑問が出てくると思います。

ショアのアルゴリズム

1994年、ピータ・ショアが上記の加算のような単純なものではなく、暗号解読にながる素因数分解のアルゴリズムに対して、操作する実用的なロジックが考案されて、量子コンピュータの研究が大きく進みました。

普通の並列コンピュータとの違い

以上、正確ではないですが、簡単に説明を試みました。　少しでも、イメージを掴むことができれば幸いです。

もちろん、上記の例では、今の一般的な PC の CPU でも加算器を複数持つので並列演算ができ、プログラミングで一回の演算サイクルで計算することが可能ですが、一つの素子のレベルで多重状態を表現できるのが、量子コンピュータです。　

ただし、量子コンピュータは答えを一つしか引き出せません。　正解だけ計算するようにロジックを操作している...ような感じです。　しかし、普通の並列コンピュータでは、正解以外も含めて、すべての結果を引き出せます。　だって、並列で全部計算していますから。

これが答えが一つで良い暗号解読、最適解を探す問題などに量子コンピュータが、威力を発揮すると言われる所以です。