Open Collections

Simulating quantum computers with probabilistic methods

University of British Columbia. Department of Physics and Astronomy; Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics; Pacific Institute for the Mathematical Sciences; Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.)

The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. From a fundamental point of view, such an investigation sheds light on the intrinsic computational power harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-up over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. In this talk we discuss novel classical simulation methods that are centered on probabilistic methods ('weak simulation'). We show how these techniques outperform existing methods that rely on the exact computation of measurement probabilities ('strong simulation'). Using weak simulation methods, several new classes of simulatable quantum circuits are generated. For example, we show that various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform an! d other circuits are classically simulatable. Finally, we focus on famous quantum algorithms and investigate the origin of their computational power, or their lack thereof.

Presentation

eng

Vancouver : University of British Columbia Library

10.14288/1.0103166

Non UBC

Postdoctoral

DSpace