電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2014-06-14 09:25
局所ハミルトニアンの非冗長性の計算量
川崎 涼・○西村治道名大
技報オンラインサービス実施中
抄録 (和) Gharibian, Kempe [ICALP2012] は局所ハミルトニアンの冗長性に関する問題QIRRを導入した. この問題は,局所ハミルトニアンの和が与えられたときにエネルギー期待値の条件を満たした部分和が存在するかを問う問題である. 彼らはこの問題がcq-Sigma_2^p困難であることを証明したが,その完全性を示すことはなかった. 本論文ではまず,局所ハミルトニアンに関する計算複雑さの高い問題からQIRRへの帰着を与え,QIRRがcq-Sigma_2^pに属さない証拠を与える. その後,より適切な形で局所ハミルトニアンの冗長性に関する問題を定義し,再定式化した問題がcq-Sigma_2^p完全であることを示す. 
(英) Gharibian and Kempe [ICALP2012] introduced a problem on irredundancy of local Hamiltonians, named as QIRR, which asks whether, given a sum of local Hamilitonians, there is a partial sum preserving a given energy constraint. They showed that QIRR is hard for the class cq-Sigma_2^p (a quantum analogue of Sigma_2^p), while they did not show cq-Sigma_2^p-completeness. In this paper we first show that QIRR is reduced from some problem that seems too hard to show cq-Sigma_2^p-completeness. Then, we introduce another problem on irredundancy of local Hamiltonians in a more suitable form, and show that the problem is cq-Sigma_2^p-complete.
キーワード (和) 量子計算量理論 / 量子多項式階層 / 局所ハミルトニアン / / / / /  
(英) quantum computational complexity / quantum polynomial hierarchy / local Hamiltonian / / / / /  
文献情報 信学技報, vol. 114, no. 80, COMP2014-11, pp. 69-76, 2014年6月.
資料番号 COMP2014-11 
発行日 2014-06-06 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 COMP IPSJ-AL  
開催期間 2014-06-13 - 2014-06-14 
開催地(和) 道後温泉(愛媛県松山市) 
開催地(英) Matsuyama, Ehime 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2014-06-COMP-AL 
本文の言語 日本語 
タイトル(和) 局所ハミルトニアンの非冗長性の計算量 
サブタイトル(和)  
タイトル(英) Computational Complexity of Irredundancy of Local Hamiltonian 
サブタイトル(英)  
キーワード(1)(和/英) 量子計算量理論 / quantum computational complexity  
キーワード(2)(和/英) 量子多項式階層 / quantum polynomial hierarchy  
キーワード(3)(和/英) 局所ハミルトニアン / local Hamiltonian  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 川崎 涼 / Ryo Kawasaki / カワサキ リョウ
第1著者 所属(和/英) 名古屋大学 (略称: 名大)
Nagoya University (略称: Nagoya Univ.)
第2著者 氏名(和/英/ヨミ) 西村 治道 / Harumichi Nishimura / ニシムラ ハルミチ
第2著者 所属(和/英) 名古屋大学 (略称: 名大)
Nagoya University (略称: Nagoya Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2014-06-14 09:25:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2014-11 
巻番号(vol) IEICE-114 
号番号(no) no.80 
ページ範囲 pp.69-76 
ページ数 IEICE-8 
発行日 IEICE-COMP-2014-06-06 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会