量子コンピュータ
出典: フリー百科事典『ウィキペディア（Wikipedia）』
量子コンピュータ（りょうしコンピュータ）は、量子力学的な重ねあわせを用いて並列性を実現するコンピュータ。量子計算機。
従来の計算機（量子計算機に対して、古典計算機という）は1ビットにつき、0か1の何らかの値しか持ち得ないのに対して、量子計算機では量子ビット（qubit）により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない並列性を実現している。
目次 |
[編集] 歴史
量子計算機の歴史は、1982年にベニオフが量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、同年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、ドイチュによって、量子計算機の原モデルである量子チューリングマシンが定義されるなど量子計算の分野に関する研究が進められていた。しかし、数年が経つと、量子的重ね合わせによる並列性を効率的に活用する手法が発見できなかったり、量子計算機自体の開発の困難性が明らかになり、一時的に量子計算機に関する研究は下火になった。この状況を打破するきっかけになったのが、1994年にショアによって考案された所謂、Shorのアルゴリズムである。Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機で現実的な時間で解くことの出来ないとされる素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。このため、量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。
実験的には、非線形光学、レーザー冷却、量子ドット、核磁気共鳴などによる実現法が研究されている。
[編集] 実用化へ向けて
2003年に世界で初めて固体素子による2ビット演算に成功したNEC基礎環境研究所は、量子計算機で30から40ビットの計算を実現することが1つのマイルストーンになるだろうと予測した。古典計算機で原子・分子系のシミュレーションを行おうとすると、原子30個程度で限界がくる。これが量子計算機ならば、同じシミュレーションを30から40ビットで実行できると考えられる。これが可能になれば、アミノ酸やタンパク質の立体構造の解析など負荷が大きい問題に、直接計算で挑むことができる。
量子計算機の開発は、通信ネットワークにも大きな変化をもたらす。例えば、原理的に盗聴が不可能な暗号方式を実現したり、従来の限界を超える量の情報を伝送することができる（ここでいう「限界」とはいわゆるシャノン限界のことで、雑音などにより伝送できる情報量に上限が存在することに起因する）。こうした量子理論を応用したネットワークを、量子インターネットと呼ぶ。
量子インターネットに向けた研究開発の中でも、量子暗号は実用化という点で先行した。アメリカ合衆国では2004年夏からボストン市街地で3箇所を光ファイバーで結ぶ量子暗号ネットワークの実証実験が進められ、100キロメートルを超える通信を可能にした。
通信路を介して送受するデータは、量子計算機の原理で処理すれば、従来の限界を超える量の情報を伝達できることも2003年、日本の情報通信研究機構が原理的に確認した。この仕組みは衛星通信などに利用することで、通信効率を大幅に改善できる。
[編集] 原理
量子計算機の計算能力はいかにして生み出されるのか。簡単な計算を例に説明する。
ここで、素因数分解を例にとる。大きな数、例えば64ビットで表せる素数を2つ、掛け算する場合を考える。64ビットあれば10の19乗程度の数を表現できる。この計算は単なる掛け算で、簡単に実行できる。これを A×B→C と表すと、Cは128ビットで、10の38乗程度になる。
ではCが与えられたときに素因数分解するには、すなわち素数AとBを求めるにはどうすればよいか。実は効率的なアルゴリズムは発見されていない。したがってこれを計算するには、適当に仮定したAでCを割ってみるしか手がない。Aの値を次々に変化させていき、割り切れたときにそれが正解となる。
この方法では、いったい何回計算すれば、正解にたどり着けるだろうか。偶然、1回ですむこともあるだろうが、平均的には計算回数が天文学的な大きさになる。例えば200桁程度の数を素因数分解するには、古典計算機で何億年もの時間を要する。公開鍵暗号方式はこの方法を利用して事実上の安全を保証している。
ここで計算機をAの大きさだけ、すなわち10の19乗台用意して並列に動作させれば、それこそ一発で答えを計算できることは誰の目にも明らかだ。もちろん、このような莫大な数の計算機をそろえることなど、現実にはできない。ところが量子計算機ならば、この超並列計算を1台で実現できる。
[編集] 量子重ね合わせ
量子計算機の持つ計算能力の源泉は、量子の性質である「量子重ね合わせ」にある。古典計算機では、1ビットの値は0か1かのどちらかに必ず決まる。「どちらでもある」という状態は、古典的な電子回路では事実上、意味を持たない。これに対し量子計算機では、ビットの値として「0でも1でもある」という状態をとることができる。これが重ね合わせの状態である。
このような量子計算機のビットを「量子ビット」と呼ぶ。古典計算機のビットを「古典ビット」と呼んで、両者を区別する。
[編集] 量子ビットの表現
古典的な電子回路では、電流や電圧は連続した値をとる。そのため古典計算機では、ビットを表すときに、例えば3ボルト以上なら「1」、1ボルト以下なら「0」を表す、といった具合に決めている。この回路は古典物理学の法則に従って動作する。
これに対し、量子物理学の法則に従うミクロの世界では、量子のエネルギーは連続ではなく、飛び飛びになっている。そうした非連続なエネルギーの値をとる量子の状態のそれぞれを「エネルギー準位」などと呼ぶ。
量子ビットは、エネルギー準位を2つ選び、それらを0と1に対応するものと見なしたものである。このとき、量子の周囲の条件を上手く与えると、その量子が2つのエネルギー準位の間を行ったり来たりするようにできる。その場合、どちらのエネルギー値をとるかは確率によって表現される。この状態を
と表す。
と
は量子ビットの値を表す。
は量子力学で使用する記号で、量子の「状態」を意味する。量子ビットを古典ビットと区別して、このように表記する。
ここでいう確率は、サイコロの目が出る確率とは少し違う。サイコロの場合、例えば出る確率は6分の1という実数に成る。これに対し、上記の量子ビットでは、αの絶対値の2乗が「になる確率」、βの絶対値の2乗が「になる確率」をそれぞれ表す。
量子ビットを使った計算そのものを、人間が把握できる現実の世界に対応させることはできない。以上のような計算の結果を通じてのみ、人間は量子を使った計算について知ることができる。
[編集] 量子ビットによる計算
1つの量子ビットがにもにもなり得ることを、量子重ね合わせと呼ぶ。ここで前記の A×B→C という計算に戻る。AとBは64ビットのデータであった。1つの量子ビットはとを重ね合わせているのだから、64ビットならおよそ10の19乗通りのデータを「同時に表現できている」ということになる。このAで同じような状態にあるCを割ることができると仮定しよう。すると、その結果であるBは、同じ10の19乗通りだけ重ね合わされた状態として得られる理屈になる。すなわち10の19乗通りの演算を一瞬に実行できることになる。これが量子計算機の並列計算の原理である。
この計算をさらに詳しく見てみる。簡単のため2量子ビットの計算を例にとる。古典ビットの場合と同様、計算の原理はビット数が増えても変わらない。ここではfという計算の入力データとして、2つの量子ビットaとbを与えるものとする。このとき、まとめて
と書く。
出力となる2量子ビットのうち、1つはaの内容をそのまま通過させ、もう1つはaの値によって変わると仮定しておく。この出力を、aによって変わるという意味でf(a)と書くことにする。出力の2量子ビットをまとめて書くと
になる。
さて、入力aが量子重ね合わせ状態
にあるとする。すると出力は、aがである度合いの分だけ
になり、同様にaがである度合いの分だけ
になる。したがって、
で表されるような量子重ね合わせ状態が、この計算の結果となる。2つの計算f(0)とf(1)が並列に実行されたことになる。
ここで入力bも量子重ね合わせの状態にあって、例えば
と表せるとする。計算を分かりやすくするためにfは入力aがのときはbをそのまま通過させ、aがのときはbの値を反転させる操作であるとする。このとき出力となる2量子ビットの組は、
、
、
、
の4つの状態が重ね合わされた状態になる。これは4つの計算が並列に実行されたことを意味する。同様にして、入力がNビットであれば、2のN乗通りの計算が並列に実行されるのである。
[編集] アルゴリズム
2006年現在で量子計算機特有のアルゴリズムがいくつか知られており、代表的なものは以下の2つである。
[編集] Shorのアルゴリズム
素因数分解問題を高速に（多項式時間で）解く事ができるアルゴリズム。古典計算機では非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。少し改造することで離散対数問題も多項式時間で解く事ができる。2001年12月にIBMアルマデン研究所にて7qubitの量子計算機で15(=3*5)の素因数分解に成功したことが発表された（Nature,12月20日発行号）。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。
[編集] Groverのアルゴリズム
n個のデータの中から、ある特定のデータを
ステップで取得することが出来るアルゴリズム。古典計算機では凡そn / 2ステップが必要である。 1996年にGroverが発表した(\[G96\])。きわめて広範な種類の 確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで 落とすことができる。Shorのアルゴリズムほどその効果は劇的ではないが、広い応用をもつことが特徴である。検索条件や検索対象について改良されている。
[編集] 計算理論からの視点
量子計算機により、効率的に解ける計算量のクラスとしてBQPが存在する。確率アルゴリズムに対する古典計算機の計算量クラスとしてBPPが存在するが、BQPはこれと似た概念である。
古典計算機で効率的に解ける問題のクラスであるとされているPはBQPの真部分集合であると考えられている。素因数分解問題と離散対数問題はBQPに属される。これら二つの問題はNP問題であり、BPPの外側にあるのではないかと考えられている。よって、Pの外側でもあると考えられている。もし、これらの問題がBPPの外側にあると証明されれば、量子計算機が古典計算機より強力である証拠となりえる。しかし、まだ証明されたわけではないので、量子計算機が古典計算機より強力であるという根拠はまだない。また両問題はNP完全問題ではないだろうと考えられている。
[編集] 参考文献
- [S94n] Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", In Proceeding of 35th IEEE FOCS, pp.124-134, Santa Fe, NM, Nov 20-22, 1994. (Shorのアルゴリズムの論文)
- [S97] Peter W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing, Vol.26, No.5, pp.1484-1509, Oct 1997. (ジャーナル版) http://arxiv.org/abs/quant-ph/9508027
- [G96] Lov K. Grover, "A fast quantum mechanical algorithm for database search", STOC'96, pp.212-219, Philadelphia, Pennsylvania, United States, May 22-24, 1996. (Groverのアルゴリズムの論文) http://arxiv.org/abs/quant-ph/9605043/
- [G00] Lov K. Grover, "Rapid sampling though quantum computing", STOC'00, pp.618-626, Portland, Oregon, United States, May 21-23, 2000. (Groverの新アルゴリズム) http://arxiv.org/abs/quant-ph/9912001/
[編集] 関連項目
