Classical simulation complexity of restricted models of quantum computation
Dax Enshan Koh
Abstract
Restricted models of quantum computation are mathematical models which describe quantum computers that have limited access to certain resources. Well-known examples of such models include the boson sampling model, extended Clifford circuits, and instantaneous quantum polynomial-time circuits. While unlikely to be universal for quantum computation, several of these models appear to be able to outperform classical computers at certain computational tasks, such as sampling from certain probability distributions. Understanding which of these models are capable of performing such tasks and characterizing the classical simulation complexity of these models--i.e. how hard it is to simulate these models on a classical computer--are some of the central questions we address in this thesis. Our first contribution is a classification of various extended Clifford circuits according to their classical simulation complexity.