On the exact evaluation of certain instances of the Potts partition function by quantum computers

DOI10.1007/S00220-008-0438-0zbMATH Open1200.82007arXivquant-ph/0703023OpenAlexW2013557783MaRDI QIDQ926258FDOQ926258

Authors: Joseph Geraci, Daniel A. Lidar 

Publication date: 27 May 2008

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: We present an efficient quantum algorithm for the exact evaluation of either the fully ferromagnetic or anti-ferromagnetic q-state Potts partition function Z for a family of graphs related to irreducible cyclic codes. This problem is related to the evaluation of the Jones and Tutte polynomials. We consider the connection between the weight enumerator polynomial from coding theory and Z and exploit the fact that there exists a quantum algorithm for efficiently estimating Gauss sums in order to obtain the weight enumerator for a certain class of linear codes. In this way we demonstrate that for a certain class of sparse graphs, which we call Irreducible Cyclic Cocycle Code (ICCC_epsilon) graphs, quantum computers provide a polynomial speed up in the difference between the number of edges and vertices of the graph, and an exponential speed up in q, over the best classical algorithms known to date.

Full work available at URL: https://arxiv.org/abs/quant-ph/0703023

Recommendations

• Quantum algorithms for classical lattice models
• A new connection between quantum circuits, graphs and the Ising partition function
• On the quantum complexity of evaluating the Tutte polynomial
• Efficient algorithms for approximating quantum partition functions
• The complexity of approximating complex-valued Ising and Tutte partition functions

Mathematics Subject Classification ID

Quantum computation (81P68) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Exactly solvable models; Bethe ansatz (82B23) Cyclic codes (94B15)

Cites Work

• A polynomial invariant for knots via von Neumann algebras
• Simulation of topological field theories by quantum computers
• Hasse-Davenport curves, Gauss sums, and weight distributions of irreducible cyclic codes
• A categorification of the Jones polynomial
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• Weights of irreducible cyclic codes
• Coding and Cryptography
• Topological quantum field theory
• q-DEFORMED SPIN NETWORKS, KNOT POLYNOMIALS AND ANYONIC TOPOLOGICAL QUANTUM COMPUTATION
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the computational complexity of the Jones and Tutte polynomials
• Topological quantum computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact Potts model partition function on strips of the triangular lattice
• A polynomial quantum algorithm for approximating the Jones polynomial
• Knots and physics
• Is the class of cyclic codes asymptotically good?
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• On knot invariants related to some statistical mechanical models
• Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
• Quantum computation of zeta functions of curves
• Exponential sums, Gauss sums and cyclic codes
• On some polynomials related to weight enumerators of linear codes
• Title not available (Why is that?)

Cited In (11)

• Graph isomorphism and Gaussian boson sampling
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• Completeness of classical spin models and universal quantum computation
• Systematic study of the completeness of two-dimensional classical \(\mathbf{\phi}^4\) theory
• Classical Ising model test for quantum circuits
• Quantum algorithms for classical lattice models
• Low depth quantum circuits for Ising models
• A new connection between quantum circuits, graphs and the Ising partition function
• Calculation of partition function of Ising model on quantum computer
• Quantum computation and the evaluation of tensor networks
• Efficient algorithms for approximating quantum partition functions

This page was built for publication: On the exact evaluation of certain instances of the Potts partition function by quantum computers

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