We study the complexity of approximating the partition function of the $q$-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on $q=2$, which corresponds to the case of the Ising model; for $q>2$, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing \#P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all $q\geq 2$ and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lov\'{a}sz and Welsh in the context of quantum computations.


翻译:我们研究了近似美元-州波茨模型分割功能的复杂程度,以及与基本参数的复杂值密切相关的图特多元分子值。除了与量子计算和统计物理阶段过渡的古老联系外,最近的近似计算工作表明,复杂平面的行为,更确切地说零的位置,与近似问题的复杂性密切相关,即使是对正实际价值参数也是如此。戈德贝格和古奥以往在复杂平面上的工作重点是$=2美元,这与Ising模型的情况相对应;对于$>2美元,复杂平面上的行为不那么容易理解,而且大部分工作只适用于实际价值的图特平面。我们的主要结果是对参数所有非真实值的近似问题的复杂性进行彻底分类,确定“P-硬度”结果,即使局限于平面图示时也适用。我们的技术适用于所有$\ge2美元,进一步补充/补充了以前在Ising模型和图特平面上的结果,对于实际价值的图特平面的行为则不甚为理解,而且大部分工作仅适用于实际价值的图特平面。我们的主要结果是对参数所有非实际值的精确值问题作了完整分类,由Berdez 和Freez的计算,在Berdz 和Servicesa 上提出了一个特定的答案。

1
下载
关闭预览

相关内容

【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员