On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers

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_ε) 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.

References in corpus (11)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Simulation of topological field theories by quantum computers
• Simulating Ising Spin Glasses on a Quantum Computer
• Exact Potts Model Partition Functions on Ladder Graphs
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Classical spin models and the quantum stabilizer formalism
• Partition function of two- and three-dimensional Potts ferromagnets for arbitrary values of q>0
• Efficient Quantum Algorithms for Estimating Gauss Sums
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• Real-Time Dynamics from Imaginary-Time Quantum Monte Carlo Simulations: Tests on Oscillator Chains
• Hardness of approximating the weight enumerator of a binary linear code

Cited by in corpus (27)

• Quantum speedup of Monte Carlo methods
• Quantum Algorithm Implementations for Beginners
• Graph isomorphism and Gaussian boson sampling
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Quantum Computation Beyond the Circuit Model
• Quantum algorithms for classical lattice models
• Completeness of classical spin models and universal quantum computation
• A simple encoding of a quantum circuit amplitude as a matrix permanent
• Twins Percolation for Qubit Losses in Topological Color Codes
• Classical Ising model test for quantum circuits
• Dual correspondence between classical spin models and quantum CSS states
• Fundamental thresholds of realistic quantum error correction circuits from classical spin models
• An algorithmic proof for the completeness of two-dimensional Ising model
• Low Depth Quantum Circuits for Ising Models
• Phase transition in a noisy Kitaev toric code model
• Analytical percolation theory for topological color codes under qubit loss
• A quantum information approach to statistical mechanics
• Classical criticality establishes quantum topological order
• Quantum computation and the evaluation of tensor networks
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• Evaluating the Jones polynomial with tensor networks
• Quantum algorithm for exact Monte Carlo sampling
• Noisy Toric code and random bond Ising model: The error threshold in a dual picture
• Systematic study of the completeness of two-dimensional classical ${\varphi }^4$ theory
• A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets
• Ising models and topological codes: classical algorithms and quantum simulation