Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, die Grundlagen und zentralen Konzepte der Algorithmik, der Komplexitätstheorie und des Quantum Computing  im Hinblick auf deren Relevanz in Quanteninformationswissenschaften und -technologien illustrieren und bewerten. Sie können beispielsweise die elementaren Algorithmik und Datenstrukturen und die Ideen, die und verschiedenen Quantenalgorithmen zu Grunde liegen, erklären und begründen, den Begriff und die Konsequenzen der Dekohärenz erläutern und elementare Fehlerkorrekturstrategien diskutieren und evaluieren.

 Algorithmics:
- Basics of graphs: connectivity, traversal, bipartiteness, topological ordering
- Greedy algorithms: Interval scheduling, minimum spanning tree
- Divide and conquer: Recurrence relation, counting inversions, closest pairs of
points
- Dynamic programming (DP): Principles of DP, weighted inter scheduling, knap-
sack problem, shortest path problem
- Network flow algorithms: Ford-Fulkerson algorithm, MaxCut versus MinFlow,
applications
- Linear Programming vs. Integer Linear Programming

 Complexity theory:
- Basic notions
- Deterministic, non-deterministic, probabilistic, quantum models of computation
(including corresponding classical problems)
- Complexity measures and important complexity classes like, P, NP, PSPACE,
and the polynomial hierarchy
- Concept of problem reductions
- Concept of NP hardness and NP completeness
- Important probabilistic complexity classes
- Important quantum complexity classes
- Relation between complexity classes
- Discussion of the (extended) Church-Turing thesis
- Classical and quantum circuit models

 Quantum computing:
- Basic notions (including mathematical and quantum-mechanical background)
- Programming techniques and reverse computation
- Simple quantum algorithms like Deutsch, Deutsch-Jozsa, Bernstein-Vazirani,
quantum teleportation
- Algorithm of Grover
- Algorithm of Simon
- Quantum Fourier transformation, phase estimation, and order finding
- Algorithm of Shor
- Variational solvers and examples for combined classical/quantum algorithms

Lectures + exercises

Exercises + written exam