BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum matchgate computations and linear threshold gates - Maarte
 n van den Nest
DTSTART:20110331T131500Z
DTEND:20110331T141500Z
UID:TALK29997@talks.cam.ac.uk
CONTACT:Ashley Montanaro
DESCRIPTION:The theory of matchgates is of interest in various areas in ph
 ysics and computer science. Matchgates occur in e.g. the study of fermions
  and spin chains\, in the theory of holographic algorithms and in several 
 recent works in quantum computation. In this talk I will discuss a paper i
 n which we completely characterize the class of boolean functions computab
 le by unitary two-qubit matchgate circuits with some probability of succes
 s. We show that this class precisely coincides with that of the linear thr
 eshold gates. The latter is a fundamental family which appears in several 
 fields\, such as the study of neural networks. Using the above characteriz
 ation\, we further show that the power of matchgate circuits is surprising
 ly trivial in those cases where the computation is to succeed with high pr
 obability. In particular\, the only functions that are matchgate-computabl
 e with success probability greater than 3/4 are functions depending on onl
 y a single bit of the input. 
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR