Topics in classical and quantum computing
by Antonello Scardicchio
The course is aimed at physicists that want to take a look at
the current status of classical and quantum computing. I will
provide a phyisicist's perspective starting from the basics of
computer science and presenting a selection of the recent research
topics, among which topological quantum computing, adiabatic
quantum computing and local hamiltonian problems.
I will require a good knowledge of quantum
mechanics (finite number of degrees of freedom) as I will not have
time to review it. The topic "Topological QC" will require
knowledge of some concepts of field theory.
The reference books:
- Sipser 'Introduction to the theory of computation'
- Kitaev et al. 'Classical and quantum computation'
- Nielsen and Chuang
- Preskill's notes
- Introduction; Turing machines
- Turing machines and complexity: P, NP, PSPACE...
- Classical circuits
- Completeness for NP: Cook and Levin's theorem.
- More NP-complete problems and physics.
- Probabilistic algorithms; BPP
- More on complexity classes: a zoo
- Quantum computation: quantum circuits.
- More on entanglement.
- Grover's algorithm
- Schor's algorithm
- Adiabatic QC
- Quantum complexity classes: QMA and local hamiltonians
- QMA and local hamiltonians: finding the simplest QMA-complete problems
- Topological QC 1
- Topological QC 2