Quantum Algorithms - A short introduction

Table of Contents
Deutsch algorithm 
Deutsch-Jozsa-algorithm 
Shor algorithm 
Grover algorithm with student tasks  

Computers solve problems using algorithms – you can think of an algorithm as being a set of instructions. Classical algorithms run on classical computers, while quantum algorithms run on quantum computers. The key difference between them lies in how they process information.

Classical computers use bits, which can be either 0 or 1. They process data sequentially, solving one step at a time. Even supercomputers, which run algorithms across multiple processors in parallel, still execute those algorithms in a step-by-step manner. While classical algorithms are highly efficient for many tasks, they become inefficient for complex problems such as breaking encryption or simulating large molecules – because the runtime of the programs becomes just too large.

Quantum computers use qubits, which can be in a superposition of two states. This allows quantum algorithms to process computation steps simultaneously, making them much faster to solve certain type of problems. Another key property of quantum physics, entanglement, enables qubits to be linked to each other, again improving the computation efficiency.

Deutsch algorithm

What it does  
Imagine a function ${\displaystyle f}$ that takes a single bit (0 or 1) as input and produces a single bit as output. There are four possible functions for describing this: two constant functions (${\displaystyle f(0)=f(1)=0}$ or ${\displaystyle f(0)=f(1)=0}$) and two so-called balanced functions ${\displaystyle \left(f\left(0\right)\ne f\left(1\right)\right)}$. The Deutsch algorithm can determine whether the function ${\displaystyle f}$ is constant or balanced.

Quantum vs. classical 
Classically, to determine if the function is constant or balanced, you would need to evaluate the function for both inputs, ${\displaystyle f\left(0\right)}$ and ${\displaystyle f\left(1\right)}$. This requires two function evaluations. The Deutsch algorithm, however, achieves the same result with just one quantum query to the function.

Deutsch-Jozsa-algorithm

What it does 
Imagine a function ${\displaystyle f}$ that takes ${\displaystyle n}$ bits as input and produces a single bit as output. The Deutsch-Jozsa algorithm determines whether the function is constant (meaning it outputs the same bit for all possible inputs) or balanced (meaning it outputs 0 for exactly half of the inputs and 1 for the other half). 

Quantum vs. classical 
Classically, to determine if the function is constant or balanced, you would need to evaluate the function for all possible inputs. Since there are  ${\displaystyle 2^n}$ possible inputs, this requires ${\displaystyle 2^n}$ function evaluations. If the function is balanced, you might be lucky and determine it after fewer tries, but in the worst case, you have to check half of the inputs. The Deutsch-Jozsa algorithm, however, can determine the nature of the function with just one quantum query to the function, regardless of the number of input bits ${\displaystyle n}$.

Shor's algorithm 

What it does 
Shor's algorithm is a quantum algorithm that efficiently finds the prime factors of large integers. This is a problem recognised for its computational difficulty on classical computers, and is thus the reason why prime factorisation is widely used for encryption methods like the RSA encryption (RSA stands for the inventors of the method: mathematicians Rivest, Shamir and Adleman). A quantum computer that uses Shor's algorithm to efficiently factorise large numbers poses a significant threat to current cryptographic systems.

Quantum vs. classical 
The key difference lies in the period-finding step, i. e. finding one or several periodical patterns in the factors of the factorisation. Classical algorithms for finding the period require exponential runtime, meaning the time it takes to factorise a given number increases exponentially with the size of the number. For very large numbers, the runtime is just absurdly large to have it run on a classical computer. Shor's algorithm, however, can find the period in a polynomial runtime. This is a dramatic speedup.

Grover algorithm

Grover's algorithm is a quantum algorithm for searching an unsorted database. It offers a significant speedup for this kind of problems.

Quantum vs. classical 
In classical computing, searching for an item in an unsorted database of N entries requires, on average, checking N/2 entries. In the worst case, you might have to check all N entries (N – 1 to be exact). Grover's algorithm, however, only requires approximately √N steps to find the target entry. This is a speedup, which becomes more relevant as the size of the database grows.

Worksheet: Understanding Grover's algorithm

Objective: To get a basic understanding of how Grover’s algorithm works and how it can speed up a search in an unsorted list of items. You need to be a group of five students to carry out this exercise.

Download worksheet with solution as docx or as pdf.
Download worksheet for students as docx or as pdf.