PIRSA:08040048

Matchgates and the classical simulation of associated quantum circuits

Jozsa, R. (2008). Matchgates and the classical simulation of associated quantum circuits . Perimeter Institute. https://pirsa.org/08040048

Jozsa, Richard. Matchgates and the classical simulation of associated quantum circuits . Perimeter Institute, Apr. 28, 2008, https://pirsa.org/08040048 

          @misc{ pirsa_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},
            year = {2008},
            month = {apr},
            note = {PIRSA:08040048 see, \url{https://pirsa.org}}
          }

Richard Jozsa University of Cambridge

Talk numberPIRSA:08040048
DOI10.48660/08040048
Collection
Talk Type Conference
Subject

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.