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 open-source 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 (2020-21)
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:00-20:00 and Fri, 18:00-20:00 (please send an email the day before)
- Appointments - Ana: Wed, 17:00-19: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