Quantum Computing: seminar on Quantum Algorithms - FS24, USI

Course information



Time Room Professor

TBD TBD → Stefan Wolf

Subject of this seminar

In this seminar we will discuss quantum algorithms. Each of the entries below is about a problem in computer science. For each topic, we explore algorithms that can achieve better time and/or query complexity than classical algorithms.
Your task will be to give a presentation stating the problem, the idea of the algorithm(s), and their time/query complexity with a comparison with classical complexities (if applicable). Each presentation can be prepared by a group of 2-4 students, depending on the complexity of the topic. If fewer students work on a topic, some parts can be omitted. Preliminary material can be found in the iCorsi page for Quantum Computing.

Good materials for quantum algorithms are the lecture notes by Childs, and de Wolf. If there is another topic that interests you and is not listed here, please let us know.

For questions and clarifications please contact Lorenzo Laneve.

List of topics

Papers Date and speakers
[1]Universality of quantum circuits (3 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapters 2-3) PDF
Quantum Information and Quantum Computation, M. Nielsen, I. Chuang (Chapter 4 + Appendix 3)
[2]Beyond Shor's Algorithm: Quantum Fourier Transform and Hidden Subgroup problem (4 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapters 4-6) PDF
Quantum Computing: Lecture Notes, R. de Wolf (Chapters 4-6) PDF
Quantum Information and Quantum Computation, M. Nielsen, I. Chuang (Chapter 5)
[3]Quantum random walks: how to quantize a Markov chain (3 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapter 17) PDF
Quantum speed-up of Markov chain based algorithms [Original paper], M. Szegedy (2004) PDF

Note: A prior knowledge on random walks/Markov chains is recommended, although not required. For materials on Markov chains, contact us.
[4]Quantum random walks: the glued trees problem (2 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapter 16) PDF
Exponential algorithmic speedup by quantum walk [Original paper], A. Childs et al. (2002) PDF

Note: A prior knowledge on random walks/Markov chains is recommended, although not required. For materials on Markov chains, contact us.
[5]Quantum random walks: element distinctness (2 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapter 19) PDF
Quantum walk algorithm for element distinctness [Original paper], A. Ambainis (2003) PDF
[6]Solving linear systems: the HHL algorithm (2 students)
Quantum Computing: Lecture Notes, R. de Wolf (Chapter 10) PDF
Quantum algorithm for solving linear systems of equations [Original paper], A. W. Harrow, A. Hassidim, S. Lloyd (2008) PDF
[7]Lower bounds for quantum algorithms: the polynomial method and the adversary bound (4 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapters 20-23) PDF
Quantum Computing: Lecture Notes, R. de Wolf (Chapters 11-12) PDF

Note: The dual adversary bound uses semidefinite programming. Some knowledge of linear programming is enough. Otherwise, contact us for a brief introduction.
[8]Simulation of quantum systems: Hamiltonian simulation (4 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapters 25-27) PDF
Quantum Computing: Lecture Notes, R. de Wolf (Chapter 9) PDF

Note: No prior knowledge of quantum mechanics is required. If you need a quick introduction on the Schrödinger equation, contact us.
[9]Quantum machine learning and variational quantum algorithms (3 students)
Quantum Computing: Lecture Notes, R. de Wolf (Chapter 19) PDF
Variational Quantum Algorithms, M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, L. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, P. J. Coles (2020) PDF
[10]Adiabatic quantum computing (3 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapters 28-29) PDF
[11]Quantum error correction: stabilizers, fault-tolerance and the threshold theorem (3 students)
Quantum Computing: Lecture Notes, R. de Wolf (Chapter 20) PDF
Quantum Information and Quantum Computation, M. Nielsen, I. Chuang (Chapter 10)
[12]Quantum Amplitude Estimation and application to Option Pricing (1 student)
Option Pricing using Quantum Computers, N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, S. Woerner (2019) PDF
An Introduction to Quantum Computing, P. Kaye, R. Laflamme, M. Mosca (2007)
[13]The grand unification of quantum algorithms: quantum signal processing and the quantum singular value transformation (3 students)
Lecture Notes on Quantum Algorithms, A. Childs (Chapter 27) PDF
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, A. Gily√©n, Y. Su, G.H. Low, N. Wiebe (2018) PDF
A Grand Unification of Quantum Algorithms, J. Martyn, Z. Rossi, A. Tan, I. Chuang (2021) PDF

Note: This is a very recent topic and subject to intense research, with applications to both algorithms and machine learning. If you want a challenging topic for a possible project/thesis on quantum algorithms, then this should be a valid option.
[14]Quantum Cryptography (4 students)
Quantum Computing: Lecture Notes, R. de Wolf (Chapter 18) PDF
Quantum cryptography: Public key distribution and coin tossing, C. H. Bennett, G. Brassard (1984) PDF
Quantum cryptography based on Bell's theorem, A. Ekert (1991) PDF