巡回群の半直積群上の隠れ部分群問題に対する量子アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
素因数分解などいくつかの問題に対して量子アルゴリズムは既に知られている最良の古典的アルゴリズムよりも準指数的に速く解ける事が分かっている。そのような問題の多くはAbel群上の隠れ部分群問題と捉えて理解することが出来て、それは多項式時間量子アルゴリズムによって解けることが知られている。非Abel群上の隠れ部分群問題には重要な問題と関連のあるものもあるが、一般の群上の隠れ部分群問題に対する多項式時間アルゴリズムは知られていない。そこで本論文では格子内の最短ベクトルを求める問題と関連のある正二面体群を含む二つの巡回群の半直積群を考え、その内のあるクラスの群の隠れ部分群問題に対する多項式時間アルゴリズムを提案する。
- 社団法人電子情報通信学会の論文
- 2005-04-11
著者
-
ルガル フランソワ
科学技術振興機構ERATO-SORST量子情報システムアーキテクチャ
-
ルガル フランソワ
科学技術振興機構量子情報システムアーキテクチ
-
乾 義文
東京大学大学院情報理工科学系研究科
-
ルガル フランソワ
東京大学大学院情報理工学系研究科コンピュータ科学専攻
関連論文
- General scheme for perfect quantum network coding with free classical communication (コンピュテーション)
- 半直積群の同型性判定問題に対する量子アルゴリズム
- 量子分散コンピューティング(量子情報処理論文)
- 巡回群の半直積群上の隠れ部分群問題に対する量子アルゴリズム
- 巡回群の半直積群上の隠れ部分群問題に対する量子アルゴリズム
- Constructing quantum network coding schemes from classical nonlinear protocols (コンピュテーション)
- 机間指導の振り返りを支援するシステムの開発(若手フォーカス企画/一般)
- 机間指導の振り返りを支援するシステムの開発