BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum advantage from energy measurements - Leonardo Goncalves No
 vo\, QuIC\, Université libre de Bruxelles
DTSTART:20191004T110000Z
DTEND:20191004T120000Z
UID:TALK131404@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:A central challenge in the field of quantum computation is to 
 demonstrate that a quantum device can show an unambiguous computational ad
 vantage over classical computers. Although several quantum algorithms exhi
 bit an advantage when compared to the best-known classical algorithms for 
 the same problem\, it is hard to guarantee that future algorithmic develop
 ments will not erase these advantages.\n\nRecently\, a considerable resear
 ch effort has been devoted towards demonstrating a more reliable quantum a
 dvantage by considering the problem of sampling from certain quantum circu
 its that could conceivably be implemented in the near-term\, such as the p
 roblems of boson sampling\, IQP sampling or sampling from random quantum c
 ircuits. The existence of an efficient classical simulation of these probl
 ems would have strong implications in complexity theory\, such as the coll
 apse of the Polynomial Hierarchy\, and thus is believed to be highly unlik
 ely. Unfortunately\, these sampling problems are rather artificial\, in th
 at they were constructed with the primary purpose of being hard to simulat
 e classically.\n\nIn this work\, we focus on demonstrating quantum advanta
 ge for the problem of sampling from energy measurements on easy-to-prepare
 \, product quantum states. We give examples of local Hamiltonians and regi
 mes of resolution and error parameters characterizing the measurement that
  can be efficiently reached by quantum devices\, while providing strong co
 mplexity theoretic evidence for the impossibility of efficient classical m
 ethods to simulate such measurements. We believe this is an important step
  towards bringing quantum advantage demonstrations to more physically moti
 vated problems\, occurring naturally in many-body physics.
LOCATION:MR14\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR