Learning Outcomes
On successful completion of the course students should be able

To understand basic concepts of computability, computational complexity, and underlying mathematical structures.

To master the quantum computational model.

To design and analyse quantum algorithms.

To implement and run quantum algorithms in the Qiskit opensource software development kit for IBM Q quantum processors.
Syllabus
 Computability and complexity
 Mathematical backgound: sets, orders, groups, automata.
 Turing machines and computability.
 Computational complexity. Agorithms and complexity classes.
 Quantum computation and algorithms:
 The quantum computational model (circuits, gates, measurements).
 Introduction to quantum algorithms.
 Algorithms based on phase amplification.
 Algorithms based on the quantum Fourier transform.
 Case studies in quantum algorithmics.
 Quantum complexity.
 Quantum programming
 Quantum programming in a functional setting.
 Quantum programming in Qiskit
Summaries (202021)
T Lectures
Virtual classroom: Join
here every week

Feb 19:
Introduction to Quantum Computation and the course dynamics (slides).
Link for the first lecture (only): Join
here

Feb 23:
Background: Discrete mathematical structures  sets and cardinality (lecture notes).

Mar 2:
Background: Discrete mathematical structures  groups (lecture notes).
TP Lectures
Bibliography
Computability and Computational Complexity

H. R. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation. Prentice
Hall (2nd Ed), 1997.

S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge
University Press, 2009.
Quantum Computation and Algorithms

M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (10th
Anniversary Edition). Cambridge University Press, 2010

E. Rieffel and W. Polak. Quantum Computing: A Gentle Introduction. MIT Press, 2011.

F. Kaye, R. Laflamme and M. Mosca. An Introduction to Quantum Computing. Oxford University Press, 2007.

N. S. Yanofsky and M. A. Mannucci. Quantum Computing for Computer Scientists. Cambridge
University Press, 2008.

W. Scherer. Mathematics of Quantum Computing. Springer, 2019.
Bedtime readings

N. S. Yanofsky. The Outer Limits of Reason. MIT Press, 2013.
 S. Aaronson. Quantum Computing since Democritus. Cambridge
University Press, 2013.
Links
Pragmatics
Lecturers
Assessment
 Training assignment (60%): to be discussed on 25 May
(with intermediate ckeckpoints)
 Individual assynchronous test (40%): 4 exercises proposed along the T lectures
Contact
 Appointments  Luis: Wed, 18:0020:00 and Fri, 18:0020:00 (please send an email the day before)
 Appointments  Ana: Wed, 17:0019:00 (please send an email the day before)
 Email: lsb at di dot uminho dot pt (Luis) and aicneri at gmail dot com (Ana)
 Last update: 2021.03.5