Quantum Computation 2025/26

Learning Outcomes

On successful completion of the course students should be able

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.

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).
Oct 13 (16:00 - 18:00)	Quantum approach to unstructured search problems. The Grover's algorithm (slides).
Oct 20 (16:00 - 18:00)	Quantum fundamentals with pennylane: Superposition, interference, entanglement and universal gate sets. (notebook from class).
Oct 27 (16:00 - 18:00)	Simon’s algorithm and its generalisations (slides). Complementary notes on group theory (notes)
Nov 3 (16:00 - 18:00)	Meeting at ECUM "A Segunda Revolução Quântica: ciência fundamental e novas tecnologias" part of the celebration for the international year of quantum science and technology
Nov 10 (16:00 - 18:00)	Phase estimation and the quantum Fourier transform. (slides).

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).
Oct 15 (09:00 - 11:00)	Quantum computing introduction with pennylane (slides) and (notebook from class).
Oct 22 (09:00 - 11:00)	Deutsch algorithm (notebook from class) and written notes (slides)
Oct 29 (09:00 - 11:00)	(to be re-scheduled)
Nov 5 (09:00 - 11:00)	Grover's algorithm (notebook from class) and written notes (slides)
Nov 12 (09:00 - 11:00)	Exercises (on grover algorithm and amplitude amplification) (exercises 3).

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.

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.

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.

Individual assignment on quantum algorithms, with written report and oral defense (40%)
Individual written test (60%)

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.11.11