量子コンピューティング

計算機:The Next Generation

因数分解に対する量子アルゴリズム

 P. Shor は、整数の因数分解を小さな誤り確率で高速に行う量子アルゴリズムを提案しました。現在のコンピュータは因数分解に膨大な時間を必要とし、このことはRSA公開鍵暗号系の安全性の拠り所になっています。
 私たちは、既存のコンピュータ上で可能な限りシミュレーションを行なうことにより、Shorのアルゴリズムの振舞いや種々の性質を明らかにすることを目指しています。

非線形量子計算の模倣

非線形量子計算の模倣  D.S.AbramsとS.Lloydは非線形量子力学の効果を使い、難しいと考えられているNP完全問題を効率的に解くためのアルゴリズム(ALアルゴリズム)を示しました。私たちはこのアルゴリズムをTuring機械で模倣できることを示しましたが、量子Turing機械はTuring機械を効率的に模倣できるので、線形領域の量子Turing機械を用いてある種の非線形効果を模倣できることがわかりました。
  ただし、量子Turing機械を使用した模倣では、ALアルゴリズムよりも大きな領域が必要となります。

NMR量子計算

 NMR装置は原子一つ一つのエネルギーを測定する装置です。NMR量子計算では、0と1を分子の回転の向きに対応させて、量子ビットを構成します。現在までに5 qubit NMR量子計算の実験が成功しています。私たちは、計算量理論の立場からNMR量子計算の理論の構築を行なっています。

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

Groverのアルゴリズムの応用

 Groverのアルゴリズムは有名な量子アルゴリズムの1つで、ソートされていないデータベースの中から所望の要素を高い確率で発見するために用いられます。
 概念的な動作原理は以下の図のように示されます。

Grover のアルゴリズム初期状態
全ての状態が
等しい振幅を
持つように初期化

反転
所望の状態の
振幅を反転

折り返し
振幅の平均について折り返し演算を行うと所望の状態を発見する確率が高くなる

Groverのアルゴリズムは本来の機能よりも、その汎用性が注目されており、西野研究室でも以下の問題への応用を研究しています。

グラフの同型性判定問題

右図は2つの同型なグラフを示しています。2つのグラフΓ1とΓ2が同型か否かを判定するのがグラフの同型性判定問題です

最短ベクトル探索問題
  最短ベクトル探索問題とは、n本の基底ベクトルを与えられ、それらを整数倍して足し合わせて得られるベクトルのうち、最短のベクトルを求める問題です。

衝突問題

  写像先が同じ要素となる組(collision)を探索する問題です。

衝突問題

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

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


Valid HTML 4.01!