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:Recent results on the classical simulation of quan
tum circuits - Richard Jozsa (CQC)
DTSTART;TZID=Europe/London:20100520T141500
DTEND;TZID=Europe/London:20100520T151500
UID:TALK24884AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/24884
DESCRIPTION:A fundamental goal of quantum computation is to un
derstand the relationship of classical to quantum
computational power and to identify specific quant
um features that may be exploited for novel algori
thmic benefit. A mathematically precise approach t
o these heuristic goals is to study the extent to
which various kinds of quantum computations (perha
ps involving only restricted quantum resources) ca
n be classically simulated. We will discuss recent
results in this direction\, on the classical simu
lation properties of two classes of quantum circui
ts\, and speculate upon their significance. (a) We
will introduce the notion of a matchgate\, a part
icular kind of 2-qubit gate. It may then be shown
that circuits of matchgates\, restricted to act on
only nearest-neighbour qubits\, are classically
efficiently simulable\, whereas if the matchgates
are allowed to act on just next-nearest-neighbour
qubits as well\, then we recover fully universal q
uantum computation. (b) We will discuss quantum ci
rcuits comprising only commuting gates. Despite th
eir tantalising apparent simplicity we will outlin
e evidence that such quantum computational process
es are unlikely to be classically efficiently simu
lable\, even in a suitable weak approximate sense.
\nThese results were obtained in collaborations\,
variously with A. Miyake\, B. Kraus\, J. Watrous\,
M. Bremner and D. Shepherd.
LOCATION:MR3\, Centre for Mathematical Sciences
CONTACT:Jonathan
END:VEVENT
END:VCALENDAR