BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Recent results on the classical simulation of quantum circuits - R
 ichard Jozsa (CQC)
DTSTART:20100520T131500Z
DTEND:20100520T141500Z
UID:TALK24884@talks.cam.ac.uk
CONTACT:Jonathan
DESCRIPTION:A fundamental goal of quantum computation is to understand the
  relationship of classical to quantum computational power and to identify 
 specific quantum features that may be exploited for novel algorithmic bene
 fit. A mathematically precise approach to these heuristic goals is to stud
 y the extent to which various kinds of quantum computations (perhaps invol
 ving only restricted quantum resources) can be classically simulated. We w
 ill discuss recent results in this direction\, on the classical simulation
  properties of two classes of quantum circuits\, and speculate upon their 
 significance. (a) We will introduce the notion of a matchgate\, a particul
 ar kind of 2-qubit gate. It may then be shown that circuits of matchgates\
 , restricted to act on only nearest-neighbour qubits\,  are classically ef
 ficiently 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 circuits comprising only c
 ommuting gates. Despite their tantalising apparent simplicity we will outl
 ine evidence that such quantum computational processes are unlikely to be 
 classically efficiently simulable\, even in a suitable weak approximate se
 nse.\nThese results were obtained in collaborations\, variously with A. Mi
 yake\, B. Kraus\, J. Watrous\, M. Bremner and D. Shepherd. 
LOCATION:MR3\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR