超並列計算で革命を起こす：『量子コンピュータとは何か』
『量子コンピュータとは何か』ハヤカワ文庫
著者：ジョージ・ジョンソン
次世代コンピュータの原理と潜在能力を語る
量子的な現象を用いることで全ての計算を同時に行うことで計算回数を劇的に少なくできる量子コンピュータは今まさに開発が進んでいるテクノロジーで、注目を集めています。従来のコンピュータに対する量子コンピュータの性能は、火に対する原子力の能力の大きさに例えられるほどです。本書では量子コンピュータの原理とその潜在能力を数式を用いない形で紹介します。
本書の概要
序章 なぜ量子コンピュータは注目されているのか
本書の執筆当時(2004年)の最新のスーパーコンピュータ「Q」は1秒間に3兆回の演算を処理する性能を有していましたが、わずか64個の原子を用いた量子コンピュータに太刀打ちするのは単純計算で地球の表面積の5000倍の敷地が必要です。機密情報を守る暗号の堅牢性を担保している因数分解は、スーパーコンピュータを用いても計算には何十億年もかかりますが、量子コンピュータは計算時間を劇的に短縮します。
第1章 そもそもコンピュータとは何か 第2章 コンピュータの仕組み
現在のいかなるコンピュータの動作も、微小なスイッチのオン・オフでしかありません。従って原理的には棒と糸まきを組み合わせた装置で全く同じ動作を実現することが可能です。
第3章 量子の奇妙な振る舞いー「重ね合わせ」と「絡み合い」
ほとんどに人間には理解しがたい量子的振る舞いとして、「重ね合わせ」と「絡み合い」があります。
第4章 コンピュータの限界「因数分解」と量子コンピュータ
因数分解の問題の複雑さは桁数に対応して指数関数的に大きくなり、計算時間は最良のアルゴリズムを用いても「超多項式関数」によって増大するため、十分な桁数を持つ数の因数分解はスーパーコンピュータでは行えません。
第5章 難題を解決するショアのアルゴリズム 第6章 公開鍵暗号を破る
古典的コンピュータは1または0となるビットで記述されますが、量子コンピュータは0と1の重ね合わせとなることができるキュビットで記述されるため、複数の計算を同時に行うことができます。1994年にピーター・ショアは、因数分解を波の重ね合わせとして計算し、重ね合わせとして出力される計算結果から必要な答えをうまく抽出するアルゴリズムを発見したことで、因数分解において量子コンピュータがその能力を発揮できることがわかりました。
また、1996年にはロヴ・グローヴァーが、膨大な情報を高速で計算するアルゴリズムを発見しました。
第7章 実現に向けた挑戦 第8章 「重ね合わせ状態の崩壊」に立ち向かう
ショアやクローヴァーのアルゴリズムに代表されるようなソフトウェアの開発と共に、量子コンピュータ実現のためにはハードウェアの開発が必要です。すなわち、古典的コンピュータの万能素子NANDゲートに対応する量子コンピュータの制御NOTゲートの開発です。研究者たちはベリリウムイオンや光子、分子、電子など様々なものを使って制御NOTゲートを実現しようと思考錯誤しています。幾つものキュビットが計算に必要な時間の間、重ね合わせ状態を保持できるようにすることが難しいようです。
第9章 絶対堅牢な暗号「量子暗号」
RSA暗号は量子コンピュータによって打ち破られる可能性があります。しかし、量子コンピュータの完成より前に量子暗号が実現されれば我々の機密情報は永久に絶対的に安全であることが保証されます。量子暗号は、原理的に、解読不可能なのです。
第10章 宇宙一の難問—タンパク質折りたたみ・巡回セールスマン・バグ検証
タンパク質が正しい三次元構造を取るために膨大な折りたたみ方から一つだけを選ばなくてはならないという「タンパク質折りたたみ問題」、幾つかの点を採最短で巡回する経路を探索する「巡回セールスマン問題」、ソフトウェアの膨大なコマンドの全ての組み合わせに対してバグが生じないか検証する「充足化問題」などは「NP完全」と呼ばれ、非決定論的に多項式時間で解けるが、決定論的には指数関数的時間でしか解けません。量子コンピュータがNP完全という壁に風穴を開けられるかどうかは、科学の世界における最大の未解決問題の一つです。
ショアのアルゴリズム
ショアのアルゴリズムについて少し詳しく見ていくために、まずモジュロ計算によって15を因数分解することを考えてみます。
⑴まず、因数分解したい数(この例では15)より小さな数を一つ、適当に選びます(例えば7)。
⑵この数の1乗、2乗、3乗、…に対し因数分解したい数で割った余りを項とする数列を生成します(7=15*0+7, 49=15*3+4, 343=15*22+13, …により数列は7,4,13,1,7,4,13,1,…となります)。
⑶この数列の周期を調べます(この例では4)。
⑷はじめに選んだ適当な数の(周期/2)乗を計算します(この例では7*7=49)。周期が奇数になった場合は⑴に戻り、適当な数の選び方を変えます。
⑸⑷で計算した数の両隣の2つの数と、因数分解したい数の最大公約数を、ユークリッドの互除法などを用いて求めます(48と15の最大公約数は3、50と15の最大公約数は5)。
⑹⑸で得られた2つの数は因数分解したい数の約数になっています。
ショアのアルゴリズムではまず、スピンを持った原子の列を使って、⑵で何乗するか表す数1,2,3,…を表す状態を量子的に重ね合わせます。この原子列を「入力レジスタ」と呼びます。次に量子版のAND、OR、NOTゲートを使って累乗計算を行います。この時、全ての入力値は重ね合わされているので必要な計算は全て同時に行われます。この計算の答えも、スピンを持つ原子の列(出力レジスタ)の状態の重ね合わせとして出力されます。最後にすべきことはこの周期を知ることです。原子の列のスピンを測定すると、数列の中の一つへランダムに壊れます(例えば7)。入力レジスタと出力レジスタは互いに絡み合っているため、同時に入力レジスタも部分的に壊れます。すなわち、7を出力するような累乗数(1,5,9,13,…)だけを重ね合わせた状態へ変化します。この出力レジスタに対して量子的なフーリエ変換を施すことにより、周期を求めることができ、あとは単純な計算を行うことで約数を得るとこができます。
まとめ
量子コンピュータの概要を知りたくて本書を読みました。量子を使って計算を同時に行うという発想は割と昔からあったそうですが、ショアのアルゴリズムによって因数分解に対して量子コンピュータがその絶大な威力を発揮できるということが分かたことで注目を集めるようになったようです。量子コンピュータの実現のためにはハードウェア面の問題の解決が必要だそうなので、もしかしたら日本人研究者の活躍が期待できるかも知れないと思いました。
また、本書の巻末の解説を担当する竹内繁樹氏の著書『量子コンピュータ』(BLUE BACKS)では、竹内氏が研究者の立場から制御NOTゲートや量子フーリエ変換についてもう少し詳しく解説しており、本書と相補的な関係にあると竹内氏は言います。
