On the quantum computational complexity of the Ising spin glass partition function and of knot invariants
On the quantum computational complexity of the Ising spin glass partition function and of knot invariants
复制标题
关于伊辛自旋玻璃配分函数和结不变量的量子计算复杂性
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Daniel A. Lidar
中科院分区：
文献类型：
--
作者：
Daniel A. Lidar
它表明，经典统计热力学的正则问题，配分函数的计算，是在±J伊辛自旋玻璃的情况下，被称为二次符号重量计数器（QWGT）的某些简单和的一个特殊实例。另一方面，已知量子计算多项式等价于具有用于估计某些QWGT的预言的经典概率计算。这表明了自旋玻璃配分函数估计问题与量子计算之间的联系。这种联系通过考夫曼括号多项式和波茨模型的配分函数的等价性扩展到节点和图论。
It is shown that the canonical problem of classical statistical thermodynamics, the computation of the partition function, is in the case of ±J Ising spin glasses a particular instance of certain simple sums known as quadratically signed weight enumerators (QWGTs). On the other hand, it is known that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating certain QWGTs. This suggests a connection between the partition function estimation problem for spin glasses and quantum computation. This connection extends to knots and graph theory via the equivalence of the Kauffman bracket polynomial and the partition function for the Potts model.