Classical simulation of quantum computations

The notion of efficient classical simulation of a quantum computation provides an explicit tool for exploring the rich relationship between classical and quantum computational complexity. In this talk we will introduce this notion and discuss a variety of interesting associated applications and constructions. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. We will introduce Clifford computations and show with some striking examples, how the classical simulation complexity can change dramatically with the inclusion of some seemingly modest extra resources. Then, inspired by the Clifford simulation method, we will outline a general formalism based on some elementary Lie algebra theory, for constructing other classes of classically simulatable quantum computations.  We will see that this method can be applied to demonstrate the efficient classical simulation of Valiant's matchgate circuits.