PIRSA:08040048

Matchgates and the classical simulation of associated quantum circuits

APA

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

MLA

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

BibTex

          @misc{ 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

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.