复参数Ising与Tutte配分函数近似计算复杂性全面研究

本研究论文深入探讨了复值Ising和Tutte配分函数逼近计算的复杂性理论，由 LeslieAnn Goldberg 和 HengGuo 于2017年1月24日提出。Ising和Tutte配分函数在组合数学和统计物理学中具有重要意义，特别是在描述物理系统中的能量和关联性时，尤其是在考虑物理相变时，复数参数是必不可少的，因为这些相变通常对应于配分函数在复平面上的零点。 以往的研究主要集中在实参数版本上，而本文则首次扩展到复参数，试图全面理解这些配分函数逼近问题的复杂性。作者引入了组合参数，首次给出了关于复值Ising配分函数中带有复杂边缘相互作用的乘法和加法逼近的完整复杂性分类。在处理外场存在时，特别是在参数为单位根的情况下，研究提供了比之前更为详尽的二分法，强化了从BQP（量子可计算）难度提升到#P（组合难题）难度的结果。这标志着对这些特定问题理解的显著进步，因为之前此类分析仅限于少数几个特殊点。 论文还关注了Tutte多项式符号计算的复杂性，证明了在某些情况下它是#P-hard，与量子计算的模拟BQP相关联。通过这些分类，作者重新审视了量子计算与配分函数计算之间的联系，尽管得出的结论与现有量子文献中的观点有所不同，但研究路径相似，进一步深化了对这两个领域的交叉理解。 该研究得到了欧洲研究委员会和英国工程和物理科学研究理事会（EPSRC）的资助，展示了对这类问题的多维度探索和理论进展。通过本文，研究人员不仅推动了复杂性理论在经典计算中的边界，也为量子计算的理论基础提供了新的洞见。