This (2SWS) lecture course is a basic and concise introduction to the mathematics of quantum computing. Quantum computing is a type of computation whose operations use phenomena of quantum mechanics. Even though devices that perform these quantum computations -- i.e. quantum computers -- exist, at the moment, only very limited in size, an associated theory of computation is well established and precise.

Just as a bit (0 or 1) is a fundamental unit of classical computation, a qubit (a unit vector in the complex ℂ^2) is a fundamental unit of quantum computation. (Think of the classical bits as (1,0) and (0,1).) A system of such qubits, a quantum state, can be modified by quantum logic gates, e.g. NOT, AND, OR, which are just certain unitary matrices. In contrast to the classical situation, there are "more" operations one can perform. Systems of such quantum gates (and more), are called quantum circuits. Just as in the classical setting (with just 0 and 1), one may model elementary arithmetic operations by these circuits and ask about benefits in complexity. In the lecture, we will explore the language of this non-binary world and study some fundamental problems.

• Qubits and entangled states
• Quantum logic gates and quantum circuits
• Toffoli gate and universality
• Quantum circuits for elementary arithmetic operations
• No-cloning theorem vs. quantum teleportation
• Holevo's bound vs. dense coding
• Deutsch-Jozsa algorithm
• Grover's search algorithm
• Quantum Fourier transformation (and arithmetic addition revisited)
• Shor's factorization algorithm and consequences for cryprography
• Recollection of complexity theory: Turing machines and the classes P and NP (if time permits)
• Quantum complexity theory: Quantum Turing machines the classes BQP and QMA (if time permits)

• Burkhard Lenze - Mathematik und Quantum Computing
• Kurgalin, Borzunov - Concise Guide to Quantum Computing
• Nielsen, Chuang - Quantum Computation and Quantum Information
• Scherer - Mathematics of Quantum Computing
• Scherer - Mathematik der Quanteninformatik
• Bernstein, Vazirani - Quantum complexity theory
• Vazirani - A survey of quantum complexity theory

• Registration for course work/examination/ECTS: FlexNow

• Oral examination (without grade): Duration: 30, Date: individually

• Oral exam: Duration: 30, Date: individually, re-exam: Date: individually