講演抄録/キーワード |
講演名 |
2014-06-14 09:25
局所ハミルトニアンの非冗長性の計算量 川崎 涼・○西村治道(名大) COMP2014-11 |
抄録 |
(和) |
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 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-11 |