Topics in Classical and Quantum Computing

$ID = get_the_ID();
add_post_meta($ID, 'Author', 'A.Scardicchio', True);
add_post_meta($ID, 'Credits', '2', True);

$AUTHOR = get_post_meta(get_the_ID(),'Author',True);
$CREDITS = get_post_meta(get_the_ID(),'Credits',True);
echo "

by $AUTHOR ($CREDITS 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
  • Shor’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

Comments are closed.