论文标题
近似复杂值POTTS模型的复杂性
The complexity of approximating the complex-valued Potts model
论文作者
论文摘要
我们研究了$ q $ - 州Potts模型的分区功能和与基础参数复杂值密切相关的Tutte多项式的复杂性。除了与统计物理学中的量子计算和相变的经典连接外，最近的近似计数中的工作表明，复杂平面中的行为以及更精确的零位置与近似问题的复杂性（即使是正面实价参数）也密切相关。 Goldberg和Guo在复杂飞机上的先前工作重点是$ Q = 2 $，这与Ising模型相对应。对于$ q> 2 $，复杂平面中的行为尚未充分理解，大多数工作仅适用于实值的Tutte平面。 我们的主要结果是通过建立\＃p-hardness结果，即使限制在平面图时，都可以完全分类参数的所有非现实值的近似问题的复杂性。我们的技术适用于所有$ Q \ geq 2 $，并进一步补充/完善了Ising模型和Tutte平面的先前结果，特别是在量子计算的背景下，Bordewich，Freedman，Lovász和Welsh提出的一个问题。
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ász and Welsh in the context of quantum computations.
