量子コンピューティング

計算機:The Next Generation

量子コンピュータとは

 量子コンピュータとは、現在のコンピュータに量子力学的動作原理を導入した新しい仕組みのコンピュータです。
  量子コンピュータが実現すれば、現在のコンピュータでは時間がかかりすぎて解けない問題を、高速に解くことができると考えられています。
  西野研では、Shorの因数分解アルゴリズム、Groverのデータベース検索アルゴリズム、非線形量子計算、NMR量子計算などの研究を、理論計算機科学の側面からおこなっています。

情報通信工学科
西野研究室

量子計算の簡単な歴史

1985 D.Deutsch が量子Turing機械を提唱。
1993 E.Bernstein and U.Vazirani が
     効率的な万能量子 Turing 機械を構成。
1994 P.W.Shor が因数分解の誤り限定多項式
    時間量子アルゴリズムを発見。
1996 L.K.Grover がデータベース
     検索アルゴリズムを発見。

Turing 機械

  現在の計算機の数学的モデルはA.Turingが提唱したTuring機械です(右図参照)。テープは記憶装置にあたり、区画分けされた各領域には記号をひとつ書くことができます。ヘッドはこの記号を読み書きします。
  Turing機械は状態遷移関数に従って動作します。有限制御部は状態を保持し、動作の各ステップにおいて、現在の状態とヘッドが読んでいる記号に応じてテープのヘッド位置の記号を書き換え、現在の状態を変更し、ヘッドを右または左に1区画移動します。
  右表はテープ上の二進数に1を足Turing機械の状態遷移関数です。初期状態はq で、最終状態q になると停止します。Bは空白記号です。

Turing machine

現在の状態 現在の記号 書き込む記号 次の状態 ヘッドの移動方向
q0
0
0
q0
R
q0
1
1
q0
R
q0
B
B
q1
L
q1
0
1
qF
L
q1
1
0
q1
L
q1
B
1
qF
L
量子計算のしくみ

 量子並列化は量子力学の以下のような基本原理に基づいています。
  ・重ね合わせの原理
  ・状態のユニタリ時間発展
  ・確率解釈
 今までのコンピュータでは1bitで0または1の一方しか表現できませんでしたが、量子コンピュータでは1qubit(1量子bit、現在の1bitに対応)として0と1の重ね合わせ状態を扱うことができます。

たとえば1qubitどうしの足し算では

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

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

http://www.tnlab.ice.uec.ac.jp/


[研究内容紹介 に戻る] [TOP に戻る]


Valid HTML 4.01!