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 and analyse quantum algorithms.
• To implement and run quantum algorithms in the Qiskit software development kit.

Syllabus

• Computability and complexity
  • Mathematical backgound: sets, orders, groups.
  • Turing machines and computability.
  • Computational complexity. Algorithms and complexity classes.
• 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 (2023-24)

T Lectures

Sep 22 (11:00 - 13:00)	Introduction to Quantum Computation and the course dynamics. (slides) Mathematical background for the study of computability and computational complexity. (notes).
Sep 27 (09:00 - 11:00)	Computability. The halting problem. Turing machines. (notes). Recommended additional reading: David Deutsch 1985 paper "Quantum theory, the Church-Turing principle and the universal quantum computer" (link).
Sep 29 (11:00 - 13:00)	Introduction to quantum algorithms. Deutsch algorithm: A simple algorithm with exponential quantum advantage. (slides)
Oct 6 (11:00 - 13:00)	Computational Complexity. The asymptotic notation. Case study: closure operations. (Lecture notes 3)
Oct 13 (11:00 - 13:00)	Quantum complexity (Lecture notes 3). Debate on the "Quantum theory, the Church-Turing principle and the universal quantum computer" paper
Oct 20 (11:00 - 13:00)	Quantum algorithms: the pahse kick-back pattern. Bernstein-Varizani algorithm. Deutsch-Joza algorithm. (slides)
Oct 27 (11:00 - 13:00)	Quantum algorithms: unstructured search and Grover's algorithm. (slides)
Nov 3 (11:00 - 13:00)	Generalizing Grover's algorithm. The amplitude amplification technique. (slides)
Nov 10 (11:00 - 13:00)	Simon's algorithm and its generalizations. Introduction to the hidden subgroup problem. (slides) (complementary notes on groups)
Nov 17 (11:00 - 13:00)	An algorithm for quantum phase estimation. The quantum Fourier transform. (slides) (solutions to the exercises)
Nov 24 (11:00 - 13:00)	Case study: quantum protocols for secure multi-party computation. (slides) (Jupyter Notebook)
Jan 3 (09:00 - 11:00)	The quantum Fourier transform (slides). Application to eignevalue estimation (slides).
Jan 5 (11:00 - 13:00)	An algorithm for order-finding and its role in Shor's algorithm (slides). Quantum walks (Jupyter Notebook).

TP Lectures

Sep 13 (09:00 - 11:00)	Algebra of quantum operations (Exercises 1)
Sep 20 (09:00 - 11:00)	Introduction to Qiskit; Quantum Operations and Simulations (Jupyter Notebook 1)
Oct 4 (09:00 - 11:00)	Computability. The halting problem. Turing machines. (Exercises - Lecture notes 2)
Oct 11 (09:00 - 11:00)	Complexity classes. (Lecture note 3)
Oct 18 (09:00 - 11:00)	The Deutsch-Jozsa Algorithm; Simulate Real Devices (Jupyter Notebook 2)
Oct 25 (09:00 - 11:00)	Bernstein-Vazirani Algorithm; Simon's Algorithm; Noise Models (Jupyter Notebook 3)
Nov 8 (09:00 - 11:00)	Grover's Algorithm (Jupyter Notebook 4)
Nov 15 (09:00 - 11:00)	Quantum Counting and Quantum Fourier Transform (QFT) (Jupyter Notebook 5)
Nov 22 (09:00 - 11:00)	Quantum Counting (part 2) and Quantum Phase Estimation (QPE) (Jupyter Notebook 6)
Nov 29 (09:00 -11:00)	Quantum Period Finding (QPF) (Jupyter Notebook 7)
Dez 6 (09:00 - 11:00)	Shor's Algorithm (Jupyter Notebook 8)
Dez 13 (09:00 - 11:00)	Repetition Codes ( Jupyter Notebook 9)

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
• Quantum and Linear Optical Computation Group at INL
• Logic and Formal Methods Group

Pragmatics

Lecturers

• Luís Soares Barbosa
• Ana Neri

Assessment

• Group training assignment on programming quantum algorithms, with written report and individual, oral defense (60%)

  (Project)

  Oral Discussion: 16th January 2024, 15h, DI(7) 0.04

  Group	Schedule
  1	15:00
  2	15:20
  3	15:40
  4	16:10
  5	16:30
  6	16:50

  
  
• Individual test (40%):

  18th January 2024, 15.30h, room DI 0.04

• Results (Training Assignment + Test)
• Exam:

  25 January, 9h, Building 2, Room 1.12

• Results (Training Assignment + Test or Exam)

Contact

• Appointments - Luis: Wed, 18:00-20:00 and Fri, 18:00-20:00 (please send an email the day before)
• Appointments - Ana: Thu, 16:00-18:00 and Fri, 14:00-16:00 (please send an email the day before)
• Email: lsb at di dot uminho dot pt (Luis) and ana dot i dot neri at inesctec dot pt (Ana)
• Last update: 2024.01.26