by A. Scardicchio (2 credits)
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.
Required knowledge:
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
Main topics
- 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