## Physics & Astronomy ETDs

#### Publication Date

Spring 3-20-2020

#### Abstract

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

Physics

#### Level of Degree

Doctoral

#### 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

#### Language

English

#### Keywords

Sampling complexity, Boson sampling, quantum information

#### Document Type

Thesis

#### Recommended Citation

Muraleedharan, Gopikrishnan. "On the complexity of Boson Sampling using atoms in optical lattices." (2020). https://digitalrepository.unm.edu/phyc_etds/241