BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Simulating Quantum Circuits with Sparse Output Dis
tributions - Martin Schwarz\, Freie Universität Be
rlin
DTSTART;TZID=Europe/London:20160520T120000
DTEND;TZID=Europe/London:20160520T130000
UID:TALK65784AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/65784
DESCRIPTION:We show that several quantum circuit families can
be simulated efficiently classically if it is prom
ised that their output distribution is approximate
ly sparse i.e. the distribution is close to one wh
ere only a polynomially small\, a priori unknown s
ubset of the measurement probabilities are nonzero
. Classical simulations are thereby obtained for q
uantum circuits which---without the additional spa
rsity promise---are considered hard to simulate. O
ur results apply in particular to a family of Four
ier sampling circuits (which have structural simil
arities to Shor's factoring algorithm) but also to
several other circuit families\, such as IQP circ
uits. Our results provide examples of quantum circ
uits that cannot achieve exponential speed-ups due
to the presence of too much destructive interfere
nce i.e. too many cancelations of amplitudes. The
crux of our classical simulation is an efficient a
lgorithm for approximating the significant Fourier
coefficients of a class of states called computat
ionally tractable states. The latter result may ha
ve applications beyond the scope of this work. In
the proof we employ and extend sparse approximatio
n techniques\, in particular the Kushilevitz-Manso
ur algorithm\, in combination with probabilistic s
imulation methods for quantum circuits.
LOCATION:MR13\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Steve Brierley
END:VEVENT
END:VCALENDAR