Computational Complexity and Extended Clifford Circuits

11:00 Thu 30 Aug – RED 351

11:00 Mon 03 Sep – RED 351

11:00 Wed 05 Sep – RED 359

11:00 Fri 07 Sep – RED 359

Biography. Dax Enshan Koh (Skoltech Summer Intern 2018 – Biamonte Group) is a PhD candidate in the Mathematics department at the Massachusetts Institute of Technology (MIT), advised by Professor Peter Shor. His current research interests include quantum computation and quantum information, computational complexity theory, classical simulation of quantum computation, foundations of quantum mechanics as well as the theoretical underpinnings of quantum supremacy experiments. Prior to MIT, Dax completed the Perimeter Scholars International (PSI) Master’s program in Physics at the Perimeter Institute for Theoretical Physics. Prior to PSI, Dax received his undergraduate degree from Stanford University, with a double major in Mathematics and Physics.

Synopsis. Are quantum computers more powerful than their classical counterparts? Even though it is widely conjectured that the answer is yes, the question remains open, at least in the standard computational complexity paradigm of polynomial-versus-exponential separation. In this course, I’ll introduce the basic notions of computational complexity theory that underlie this conjecture, and present evidence for it that is based on plausible complexity assumptions. I will describe how we could shed light on this question by using the framework of restricted models of quantum computation, an example of which is the class of extended Clifford circuits. I’ll show that by changing the ingredients of extended Clifford circuits, we can probe the boundary between classical and quantum computational power.

Lecture 1: The extended Church-Turing thesis and complexity classes. Models of computation・Turing machine model・Church-Turing thesis・extended Church-Turing thesis・computational problems・decision problems・complexity zoo: P, NP, NP-completeness, polynomial hierarchy, BPP, PP, PSPACE, BQP, #P.

・Michael Sipser. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.
・Sanjeev Arora, and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.

Lecture 2: Restricted models of quantum computation Restricted circuit models of quantum computation: IQP circuits, DQC1 circuits, matchgate circuits, Clifford circuits・relation to quantum supremacy・Pauli group・Clifford group・Gottesman-Knill Theorem.

Optional: F2 representation of Clifford group, stabilizer formalism

・Michael A. Nielsen, and Isaac L. Chuang. “Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences).” (2004).
・Daniel Gottesman. “The Heisenberg representation of quantum computers.” arXiv preprint quant-ph/9807006 (1998).

Lecture 3: Extended Clifford circuits Notions of classical simulation: weak simulation, strong simulation・extensions of Clifford circuits: product inputs, product outputs, adaptive Clifford circuits・fine-grained weak and strong simulation・complexity classification theorems for extended Clifford circuits.

・Richard Jozsa, and Maarten Van den Nest. “Classical simulation complexity of extended Clifford circuits.” Quantum Information & Computation, 14(7&8):633–648, (2014).
・Dax Enshan Koh. “Further extensions of Clifford circuits and their classical simulation complexities.” Quantum Information and Computation 17 (3&4), 0262-0282 (2017).

Lecture 4: Hardness of sampling Proofs of complexity classification theorems for extended Clifford circuits・postselection・Aaronson’s theorem・Bremner-Jozsa-Shepherd postselection trick・hardness of sampling

Optional topics: conjugated Clifford circuits, approximate notions of simulation.

・Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. The Royal Society (2010).
・Scott Aaronson. “Quantum computing, postselection, and probabilistic polynomial-time.” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. Vol. 461. No. 2063. The Royal Society (2005).
・(optional) Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh. “Complexity Classification of Conjugated Clifford Circuits.” arXiv preprint arXiv:1709.01805 (2017).

Linear algebra, basic familiarity with the circuit model of quantum computation. Prior knowledge of computational complexity not needed.

Dax Enshan Koh, PhD Candidate, Department of Mathematics, Massachusetts Institute of Technology.

Leave a Reply

Your email address will not be published. Required fields are marked *