文献

J-GLOBAL ID：200902222646545662   整理番号：08A0514821

半直積群の同型性判定問題に対する量子アルゴリズム

Quantum Isomorphism Testing for Semidirect Product Groups

著者 (5件)： INUI Yoshifumi (Univ. Tokyo) ,  INUI Yoshifumi (JST-ERATO) ,  INUI Yoshifumi (JST-SORST) ,  LE GALL Francois (JST-ERATO) ,  LE GALL Francois (JST-SORST)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 108  号： 11(COMP2008 1-7)  ページ： 29-34  発行年： 2008年04月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフ同形問題に密接に関連している問題として,2つの任意の群が同形かどうかを問う群同形問題がある。本論文では,pおよびqが異なる素数であるとき,Z_s×Z_q(ただしs=p^r)の形をした半直積群のクラスを含む可解群クラスに対するこの問題を解く効率的量子アルゴリズムを与えた。提案アルゴリズムの実行時間は入力群の位数において多対数になる。(翻訳著者抄録)

シソーラス用語： *計算機アルゴリズム ,  *量子計算 ,  同形写像 ,  *グラフ ,  *群 ,  素数 ,  直積 ,  高速アルゴリズム ,  性能分析 ,  計算量 ,  *量子アルゴリズム
準シソーラス用語： *グラフ同形問題 ,  可解群 ,  *群同形問題 ,  半直積群

分類 (4件)： 計算理論  (JB02000A) ,  その他の計算機  (JC06020B) ,  グラフ理論基礎  (IA02020S) ,  システム・制御理論一般  (IA02010H)

引用文献 (26件)：

• AARONSON, S. Quantum versus classical proofs and advice. 22nd Complexity, 2007. 2007, 115-128
• ARVIND, V. Solvable group isomorphism is almost in NP∩co-NP. 19th Complexity, 2004. 2004, 91-103
• BABAI, L. Bounded round interactive proofs in finite groups. SIAM Journal of Discrete Mathematics. 1992, 5, 1, 88-111
• BABAI, L. Fast Monte Carlo algorithms for permutation groups. Journal of Computer and System Sciences. 1995, 50, 2, 296-307
• BABAI, L. On the complexity of matrix group problems. 25th FOCS, 1984. 1984, 229-240

タイトルに関連する用語 (3件)： 直積 ,  判定問題 ,  量子アルゴリズム