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
  • 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 the quantum Fourier transform.
  • Algorithms based on phase amplification
  • Quantum complexity.
• Quantum modelling and programming in Qiskit
• Advanced topics in quantum computation
  • Hybrid quantum programming.
  • Quantum tomography.
  • Formal models for quantum computation.

Summaries (2019-20)

T Lectures

• Feb 6: Introduction to Quantum Computation and the course dynamics (slides).

  Background: Discrete mathematical structures -- sets, orders, groups and automata (lecture notes).

• Feb 13: Conclusion of the previous lecture (orders, groups and automata - non deterministic, probabilistic and quantum)

• Feb 20: Computability. Turing machines and the halting problem. Primitive recursive and recursive functions. (lecture notes).

• Feb 27: Computational complexity: basic definitions and examples. Complexity classes. What has quantum to say.

  (lecture notes).

• Mar 5: CANCELLED: Lecturer in UM mission

• Mar 12: CANCELLED: Covid-19 preventive determination

• Mar 19: (Non presencial lecture) The quantum computational model. Introduction to quantum algorithms.

  Lecture support: (slides)
  Live session 1: Join here!

• Mar 26: CANCELLED

• Apr 2: (Non presencial lecture) Phase amplification. Quantum search through the Grover algorithm.

  Lecture support: (slides)
  Problem 1: (until 9 April)
  Live session 2: Join here! (check the meeting id at your academic mailbox)

