BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Simulating Quantum Circuits with Sparse Output Distributions - Mar
 tin Schwarz\, Freie Universität Berlin
DTSTART:20160520T110000Z
DTEND:20160520T120000Z
UID:TALK65784@talks.cam.ac.uk
CONTACT:Steve Brierley
DESCRIPTION:We show that several quantum circuit families can be simulated
  efficiently classically if it is promised that their output distribution 
 is approximately sparse i.e. the distribution is close to one where only a
  polynomially small\, a priori unknown subset of the measurement probabili
 ties are nonzero. Classical simulations are thereby obtained for quantum c
 ircuits which---without the additional sparsity promise---are considered h
 ard to simulate. Our results apply in particular to a family of Fourier sa
 mpling circuits (which have structural similarities to Shor's factoring al
 gorithm) but also to several other circuit families\, such as IQP circuits
 . Our results provide examples of quantum circuits that cannot achieve exp
 onential speed-ups due to the presence of too much destructive interferenc
 e i.e. too many cancelations of amplitudes. The crux of our classical simu
 lation is an efficient algorithm for approximating the significant Fourier
  coefficients of a class of states called computationally tractable states
 . The latter result may have applications beyond the scope of this work. I
 n the proof we employ and extend sparse approximation techniques\, in part
 icular the Kushilevitz-Mansour algorithm\, in combination with probabilist
 ic simulation methods for quantum circuits.
LOCATION:MR13\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR