前のページ 1/1 次のページ

量子コンピュータ (りょうし-) は、量子力学的な重ねあわせを用いて並列性を実現する次世代のコンピュータ。年現在、実用的なレベルでの実現には至っていない。量子計算機とも言う。

◆概要

従来の計算機(量子計算機に対して、古典計算機という)は1ビットにつき、0か1の何らかの値しか持ち得ないのに対して、量子計算機では量子ビット(qubit)により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。

この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない超並列処理を実現する。

量子計算機の歴史は、1982年にベニオフが量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、同年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、ドイッチュによって、量子計算機の原モデルである量子チューリングマシンが定義されるなど量子計算の分野に関する研究が進められていた。

しかし、数年が経つと、量子的重ね合わせによる並列性を効率的に活用する手法が発見できなかったり、量子計算機自体の開発の困難性が明らかになり、一時的に量子計算機に関する研究は下火になった。

この状況を打破するきっかけになったのが、1994年にショアによって考案されたいわゆる、Shorのアルゴリズムである。

Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機では現実的な時間で解くことができないと予想されている素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。

このため、実用的な量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。

実験的には、超伝導素子、非線形光学、レーザー冷却、量子ドット、核磁気共鳴などによる実現法が研究されている。

理論上、現在の最速スーパーコンピュータで数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができるといわれる。

従来型のノイマン型コンピュータはプログラムによってどのような計算でも実行できる汎用計算機であるのに対し、現時点での量子コンピュータは、特定のアルゴリズムを超高速に処理する専用計算機や、古典計算機を補助するコプロセッサとして考察されている。

◆計算能力

A. D. バーンスタインとU. ヴァジラニは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、古典コンピュータで原理的に解くことができない問題は量子コンピュータにも解くことはできない。

量子コンピュータは古典コンピュータを容易にシミュレートすることが可能であるため、古典的なコンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、「より大きい」計算速度を持つのかどうか(量子コンピュータにしか速く解けない問題が存在するのかどうか)は、P≠NP予想という、現在のところ証明されていない予想に依存する。

Shorのアルゴリズムにより、NP問題(検算はすぐにできるが、解くのに時間がかかる問題)である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータに多項式時間で解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。

◆ アルゴリズム

年現在で量子計算機特有のアルゴリズムがいくつか知られており、代表的なものは以下の二つである。

◇ Shorのアルゴリズム

素因数分解問題を高速に(多項式時間で)解くことができるアルゴリズム。

古典計算機では非現実的な時間(準指数時間)で解くアルゴリズムしか知られていない。

少し改造することで離散対数問題(DLP,ElGamal暗号や楕円曲線暗号の安全性の根拠)も多項式時間で解くことができる。

2001年12月にIBMアルマデン研究所にて7qubitの量子計算機で15(=3*5)の素因数分解に成功したことが発表された(Nature,12月20日発行号)。

このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、

これをさらに非可換隠れ部分群問題に拡張する研究が進展している。

◇ Groverのアルゴリズム

$n$個のデータの中から、ある特定のデータを$\backslash sqrt\; n$ステップで取得することができるアルゴリズム。古典計算機ではおよそ$n/2$ステップが必要である。

1996年にグローバーが発表した([外部リンク]G96)。

きわめて広範な種類の

確率的アルゴリズムや量子アルゴリズムと組み合わせて、計算時間をその平方根まで

落とすことができる。Shorのアルゴリズムほどその効果は劇的ではないが、

広い応用をもつことが特徴である。

検索条件や検索対象について改良されている。

◆NMR量子コンピュータ

近年、NMR(例:[外部リンク]http://www.jrc.kindai.ac.jp/jp/souchi/souchi_index.html)を用いた量子コンピュータの研究開発が行われている。[外部リンク]http://www.px.tsukuba.ac.jp/home/tcm/kyoshida/winter2004/Nakahara.pdf

関西では、京都大学、大阪市立大学や、近畿大学に設立された量子コンピューター研究センター[外部リンク]http://alice.math.kindai.ac.jp/orc-j.htmlなどで盛んに研究が行われている。

◆参考文献

・ [外部リンク]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/

◆関連項目

・量子ビット

・ 量子状態

・ 量子もつれ

・ 量子テレポーテーション

・ アインシュタイン=ポドルスキー=ローゼンのパラドックス

・量子暗号

・NMR

前のページ 1/1 次のページ

・量子コンピュータ page1