Quantum computation is widely regarded as being more powerful than classical computation. But despite great successes such as Shor’s quantum factoring algorithm, we still have relatively little understanding of how to characterise and effectively exploit the extra quantum computational power. The notion of classical simulation of a quantum computation provides a valuable theoretical tool for obtaining insights into both the possibilities and limitations of quantum computing.
In these lectures we will give an exposition of some principal results in this area with the following topics (subject to time and interest): an introduction to some relevant concepts from computational complexity and the notion of (strong and weak) classical simulation; discussion of the role of entanglement in quantum computational speed-up; classical simulation of Clifford circuits and the Gottesman-Knill theorem; some extensions of Clifford circuits illustrating the power of additional quantum resources; introduction to matchgate circuits and their simulation via the Jordan- Wigner formalism; the unexpected hardness of commuting quantum circuits; further probabilistic methods for classical simulation, and other recent results.
| Lecture 1 | Lecture 2 |
Lecture 3 |
I will start by reviewing the main ingredients for a universal quantum computer in the circuit model: universal sets of gates, the importance of restricting input states and output measurements, etc. Then I will review the basics of alternative models of quantum computation, such as measurement-based quantum computation and models which use linear optics (e.g. the KLM scheme and Boson Sampling). By mixing and matching the various ingredients, we will identify different combinations which yield interesting regimes in terms of computational power: full universal quantum (or classical) computation, simulable quantum dynamics, or an intermediate or incomparable computational power (e.g. IQP, Boson Sampling, permutational quantum computing, DQC-1). This line of research helps identify what’s essential and what’s accessory for the quantum computational advantage, with practical implications for experimental implementations. I will give special attention to recent experimental progress in specialized linear optical computers to solve the Boson Sampling problem, which I will describe in some detail.
