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 for IBM Q quantum processors.

Syllabus

• 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
  • Quantum programming in a functional setting.
  • Quantum programming in Qiskit

  Summaries (2020-21)

  T Lectures

  Virtual classroom: Join here every week
  • Feb 19: Introduction to Quantum Computation and the course dynamics (slides).

    Link for the first lecture (only): Join here

  • Feb 23:

    Background: Discrete mathematical structures -- sets and cardinality (lecture notes).

  • Mar 2:

    Background: Discrete mathematical structures -- groups (lecture notes).

  TP Lectures

  • Feb 26:

    Introduction to the practical component of the course.
    Problem Set 1 - Haskell -- (exercises) and (support material).
    Link: : here
    Solutions and other notes

  • Mar 5:

    Problem Set 2 - Algebra of quantum operations -- (exercises) and (support material).
    Link: : here

  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.

  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.

  Links

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

  Pragmatics

  Lecturers

  • Luís Soares Barbosa
  • Ana Neri

  Assessment

  • Training assignment (60%): to be discussed on 25 May (with intermediate ckeckpoints)
  • Individual assynchronous test (40%): 4 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 - 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.03.5