量子コンピュータとかけてピアノと鍵盤と解く、その答えは~並列処理
竹内氏は量子コンピュータの研究者。 『「量子ビット」を使うと、なぜ「超並列計算」ができる?莫大な計算結果の重ね合わせ状態から、答えを1つに確定できるのはなぜ?』
量子コンピューターの概念((wiki)
従来の計算機(量子計算機に対して、古典計算機という)は1ビットにつき、0か1の何れかの値しか持ち得ないのに対して、量子計算機では量子ビット (qubit; quantum bit) により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。
n量子ビットあれば、2^nの状態を同時に計算可能。(Wiki)
現時点での量子コンピュータは、特定のアルゴリズムを高速に処理する専用計算機や、古典計算機を補助するコプロセッサとして考察されている(量子コンピュータは非ノイマン型である)。
量子コンピュータの誕生:重ね合わせ状態の中で並列に動くコンピュータ
量子コンピュータのアイデアの登場は、1985年。場所はイギリス、オックスフォード大学である。発案者は、デビッド・ドイチュ。彼はそのころ理論物理学を研究する若手の研究者で、特に平行宇宙論に関心を持っていた。平行宇宙論はとは「重ね合わせ」の考え方をもっと拡張して解釈する考え方だ。「重ね合わせ」にあるそれぞれの状態は、実際には別々に平行している宇宙に属しているものと解釈する。(81ページ)
量子コンピュータのアルゴリズムの特徴
量子コンピュータのアルゴリズムでは重ね合わせ状態にある膨大な計算結果から、「特徴を重ね合わせ状態にある膨大な計算結果から、「特徴をうまく抽出」する処理により、目的の計算結果を高速に得ているのだ。(84ページ)
すべての場合を調べてみなければ結論の出ない問題~巨大整数の素因数分解
1994年にショアが発見した因数分解の量子計算アルゴリズムを取り上げよう。因数分解は、一見簡単そうに見えるが、桁数の増大とともに指数関数的に計算時間が増大する事が知られている。(154ページ)
ショアのプログラムの要素を159ページから抜粋すると「因数分解したい数を『X^RをNで割ったら余りが1を満たすような、自然数Rを探す』」というプログラムにかけまず第一段階の処理を終わらせる」となる。
量子コンピュータをピアノと楽譜に例えてみる
現在のノイマン型コンピュータが一つ一つ論理判断をしていく。言ってみればピアノを楽譜にしたがって引いていくので回答を出すのに一定の時間がかかる。巨大整数の因数分解は弾けば弾くほど楽譜が長くなる様なもの。
量子コンピュータはすべての鍵盤に対し「同じアルゴリズムを実行」=「同時に同じ方法で鍵盤を押す」て、合致する回答(例えば余りが1とあるR)を抽出する。この合致した答をつなぎ合わせると、「すべてを調べてみるのと同じこと」になる。
40の鍵盤をイメージしてみる。40の鍵盤を同時に押し、その響きから出た応えを結合させる。これにより2^40=1兆ステップを越える処理が行える。
40の鍵盤を同時に弾き、その結果を一度に聞き取る事ができるか、これが現在の量子コンピュータの実装・実現としての技術的課題ともイメージできる。
蛇足
我々は指数関数的増加を想像できる。