| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-03-10 10:30 可換量子回路とイジング分配関数の計算複雑性 ○藤井啓祐（京大）・森前智行（群馬大）  COMP2013-63 |
|
| 抄録 | （和） | 可換量子演算のみから構成される量子計算，IQP（Instantaneous Quantum Polynomial time computation）は，その可換性にも関わらず，古典計算機では効率よくシミュレートできないことが最近示された．本研究では，IQPとイジング模型の分配関数の計算複雑性との対応を構築した．この対応を用いて，IQPとイジング模型分配関数の計算複雑性についていくつかの知見を紹介する． |
| （英） | Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal in the sense of standard quantum computation. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy (PH) collapses at the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of the partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable in the strong sense, by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising models with imaginary coupling constants. Specifically, we show that there is no fully polynomial randomized approximation scheme (FPRAS) for Ising models with almost all imaginary coupling constants even on a planar graph of a bounded degree, unless the PH collapses at the third level. Furthermore, we also show a multiplicative approximation of such a class of Ising partition functions is at least as hard as a multiplicative approximation for the output distribution of an arbitrary quantum circuit. | |
| キーワード | （和） | 量子計算 / イジング模型 / 分配関数 / / / / / |
| （英） | quantum computation / Ising model / partition function / / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 488, COMP2013-63, pp. 23-27, 2014年3月. | |
| 資料番号 | COMP2013-63 | |
| 発行日 | 2014-03-03 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-63 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-03-10 - 2014-03-10 |
| 開催地（和） | 明治大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-03-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 可換量子回路とイジング分配関数の計算複雑性 |
| サブタイトル（和） | |
| タイトル（英） | Quantum Commuting Circuits and Complexity of Ising Partition Functions |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 量子計算 / quantum computation |
| キーワード(2)（和/英） | イジング模型 / Ising model |
| キーワード(3)（和/英） | 分配関数 / partition function |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 藤井 啓祐 / Keisuke Fujii / フジイ ケイスケ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 森前 智行 / Tomoyuki Morimae / モリマエ トモユキ |
| 第2著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-03-10 10:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-63 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.488 |
| ページ範囲 | pp.23-27 |
| ページ数 | 5 |
| 発行日 | 2014-03-03 (COMP) |
[研究会発表申込システムのトップページに戻る]