41174 Quantum Algorithms
Warning: The information on this page is indicative. The subject outline for a
particular session, location and mode of offering is the authoritative source
of all information about the subject for that offering. Required texts, recommended texts and references in particular are likely to change. Students will be provided with a subject outline once they enrol in the subject.
Subject handbook information prior to 2024 is available in the Archives.
Credit points: 6 cp
Subject level:
Undergraduate
Result type: Grade and marksRequisite(s): 41076 Methods in Quantum Computing
Description
Students will develop an understanding of the most famous quantum algorithms, including Shor’s efficient quantum algorithm for integer factorisation and Grover’s search algorithm. Students will also be introduced to algorithms based on quantum walks, an analog of random walks, algorithms for simulating quantum systems, and quantum algorithms for solving systems of linear equations. Further applications of these algorithms to optimisation and machine learning will be discussed.
Subject learning objectives (SLOs)
Upon successful completion of this subject students should be able to:
| 1. | Write algorithms in the quantum circuit model. (D.1) |
|---|---|
| 2. | Apply the quantum algorithms learned to new problems and describe solutions. (C.1) |
| 3. | Demonstrate and communicate limitations of quantum algorithms. (E.1) |
Course intended learning outcomes (CILOs)
This subject also contributes specifically to the development of the following Course Intended Learning Outcomes (CILOs):
- Design Oriented: FEIT graduates apply problem solving, design and decision-making methodologies to develop components, systems and processes to meet specified requirements. (C.1)
- Technically Proficient: FEIT graduates apply abstraction, mathematics and discipline fundamentals, software, tools and techniques to evaluate, implement and operate systems. (D.1)
- Collaborative and Communicative: FEIT graduates work as an effective member or leader of diverse teams, communicating effectively and operating within cross-disciplinary and cross-cultural contexts in the workplace. (E.1)
Teaching and learning strategies
There will be 2 hours per week of lecture, interspersed with simple problems for the students to answer for further discussion. One hour per week will be spent in tutorial. The tutorial will begin with a short quiz to check understanding. The quiz will then be discussed. The rest of the time in tutorial will be spent working in groups on the weekly problem set. Working in groups will allow students to practise explaining their ideas to others. The instructor will go around and provide assistance in this time, and bring the class together for further discussion of any issues that come up. The problem sets will be turned in the following week. Feedback will be given both through the quiz and grading of the problem sets.
The last 3 weeks of class, students will work in groups on a project. For this project they will pick a topic from a given list, or choose their own with approval. This topic will cover a quantum algorithm not discussed in lecture, but for which the course has prepared them to understand with the necessary background. Students will work in groups to prepare a written report that explains this algorithm in their own words and gives a full analysis of its complexity.
Content (topics)
- Review of quantum circuits
- Fourier Transform
- Shor’s integer factorisation algorithm
- Extension of Shor to the hidden subgroup problem
- Grover’s search algorithm
- Quantum query complexity
- Lower bound techniques (polynomial and adversary methods)
- Quantum walks
- Hamiltonian simulation
- Quantum algorithms for solving systems of linear equations
- Quantum complexity theory
Assessment
Assessment task 1: Tutorial Quiz
| Intent: | Quizzes will be given online and will consist of simple questions to ensure that students can benchmark their understanding of concepts. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1 and 2 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Quiz/test |
| Groupwork: | Individual |
| Weight: | 30% |
| Length: | 15 minutes |
Assessment task 2: Problem Sets
| Intent: | Encourage students to engage in the topics more deeply by giving more in-depth and open-ended problems for them to solve. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2 and 3 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1, D.1 and E.1 |
| Type: | Exercises |
| Groupwork: | Group, individually assessed |
| Weight: | 30% |
| Length: | 3-5 problems, with 100-200 words describing the solution approach for each problem |
Assessment task 3: Project Report
| Intent: | To allow students to apply their knowledge to a new scenario. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2 and 3 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1, D.1 and E.1 |
| Type: | Report |
| Groupwork: | Group, individually assessed |
| Weight: | 40% |
| Length: | 2000 words |
Minimum requirements
To pass this subject, students must achieve an overall mark of 50% or greater.
Recommended texts
Lecture notes of Andrew Childs: https://www.cs.umd.edu/~amchilds/qa/
Lecture notes of Ronald de Wolf: https://homepages.cwi.nl/~rdewolf/qcnotes.pdf