このアイテムのアクセス数: 9

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
1367-2630_aa5fdb.pdf2.15 MBAdobe PDF見る/開く
タイトル: Commuting quantum circuits and complexity of Ising partition functions
著者: Fujii, Keisuke
Morimae, Tomoyuki
著者名の別形: 藤井, 啓祐
キーワード: instantaneous quantum polynomial time computation
commuting quantum circuit
quantum supremacy
classical simulation
partition function
Ising model
quantum algorithm
発行日: 1-Mar-2017
出版者: IOP Publishing
誌名: New Journal of Physics
巻: 19
論文番号: 033003
抄録: Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to 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 calculating the imaginary-valued 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 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 partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
著作権等: ©2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft
Original content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI.
URI: http://hdl.handle.net/2433/226522
DOI(出版社版): 10.1088/1367-2630/aa5fdb
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。