量子コンピュータ
量子コンピュータ （りょうし-） は、量子力学的な重ねあわせを用いて並列性を実現する次世代のコンピュータ。2008年現在、実用化には至っていない。量子計算機とも言う。
目次 |
[編集] 概要
従来の計算機（量子計算機に対して、古典計算機という）は1ビットにつき、0か1の何らかの値しか持ち得ないのに対して、量子計算機では量子ビット（qubit）により、1ビットにつき0と1の値を任意の割合で重ね合わせて保持することが可能である。 この量子ビットを複数利用して、量子計算機は古典計算機では実現し得ない超並列処理を実現している。
量子計算機の歴史は、1982年にベニオフが量子系においてエネルギーを消費せず計算が行えることを示したことに端を発し、同年、ファインマンも量子計算が古典計算に対し指数関数的に有効ではないかと推測している。これらに続き、ドイッチュによって、量子計算機の原モデルである量子チューリングマシンが定義されるなど量子計算の分野に関する研究が進められていた。 しかし、数年が経つと、量子的重ね合わせによる並列性を効率的に活用する手法が発見できなかったり、量子計算機自体の開発の困難性が明らかになり、一時的に量子計算機に関する研究は下火になった。 この状況を打破するきっかけになったのが、1994年にショアによって考案されたいわゆる、Shorのアルゴリズムである。 Shorのアルゴリズムは量子計算機特有のアルゴリズムであり、古典計算機では現実的な時間で解くことができないと予想されている素因数分解を、量子計算において極めて短い時間で解決することが出来ることが示されている。 このため、量子計算機が実現されれば、素因数分解の困難性を利用したRSA暗号の安全性が崩れることになる。
実験的には、超伝導素子、非線形光学、レーザー冷却、量子ドット、核磁気共鳴などによる実現法が研究されている。
理論上、現在の最速スーパーコンピュータで数千年かかる計算を数十秒でこなすことが出来るといわれる。
従来型のノイマン型コンピュータはプログラムによってどのような計算でも実行できる汎用計算機であるのに対し、現時点での量子コンピュータは、特定のアルゴリズムを超高速に処理する専用計算機や、古典計算機を補助するコプロセッサとして考察されている。
[編集] 計算能力
A. D. バーンスタインとU. ヴァジラニは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、古典コンピュータで原理的に解くことができない問題は量子コンピュータにも解くことはできない。
量子コンピュータは古典コンピュータを容易にシミュレートすることが可能であるため、古典的なコンピュータで速く解ける問題は、量子コンピュータにも速く解くことができる。よって、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、「より大きい」計算速度を持つのかどうか（量子コンピュータにしか速く解けない問題が存在するのかどうか）は、現在のところ証明されていない。 Shorのアルゴリズムにより、NP問題（検算はすぐにできるが、解くのに時間がかかる問題）である素因数分解を素早く解くことができるため、例えば素因数分解問題が古典コンピュータで解けないということを示せば量子コンピュータは古典コンピュータより強力であることになる。
[編集] アルゴリズム
2008年現在で量子計算機特有のアルゴリズムがいくつか知られており、代表的なものは以下の二つである。
[編集] 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/
