Seminar in Theoretical CS, Summer 2024
News
- 02.01.2024: We are online!
Introduction
Dates & Deadlines
| Tue, 16.04.2024, 14:30 | Kick-off meeting (CS Department, building E1, 2nd floor, room 4201b) |
| Fri, 19.04.2024 | Topic preferences due |
| Mon, 13.05.2024 | Detailed outline due |
| Mon, 10.06.2024 | Full report due |
| Mon, 24.06.2024 | Presentation slides due |
| Wed, 10.07.2024 afternoon | Seminar talks (CS Department, building E1, 2nd floor, room 4201b) |
Note that the full versions of your report and your slides should be your final submission and the camera-ready versions should differ only with regard to minor remarks, comments, and corrections by your supervisor. Please feel free, however, to talk to your supervisor about submitting preliminary versions before the due dates.
Overview
Practical quantum computing requires the development of efficient compilers that are able to translate high-level quantum algorithms into quantum circuits that are compatible with some given hardware constraints. The overall goal of a quantum compiler is to modify and rearrange the gates in a given quantum circuit in order to obtain an equivalent circuit with a reduced total gate count after mapping to the native gate set, and more favourable operations in terms of execution resources, fidelity, and runtime. Thus, the main purpose of a quantum compiler is to translate ideal quantum gate operations used in quantum algorithms into machine-level operations under constraints that arise from the special nature of quantum computers, to fight against the loss of quantum information due to decoherence effects. This involves techniques for synthesising (small) quantum circuits, low-level qubit control, and quantum error correction. The aim of this seminar is to give an overview of related approaches.
Prerequisites
Basic knowledge in Data Structures and Algorithms as well as Formal Languages and Automata Theory is expected. Experience with Compiler Construction and/or Quantum Computing is helpful. The following lists gives some background information:
- Andrew Helwer: Quantum Computing for Computer Scientists (tutorial video by Microsoft Research on quantum computing from a computer science perspective, including a live demo on a real-world quantum computer. The slides are available here.)
- IBM Quantum Learning (courses on quantum computing)
- Background information on quantum computing (collection of links to background material)
- John Preskill: Quantum Computing in the NISQ era and beyond. Quantum 2(79), 2018 (easy-to-read review paper on the potential applications of quantum algorithms)
- Jack D. Hidary: Quantum Computing: An Applied Approach. Springer, 2019 (textbook)
- Abhijith J. et al: Quantum Algorithm Implementations for Beginners. ACM, 2022 (journal paper)
- Marco Maronese, Lorenzo Moro, Lorenzo Rocutto, Enrico Prati: Quantum Compiling. Springer, 2022 (overview chapter in book on “Quantum Computing Environments“)
Schedule of Talks
| Time | Wednesday, July 10 (at MOVES seminar room) |
|---|---|
| 14:00 – 15:30 | Felix Leon Faßbender, Thomas Alois Jost, Dina Rachel Kogan |
| 15:45 – 16:45 | Matthias Johannes Karl, Sophia Greiwe |
| 17:00 – 18:00 | Martin Baum, Maximilian Engelen |
Topics
The following list gives a (still incomplete) overview of the topics.
| No. | Topic | Student | Supervisor |
|---|---|---|---|
| Overview Topics | |||
| 1 | Frederic T. Chong, Diana Franklin, Margaret Martonosi: Programming languages and compiler design for realistic quantum hardware. Nature 549, 2017 | – | – |
| 2 | Medina Bandic, Sebastian Feld, Carmen G. Almudever: Full-stack quantum computing systems in the NISQ era: algorithm-driven and hardware-aware compilation techniques. DATE 2022 | Felix Leon Faßbender | Thomas Noll |
| The Routing Problem in General | |||
| 3 | Alexander Cowtan et al.: On the Qubit Routing Problem. TQC 2019 | Thomas Alois Jost | Raphaël Berthon |
| 4 | Gushu Li, Yufei Ding, Yuan Xie: Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. ASPLOS 2019 | Dina Rachel Kogan | Thomas Noll |
| Compilation for Neutral-Atom Quantum Computers | |||
| 5 | Ludwig Schmid et al.: Computational Capabilities and Compiler Development for Neutral Atom Quantum Processors: Connecting Tool Developers and Hardware Experts. arXiv, 2023 | Matthias Johannes Karl | Raphaël Berthon |
| Compilation for Trapped-Ion Quantum Computers | |||
| 6 | Fabian Kreppel et al.: Quantum Circuit Compiler for a Shuttling-Based Trapped-Ion Quantum Computer. Quantum 7, 2023 | Sophia Greiwe | Thomas Noll |
| 7 | Mark Webber et al.: Efficient Qubit Routing for a Globally Connected Trapped Ion Quantum Computer. Adv. Quantum Technologies 3(8), 2020 | – | – |
| Compilation for Spin Quantum Computers | |||
| 8 | Nikiforos Paraskevopoulos et al.: SpinQ: Compilation strategies for scalable spin-qubit architectures. ACM Transactions on Quantum Computing 5(1), 2023 | – | – |
| Software Frameworks | |||
| 9 | Robert Wille, Rod Van Meter, Yehuda Naveh: IBM’s Qiskit Tool Chain: Working with and Developing for Real Quantum Computers. DATE 2019 | Martin Baum | Thomas Noll |
| 10 | Seyon Sivarajah et al.: t|ket⟩: A Retargetable Compiler for NISQ Devices. arXiv, 2020 | Maximilian Engelen | Thomas Noll |
| 11 | Damian S. Steiger, Thomas Häner, Matthias Troyer: ProjectQ: an open source software framework for quantum computing. Quantum 2, 2018 | – | – |
| 12 | Ali Javadi Abhari et al.: ScaffCC: Scalable compilation and analysis of quantum programs. Parallel Computing 45, 2015 | – | – |
Registration
Registration to the seminar is handled via the SuPra system.
Grading Scheme
You can access the grading scheme here.
Additional Material
- Report template
- Presentation template
- How to Write a Seminar Paper
- Ethische Richtlinien für das Verfassen wissenschaftlicher Arbeiten
- How to Give Presentations
- Introduction to LaTeX