BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum advantage with shallow circuits (Bravyi-Gosset-König) - N
 adish de Silva\, University of Cambridge
DTSTART:20191129T120000Z
DTEND:20191129T130000Z
UID:TALK135601@talks.cam.ac.uk
CONTACT:Sathyawageeswar Subramanian
DESCRIPTION:Rigorously separating classical and quantum computational powe
 r is a central problem of quantum computer science.  Known results tend t
 o rely on the use of oracles or unproven complexity-theoretic assumptions
 .  In contrast\, BGK prove an unconditional separation between the power 
 of constant-depth classical and quantum circuits to solve a certain proble
 m.  Their proof exploits the logical structure of nonlocal games.  \n\n
 This seminar talk aims to give a self-contained and accessible overview of
  their proof\; it is based on https://arxiv.org/abs/1704.00690 (Science\
 , 2018) and https://arxiv.org/abs/1904.01502.\n
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR