Discovering the supremacy of quantum computers

Overview

Secondary School

Computer Science

Quantum Computing

English

Overview

Keywords: computational complexity, Big O notation, RSA algorithm
Age group: 16-19 years
Required knowledge/skills: basic understanding of structured programming, basic knowledge of the programming language Python
Time frame: 30-45 minutes

Author: Christian Datzko (CH)

Content

1. Computational complexity and the Big O notation
2. The RSA algorithm
3. Additional exercises

Summary

Certain computational problems—like factoring large numbers—require an unrealistically long run time on classical computers. A quantum computer, however, can solve these problems in a reasonable time. This is an example of quantum supremacy.

quantencomputingt_teaser_ilustrationen_v01_basic_concepts_skaliert

Learning outcomes Learning outcomes

In this lesson, students …

discover the differences between a classical and a quantum computer;
can explain the Big-O notation for growth rates (linear, polynomial, exponential, factorial);
learn what quantum supremacy means.

Required materials

paper and pencil
computers/tablets and internet access

1. Computational complexity and the Big O notation

Exercise 1

Find the prime factors of the number 373628601156041617 without using a computer. Why is this so hard to do? Compare this task to the multiplication of two numbers.

Solution Solution

A prime factor of the number 373628601156041617 can theoretically be any natural number from 2 to $\sqrt{373628601156041617}$ .

To factorise a number into its prime factors, one has to check for is all prime numbers from 2 to $\sqrt{373628601156041617}$ whether this prime number is a prime factor of 373628601156041617.

Here, $\sqrt{373628601156041617}$ is a number that has half as many digits as the original number 373628601156041617 (9 instead of 18).

An obvious approach would be to use digital tools such as WolframAlpha ^[1], which factorise the number into 191206237 · 1954060741. However, this obscures the fact that it is very time-consuming for a computer to factorise numbers as large as 373628601156041617. A programme for this is presented under "Explanation". It clearly shows that the larger the number to be factorised, the longer it takes; to be precise, it takes exponentially more time.

The numbers 191206237 and 1954060741 were chosen deliberately: 23 June 1912 is Alan Turing's birthday and 7 June 1954 is the anniversary of his death.

Exercise 2

Research the RSA algorithm, which was invented in 1977 by Ronald L. Rivest (*1947), Adi Shamir (*1952) and Leonard Adleman (*1945) and is still used in today’s cryptography. How are the public and private keys created?

Solution Solution

The RSA algorithm is based on a public and a private key. The public key is published and used for encryption, while the private key remains secret and is used for decryption. The following mathematical operators are used for this purpose:

Multiplication a · b
Exponentiation b^x
Modulo operation a % b (equals the remainder of the integer division of a : b)

Three aspects are managed by the RSA algorithm:

To generate a set of public and private keys, the recipient performs the following steps:
- The recipient selects two large prime numbers p and q and calculates the product n = p · q.
- The recipient selects two numbers d and e such that d · e % (p – 1) · (q – 1) = 1.
  In addition, d and e must be coprime (i.e. their only common factor is 1) to p – 1 and q – 1.
- The recipient publishes (n, e) as his public key and keeps (n, d) as his private key. p and q are destroyed.
To encrypt a message, the sender calculates the secret message c = m^e % n for the plaintext message m.
To decrypt the message, the recipient extracts the original plaintext m’ = c^d % n from the secret text c.

Exercise 3

Compare the growth of the functions
$f_{1} (x) = x$ , $f_{2} (x) = x^{2}$ , $f_{3} (x) = x^{10}$ , $f_{4} (x) = 2^{x}$ and $f_{5} (x) = x!$

by calculating the function values for
$x = 1$ , $10$ , $100$ , $1000$ , $10000$ , $100000$ , and $1000000$ .

Hint: you might need to use special tools like Python or WolframAlpha ^[1] to calculate some of these function values.

Solution Solution

The following table shows the calculated values.

x	f₁(x) = x	f₂(x) = x²	f₃(x) = x¹⁰	f₄(x) = 2ˣ	f₅(x) = x!
1	1	1	1	2	1
10	10	100	1 · 10¹⁰	1024	3,628,800
100	100	10 000	1 · 10²⁰	1,268 · 10³⁰	9,333 · 10¹⁵⁷
1 000	1 000	1 000 000	1 · 10³⁰	1,072 · 10³⁰¹	4,024 · 10²⁵⁶⁷
10 000	10 000	100 000 000	1 · 10⁴⁰	1,995 · 10³⁰¹⁰	2,846 · 10³⁵⁶⁵⁹
100 000	100 000	1 · 10¹⁰	1 · 10⁵⁰	9,990 · 10³⁰¹⁰²	2,824 · 10⁴⁵⁶⁵⁷³
1 000 000	1 000 000	1 · 10¹²	1 · 10⁶⁰	9,901 · 10³⁰¹⁰²⁹	8,264 · 10^55555708

WolframAlpha ^[1] was used for the larger values.

The table clearly shows that $f_{4} (x) = 2^{x}$ (exponential growth) grows significantly faster than the other functions (linear, quadratic or polynomial), and that $f_{5} (x) = x!$ (factorial growth) grows even faster.

Explanation

Some calculations take more time than expected. A simple approach for factorising a very large integer $x$ would be to test every possible prime factor (starting with 2) until a first factor is found.

One only needs to test until $\sqrt{x}$ because either $x$ is a prime number, or $x$ can be factorised as $x = a \cdot b$ , where either $a$ or $b$ is smaller than $\sqrt{x}$ .

Then, this process must be continued until all factors are found or until the integer turns out to be a prime number.

The following Python programme shows this process in a simplified way (for simplicity, instead of testing only the prime numbers, all integers starting with 2 are tested).

Code Code

import math

def is_divisible_by(dividend, divisor):
    """Returns whether dividend is divisible by divisor by checking whether the remainder of the integer division of dividend by divisor is 0."""
    return dividend % divisor == 0 # the modulus operator "%" finds the remainder of an integer division

integer = 373628601156041617 # the number to be factorized
factors = [] # , starting with an empty array

x = integer # use a copy of integer because it changes over time
factor = 2 # check every integer starting with 2
while factor <= math.sqrt(x): # as long as the factor to be checked is less than or equal to the square root of x
    if is_divisible_by(x, factor):
        factors.append(factor) # append factor to the array of factors
        x = x // factor # now only numbers until x divided by factor must be checked because factor is already a factor ; "//" is an integer division, so the result is always an integer
        # factor does not have to be changed, because it cannot be less than it was before, but could be the same factor again
    else:
        factor = factor + 1 # increase the factor by 1
factors.append(x) # if no factors less than or equal to sqrt(x) are found, the remaining integer must be a prime number and thus the final factor
print("The prime factors of", integer, "are", factors)

For instance, to factorise the number 100, each iteration of the loop would yield the following values:

x	factor	all factors
100	2	[]
50	2	[2]
25	2	[2, 2]
25	3	[2, 2]
25	4	[2, 2]
25	5	[2, 2]
5	5	[2, 2, 5]
		[2, 2, 5, 5]

This takes a considerable amount of time. The best runtime is achieved if $x$ is a power of 2, because then in every loop iteration, $x$ would be divided by 2. If $b$ is the number of binary digits (bits) representing the integer $x^{2}$ , that leads to a runtime of $b$ .

The worst case occurs when $x$ is already a prime number: this would result in a runtime of $\sqrt{2^{b}} = {\sqrt{2}}^{b}$ . In other words, the runtime is exponential with respect to the length of a number.

To put this abstract notation into perspective: if a single iteration of the loop takes typically 1 microsecond, the runtime for factorising 373628601156041617 – 59 binary digits are needed to represent this number – would be between 59 microseconds and approximately 13 minutes:

${\sqrt{2}}^{59} μ s \approx 759 000 000 μ s = 759 s \approx 12.7 minutes$

You can, for example, ask WolframAlpha ^[1]: “Calculate the number of binary digits of 373628601156041617”.

How to determine the number of binary digits How to determine the number of binary digits

How to determine the number of binary digits (bits) of, for example, 25?

25 = 2 x 2 x 2 x 2 + 2 x 2 x2 + 1 = 2⁴ + 2³ + 1

Written in base 2, this is equivalent to 11001 (i.e. 5 digits). So, the number of binary digits needed to represent the number 25 is 5.

The Big O notation

The Big O notation is used in computer science to determine the approximate runtime for an algorithm to perform a given calculation, e.g. calculating the value of the function $f (x)$ depending on the input size $x$ . Any constant factors are discarded, and so are constant and/or slower growing terms of the function. Only the fastest growing term is considered. This gives a rough “general picture” of the behaviour of a function.

For instance, for $0 \leq x \leq 1$ , the parabola $f (x) = x^{2}$ grows slower than a straight line, $g (x) = x$ .

For $x > 1$ , the parabola “outgrows” the straight line. This is even true if an arbitrarily small but greater than 0 factor $a$ is put in front of the $x^{2}$ , or if an arbitrary number $c$ is added, giving $f (x) = a x^{2} + c$ .

There will always be an $x$ from which on the parabola outgrows the straight line. Therefore, for large values of $x$ , only the dominant part of the function is relevant, in this case written as $O (x^{2})$ .

Functions like straight lines grow “linearly” – which is denoted by $O (x)$ – while parabolas have a “quadratic” growth – denoted by $O (x^{2})$ .

In general, polynomials have a “polynomial” growth rate, i.e. for a polynomial $h (x) = a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{2} x^{2} + a_{1} x + a_{0}$ , the growth rate is $O (x^{n})$ – only $x^{n}$ is kept while $a_{n}$ and all slower‑growing terms are discarded.

An even larger growth rate is the “exponential” growth rate $O (2^{x})$ .

The factorial of a natural number $n$ is the product of the first $n$ natural numbers, so
$n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n - 2) \cdot (n - 1) \cdot n$ .

Overview of common runtime classes

Name	Linear runtime	Quadratic runtime	Polynomial runtime	Exponential runtime	Factorial runtime
Runtime class	O(x)	O(x²)	O(xⁿ)	O(2^x)	O(x!)

Linear runtime Linear runtime

Quadratic runtime Quadratic runtime

Polynomial runtime Polynomial runtime

Exponential runtime Exponential runtime

Factorial runtime Factorial runtime

2. The RSA algorithm

The RSA algorithm for public-key cryptography uses very large numbers (usually around 4096 bits long; this corresponds to around 1234 decimal digits) which are the product of two large prime factors. So, the runtime for factorising such a large number is approximately equal to the upper runtime limit, i.e. ${\sqrt{2}}^{b}$ (where $b$ is the number of bits) . More refined algorithms can improve the performance of the algorithm, but their runtime remains within that range and tends to be around $O (b^{x})$ , with $b$ being a base which is small but still greater than 1.

In order to factorise large numbers that are used for the RSA algorithm, it would take a classical computer hundreds of thousands of years. This is why the RSA algorithm, which is still being widely used, is so secure. To this date, no classical algorithm is known to be able to factorise a number faster than the RSA algorithm (More in RSA: The unbreakable Code). However, a quantum algorithm developed by the Mathematician Peter Shor, “Shor’s algorithm” (More in Breaking the unbreakable? Shor’s Algorithm), only requires polynomial runtime $O (x^{n})$ . This represents a significant speedup and would make RSA encryption vulnerable. Luckily, it would require a quantum computer with approximately 20 million^[2] so-called “noisy” (i.e. non-ideal) qubits to crack an RSA security key with 2048 bits in about 8 hours. This is still beyond what today’s quantum computers are capable of.

Cracking an RSA key is a good example that demonstrates quantum supremacy: in ‘classical’ computer science, the only algorithms known to date that can crack RSA keys have a runtime exceeding polynomial growth. Quantum computers, however, might provide a significant speedup.

3. Additional exercises

Exercise 1

A classical problem that requires a very long computing runtime to be solved is the “travelling salesman problem”, often abbreviated as TSP. Imagine a salesman who has to visit the 20 largest cities of your country to deliver some goods. He can travel to the cities in any order. However, the less time he spends traveling, the better for him: once all deliveries are completed, he can return home and he is paid a fixed salary, regardless of how long the trip takes.

Find the approximate runtime in Big O notation.

Hint: start with delivering to one city and then add cities one by one to find an expression for all possible routes he should check. Don’t be surprised if it takes him 77 094 years to find the best route if the calculation for a single route takes 1 µs.

Solution Solution

For one city, the problem is trivial: one single visit is required. For a second city, there are twice as many possibilities, because either the first or the second city could be visited first. For a third city, there are already three times as many possibilities as for two cities, because the new city could be visited before, between or after the already planned visits, so that there are 2 · 3 = 6 sequences in which the cities can be visited.

In general, if n cities have already been visited, there are n + 1 times as many possibilities for an additional city as there are for n cities. This type of growth is called factorial growth: for n cities there are a total of n! possible routes.

For 20 cities, there are therefore 20! ≈ 2.433 · 10¹⁸possible routes. If calculating a route takes 1 µs, this would mean that calculating all possible routes for 20 cities requires:
(2.433 · 10¹⁸)/(1000000 · 60 · 60 · 24 · 365.25) ≈ 77094 years.

Exercise 2

You are going on a hike with your class and are asked to bring a backpack with food. You would like to maximise the amount of food you may bring, but your backpack only holds 13.5 kg.

Your food items (each of which must not be divided) have the following weights: 0.025 kg, 0.9 kg, 1.6 kg, 1.7 kg, 2.25 kg, 2.85 kg, 3.15 kg, 3.45 kg, 4.9 kg and 6.05 kg.

How much can you take with you with the least amount of possible weight left over?

Solution Solution

To find the optimal solution, all possible packing combinations of the individual items must be tried. There are some possibilities to optimise this procedure, for example, by stopping as soon as a combination is found that exploits the full capacity of the backpack.

Because there are 10 items with different weights, there is a total of 2¹⁰ possible combinations of these items (for each item, whether it is in the backpack or not). Therefore, the runtime is O(2^x).

To find the optimal solution, the following programme checks every possible combination by simply iterating over the numbers 0 to 2¹⁰ – 1, which correspond to the different packing combinations. For each bit that equals 1, the corresponding item is ‘in the backpack’. If the weight is within the capacity of the backpack but greater than the weight of the largest packing combination so far, this is stored as the (currently) best packing combination. At the end, the global optimum (or one of them, if several equivalent solutions exist) is output as the result.

def bit(number, position):
"""Returns True, if the bit at position ‘position’ is 1, returns False otherwise"""
temp = number
for i in range(position): # Divide until the last bit is the one we are interested in
temp = temp //2
if temp % 2 == 0: # Can be divided by 2
return False
else:
return True

def weight(knapsack):
""" Calculates the weight of the backpack content by adding up the weights of the individual items"""
weight = 0
for i in range(len(knapsack)):
weight = weight + knapsack[i]
return weight

items = [0.025, 0.9, 1.6, 1.7, 2.25, 2.85, 3.15, 3.45, 4.9, 6.05]
maximum_weight = 13.5
optimum = []

for bitcombination in range(2 ** len(items)): # All possible combinations for packing the respective items/weights – as a number whose bits correspond to the weights
knapsack = []
for bitposition in range(len(items)):
if bit(bitcombination, bitposition): # If the bit for the item is 1, the item must be packed
knapsack.append(items[bitposition])
if weight(knapsack) <= maximum_weight: # If this item fits into the backpack
if weight(optimum) < weight(knapsack): # A backpack with a better pack weight has been found
optimum = knapsack

print("An optimally filled backpack weighs", weight(optimum), "and contains the items with the following weights:", optimum)

Exercise 3

(alternative to exercise 2)

The Eight Queens Puzzle is a chess problem: on a standard 8×8 chess board eight queens (which may move vertically, horizontally and diagonally) are to be placed so that they cannot move from one to the other within one move. Find a solution for this problem.

Once you have found how to theoretically solve the problem, write a computer program that produces all possible solutions.

Then create a computer program that produces all possible solutions for an n × n chessboard and analyse the runtime based on the size of the chessboard.

Solution Solution

The Eight Queens Puzzle is a famous example problem for various computer programming techniques. It was first published by chess composer Max Bezzel in 1848 and many mathematicians have been working on this problem and it’s generalized n-queens version ever since.

It is explained at Wikipedia: Eight queens puzzle ^[3], including a Python programme to solve the problem.

Sources Sources

WolframAlpha
https://www.wolframalpha.com/
(last accessed 13.03.2026)
Craig Gidney: How to factor 2048 bit RSA integers with less than a million noisy qubits (2025).
Wikipedia: Eight queens puzzle
https://en.wikipedia.org/wiki/Eight_queens_puzzle
(last accessed 13.03.2026)

Share this page

Discovering the supremacy of quantum computers

Overview

Overview

Content

Summary

Required materials

1. Computational complexity and the Big O notation

Exercise 1

Exercise 2

Exercise 3

Explanation

The Big O notation

Overview of common runtime classes

2. The RSA algorithm

3. Additional exercises

Exercise 1

Exercise 2

Exercise 3

Similar teaching materials

How to implement Deutsch’s algorithm with a Mach–Zehnder interferometer

Careers in Quantum Technologies