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

DOI10.1007/s00037-017-0162-2zbMath1382.68090arXiv1409.5627OpenAlexW2963721130MaRDI QIDQ1686832

Heng Guo, Leslie Ann Goldberg

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 modelTutte polynomialapproximate countingcounting 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)

Related Items (9)

The complexity of approximating the complex-valued Potts model ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Inapproximability of the Independent Set Polynomial in the Complex Plane ⋮ Location of zeros for the partition function of the Ising model on bounded degree graphs ⋮ Unnamed Item ⋮ The complexity of approximating the complex-valued Potts model ⋮ Efficient algorithms for approximating quantum partition functions ⋮ The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Low depth quantum circuits for Ising models
• The complexity of complex weighted Boolean \#CSP
• Inapproximability of the Tutte polynomial
• NP is as easy as detecting unique solutions
• A spanning tree expansion of the Jones polynomial
• A modular functor which is universal for quantum computation
• Inapproximability of the Tutte polynomial of a planar graph
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Polynomial-Time Approximation Algorithms for the Ising Model
• Relative Distance--An Error Measure in Round-Off Error Analysis
• Temporally unstructured quantum computation
• On the computational complexity of the Jones and Tutte polynomials
• Topological quantum computation
• The Complexity of Computing the Sign of the Tutte Polynomial
• Classical Ising model test for quantum circuits
• The BQP-hardness of approximating the Jones polynomial
• Quantum algorithms for classical lattice models
• Quantum computing, postselection, and probabilistic polynomial-time
• Approximate Counting and Quantum Computation

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