QC804: Quantum Algorithms

The Study Board for Science

Teaching language: English
EKA: N310088102
Assessment: Second examiner: Internal
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master

STADS ID (UVA): N310088101
ECTS value: 10

Date of Approval: 09-05-2025


Duration: 1 semester

Version: Archive

Entry requirements

None.

Academic preconditions

Students following the course are expected to be familiar with quantum computing and its mathematical foundation (corresponding to the completion of an introductory course such as QC801). Knowledge of classical algorithms and complexity theory is not required, but some familiarity will be helpful. 

Course introduction

The central aim of this course is to introduce a variety of algorithms that exploit the properties of quantum computation to deliver an asymptotic computational advantage over the best classical algorithms. This includes both theoretical aspects, such as proof of correctness and analyses of time and space complexity, as well as practical ones, such as the implementation of these algorithms on state of the art quantum platforms.


Expected learning outcome

At the end of the course, students are expected to be able to
  • Describe fundamental aspects of classical and quantum complexity (including the complexity classes P, NP, BQP, and QMA);
  • Present a variety of quantum algorithms, argue for their correctness and space and time complexity, and compare to the best known classical algorithms;
  • Implement quantum algorithms on state-of-the-art quantum platforms;
  • Identify sources of potential quantum advantage and apply quantum algorithms to exploit this.




Content

This course will cover a selection of the following topics:
  • Fundamentals of classical and quantum complexity theory.
  • Techniques for quantum algorithms (phase kickback, amplitude amplification, quantum Fourier transform, phase estimation). 
  • The hidden subgroup problem (Deutsch-Jozsa, Simon’s problem).
  • Quantum search algorithms (Grover, string matching, quantum counting).
  • Quantum simulation.
  • Quantum optimisation (QAOA, quantum annealing, Gaussian Boson sampling).
  • Factoring and related algorithms (Shor’s algorithm, order finding, discrete logarithm).

Literature

See itslearning.

Examination regulations

Exam element a)

Timing

Spring and June

Tests

Portfolio

EKA

N310088102

Assessment

Second examiner: Internal

Grading

7-point grading scale

Identification

Full name and SDU username

Language

English

Duration

Oral exam - 30 minutes + 30 minutes preparation

Examination aids

All common aids allowed

ECTS value

10

Additional information

Portfolio consisting of the following elements: 
  1. Two individual assignments handed in during the course
  2. Final oral exam during the exam period 
To achieve a passing grade overall, both elements 1 and 2 must individually meet the learning objectives. 
The assessment of element 1 takes place in conjunction with the completion of element 2.
The grade is primarily based on element 2, but element 1 can raise or lower the grade by one grade step.

Indicative number of lessons

60 hours per semester

Teaching Method

Planned lessons:
Total number of planned lessons: 60

Of which:
Common lessons in classroom/auditorium: 30
Team lessons in classroom: 30

Each week will have two hours of lectures, in which the weekly course material is presented and discussed, and two hours of exercises, in which students solve the weekly exercise sheet individually or in small groups. Exercise classes may also be used to recap weekly course material as necessary.

Other planned teaching activities: 
Reading weekly course material, completing weekly exercise sheet (if not finished during exercise classes), solving mandatory assignments.

Teacher responsible

Name E-mail Department
Robin Kaarsgaard Sales kaarsgaard@imada.sdu.dk Institut for Matematik og Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (matematik)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.