BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum states cannot be transmitted efficiently classically - Ash
 ley Montanaro\, Bristol
DTSTART:20170512T110000Z
DTEND:20170512T120000Z
UID:TALK72383@talks.cam.ac.uk
CONTACT:Steve Brierley
DESCRIPTION:In this talk I will discuss recent work showing that any class
 ical communication protocol that can approximately simulate the result of 
 applying an arbitrary measurement (held by one party) to a quantum state o
 f n qubits (held by another) must transmit at least 2^n bits\, up to const
 ant factors. The argument is based on proving a lower bound on the classic
 al communication complexity of a distributed variant of the Fourier sampli
 ng problem. Two optimal quantum-classical separations follow as corollarie
 s. First\, a sampling problem which can be solved with one quantum query t
 o the input\, but which requires order-N classical queries for an input of
  size N. Second\, a nonlocal task which can be solved using n Bell pairs\,
  but for which any approximate classical solution must communicate 2^n bit
 s\, up to constant factors.\n\nThe talk will be based on the paper arXiv:1
 612.06546.\n
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR