Seminar: Quantum Optimization
General Information
Course instructors: Andreas S. Schulz, Maximilian von Aspern
While quantum computers have the potential to greatly speed up the solution of some problems, they work in fundamentally different ways than classical computers. To really apply quantum computing to relevant mathematical and practical problems, one has to understand these differences and how to leverage them.
In this seminar for mathematics students with a basic knowledge of optimization, we give a brief and uncomprehensive overview of the field of quantum optimization. We explore the quantum circuit model of computation and its application to discrete optimization problems and learn how to design efficient algorithms for quantum computers. Participants are not required to have a background in quantum mechanics or physics.
Schedule
| March 5 | Send topic preferences (e.g. A > B > C > E > D) to Maximilian von Aspern per e-mail |
| 2 weeks before your presentation | Send your final draft to receive feedback |
| tbd | Presentations |
Topics
| [A] | S. Dörn, “Quantum Algorithms for Matching Problems,” Theory of Computing Systems, vol. 45, no. 3, pp. 613–628, May 2008, https://doi.org/10.1007/s00224-008-9118-x. |
| [B] | K. DeLorenzo, S. Kimmel, and R. T. Witter, “Applications of the Quantum Algorithm for st-Connectivity,” Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.TQC.2019.6. |
| [C] | A. Bochkarev, R. Heese, S. Jäger, P. Schiewe, and A. Schöbel, “Quantum Computing for Discrete Optimization: A Highlight of Three Technologies.” arXiv, 2024. https://doi.org/10.48550/ARXIV.2409.01373. |
| [D] | A. Montanaro, “Quantum speedup of branch-and-bound algorithms,” Physical Review Research, vol. 2, no. 1, p. 13056, Jan. 2020, https://doi.org/10.1103/physrevresearch.2.013056. |
| [E] | F. G. S. L. Brandao and K. M. Svore, “Quantum Speed-Ups for Solving Semidefinite Programs,” in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Oct. 2017, pp. 415–426. https://doi.org/10.1109/focs.2017.45. |
| [F] | C. Grange, E. Bourreau, M. Poss, and V. T’Kindt, “Quantum Speed-ups for Single-machine Scheduling Problems,” in Proceedings of the Companion Conference on Genetic and Evolutionary Computation, in GECCO ’23 Companion. ACM, Jul. 2023, pp. 2224–2231. https://doi.org/10.1145/3583133.3596415. |
| [G] | R. Griset, I. Lavdas, and J. G. Jarkovsky, “State-space reduction techniques exploiting specific constraints for quantum search Application to a specific job scheduling problem.” arXiv, 2025. https://doi.org/10.48550/ARXIV.2501.07174. |
| [H] | E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm.” arXiv, 2014. https://doi.org/10.48550/ARXIV.1411.4028. |
Further Literature
Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press.