Quantum Information Science II, Part 2 - Efficient Quantum Computing - fault tolerance and complexity

Cluster states and graph states – examples I

Models of quantum computation – perspective

Fault-tolerant quantum circuit construction example

Complete problems and the generality of complexity class definitions – reductions

Post-BPP is contained in Approximate Counting

Fault-tolerant quantum computation – ingredients I

Complexity and hardness – lecture introduction

The role of classical error correction in FTQC – measurement

Post-selection

Fault-tolerant quantum computation – ingredients II

Complexity classes – BPP and BQP

The threshold theorem – proof sketch – level 1

PostBQP is equal to Exact Counting in complexity

Fault-tolerant quantum computation – introduction

Complexity classes – deterministic time

The threshold theorem – proof sketch – recursing

Principles of fault tolerance

Fault-tolerant quantum computation – theorem idea

The threshold theorem – statement

The toric code – boundary map

Complexity classes – NP

Fault-tolerant quantum computation – theorem overview

Promise problems – sampling problems – and relations

Fault-tolerant quantum gates on 5-qubit and 7-qubit codes

Quantum gate compiling – significance of the Solovay-Kitaev theorem for BQP