Physics – Quantum Physics
Scientific paper
2007-03-03
Comm. Math. Phys. 279, 735 (2008)
Physics
Quantum Physics
Scientific paper
10.1007/s00220-008-0438-0
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.
Geraci Joseph
Lidar Daniel A.
No associations
LandOfFree
On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-719986