COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |
University of Cambridge > Talks.cam > CQIF Seminar > Simulating Quantum Circuits with Sparse Output Distributions
Simulating Quantum Circuits with Sparse Output DistributionsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Steve Brierley. 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 probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which—-without the additional sparsity promise—-are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor’s factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation 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. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits. This talk is part of the CQIF Seminar series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsCambridge Risk and Uncertainty Series Cambridge Climate Institute of Astronomy Extra Talks Junior Geometry Seminar Mechanisms of Language Change Research Cluster – student run event 2012 DAK Group MeetingsOther talksDisease Migration Cerebral organoids: modelling human brain development and tumorigenesis in stem cell derived 3D culture Lung Cancer. Part 1. Patient pathway and Intervention. Part 2. Lung Cancer: Futurescape The Digital Railway - Network Rail Whence the force of the law? John Rawls and the course of American legal philosophy Handbuchwissenschaft, or: how big books maintain knowledge in the twentieth-century life sciences |