量子コンピュータ
出典: フリー百科事典『ウィキペディア（Wikipedia）』
量子コンピュータ （りょうし-） は、量子力学的な重ねあわせを用いて並列性を実現するコンピュータ。量子計算機。
目次 |
[編集] 概要
従来の計算機（量子計算機に対して、古典計算機という）は1ビットにつき、0か1の何らかの値しか持ち得ないのに対して、量子計算機では量子ビット（qubit）により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。 この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない並列性を実現している。
量子計算機の歴史は、1982年にベニオフが量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、同年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、ドイチュによって、量子計算機の原モデルである量子チューリングマシンが定義されるなど量子計算の分野に関する研究が進められていた。 しかし、数年が経つと、量子的重ね合わせによる並列性を効率的に活用する手法が発見できなかったり、量子計算機自体の開発の困難性が明らかになり、一時的に量子計算機に関する研究は下火になった。 この状況を打破するきっかけになったのが、1994年にショアによって考案された所謂、Shorのアルゴリズムである。 Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機で現実的な時間で解くことの出来ないとされる素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。 このため、量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。
実験的には、非線形光学、レーザー冷却、量子ドット、核磁気共鳴などによる実現法が研究されている。
[編集] アルゴリズム
2007年現在で量子計算機特有のアルゴリズムがいくつか知られており、代表的なものは以下の二つである。
[編集] Shorのアルゴリズム
素因数分解問題を高速に（多項式時間で）解く事ができるアルゴリズム。 古典計算機では非現実的な時間（準指数時間）で解くアルゴリズムしか知られていない。 少し改造することで離散対数問題も多項式時間で解く事ができる。 2001年12月にIBMアルマデン研究所にて7qubitの量子計算機で15(=3*5)の素因数分解に成功したことが発表された（Nature,12月20日発行号）。 このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、 これをさらに非可換隠れ部分群問題に拡張する研究が進展している。
[編集] Groverのアルゴリズム
n個のデータの中から、ある特定のデータを
ステップで取得することが出来るアルゴリズム。古典計算機では凡そn / 2ステップが必要である。 1996年にGroverが発表した(\[G96\])。 きわめて広範な種類の 確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで 落とすことができる。Shorのアルゴリズムほどその効果は劇的ではないが、 広い応用をもつことが特徴である。 検索条件や検索対象について改良されている。
[編集] 参考文献
- [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/
[編集] 関連項目
カテゴリ: コンピュータアーキテクチャ | 量子力学 | スーパーコンピュータ
