BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Boson-Sampling in the light of sample complexity - Eisert\, J (Fre
 ie Universitt Berlin)
DTSTART:20130906T130000Z
DTEND:20130906T133000Z
UID:TALK46980@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Boson-Sampling is a classically computationally hard problem t
 hat can - in principle - be efficiently solved with linear quantum optical
  networks. Very recently\, a rush of experimental activity has ignited wit
 h the aim of developing such devices as feasible instances of quantum simu
 lators. Even approximate Boson-Sampling is believed to be hard with high p
 robability if the unitary describing the optical network is drawn from the
  Haar measure. In this work we show that in this setup\, with probability 
 exponentially close to one in the number of bosons\, no symmetric algorith
 m can distinguish the Boson-Sampling distribution from the uniform one fro
 m fewer than exponentially many samples. This means that the two distribut
 ions are operationally indistinguishable without detailed a priori knowled
 ge. We carefully discuss the prospects of efficiently using knowledge abou
 t the implemented unitary for devising non-symmetric algorithms that could
  potentially improve upon this. We conclude that due to the very fact that
  Boson-Sampling is believed to be hard\, efficient classical certification
  of Boson-Sampling devices seems to be out of reach.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR