研究复值Ising和Tutte配分函数逼近的复杂性

1复值Ising和Tutte配分函数逼近的复杂性Leslie Ann Goldberg<$HengGuo2017年1月24摘要研究了复参数Ising和Tutte配分函数近似计算的复杂性.我们的结果的部分动机的量子复杂性类BQP和IQP的研究。最近的结果显示了如何将量子计算编码为经典配分函数的评估这些结果依赖于有趣的和深入的结果量子计算，以获得硬度结果的困难（经典）评估某些固定参数的配分函数。本文的动机是更全面地研究（经典）逼近的复杂性Partition函数本质上是组合的，量化它们的近似复杂性不需要对量子计算有详细的了解。使用组合参数，我们给出了第一个完整的分类的复杂性乘法逼近的范数和加法逼近的参数的伊辛配分函数复杂的边缘相互作用（以及近似的配分函数根据一个自然的复杂的度量）。我们还研究了在外场存在下的范数逼近问题，当参数是单位根时，我们给出了一个完全的二分法以前的结果是已知的只有几个这样的点，我们加强这些结果从BQP-硬度到#P-硬度。此外，我们表明，计算的Tutte多项式的符号是#P-硬在某些点相关的模拟BQP。使用我们的分类，我们重新审视了量子计算的联系，得出的结论与量子文献中的结论略有不同（也无法比拟），但沿着相似的路线。1介绍我们研究了Ising和Tutte配分函数，这是著名的配分函数，在组合数学和统计物理学（见，例如，[26]）。早期研究（精确）评估这些配分函数的复杂性的工作[17]考虑了实参数和复参数。在统计力学中的应用实际上需要考虑复数，因为物理相变的可能点正好发生在这些配分函数的复零点的实极限点上（参见Sokal[26]）。然而，由于很难完全解决逼近问题的复杂性，大多数全面研究复杂性的工作，导致这些结果的研究已获得欧洲研究委员会根据欧盟第七框架计划（FP 7/2007-2013）ERC赠款协议编号的资助三三四八二八。本文仅反映作者欧洲联盟对可能使用其中所载信息的任何行为概不负责†英国牛津大学计算机科学系英国伦敦大学玛丽皇后学院数学科学学院，地址：Mile End Road，London E1 4NS，United Kingdom。部分工作是在HGHG还得到EPSRC赠款EP/N 004221/1的支持。arXiv：1409.5627v4 [cs.CC] 2017年1月2−−±近似评估这些配分函数[13，15，18]限制了对实际参数的关注一个显着的反例是文件Bordewich等人。[4]研究了包括这些配分函数的#PBordewich等人受到Freedman等人[9]的结果的启发，该结果表明与特定复参数（单位的5次方根）相关的琼斯多项式的近似计算可以用于模拟量子复杂性类BQP中任何算法的量子部分，BQP是量子计算机在多项式时间内可解决的一类决策问题，具有有限误差。这个结果与我们研究的配分函数的相关性来自Thistlethwaite [27]的结果，表明Jones多项式本质上是Tutte配分函数的特殊化。最近，有几篇论文展示了如何将量子计算编码为配分函数的评估。这些结果依赖于有趣的和深入的结果量子计算获得硬度结果的困难（经典）评估伊辛和Tutte配分函数。例如，Kuperberg [20]使用量子计算中的三个结果（[10]中的密度定理，Solovay-Kitaev定理（见[22]）和PostBQP =PP[1]）来证明琼斯多项式的某种近似的#P他的定理后来被重复为定理36，在那里它被更详细地讨论。他还得出有关结果乘法近似的Tutte多项式的某些真正的参数。IQP代表“瞬时量子多项式时间”。它的特征是由Shepherd和Bremner引入的一类量子电路[25]。 Fujii和Morimae [11]展示了如何将IQP电路编码为Ising模型的实例。因此，他们能够使用Bremner等人的量子复杂性结果。[5，推论3.3]（显示弱模拟具有乘法误差的IQP意味着多项式层次崩溃到第三级）来获得关于伊辛模型近似的结果-即参数y=exp（iπ/ 8）的伊辛模型的FPRAS将类似地导致多项式层次的崩溃。（作为他们提到，类似的结果适用于IQP通用的其他参数。）这一结果将在第4.1节中进一步讨论。 其他例子包括[8，结果2]，[16，定理6.1]和[21，定理2和3]，它们给出了某些伊辛模型近似的BQP-硬度，使得能够得出这样的结论，即用于近似这些配分函数的某些有效算法不太可能存在。 Ilblisder等人[16]指出，有些情况下，他们很难证明有乘法近似，由于Jerrum和Sinclair [18]，强调加法近似和乘法近似的区别。Matsuo等人[21，定理4]还将IQP电路的模拟与具有实参数的伊辛模型近似相我们的论文的动机是更全面地研究在复参数下逼近伊辛配分函数的复杂性，也可以反过来，从组合模型到量子计算。配分函数在本质上是组合的，并且对近似这些配分函数的困难进行分类不应该要求对量子力学或量子计算的详细理解。 因此，我们进行了详细的分类的复杂性的分区函数的问题，使用- ING组合方法。我们主要关注伊辛模型，因为这个模型在统计物理学中特别相关（第3节）。该模型也与IQP相关（如第4.1节所述）。我们还考虑了在任意点（x，y）的更一般的Tutte多项式，其中x=t且y=t−1，对于单位根t（这与BQP有关，将在第5节中解释）。我们的主要结果为伊辛模型（定理1）是一个分类的复杂性近似的配分函数与复杂的边缘相互作用。这一结果如图1.3所示。如图所示，在复平面中只有很少的参数（边缘相互作用）可以处理近似问题对于大多数边的相互作用，这是非常棘手的（#P-难以在任何常数因子内近似范数，π/3内的参数定理2将这些结果推广到一个更宽松的设置，其中近似算法是无约束的（允许输出任何有理数），如果correct输出为零。我们强调，我们的工作的目标是分类的复杂平面中的所有固定参数我们的定理的证明是初等的和组合的。其主要思想（见引理15）是一个二分法的扩展，3/- −Goldberg和Jerrum [15]展示了如何使用函数范数的近似来非常接近函数的零点。我们对Tutte多项式（4）的结果也用二分法证明了。它表明，对于任何相关参数，确定多项式的符号是非负还是非正是#P-困难的（当它为零时允许任意答案）。使用我们的分类，然后我们重新审视量子计算的联系，得出与前面提到的论文中的结论略有不同（并且无法比较）的结论，但沿着类似的路线，正如我们现在解释的那样。定理3表明，在任何常数因子内，IQP的强模拟都是P-困难的，即使对于Bremner等人[5]考虑的限制类电路也是如此我们的结果与他们的硬度结果[5，推论3.3]是不可比较的。这两个结果都表明乘法近似的困难然而，他们的结果是弱仿真（从电路的输出分布采样），而我们的是强仿真（估计给定输出的概率一般情况下，弱模拟的硬度结果更令人满意，但乘法近似不太适合弱模拟，其中总变化距离更重要。此外，我们的结果（与[5]的结果不同）对正确值为零时算法的行为不敏感此外，我们的复杂性假设（FP=#P）隐含在他们的假设（多项式层次不会塌缩到第三层）中，因此比他们的假设温和这些结果在第4.1节中进一步讨论。似乎通过玻色子采样也可以获得类似于我们的IQP结果的结果[2]。特别地，Aaronson和Arkhipov [2，定理4.3]使用了类似于Goldberg和Jerrum [15]的二分法来证明在常数因子内近似实值输入矩阵的积和式的平方是#P-困难的。任何这样的输入[2，引理4.4]都可以变成酉矩阵，其可以被视为玻色子采样问题的输出本质上是矩阵的积和的平方（所以很难近似）。此外，玻色子采样问题可以用BQP电路和自适应IQP电路（强意义上）来模拟。因此，虽然有趣的是，我们的伊辛模型的结果有IQP的应用，重要的一点是关于我们的结果是伊辛复杂性的综合分类，而不是特定的量子应用。正如我们在1.5.2节中所解释的，复杂性类BQP的经典模拟与确定Tutte多项式在某个点（t，t−1）的符号有关（但不是直接的结果）。定理4表明这个问题是#P-困难的（即使算法不需要处理输出为零的情况），回答了Bordewich等人提出的问题。这与Kuperberg[20]的一个结果（定理36）这些结果将在第5节中进一步讨论。最后，我们研究了外场作用下的伊辛模型De las Cuevas等人[8，结果2]表明，当边相互作用i和外场eiπ/4时，配分函数的另一个近似是BQP-困难的。出于这样的连接，我们专注于问题的（乘法）近似的规范的配分函数的相互作用参数和外部字段的根的单位。我们扩展我们的硬度结果表明，对于大多数这样的参数，包括De las Cuevas等人研究的参数，近似问题是P-困难的（关于精确的陈述，见定理6）。对于其余的参数，配分函数可以在多项式时间内精确地计算，因此我们得到一个完全的二分法（定理6）。这种扩展依赖于超越数论的一些下界，它允许我们将加法距离转换为乘法距离。下限结果在6.1节中给出，我们的硬度结果在6.2节中给出。正如我们已经提到的，有许多论文将量子模拟编码为伊辛模型，特别是Fujii和Morimae的结果[11]。我们可以使用这种编码（以及我们的定理2）来推导我们的量子应用（定理3）。为了使论文自成一体，并使读者能够从量子计算领域之外访问它，我们给出了我们自己的，更组合的，如何将IQP电路编码为Ising实例的演示。这在第4.1节中给出。4Σ^^^∈^^1.1Ising模型我们研究的主要配分函数是伊辛模型的配分函数。设y（称为边缘相互作用）和λ（称为外场）是两个参数。对于（多）图G=（V，E），划分函数被定义为ZIsing（G;y，λ）=σ：V→{0， 1}ym（σ）λn1（σ），（1）其中m（σ）是在σ下的单色边的数目（即，满足σ（u）=σ（v）的边（u，v）的数目），并且n1（σ）是满足σ（v）=1的顶点v我们写ZIsing（G;y）来表示ZIsing（G;y，1）。我们将考虑来自代数数集合Q的复参数y和λ。因此，y和λ的实部和虚部将是代数的。 我们使用arg（z）来表示复数z。对于固定的y和λ，我们研究了几个计算问题。第一个问题是在因子K > 1内逼近ZIsing（G;y，λ）的 范 数。名字FACTOR-K-N ISING（y，λ）.实例A（多）图G.输出一个有理数nberN，满足N/K≤|ZIsin g（G;y，λ）|≤KN。我们还考虑了在ρ（0，2π）的加性距离内近似配分函数的辐角的问题。在这里，我们必须把零的情况例外，因为参数是未定义的。名称 距离-ρ -ARG ISING（y，λ）。实例A（多）图G.如果ZIsing（G; y，λ）= 0，则0。否则，一个有理数A使得|≤ρ。|≤ ρ.当参数λ等于1时，我们丢弃参数λ，因此FACTOR-K-N ISING（y）表示概率，LemFactor-K-N_RG_LSING（y，1）和DISTANCE-ρ-A_RG_LSING（y）表示DISTANCE-ρ-A_RG_LSING（y，1）。1.2近似复数我们相对地近似复数的范数，而我们相加地近似自变量，这是有意义的这是很自然的，因为复数相乘会乘以范数并增加参数，所以它保留了通常的性质，即如果你可以近似两个数字，你就可以近似乘积。其他的近似概念也被提出。最值得注意的是，Ziv [29]提出两个复数y和y′之间的距离应该测量为d（y′，y）= |y′ − y|、最大的）|y′|、|y|）其中d（0， 0）= 0。我们还研究了以下近似问题。5−−∞ −∞R≥∈221IM{y}我−110Re{y}−i图1：定理1对于因子-K-N-SING（y）的说明。五个白点对应于第1项中描述的简单评估。绿色线段（1，）对应于RP中近似的区域-参见第2项。蓝色线段（，1）对应于近似等于近似计数完美匹配的区域。见第4项。轴（虚轴和线段（1， 0））和单位圆上的红点对应于近似为#P-困难的区域。见第5、6和7项。在其他地方，这些点是灰色的，并且已知近似是NP-难的（第3、9和10项），有时是#P-难的（第8项，未图示）。名称 复APX-ISING（y，λ）。例如一个（多）图G和一个正整数R，在一元。输出If|ZIsin g（G;y，λ）|=0，则算法应输出0。否则，它应该输出一个复数y，使得d（y，ZIsing（G; y，λ））≤。与其他问题一样，我们使用符号CCOMPLEX APX-ISING（y）来表示CCOMPLEX APX- ISING（y，1）。 我们将误差R指定为问题的输入，而不是参数为了强调复APX-ISING（y，λ）作为y为复时Ising配分函数的近似的适当概念的适用性。数R用一元表示，因此复Apx-ISING（y，λ）的多项式时间算法将给出所谓的对于配分函数，众所周知，在一元输入R中的逆多项式的因子内逼近范数等价于难以逼近具有任何特定因子K>1的范数。我们将在后面的引理11中回到这一点。1.3Ising模型的主要结果下面的定理给出了我们关于伊辛模型的主要复杂性结果。这些结果分类的问题近似的配分函数在整个复杂的平面。对于参数y的每一个值，我们要么证明这个问题很容易，因为配分函数的范数和arg都可以很好地近似（使用Ziv距离的聚集问题也是如此），要么证明近似至少一个是困难的（使用Ziv距离的聚集问题也是如此）。近似范数的结果如图1.3所示。定理1. 设y=reiθ是一个代数复数，r0和θ[0，2 π）。 假设K >1。1. 若y= 0或r = 1且θ∈ { 0，π，π，3π}，则因子-K-N∈ ISING（y），距离-（π/3）-A RG I SING（y）和C COMPLEX A PX-I SING（y）在FP中。6−−/2B关于我们2^^^2222. 如果y > 1是实数，则F actor-K-N-ISING（y）和COMPLEXAPX-ISING（y）在RP中，并且DISTANCE-（π/3）-A RGISING（y）在FP中。3. 如果y是（0， 1）中的实数，则Factor-K-NISING（y）和COMPLEXA px-ISING（y）是NP-难的，距离-（π/3）-A RGISING（y）是FP中的.4. 如果 0，θ = aπ，其中a，b是两个互质正整数，a是奇数，则F因子-K-N_X-ISING（y），距离-（π/3）-A_RG_X-ISING（y）和复A_PX_X-ISING（y）是#P-难的.9. 若1，θ0，π然后FACTOR-K-N ISING（y） 和复APX-ISING（y）是NP-困难。1.4问题的简化版本对于我们已经定义的任何问题，如果给定一个输入G使得ZIsing（G;y，λ）=0，则要求多项式时间算法输出0。定理1给出了这些问题的硬度结果。 硬度不是由于特殊的困难时出现的配分函数的值为零。为了证明这一点，（也为了使后面的某些约简更容易），我们还考虑了以下问题的更宽松的版本如前所述，参数K大于1，参数ρ在（0， 2π）中。名称FACTOR-K-NONZERO-NISING（y，λ）.实例A（多）图G.输出If|ZIsin g（G;y，λ）|=0，则该算法可以输出一个ny有理数nber。 否则，它不能输出N的有理数，如果N/K≤|ZIsin g（G;y，λ）|≤KN。名称距离-ρ-NONZERO-ARG ISING（y，λ）.实例A（多）图G.如果ZIsing（G;y，λ）= 0，则算法可以输出任意有理数。否则，它必须输出一个有理数A^，使得|A^−ar g（ZIsin g（G; y，λ））|≤ρ。7RΣ- -||名称复A px-NONZERO-ISING（y，λ）。例如一个（多）图G和一个正整数R，在一元。输出If|ZIsin g（G;y，λ）|=0，则该算法可以输出一个ny_comple_x_n_b_er。否则，它必须输出一个复数z，使得d（z，ZIsing（G;y，λ））≤1。与问题的非松弛版本一样，当参数“λ“为1时，我们将其从问题名称中删除。我们给出定理1的如下推广。定理2.定理1中的所有结果都推广到松弛情形。 也就是说，分别用F actor-K-N onzero -N onzero-I SING（y）、D ISTANCE-（π/3）-N onzero -A RG I SING（y）和C COMPLEX A PX-N ONZERO-I SING（y）代替Factor-K-N ONZERO-I SING（y），结果仍然成立。1.5量子模拟1.5.1IQPIQP的特征在于量子电路的限制类[25]。我们将在4.1节给出一个正式的定义。在那里，我们还将讨论Fujii和Morimae [11]，Bremner等人[5]和Jozsa等人[19]的相关工作。在这里，我们给出一个非正式的描述，使我们能够陈述我们的定理。Bremner等人证明了对一类被称为IQP 1，2（θ）电路的有限电路进行某种“弱模拟”的难度电路中的量子比特沿着“线”行进，这些“线”进入（和离开）量子门。这样的电路C的输出是随机变量Y（在输出中测量的量子比特上）。 给定所有零量子比特的字符串和输出字符串y∈ {0，1}作为输入|我|在集合I上-在输出中测量的量子位的集合，Pr C; I表示Y=y的概率。强模拟是（近似）计算这种概率的问题。我们考虑以下问题，其中K >1是误差参数。名称FACTOR-K-STRONG SIM IQP1， 2（θ）。实例IQP1，2（θ）回路C，线的子集I [n]，以及字符串y ∈ {0，1}|我|。输出一个有理数p使得p/K≤PrC;I（Y=y）≤Kp。我们关于这个应用的主要结果如下。定理3. 设K> 1，θ ∈（0，2 π）. 如果ei θ是一个代数复数且ei8 θ/= 1然后FACTOR-K-STRONG SIM IQP1， 2（θ） 是#P-硬。1.5.2Tutte多项式的符号与BQP配分函数ZIsing（G;y，λ）等价于Tutte多项式的特殊化，Tutte多项式是具有两个参数x和y的图多项式，定义如下，T（G;x，y）=A类（G）（x−1）κ（A）−κ（E（G））（y − 1）|一|−n+ κ（A）， （2）其中n=V（G），κ（A）是子图（V（G），A）中连通分支的个数。如果量q=（x1）（y1）是正整数，则具有参数x和y的Tutte多项式与Potts模型的配分函数密切相关，其包括Ising模型作为q= 2的特殊情况。特别地，当q= 2时，T（G; x，y）=（y − 1）−n（x − 1）−κ（E（G））ZIsing（G; y）. （三）Bordewich等人 [4]提出了“确定Tutte多项式在给定点是否大于或等于或小于零”的问题。正如我们将看到的，这个问题与量子复杂性类BQP有关。我们考虑以下问题。8- −- −关于我们−±∈ {− −}±−和|arg z − arg z′|≤NameSIGN-REAL TUTTE（x，y）实例A（多）图G.求T（G;x，y）的实数部分的符号为正、负或0。名称SIGN-REAL-NONZERO TUTTE（x，y）实例A（多）图G.输出一个形式为“T（G ; x，y）≥ 0”或“T（G ; x，y）≤ 0”的正确状态。BQP是一类可由量子计算机在多项式时间内以有界误差解决的决策问题。定理[4，定理6.1]表明，BQP中的所有问题也可以在多项式时间内使用一个oracle来经典地解决，该oracle返回链路的琼斯多项式的实部的符号，在点t= exp（2πi/ 5）处求值。Thistlethwaite [27]（见[17，（6.1）]）表明，这个问题反过来又与求平面图G的Tutte多项式T（G;t，t−1）的问题有关。这启发了Bordewich等人关于确定Tutte多项式的符号的复杂性的问题，特别是对于点（x，y）=（t，t−1）。 我们表明，这个问题是很难的t值，包括相关的值t= exp（2πi/ 5）。请注意，我们的结果对BQP的模拟没有直接影响，因为我们没有处理平面性（尽管它回答了Bordewich等人的问题）。我们在第5节中给出了详细的内容，在那里我们还讨论了Kuperberg [20]的一个相关结果。我们的定理如下。定理4. 考虑点（x，y）=（exp（aπ i/b），exp（aπ i/b）），其中a和b是满足0 1。 设y和z是两个单位根。则以下成立：1. 如果y = i和z1，1，i，i，或y =1，则ZIsing（; y，z）可以在多项式时间内精确计算。2. 否则FACTOR-K-NONZERO-NISING（y，z）是#P-hard。2预赛2.1关于复数近似的我们将使用以下关于1.2节中Ziv距离测度的技术引理。引理7. 若z和z′是两个非零复整数且d（z′，z）≤ε，则|z′|/|z|≤1/（1−ε）36ε/11。9−−−√R||/≤||RR等于11（θ-θ）/24，|θ − θ |≤KR1 −1−证据设d（z′，z）≤ε，|z′| ≥ |z|.首先，根据三角不等式，|z|+的|z′−z| ≥ |z′|所以|= 1+| z′|−| z|≤ 1 +| z′ −z|=1+| z′ −z|z|z ′|≤ 1 +ε|z′|、|,按要求|z||z||z||z′||z||z|第二、|z′−z|≤ε|z′|所以（|z′−z|）2≤ε2|z′|二、 设z=rexp（iθ）和z′=r′exp（iθ′），我们（（r′cos（θ′）− r cos（θ））2+（（r′sin（θ′）−r sin（θ））2 ≤ ε2r′2.左边等于r2+r′2−2rr′ cos（θ−θ′）。但我们已经证明了r′11≤r≤1−ε，所以r′2（1−ε）2+r′2− 2r′2 cos（θ−θ′）≤ε2r′2，这意味着，通过重新安排上述内容，cos（θ − θ′）≥1 −但cos（x）= 1 − x2/2！ + x4/4！ -6/6！+···，所以3ε ε2+。2 2（θ θ′）2二号！ −（θθ′）4+四个！（θ θ′）6六！ − · · ·≤ 3ε ε2.2 2假设ε非常小（所以θ−θ′≤1），则左手边至少为（θ−θ′）2−（θ−θ′）4′2′√二号！四个！引理8. 设K> 1，0 <ρ <2 π。 然后存在以下多项式时间图灵约简。FACTOR-K-NISING（y，λ）≤TCCOMPLEX APX-ISING（y，λ），因子-K-NONZERO-NISING（y，λ）≤TCCOMPLEX A px-NONZERO-ISING（y，λ），距离-ρ-ARG ISING（y，λ）≤TCCOMPLEX APX-ISING（y，λ），距离-ρ-NONZERO-ARG ISING（y，λ）≤TCCOMPLEX APX-NONZERO-ISING（y，λ），证据设R是任何（足够大的）整数，使得1− 1/R > 1/K且36/ 11R≤ρ。考虑一个重图G，其中ZIsing（G;y，λ）= 0.给定输入G和R，C COMPLEX A PX-ISING（y，λ）或C COMPLEX A PX-N ONZERO-I SING（y，λ）的预言机返回复数z，使得 d （ z ， ZIsing （ G; y ， λ ） ） 1 。 另 一 方 面 ， 如 果 ZIsing （ G;y ， λ ） = 0 ， 则COMPLEXAPX-ISING（y，λ）的预言机返回复数z= 0，而COMPLEXAPX- NONZERO-ISING（y，λ）的预言机返回任何复数z。对于前两个还原，首先假设|ZIsin g（G;y，λ）|为0.根据引理7，d（z，ZIsing（G;y，λ））≤1意味着|≤。|≤.1−1Σ|z|≤|Z（G; y，λ）|≤|z|≤K|z|、R所以|z|是F actor-K-N I SING（y，λ）或F actor-K-N ONZERO-N I SING（y，λ）与输入G的合适输出。 另一方面如果|ZIsin g（G;y，λ）|=0，则|z|在两种情况下仍然适用。对于最后两次还原，首先假设|ZIsin g（G;y，λ）|=0。 则由引理7，d（z，ZIsing（G;y，λ））≤1意味|≤ε 36 ε/ 11 ≤ ρ，|≤ √36 ε/11 ≤ ρ,有36ε/11。Ising10||/ΣY^^^⊆ ∈∈一位女发言人：e∈A∗∗因此arg z是具有输入G的D I STANCE-ρ-A RG I SING（y，λ）或D I STANCE-ρ-N ONZERO-A RGI SING（y，λ）的合适输出。 另一方面，如果|ZIsin g（G;y，λ）|=0和z=0，则在这两种情况下0都是合适的输出。如果ZIsing（G;y，λ）= 0且z= 0，则argz是合适的（作为DISTANCE-p-NONZERO-ARGISING（y，λ）的输出）。2.2多元Tutte多项式我们将需要多元Tutte多项式的随机聚类公式。给定一个边权为γ的（多）图G：E（G）→Q且q∈Q，定义为ZTutte（G;q，γ）：=A类（G）其中γe是对边e∈E（G）的γ（eqκ（A） γe，（4）e∈A假设x和y满足q=（x−1）（y−1）。对于图G=（V，E），设γ：E→Q是将每条边映射到值y−1的常数函数然后（例如见[26，（2.26）]）T（G; x，y）=（y − 1）−n（x − 1）−κ（E（G））ZTutte（G; q，γ）.（五）显然，从（3），这意味着如果q=2，则ZIsing（G;y）=ZTutte（G;q，γ）。为了应用[15]中的技术，我们需要问题FACTOR-K-NONZERO-NNUMERISING（y，λ）的多变量版本我们可以对一般的q这样做，但我们只使用下面的版本，它被限制为q=2，有两个复参数γ1和γ2。名称因子-K-N onzero-N 2TUTTE（γ1，γ2）.实例A（多）图G =（V，E）和边权γ：E→ {γ1，γ2}。输出If|ZTutt e（G;2，γ）|=0，则该算法可以输出一个ny有理数nber。否则，它应在N上输入一个有理数，使得N/K≤|ZTutt e（G;2，γ）|≤KN。设s和t是G的两个可区别的顶点.设Zst（G;q，γ）是子图A对ZTutte（G;q，γ）的贡献，其中s和t在（V（G），A）的同一分支中，即，Zst（G;q，γ）：=<$qκ（A）Yγe.同一部件中的s和t类似地，令Zs|t表示构型A对ZTutte（G; q，γ）的贡献，其中s和t是不同的成分。2.3实现新的边权重、串行合成和并行合成我们对实现、串行组合和并行组合的处理是完全标准的，并且取自[14，2.1节]。熟悉本材料的读者可以跳过本节（为了完整起见，将其包含在此处）。固定WQ和QQ。设w=Q是我们想要“实现”的权重（可能不在W中）。假设有一个图E，它有区别的顶点s和t，权函数γ^：E（E）→W满足w= qZs t（q;q，γ^）/Zs|t（q;q，γ^）。（六）、∗在这种情况下，我们可以说，γ和γ实现了w（或者甚至W实现了w）。“实现”边权重的目的是这样的。设G是一个权函数为γ的图. 设f是G的某条边，其权为γf=w<$。假设W实现了w。设k是图11^→^^/−^- -- − −联系我们αww1w2.Σ和具有不同的顶点s和t，权函数γ：E（n）W满足（6）。通过将边f替换为f的一个副本来构造加权图G ′（将s标识为f的任意一个端点（不管是哪一个），将t标识为f的另一个端点并删除边f）。让′ ′ ′ ′权函数γG从γ和γ^中继承weights（所以如果e∈E（n）且γe=γe，则γe=γ否则）。 然后给出多元Tutte多项式的定义，全明星（G′; q，γ′）= Zs|t（q;q，γ）ZQ2Tutte（G; q，γ）。（七）所以只要q=0，|t（n; q，γ）的值很容易求，用权函数γ ′求G ′的多元Tutte多项式与用权函数γ求G的多元Tutte多项式本质上是一样的.由于两个复数的乘积的范数是范数的乘积，这将计算（或相对近似）具有权重函数γ的范数的问题简化为计算（或相对近似）具有权重函数γ′的范数的问题。此外，由于两个复数的乘积的幅角是数的幅角之和，这将计算（或加法近似）具有权重函数γ的幅角的问题减少为计算（或加法近似）具有权重函数γ'的幅角的问题。两个特别有用的实现是串行和并行组合。 平行合成是这样一种情况，其中γ由两条端点为s和t的平行边e1和e2组成，γ∈e1=w1，γ∈e2=w2。从等式（6）容易地推导出，w=（1+w1）（1+w2）1.一、此外，等式（7）中的额外因子抵消，因此在这种情况下ZTutte（G′; q，γ′）= ZTutte（G; q，γ）。级数复合是这样一种情况，其中γ是从s到t的长度为2的路径，由边e1和e2组成 ， 其 中 γ∈e1=w1 和 γεe2=w2.从 等 式 （ 6 ） 可 以 容 易 地 推 导 出 w=w1w2/（q+w1+w2）。此外，等式（7）中的额外因子是q+w1+w2，因此在这种情况下ZTutte（G′;q，γ′）=（q + w1+ w2）ZTutte（G; q，γ）。 值得注意的是，W*满足.1 +Q =.1 +q。1 +q。我们说存在其中W是单例集W=α。 取y=α+1，y′=α′+1，定义x和x′为q=（x1）（y）1）=（x′1）（y′（1）等同于从（x，y）到（x′，y′）的转换。 这是一个简单但重要的观察，保持冷静，以获得新的转变。 因此，如果我们有从（x，y）到（x′，y′）的移位，以及从（x′，y′）到（x′，y′）的移位，那么我们也有从（x，y）到（x′，y′）的移位。[17]的k-稠化是k条权为α的边的平行合成。它实现了α′=（1+α）k1，并且是从（x，y）到（x′，y′）的移位，其中y′=yk（并且x′由（x′1）（y′1）=q给出）。类似地，k-拉伸是k条权为α的边的级数合成。它实现了一个α′满足1+q=1+qk，α′它是从（x，y）到（x′，y′）的移位，其中x′=xk。（在经典的双变量（x，y）参数化中，实际上只有一个边权重，因此拉伸或增厚均匀地应用于图的每条边因此，我们有以下观察。观察9. k-增厚运算给出以下多项式时间约简。• Factor-K-NISING（yk）≤Factor-K-NISING（y），• 距离-ρ -ARG ISING（yk）≤距离-ρ-ARG ISING（y），• SIGN-REAL TUTTE（1 +（x−1）（y−1）/（yk−1），yk）≤SIGN-REAL TUTTE（x，y），其中yk/=1，12−和• C复A PX-ISING（yk）≤C复A PX-ISING（y）.类似地，k-拉伸给出了以下对于yi = 1的多项式时间约简。• FACTOR-K-N ISING（1 + 2/（（1 + 2/（y−1））k−1））≤FACTOR-K-N ISING（y），• DISTANCE-ρ-ARG ISING（1 + 2/（（1 + 2/（y−1））k−1））≤DISTANCE-ρ-ARG ISING（y），• SIGN-REALTUTTE（xk，1+（x−1）（y−1）/（xk−1））≤SIGN-REALTUTTE（x，y），其中xk/= 1，• C COMPLEX A PX-I SING（1 + 2/（（1 + 2/（y−1））k− 1））≤ C COMPLEX APX-I SING（y）.类似的陈述适用于问题的放松版本3Ising模型的硬度结果在本节中，我们证明定理1和2。3.1实际重量首先，我们收集了一些已知的结果近似的分区函数Z伊辛（G;y）的伊辛模型时，y是一个代数实数。如果y∈ {− 1，0，1}，则从定义（1）计算ZIsing（G;y）是平凡的。Jerrum和Sinclair [ 18 ]的一个经典结果解决了当y > 0时逼近ZIsing（G;y）的复杂性。他们表明，当y > 1时，存在一个<<消极的情况似乎更为复杂。Goldberg和Jerrum [13]证明了，如果-1< y<0，则近似ZIsing（G;y）也是NP -困难的，但如果y<1、问题等价于近似图中完美匹配的数量，并且不知道是否存在FPRAS。从技术上讲，无论是杰拉姆和辛克莱，还是戈德堡和杰拉姆，都没有对代数数进行研究。为了避免实数运算的问题，杰鲁姆和辛克莱使用了一个计算模型，在这个模型中，实数运算是以完美的精度执行的，而戈德堡和杰鲁姆限制了对有理数的关注。 然而，在这些文件中的操作很容易实现代数实数。使用我们的符号，这些结果总结如下。引理10. （[18，13]）设y∈Q且K >1。然后F演员-K-N I唱（y）• 在FP中，如果y∈ {−1， 0， 1};• 如果y >1，则在RP中;• 是NP难的，如果0 1，在F ACTOR-K-N I SING（y，λ）和FPRAS-N I SING（y，λ）之间存在多项式时间图灵约简。证据 从FACTOR-K-N I SING（y，λ）到FPRAS-N I SING（y，λ）的简化是直接的：给定Factor-K-N I SING（y，λ）的输入G，选择R，使得K R/（R 1），并使用输入G和R运行FPRAS-N I SING（y，