On the exact evaluation of certain instances of the Potts partition function by quantum computers
From MaRDI portal
Publication:926258
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.
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
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1702955 (Why is no real title available?)
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 5296403 (Why is no real title available?)
- scientific article; zbMATH DE number 3763833 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1270594 (Why is no real title available?)
- scientific article; zbMATH DE number 1131801 (Why is no real title available?)
- scientific article; zbMATH DE number 1160035 (Why is no real title available?)
- A categorification of the Jones polynomial
- A polynomial invariant for knots via von Neumann algebras
- A polynomial quantum algorithm for approximating the Jones polynomial
- Coding and Cryptography
- Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
- Exact Potts model partition function on strips of the triangular lattice
- Exponential sums, Gauss sums and cyclic codes
- Hasse-Davenport curves, Gauss sums, and weight distributions of irreducible cyclic codes
- Is the class of cyclic codes asymptotically good?
- Knots and physics
- On knot invariants related to some statistical mechanical models
- On some polynomials related to weight enumerators of linear codes
- On the computational complexity of the Jones and Tutte polynomials
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum computation of zeta functions of curves
- Simulation of topological field theories by quantum computers
- The Jones polynomial: quantum algorithms and applications in quantum complexity theory
- Topological quantum computation
- Topological quantum field theory
- Weights of irreducible cyclic codes
- q-DEFORMED SPIN NETWORKS, KNOT POLYNOMIALS AND ANYONIC TOPOLOGICAL QUANTUM COMPUTATION
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)
