Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.
 

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

Recording Details

Speaker(s): 
Scientific Areas: 
Collection/Series: 
PIRSA Number: 
07050024

Abstract

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.