Course syllabus
COURSE DETAILS
This is a survey paper on computational and descriptive complexities and applications.
Weeks 1-6 introduce descriptive complexity, algorithmic randomness and a form of quantum randomness followed by a brief theoretical and practical introduction to quantum computing which includes the quantum gates and adiabatic models and applications.
Weeks 7-12 cover the complexity classes P and NP, NP-completeness, space complexity, intractability, BPP and randomised algorithms, and more detail on theoretical quantum computing: mathematical background, BQP, Shor's factoring algorithm.
LECTURES:
Tu 16:00 - 17:00 Commerce A, Room G14
Th 14:00 - 15:00 303-G15
Fr 16:00 - 17:00 Commerce A, Room G01
TEACHING STAFF
Weeks 1-6
Office hours by appointment
Weeks 7-12 Office 810-847 in Short Street
andre@cs.auckland.ac.nz
Office hours: Tu 2:30-3:30
Class Rep: TBA
Useful text: Michael Sipser, Introduction to the theory of computation, 2d or 3d edition
ISBN13: 978-1-133-18779-0
Nielsen and Chuang: Quantum Computation and Quantum Information, 2d edition, 2010.
ASSESSMENT
50% exam; 20% test; 30% assignments
Course summary:
Date | Details | Due |
---|---|---|