- Home »
- Efficient quantum algorithms for an additive approximation of the Tutte polynomial and the q-state Potts model.

Speaker(s):

Scientific Areas:

Collection/Series:

PIRSA Number:

07050024

I will present an efficient quantum algorithm for an additive

approximation of the famous Tutte polynomial of any planar graph at

any point. The Tutte polynomial captures an extremely wide range of

interesting combinatorial properties of graphs, including the

partition function of the q-state Potts model. This provides a new

class of quantum complete problems.

Our methods generalize the recent AJL algorithm for the approximation

of the Jones polynomial; instead of using unitary representations, we

allow non-unitarity, which seems counter intuitive in the quantum

world. Significant contribution of this is a proof that non-unitary

operators can be used for universal quantum computation.

©2012 Perimeter Institute for Theoretical Physics