Physics & Astronomy ETDs

Publication Date

Spring 3-20-2020


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 extend the physical paradigm of the Boson Sampling problem from photons in linear optics to bosonic atoms in optical lattices. The experimental implementations using photons have many limitations such as the preparation of single-photon states and photon counting measurement. We show that the required features to demonstrate “quantum computational supremacy” can be achieved using noninteracting bosonic atoms in a 1D tight-binding model. We show that using noninteracting bosonic atoms in 1D time-dependent optical lattice we can implement the Boson Sampling problem using quantum control. This physical platform is potentially scalable than photons in linear optics with fewer preparation and measurement errors. We also show that the complexity of sampling in the presence of weak on-site interactions between the atoms is the same as that of sampling noninteracting bosons. We further show that random time-dependent Hamiltonian evolution can generate pseudo-random unitary transformations that are close to Haar random unitary transformation required to implement approximate Boson Sampling.

Degree Name


Level of Degree


Department Name

Physics & Astronomy

First Committee Member (Chair)

Ivan H. Deutsch

Second Committee Member

Akimasa Miyake

Third Committee Member

Carlton M. Caves

Fourth Committee Member

Rolando Somma




Sampling complexity, Boson sampling, quantum information

Document Type