講演抄録/キーワード |
講演名 |
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 |