• Apr 16: (Non presencial lecture) Revisiting `quantum parallelism'. The Bernstein-Vazirani algorithm. Introduction to hidden group problems through the Simon's algorithm.

  Lecture support: (slides)
  Live session 3: Join here!

• Apr 23: (Non presencial lecture) The quantum Fourier transform. Application to the phase estimation problem.

  Lecture support: (slides)
  Live session 4: Join here!

• Apr 30: CANCELLED

  Problem 2: (until 15 May)
  

• May 7: (Non presencial lecture) Invited lecture by Ernesto Galvão on measurement-based quantum computation.

  Lecture support: (slides) (video) (commented links)
  Live session 5: Join colibri-zoom here!

• May 14: (Non presencial lecture) The eigenvalue estimation problem. The order-finding problem. Shor's algortithm.

  Lecture support: (slides) (P. Shor original paper)
  Live session 6: Join here!

• May 27: (Non presencial lecture) The period-estimation algorithm and variants. An exercise on algorithmic design.

  Lecture support: (slides)
  Problem 3: (until 27 June)
  Problem 4: (until 27 June)
  Live session 7: Join here!

• May 28: (Non presencial lecture) Quantum simulation in biology and chemestry: quantum evolution; computation of the fundamental state with the variantional method. Complexity classes for quantum algorithms.

  Lecture support: Invited lecture by Carlos Tavares on quantum simulation (slides)
  Live session 8: Join here! (zoom)

• Jun 4: (Non presencial lecture) An algorithm for computing the discrete logarithm. The hidden group problem: formulation, instances, algorithm.

  Lecture support: (slides)
  Live session 9: Join here!

• Jun 18: Discussion experimental assignment

TP Lectures

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

  Problem Set 1 - Haskell. (exercises)

• Feb 14: Problem Set 2 - Algebra of quantum operations. (exercises)

• Feb 21: Conclusion of Problem Set 2.

  Problem Set 3 - Simulation of quantum circuits. (exercises)

• Feb 28: Conclusion of Problem Set 3.

• Mar 6: Introduction to Qiskit and its components.

  Deutsch-Josza Algorithm. (Jupyter notebook)

• Mar 13: CANCELLED: Covid-19 preventive determination

• Mar 20: (Non presencial lecture) Working with the IBMQ backends.

  Quantum Teleportation protocol. (Jupyter notebook)

• Mar 27: (Non presencial lecture) Grover's search algorithm - first steps.

  Solving a 3-SAT problem with Grover's algorithm. (Jupyter notebook)

• Apr 3: (Non presencial lecture) Solving a 3-SAT problem with Grover's algorithm (continued).

  C(n)NOT decomposition. (Jupyter notebook)

• Apr 17: (Non presencial lecture) Quantum state tomography.

  Simulating measurement noise. (Jupyter notebook)

• Apr 24: (Non presencial lecture) Quantum Fourier transform.

  Period Finding. (Jupyter notebook)

• May 8: (Non presencial lecture) Quantum phase estimation. (Jupyter notebook)

• May 15: (Non presencial lecture) Quantum counting. (Jupyter notebook)

• May 22: (Non presencial lecture) Variational Quantum Eigensolver with Qiskit Aqua.

  Quantum Approximate Optimization Algorithm. (Jupyter notebook)

• May 29: Discussing ongoing experimental assignments.

• Jun 19: Discussion of delivered experimental assignments.

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

News

May 26: Some references on quantum algorithms NEW

• Introductory text on quantum computation.
• Quantum algorithms implementations for beginners a recent, systematic survey paper, a bit terse, but with implementation schemes in Qiskit. Here another one, and another still.
• An interesting review on quantum search algorithms. Peter Shor paper on the scarcity of quantum algorithms.
• John Preskill 2017 paper on current NISQ technology --- very important reading to complement the stuff covered in the lectures.
• Some recent papers on specific algorithms: the triangle problme; tree size estimation; risk analysis; quantum walks and their implementation.
• And, finally, some papers on quantum programming languages: here; there, and there.

May 7: References for measurement-based quantum computation

• MBQC - The model: This survey is an excellent review of the area by Josza, to complement these short, self-contained lecture notes, also by Jozsa, which provide the best overview of the model for novices. Part of Ernesto's lecture was based on section 2.1 of this paper by McKague.
• The gate teleportation idea by Gottesman and Chuang appear in this 1999 paper.
• Look at this paper by Gross at al for other known universal resources for MBQC.
• References for experimental implementations can be found here, here, and there.
• Due to the neat separation between classical and quantum resources, the power of MBQC must come from the correlations exhibited by measurements of the cluster. The connection with non-locality and contextuality has been studied in a few papers, for example this one, on the relation with non-locality tests, and that one relating MBQC with quantum contextuality.
• Ernesto's paper shows that arbitrarily small violations of non-contextuality inequalities are sufficient for reliable evaluation of general Boolean functions. On the other hand, the paper by Howard et al. shows that contextuality is necessary for computation in the model of magic state distillation and injection.

Mar 16: Going virtual (from 16th March ...)

• Para cada aula será disponibilizado antecipadamente nesta página o material de suporte necessário que deverá ser estudado individualmente por cada um.
• No horário previsto para cada aula haverá uma sessão “live” que permitirá alguma sincronização à distância onde tentarei apresentar um sumário da matéria e responder às vossas questões. A duração da sessão será ajustada às necessidades de interacção, não excedendo o tempo regulamentar. Utilizaremos para isso a plataforma Blackboard Collaborate Ultra disponibilizada pela Universidade. O link para cada sessão estará anunciado nesta página.
• Para colmatar as dificuldades de comunicação síncrona (nomeadamente a ausência de um quadro onde escrever), estarei disponível para esclarecer qualquer dúvida de forma assíncrona.
• No que concerne à avaliação resolvemos aumentar o peso da componente prática, que passa a valer 70% da classificação final. Esta consistirá no trabalho prático, como combinado, complementado por exercícios para resolução em casa que serão propostos nas aulas TP. Pensamos que este tipo de avaliação, reforçando o caracter prático da UC, se adequa melhor a este momento em que não dispomos de aulas presenciais. O teste individual (que agora terá 30% de peso) será realizado assincronamente através de um conjunto de 4 problmemas propostos nas aulas teóricas.

Pragmatics

Lecturers

• Luís Soares Barbosa
• Afonso Rodrigues

Assessment

• Training assignment (70%): 12 June (with intermediate ckeckpoints)
• Individual assynchronous test (30%): 4 exercises proposed along the T lectures

Contact

• Appointments: Tue, 08:00-09:00 and Thu, 18:00-20:00 (please send an email the day before)
• Email: lsb at di dot uminho dot pt
• Last update: 2020.06.03