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 A Step-by-Step HHL Algorithm Walkthrough to Enhance Understanding of Critical Quantum Computing Concepts, Anika Zaman, Hector Jose Morrell, Hiu Yung Wong (2023) 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