Learning Outcomes
On successful completion of the course students should be able
-
To understand basic concepts of computability and computational complexity.
-
To master the quantum computational model.
-
To design, analyse and implement quantum algorithms.
Syllabus
- Computability and complexity
- Problems and algorithms.
- Turing machines and computability.
- Computational complexity.
- Quantum computation and algorithms
- The quantum computational model.
- Introduction to quantum algorithms.
- Algorithms based on phase amplification.
- Algorithms based on the quantum Fourier transform.
- Case studies in quantum algorithmics.
Summaries (2025-26)
T Lectures
| Sep 15 (17:00 - 19:00) |
Introduction to Quantum Computation and the course dynamics
(slides).
Revisiting computability and computational complexity
(notes). |
| Sep 22 (16:00 - 18:00) |
Computability and decidability. Turing machines. The Church-Turing thesis and its physical counterpart
(notes). |
| Sep 29 (16:00 - 18:00) |
Introduction to quantum algorithms. The Deutsch algorithm
(slides).
|
| Oct 6 (16:00 - 18:00) |
The phase kick-back technique. Analysis of two algorithms: Deutsh-Joza and Bernstein-Vazirani
(slides). |
TP Lectures
| Sep 17 (09:00 - 11:00) |
Diagnostic exercise. |
| Sep 24 (09:00 - 11:00) |
Superposition and quantum interference
(slides).
Revisiting computational complexity
(notes). |
| Oct 1 (09:00 - 11:00) |
Exercises (on background notions): Hilbert spaces and quantum gates
(exercises 1). |
| Oct 8 (09:00 - 11:00) |
Exercises (on quantum gates, and phase kick-back algorithms)
(exercises 2). |
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.
-
C. Moore and S. Mertens The nature of computation. Oxford
University Press, 2011.
Quantum Computation and Algorithms
-
M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (10th
Anniversary Edition). Cambridge University Press, 2010
-
N. S. Yanofsky and M. A. Mannucci. Quantum Computing for Computer Scientists. Cambridge
University Press, 2008.
-
E. Rieffel and W. Polak. Quantum Computing: A Gentle Introduction. MIT Press, 2011.
-
A. M. Dalzell, S. Mcardle, et al. Quantum Algorithms. Cambridge
University Press, 2025.
-
W. Scherer. Mathematics of Quantum Computing. Springer, 2019.
Other (useful) readings
-
N. S. Yanofsky. The Outer Limits of Reason. MIT Press, 2013.
-
S. Aaronson. Quantum Computing since Democritus. Cambridge
University Press, 2013.
-
J. Preskill Quantum Computing in the NISQ era and beyond. Quantum 2, 79, 2018.
Links
Pragmatics
Lecturers
Assessment
- Individual assignment on quantum algorithms,
with written report and oral defense (40%)
-
Individual written test (60%)
Contact
- Appointments - Wed, 18:00-20:00 and Fri, 18:00-20:00 (please send an email the day before)
- Email: lsb at di dot uminho dot pt
- Last update: 2025.10.07