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.
Syllabus
 Computability and complexity
 Mathematical backgound: sets, orders, groups.
 Turing machines and computability.
 Computational complexity. Algorithms and complexity classes.
 Complexity in quantum computation.
 Quantum computation and algorithms
 The quantum computational model (gates, measurements, and circuits).
 Introduction to quantum algorithms.
 Algorithms based on phase amplification.
 Algorithms based on the quantum Fourier transform.
 Case studies in quantum algorithmics.

Quantum programming
 Quantum programming in Qiskit and other tools
Summaries (202122)
T Lectures
TP Lectures

Oct 6 (11:00  13:00):
Mathematical foundations of quantum computing pt. 1: vector space, operator, and tensor
(lecture notes).

Oct 13 (11:00  13:00):
Mathematical foundations of quantum computing pt. 2: basis and matrix representation
(lecture notes).

Oct 20 (11:00  13:00):
Mathematical foundations of quantum computing pt. 3: inner product, norm, isometry, and unitary operator.
Postulates of quantum computing
(lecture notes).

Oct 27 (11:00  13:00):
Basic aspects of Entanglement, one of the surprising quantum phenomena.
Quantum teleportation (handson via Qiskit)
(Qiskit circuit 1)
(Qiskit circuit 2).

Nov 03 (11:00  13:00):
Continuation of the previous lecture
(TPC).

Nov 10 (11:00  13:00):
Exercises with the phase kickback technique. An overview of the different functionalities
of Qiskit illustrated with examples from previous lectures
(notebook).

Nov 17 (11:00  13:00):
(Generalised) DeutschJosza in Qiskit
(notebook).

Nov 24 (11:00  13:00):
Implementation of conditional phase shift via "not", Hadamard, and Toffoli gates. Grover in Qiskit. A brief introduction to the satisfiability problem.
(TPC).

Dec 14 (11:00  13:00): Discussion of previous homeworks. Presentation of the practical assignment.
Exercises involving Simon's algorithm.
(Assignment).

Jan 05 (11:00  13:00): An introduction to a new paragigm in quantum computation: measurementbased quantum computation (by Ernesto Galvão) (slides).
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

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.

J. Preskill Quantum Computing in the NISQ era and beyond. Quantum 2, 79, 2018.
Links
Pragmatics
Lecturers
Assessment
 Training assignment on programming quantum algorithms (60%): to be discussed on 2 February 2022, 913h, with final reports due on 9th February
(with intermediate ckeckpoints and deliverables to be fixed in the TP lectures)

Individual assynchronous test (40%): to be divided into 2 or 3 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  Renato: Thu, 14:0018:00 (please send an email the day before)
 Email: lsb at di dot uminho dot pt (Luis) and nevrenato at gmail dot com (Renato)
 Last update: 2022.01.11