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 principles and main techniques of quantum programming.
• To design and analyse quantum algorithms.
• To understand the basic elements of quantum programming languages and current implementations.
• To implement and run quantum algorithms in the Qiskit open-source software development kit for IBM Q quantum processors.

Syllabus

• Classical computational models, computability and complexity
• Principles of quantum computation and programming
• Quantum algorithms
• Programming in Qiskit
• Overview of quantum programming languages and quantum lambda-calculus

Summaries (2018-19)

T Lectures

• Feb 4: Introduction to the course (slides).

  Automata and automata morphisms. Probabilistic automata and quantum automata.

• Feb 11: Computational models and underlying algebraic structures: Monoids, orders, groups. (lecture notes)

• Feb 18: Introduction to computability. Turing machines. The halting problem. Church-Turing thesis. (lecture notes)

• Mar 4: Introduction to computability (conclusion).

• Mar 11: Introduction to computational complexity. (lecture notes)

• Mar 18: Introduction to quantum computing. Review of basic notions: quantum data; measurements; unitary transformations. Quantum gates. The circuit model. Deutsch's algorithm (simplified). (slides)

• Mar 25: Introduction to quantum algorithms. The Deutsch-Jozsa algorithm. Quantum search problems. Grover's algorithm. (slides)

• Apr 1 (Afonso Rodrigues): Grover search algorithm implementation in Qiskit. (Jupyter notebook)

• May 6 (Carlos Tavaress): Quantum simulation (Introdução à simulação quântica, aplicações e teoria relevante. Métodos de simulação quântica, digitais e analógicos: ténicas de modelação e codificação e algoritmos para caracterização do espectro de energia de um sistema quântico. Vantagem quântica e problemas QMA-completos. Concepção e demonstração no qiskit de um caso de estudo para simulação quântica para moléculas de Hidrogénio e hidreto de Lítio.) (slides)

• May 20: The structure of quantum algorithms. The Bernstein-Vazirani algorithm. Period-finding problems. Simon’s and Shor's algorithms. Quantum complexity. The BQP class. (slides)

• Missed: 15 and 22 Apr (Easter); 25 Feb and 29 Apr (lecturer's external mission); 13 May (Gata)

P Lectures

• Feb 5: Introduction to the practical component of the course.

  Problem Set 1 - Haskell. (exercises)

• Feb 12: Conclusion of Problem Set 1.

  Problem Set 2 - Algebra of quantum operations. (exercises)

• Feb 19: Conclusion of Problem Set 2. (auxiliar script)

• Mar 12: Problem Set 3 - Simulation of quantum circuits. (exercises)

• Mar 19: Conclusion of Problem Set 3.

• Mar 22: Introduction to QISKit and its components. (Jupyter notebook)

• Mar 26: Gates and basis. Quantum Teleportation. Deutsch–Jozsa algorithm. (Jupyter notebook)

• Apr 2: Conclusion of Grover search algorithm. Decomposition of CⁿNOT gates.

• Apr 9: Quantum Fourier transform - from theory to implementation. (Jupyter notebook)

• Apr 23: Period finding. Phase kickback. Quantum phase estimation. (Jupyter notebook)

• Apr 30: Arithmetic for quantum circuits: a quantum full adder. (Jupyter notebook)

• May 7: Quantum simulation of the Schrödinger equation. (Jupyter notebook)

• Missed 5 Mar (Carnival); 16 Apr (Easter); 14 May (Gata)

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, Algorithms and Programming

• M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press, 2010
• N. S. Yanofsky and M. A. Mannucci. Quantum Computing for Computer Scientists. Cambridge University Press, 2008.
• E. Rieffel and W. Polak. Quantum Computing: A Gentle Introduction. MIT Press, 2011.
• R. S. Lipton and K. W. Regan. Quantum Algorithms via Linear Algebra: A Primer. MIT Press, 2014.
• M. Ying. Foundations of Quantum Programming. Elsevier, 2016.

Bedtime readings

• N. S. Yanofsky. The Outer Limits of Reason. MIT Press, 2013.
• S. Aaronson. Quantum Computing since Democritus. Cambridge University Press, 2013.

Links

• Arca website
• Quantum Algorithms zoo
• The complexity zoo

Pragmantics

Lecturers

• Luís Soares Barbosa
• Afonso Rodrigues

Assessment

• Training assignment (40%): 10 June (with intermediate ckeckpoints)
• Written test (60%): 27 May: Results!
• FINAL MARKS available HERE!

Contact

• Appointments: Wed, 9-11 (please send an email the day before)
• Email: lsb at di dot uminho dot pt
• Last update: 2019.07.01