Matchgates and the classical simulation of associated quantum circuits

          @misc{ scivideos_PIRSA:08040048,
            doi = {10.48660/08040048},
            url = {https://pirsa.org/08040048},
            author = {Jozsa, Richard},
            keywords = {Quantum Information},
            language = {en},
            title = {Matchgates and the classical simulation of associated quantum circuits },
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2008},
            month = {apr},
            note = {PIRSA:08040048 see, \url{https://scivideos.org/index.php/pirsa/08040048}}
          }
          

Abstract

Some years ago Valiant introduced a notion of \'matchgate\' and \'holographic algorithm\', based on properties of counting perfect matchings in graphs. This provided some new poly-time classical algorithms and embedded in this formalism, he recognised a remarkable class of quantum circuits (arising when matchgates happen to be unitary) that can be classically efficiently simulated. Subsequently various workers (including Knill, Terhal and DiVincenzo, Bravyi) showed that these results can be naturally interpreted in terms of the formalism of fermionic quantum computation. In this talk I will outline how unitary matchgates and their simulability arise from considering a Clifford algebra of anticommuting symbols, and then I\'ll discuss some avenues for further generalisation and interesting properties of matchgate circuits. In collaboration with Akimasa Miyake, University of Innsbruck.