Physical Sciences and Mathematics Commons^™

On The Complexity Of Boson Sampling Using Atoms In Optical Lattices, Gopikrishnan Muraleedharan

Physics & Astronomy ETDs

The extended Church-Turing thesis says that any computation that can be done by a physically realizable model of computers can be efficiently computed by the simplest model of classical computer, a Turing machine. Since the introduction of the concept of quantum computers, a central goal has been to find instances where the extended Church- Turing thesis fails. In the current noisy intermediate-scale quantum devices era, one looks for such instances that can be simulated on modest devices of small scale in the presence of noise. In this thesis, we work with one such problem, namely the Boson Sampling problem. We …