Statistical Physics @ Trieste blackboard
Course: Topics in classical and quantum computing
by Antonello Scardicchio



immagine

 



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