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.
- 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 in a functional setting.
- Quantum programming in Qiskit
New Virtual classroom: Join
here every week
Introduction to Quantum Computation and the course dynamics (slides).
Link for the first lecture (only): Join
Background: Discrete mathematical structures -- sets and cardinality (lecture notes).
Background: Discrete mathematical structures -- groups (lecture notes).
Introduction to computability. Turing machines and universal Turing machines. Recursive functions (lecture notes).
Introduction to computational complexity. Basic notions and tools. Complexity classes (lecture notes).
Introduction to quantum algorithms. Phase kick-back. The Deutsch-Joza algorithm. (slides).
Link for this lecture (only): Join
Amplitude amplification as an algorithimic technique. Search problems and Grover's algorithm. (slides).
Further quantum algorithms: Bernstein-Vazirani and Simon. Variants. (slides).
Case study: Quantum Bayesian decision making (slides) (paper).
The quantum phase estimation problem (slides).
May 7 (14.30):
Quantum Fourier transform. The eigenvalue estimation problem (slides; first section)
Link for this lecture (only): Join
Case study: Quantum reinforcement learning (slides).
Resolution of the QFT exercise (note).
The algorithm of Shor. Reduction to order-finding. (slides)
The hidden subgroup problem and its instances: finding the period of a periodic function; the discrete logarithm problem. (slides)
Case study: Quantum walks. (notebook)
Introduction to the practical component of the course.
Problem Set 1 - Haskell -- (exercises) and (support material).
Solutions and other notes
Problem Set 2 - Algebra of quantum operations -- (exercises) and (support material).
Problem Set 3 - Simulation of quantum circuits -- (exercises) and (support material).
Conclusion of Problem Sets 3 and 2.
Problem Set 4 - Quantum projects -- (exercises).
Conclusion of Problem Set 4.
Qiskit 1: Quantum Operations and Simulations -- (exercises).
Qiskit 2 -- (exercises)
Working with the IBM Q backends.
Quantum Teleportation Protocol.
Qiskit 3 -- (exercises)
Solving a 3-SAT problem with Grover's algorithm (Part 1).
Qiskit 4 -- (exercises)
Solving a 3-SAT problem with Grover's algorithm.
Qiskit 5 -- (exercises)
Quantum State Tomography;
Maesurement Errors Mitigation;
Qiskit 6 -- (exercises)
Quantum Fourier Transform
Qiskit 7 -- (exercises)
Quantum Period Finding
Quantum Phase Estimation
Qiskit 8 -- (exercises)
Qiskit 9 -- (exercises)
Variational Quantum Eigensolver with Qiskit Aqua
Discussing ongoing experimental assignments.
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.
Some extra references on quantum algorithms
N. S. Yanofsky. The Outer Limits of Reason. MIT Press, 2013.
S. Aaronson. Quantum Computing since Democritus. Cambridge
University Press, 2013.
FINAL MARKS available here
Training assignment (60%): to be discussed on 25 May
(with intermediate ckeckpoints)
Individual assynchronous test (40%): 2 exercises proposed along the T lectures
Problem 1 (16-30 March)
Problem 2 (6-27 May)
- 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.06.29