TOP研究紹介 → 量子計算の紹介パネル 2004年度版


量子計算の研究紹介パネル 2004年度版


量子計算とは


未来のコンピュータ

コンピュータの誕生から今日までの約50年間、その計算速度は年を重ねるごとに高速になり、サイズは小型化されてきました。しかし、このような急速な進歩もついに限界に直面していると言われており、将来、コンピュータの更なるミクロ化を目指すのならば、まったく新しい計算理論に基づく新技術が必要となります。

そこで、1985年にD.Deutschが「量子チューリング機械」という新しい計算モデルを提案しました。この、量子チューリング機械をモデルとするコンピュータのことを「量子コンピュータ」と呼びます。量子コンピュータは未来のコンピュータと言われ、現在のコンピュータでは時間がかかりすぎて解けない問題を、高速に解くことができると考えられています。


量子計算の簡単な歴史


Turing 機械

チューリング機械は、図1に示すようにテープ、ヘッドと有限制御部から構成されています。おおまかに言うと、テープは現在のコンピュータのメモリ(記憶装置)に対応し、ヘッドはメモリへの読み書き装置、有限制御部はCPU(中央処理装置)に対応しています。

図1はチューリング機械のハードウェアを図示したものです。

図1:Turing 機械の図
図1:チューリング機械

一方、チューリング機械のソフトウェア(プログラム)は状態遷移関数と呼ばれる関数で指定され、図2のような表形式で表現されます。この表において、SとTが有限制御部の状態。0、1、Bはテープの各区画に記入できる記号。R、Nはヘッドの移動方向をそれぞれ表しています。ここでRは「ヘッドを1区画右に動かす」ことを、Nは「ヘッドを動かさない」ことをそれぞれ表しています。

図2:状態遷移関数
現在の状態 現在の記号 次の状態 新記号 移動方向
S 0 S 0 R
S 1 S 1 R
S B T 1 N

量子計算の仕組み

量子コンピュータのモデルとなっている量子チューリング機械は、 チューリング機械のテープの1区画に、0が書き込まれている状態 と、1が書き込まれている状態の「任意の重ね合わせ」を保持する ことができます。

図3:ビットの重ね合わせ
図3:ビットの重ね合わせ

量子並列化は量子力学の以下のような基本原理に基づいています。

今のコンピュータでは1bitで0または1の一方しか表現できません。しかし、 量子コンピュータでは1qubit(1量子bit、現在の1bitに対応)として、0と1の重 ね合わせ状態を扱うことができます。 例えば、1qubitどうしの足し算では

      0 + 0 = 0,  0 + 1 = 1
      1 + 0 = 1,  1 + 1 = 0

の4通りの計算を量子コンピュータは一度に行うことができます。上の例では2qubitなので4通りですが、100qubitでは2100 = 267650600228229401496703205376通りと爆発的に量子並列度が上がります。この事を用いて計算の高速化を図っています。


Shor のアルゴリズム

現在のコンピュータは因数分解に膨大な時間を必要とし、このことはRSA公開鍵暗号系の安全性の拠り所となっています。

しかし、1994年にP.W.Shorは量子チューリング機械上で、大きな整数の因数分解を小さな誤り確率で高速に行えることを示しました。これにより、もし量子コンピュータを実際に作ることができれば、インターネット上でのセキュリティを確保することができなくなります。具体的に、500桁の「因数分解」を解くときに費やす時間を比較してみると、現在のコンピュータでは1000万年かかるのに対し量子コンピュータでは数十秒で解けてしまいます。


Grover のアルゴリズム

Groverのアルゴリズムは有名な量子アルゴリズムの1つで、ソートされていないデータベースの中から所望の要素を高い確率で発見するために用いられます。例えば、10万個のデータからほしいデータを探し出すとき、平均5万回調べなくてはなりませんが、量子コンピュータでは1000回調べればほしいデータを発見することができます。また、このアルゴリズムは、本来の機能よりもその汎用性が注目されており、西野研究室でも最短ベクトル問題や衝突探索問題、グラフの同型性判定問題、また、暗号解読などに応用して研究を進めています。


研究テーマ


NMR量子計算

NMR量子計算とは?

しかし、通常の量子計算とは枠組みが違う!

西野研では、計算量理論の立場から

などについて研究を行っています。


NMR量子アルゴリズムのシミュレータ作成

NMR量子コンピュータ上で動作する、量子探索アルゴリズが提案されている。

そこで

  1. 量子ビット数を節約できる可能性のある、ある探索アルゴリズムに注目し、そのアルゴリズムを実装したシミュレータを作成する。
  2. Groverのアルゴリズムを用いて解く量子アルゴリズムの動作を、解析しやすいように通常のコンピュータを用いてミュレータを作成する。

研究をそれぞれ行い、アルゴリズムが実行される際の問題点を明らかにしていきたいと考えています。


量子ニューラルネットワーク

量子ニューラルネットワークとは?

図4:量子ニューラルネットワークの基本素子
図4:量子ニューラルネットワークの基本素子

西野研究室では、

に関して研究を行っています。


断熱量子計算

量子計算機の汎用機を作るのはとても難しい。

図5:断熱量子計算概念図
図5:断熱量子計算概念図

西野研では、

などについて研究しています。


量子論理回路の最適化

図6:量子回路の簡単化の例
図6:量子回路の簡単化の例

西野研では、

に関して研究を行っています。


量子計算と暗号解読

多くの暗号の安全性は、解読に非常に時間が掛かることに依存している。

量子計算で高速に解けると、安全性が揺らぐ!

西野研では、特に衝突問題と最短ベクトル探索問題に注目し て研究を行っています(太田・國廣研との共同研究)。


パーマネントの計算

2部グラフのマッチング問題とは

図7:2部グラフ
図7:2部グラフ


[研究内容のページに]


Valid HTML 4.01 Transitional