The complexity of approximating complex-valued Ising and Tutte partition functions

DOI10.1007/S00037-017-0162-2MaRDI QIDQ1686832zbMATH OpenOpenAlexFDO

Authors Leslie Ann Goldberg, Heng Guo

Publication date 18 December 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.5627

zbMATH Keywords

Ising modelapproximate countingTutte polynomialcounting complexity

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These results rely on interesting and deep results about quantum computation in order to obtain hardness results about the difficulty of (classically) evaluating the partition functions for certain fixed parameters. The motivation for this paper is to study more comprehensively the complexity of (classically) approximating the Ising and Tutte partition functions with complex parameters. Partition functions are combinatorial in nature and quantifying their approximation complexity does not require a detailed understanding of quantum computation. Using combinatorial arguments, we give the first full classification of the complexity of multiplicatively approximating the norm and additively approximating the argument of the Ising partition function for complex edge interactions (as well as of approximating the partition function according to a natural complex metric). We also study the norm approximation problem in the presence of external fields, for which we give a complete dichotomy when the parameters are roots of unity. Previous results were known just for a few such points, and we strengthen these results from BQP-hardness to #P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is #P-hard at certain points related to the simulation of BQP. Using our classifications, we then revisit the connections to quantum computation, drawing conclusions that are a little different from (and incomparable to) ones in the quantum literature, but along similar lines.

Recommendations

• Commuting quantum circuits and complexity of Ising partition functions
• Complexity of Ising polynomials
• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)

Cites work

• scientific article; zbMATH DE number 2120364 (Why is no real title available?)
• A modular functor which is universal for quantum computation
• A spanning tree expansion of the Jones polynomial
• Approximate Counting and Quantum Computation
• Classical Ising model test for quantum circuits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• How hard is it to approximate the Jones polynomial?
• Inapproximability of the Tutte polynomial
• Inapproximability of the Tutte polynomial of a planar graph
• Low depth quantum circuits for Ising models
• NP is as easy as detecting unique solutions
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial-Time Approximation Algorithms for the Ising Model
• Quantum algorithms for classical lattice models
• Quantum computing, postselection, and probabilistic polynomial-time
• Relative Distance--An Error Measure in Round-Off Error Analysis
• Temporally unstructured quantum computation
• The BQP-hardness of approximating the Jones polynomial
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The complexity of complex weighted Boolean \#CSP
• The complexity of computing the sign of the Tutte polynomial
• The computational complexity of linear optics
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Topological quantum computation

Cited in

(15)

• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The complexity of approximating the complex-valued Potts model
• A new connection between quantum circuits, graphs and the Ising partition function
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• Efficient algorithms for approximating quantum partition functions
• Complexity of Ising polynomials
• Inapproximability of the independent set polynomial in the complex plane
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• Counting homomorphisms modulo a prime number
• The complexity of approximating the complex-valued Potts model
• Completeness of classical spin models and universal quantum computation
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• A complexity classification of spin systems with an external field
• Approximating the chromatic polynomial is as hard as computing it exactly
• Location of zeros for the partition function of the Ising model on bounded degree graphs

This page was built for publication: The complexity of approximating complex-valued Ising and Tutte partition functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686832)