BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Quantum matchgate computations and linear threshol
d gates - Maarten van den Nest
DTSTART;TZID=Europe/London:20110331T141500
DTEND;TZID=Europe/London:20110331T151500
UID:TALK29997AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/29997
DESCRIPTION:The theory of matchgates is of interest in various
areas in physics and computer science. Matchgates
occur in e.g. the study of fermions and spin chai
ns\, in the theory of holographic algorithms and i
n several recent works in quantum computation. In
this talk I will discuss a paper in which we compl
etely characterize the class of boolean functions
computable by unitary two-qubit matchgate circuits
with some probability of success. We show that th
is class precisely coincides with that of the line
ar threshold gates. The latter is a fundamental fa
mily which appears in several fields\, such as the
study of neural networks. Using the above charact
erization\, we further show that the power of matc
hgate circuits is surprisingly trivial in those ca
ses where the computation is to succeed with high
probability. In particular\, the only functions th
at are matchgate-computable with success probabili
ty greater than 3/4 are functions depending on onl
y a single bit of the input.
LOCATION:MR14\, Centre for Mathematical Sciences
CONTACT:Ashley Montanaro
END:VEVENT
END:VCALENDAR