期刊
NEW JOURNAL OF PHYSICS
卷 19, 期 -, 页码 -出版社
IOP PUBLISHING LTD
DOI: 10.1088/1367-2630/aa5fdb
关键词
instantaneous quantum polynomial time computation; commuting quantum circuit; quantum supremacy; classical simulation; partition function; Ising model; quantum algorithm
资金
- JSPS [25887034, KAKENHI 26730003]
- Tenure Track System by MEXT Japan [26730003]
- Grants-in-Aid for Scientific Research [16H02211, 25887034] Funding Source: KAKEN
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据