A set of lectures on Classical and Quantum Computation at SISSA.

This syllabus refers to the the lectures that took place at SISSA in May 2013.

The topics covered where:

Automata; Languages; Turing Machines; Decidability

Complexity classes: P, Time hierarchy theorem, NP, co-NP, completeness

Randomized algorithms, BPP, RP, co-RP

The polynomial hierarchy

Definition of Quantum Computation

Entanglement, its measures and power

Universal QC; quantum circuit; Solovay-Kitaev theorem

BQP; Grover’s algorithm and its optimality; phase estimation; Shor’s algorithm

The class QMA and some QMA-complete problems

Adiabatic quantum computation

Topological quantum memory; anyons and computation

The 2015 class will probably have a slightly different syllabus and will take place at SISSA in spring 2015.