Matchgates and the classical simulation of associated quantum circuits

Recording Details

Speaker(s): 
Scientific Areas: 
PIRSA Number: 
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.