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 opensource 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 (201920)
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: Covid19 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 BernsteinVazirani 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 measurementbased quantum computation.
Lecture support: (slides)
(video)
(commented links)
Live session 5: Join colibrizoom
here!

May 14:
(Non presencial lecture) The eigenvalue estimation problem. The orderfinding problem. Shor's algortithm.
Lecture support: (slides) (P. Shor original paper)
Live session 6: Join
here!

May 27:
(Non presencial lecture) The periodestimation 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.
DeutschJosza Algorithm. (Jupyter notebook)

Mar 13:
CANCELLED: Covid19 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 3SAT problem with Grover's algorithm. (Jupyter notebook)

Apr 3:
(Non presencial lecture) Solving a 3SAT 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
News
May 26: Some references on quantum algorithms
NEW
May 7: References for measurementbased quantum computation
 MBQC  The model: This survey is an excellent review of the area by Josza, to complement these short, selfcontained 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 nonlocality and contextuality has been studied in a few papers, for example
this one, on the relation with nonlocality tests, and that one relating MBQC with quantum contextuality.
 Ernesto's paper shows that arbitrarily small violations of noncontextuality 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
Assessment
 Training assignment (70%): 12 June
(with intermediate ckeckpoints)
 Individual assynchronous test (30%): 4 exercises proposed along the T lectures
Contact
 Appointments: Tue, 08:0009:00 and Thu, 18:0020:00 (please send an email the day before)
 Email: lsb at di dot uminho dot pt
 Last update: 2020.06.03