Numerical analysis on quantum computers (VO, 2h, 3ECTS)

Markus Faustmann   Michael Feischl

We explain the basics of quantum computers (what is required in order to play numerical analysis) and analyze a number of algorithms:

• Grover's algorithm (search in unsorted vectors in $\mathcal{O}(\sqrt{N})$ )
• Shor's algorithm (factorization in polynomial time)
• Solving sparse linear systems (with exponential speed-up over classical algorithms)
• Differential equations on quantum computers

Weekly lectures: Tue 9-10:30 (Seminarraum 3B, grün), Thu 10-11 (Seminarraum 3A, grün)

lecture notes:

• Slides from first lecture
• Part 1: Basics of quantum computers
• Part 2: Classical quantum algorithms (last update 23.5.2023)
• Part 3: Solving linear systems (last update 9.6.2023)
• Part 4: Solving linear differential equations (last update 22.6.2023)

examples in IBM Quantum Composer:

• Solving a 2x2 system (see lecture notes)
• Grover Algorithm with $F(x) = x_0x_1x_2x_3$ (requires free account)
• Deutsch-Josza Algorithm with $F(x) = x_0\oplus x_1x_2$ (requires free account)
• Quantum Teleportation

other material:

• Lecture Notes: Quantum Computing by Ronald de Wolf
• Book: Quantum Computation and Quantum Information by Nielsen & Chuang
• IBM Quantum Composer