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.

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 (2021-22)

T Lectures

• Oct 6 (09:00 - 11:00): Introduction to Quantum Computation and the course dynamics (slides).

• Oct 13 (09:00 - 11:00): Computability and computational complexity: motivating example (Eulerian and Hamiltonian paths). Proof and computation. A brief background tour: Sets, functions, relations. (lecture notes).

• Oct 20 (09:00 - 11:00): Conclusion of the previous lecture. Introduction to computability. The halting problem. The Church-Turing and the Physical Church-Turing conjectures. A concrete model of computation: Turing machines. (lecture notes).

• Oct 27 (09:00 - 11:00): Conclusion of the previous lecture (Turing machines) Introduction to computational complexity. The asymptotic notation. Examples. Complexity classes (P, BPP, PSPACE, NP). NP-complete and NP-hard problems. The conjecture P = NP. (lecture notes).

• Nov 3 (09:00 - 11:00): Quantum computation and quantum algorithms. The Deutsch algorithm and the "phase kick-back" tecnique. (slides).

• Nov 10 (09:00 - 11:00): Generalizing the Deutsch procedure: the Deutsch-Joza algorithm. Quantum search over unstructured spaces. The Grover iterator: idea, implementation, examples. (slides).

• Nov 24 (09:00 - 11:00): Analysis of Grover's algorithm. How to compute the required number of iterations. Generalizations of this algorithm. (slides). Analysis of the Bernstein-Vazirani algorithm iterator: idea, implementation, examples. (slides).

• Dec 15 (09:00 - 11:00): Simon's problem and the corresponding quantum algorithm. Generalizations. The hidden subgroup problem (motivation) (slides). Complementary reading: a note on groups.

• Dec 17 (11:00 - 13:00) Room DI 1.10: Algorithms for phase estimation. The quantum Fourier transform. (slides).

• Jan 5 (09:00 - 11:00): Applications of the quantum Fourier transform: the problem of estimating eigenvalues. (slides).

  Case study: Implementing quantum walks in Qiskit (by Jaime Santos) (zip: slides + code).

• Jan 12 (11:00 - 13:00): Prime factorization and its reduction to the order-finding problem. Shor algorithm. Conclusion of the course. (slides).

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 (hands-on 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) Deutsch-Josza 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: measurement-based 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

• The complexity zoo
• Quantum Algorithms zoo
• IBM Quantum Experience
• Arca website

Pragmatics

Lecturers

• Luís Soares Barbosa
• Renato Neves

Assessment

• Training assignment on programming quantum algorithms (60%): to be discussed on 2 February 2022, 9-13h, 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:00-20:00 and Fri, 18:00-20:00 (please send an email the day before)
• Appointments - Renato: Thu, 14:00-18: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