PIRSA:07050024

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

Arad, I. (2007). Efficient quantum algorithms for an additive approximation of the Tutte polynomial and the q-state Potts model.. Perimeter Institute. https://pirsa.org/07050024

Arad, Itai. Efficient quantum algorithms for an additive approximation of the Tutte polynomial and the q-state Potts model.. Perimeter Institute, May. 21, 2007, https://pirsa.org/07050024 

          @misc{ pirsa_PIRSA:07050024,
            doi = {10.48660/07050024},
            url = {https://pirsa.org/07050024},
            author = {Arad, Itai},
            keywords = {Quantum Information},
            language = {en},
            title = {Efficient quantum algorithms for an additive approximation of the Tutte polynomial and the q-state Potts model.},
            publisher = {Perimeter Institute},
            year = {2007},
            month = {may},
            note = {PIRSA:07050024 see, \url{https://pirsa.org}}
          }

Itai Arad Hebrew University of Jerusalem

DOI 10.48660/07050024
Collection
Talk Type Scientific Series
Subject

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.