The Supremacy of Quantum Algorithms
Overview
Summary
This chapter provides a complete course that offers students an introduction to quantum algorithms, showing examples of cases where quantum algorithms can achieve a speed-up over their classical counterparts. The course focuses on search algorithms, covering three specific problems: linear search; binary search; and mathematical searches (specifically, finding factors).
No prior knowledge of programming is assumed, and there is a pathway through the course for students who are either not computer scientists or do not have access to computers in their classrooms. For those who are studying computing, alternative lesson plans that involve solving problems using the Python programming language are provided.
Keywords: quantum algorithms, search algorithms, linear search, binary search, mathematical search, Deutsch algorithm, Bernstein-Vazirani algorithm, Grover's algorithm, RSA algorithm, Shor's algorithm
Age group: 16-18 years old
Time frame: 6-8 lessons, depending on the path
Authors: Wolfgang Geist (CH), Holger Vogts (DE), Sam Robbins (UK), Sergio Rivera Hernandez (DE)
Go directly to:
- 1.1 Introduction to search algorithms - Non-programming version
- 1.2 Introduction to search algorithms - Programming version
- 2.1 Deutsch's algorithm - Mathematical approach
- 2.2 Deutsch's algorithm - Computational approach
- 3.1 Bernstein-Vazirani algorithm - Mathematical approach
- 3.2 Bernstein-Vazirani algorithm - Computational approach
- 4. Grover's algorithm
- 5. RSA: the unbreakable code?
- 6. Breaking the unbreakable? Shor’s Algorithm
Lesson 1: Introduction
Introduction to search algorithms, covering three specific problems: linear search; binary search; and mathematical searches (specifically, finding factors) and how these problems are solved in classical computing.
Python listing to set up an array to be searched
namesArray = ["Adriano", "Birte", "Edouard", "Elena", "Florian", "Inez", "Niamh", "Oliver"]
nameToFind="Inez"Lesson 2: Deutsch algorithm
The Deutsch algorithm was the first quantum algorithm to achieve speed-up over a classical approach and provides the theoretical framework for how all quantum search algorithms work. There are two options offered for this lesson: a mathematical approach and a computational approach.
Lesson 3: Berstein-Vazirani algorithm
The Bernstein-Vazirani algorithm is a specific example of a binary search, where a quantum approach massively outperforms the classical approach. Again, two options are offered: a mathematical approach and a computational approach.
Lesson 4: Grover's algorithm
The Grover's algorithm is the quantum approach to the problem solved by linear search in the classical world. This shows the first potential real-world application of a quantum search algorithm.
Lesson 5: RSA: the unbreakable code?
This lesson focusses purely on the classical encryption algorithm itself, as there is a lot of groundwork to cover for the students to be able to appreciate how quantum computers might be able to break it.
Lesson 6: Breaking the unbreakable? Shor’s Algorithm
The Shor's algorithm is a quantum approach to breaking RSA. The lesson focusses on a practical example of how the algorithm may be applied, rather than going deeply into the mathematics of the algorithm (which is beyond the scope of this course).
Share this page
