著者

川崎 涼 西村 治道

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09135685)

巻号頁・発行日

vol.2014, no.12, pp.1-8, 2014-06-06

---

Gharibian, Kempe [ICALP2012] は局所ハミルトニアンの冗長性に関する問題 QIRR を導入した.この問題は,局所ハミルトニアンの和が与えられたときにエネルギー期待値の条件を満たした部分和が存在するかを問う問題である.彼らはこの問題が cq-Σp2 困難であることを証明したが,その完全性を示すことはなかった.本論文ではまず,局所ハミルトニアンに関する計算複雑さの高い問題から QIRR への帰着を与え,QIRR が cq-Σp2 に属さない証拠を与える.その後,より適切な形で局所ハミルトニアンの冗長性に関する問題を定義し,再定式化した問題が cq-Σp2 完全であることを示す.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-Σp2(a quantum analogue of Σp2 ), while they did not show cq-Σp2-completeness. In this paper we first show that QIRR is reduced from some problem that seems too hard to show cq-Σp2-completeness. Then, we introduce another problem on irredundancy of local Hamiltonians in a more suitable form, and show that the problem is cq-Σp2-complete.