Introduction to Quantum Computing

Lecture notes for the summer term 2024

Jannik Hellenkamp Dominique Unruh

2024-07-27
Table of contents

Welcome 2
Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1 Introduction 3
1.1 Double slit experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 What is a quantum computer? . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Probabilistic systems 5
2.1 Deterministic possibilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Probability distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Probabilistic processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Applying a probabilistic process . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Quantum systems 8
3.1 Quantum states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Unitary transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Observing probabilistic and measuring quantum systems 10

4.1 Observing a probabilistic system . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Measuring a quantum system . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Elitzur–Vaidman bomb tester . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Partial observing and measuring systems 14

5.1 Partially observing a probabilistic system . . . . . . . . . . . . . . . . . . . . . 14
5.2 Partially measuring a quantum system . . . . . . . . . . . . . . . . . . . . . . . 15

6 Composite Systems 15
6.1 Constructing composite systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Measuring composite systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7 Quantum Circuits 18
7.1 Visual language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.2 Important gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.2.1 Single qubit gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2.2 Controlled-NOT gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.3 Ket Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

8 Bernstein-Vazirani Algorithm 21

9 Shor’s Algorithm 25
9.1 Discrete Fourier Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2
 9.2 Reducing factoring to period finding . . . . . . . . . . . . . . . . . . . . . . . . 26
9.3 The quantum algorithm for period finding . . . . . . . . . . . . . . . . . . . . . 27
9.4 Post processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.5 Constructing the DFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

10 Grover’s algorithm 34
10.1 Preparations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
10.1.1 Constructing the oracle 𝑉𝑓 . . . . . . . . . . . . . . . . . . . . . . . . . 35
10.1.2 Constructing FLIP∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
10.2 The algorithm for searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
10.2.1 Understanding the algorithm for searching . . . . . . . . . . . . . . . . . 36

11 Quantum Physics 39
11.1 Wave function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
11.2 Energy / Hamiltonian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
11.3 Schrödinger equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
11.3.1 Time-dependent Schrödinger equation . . . . . . . . . . . . . . . . . . . 41
11.3.2 Time-independent Schrödinger equation . . . . . . . . . . . . . . . . . . 41
11.4 Infinite square well . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

12 From Quantum Physics to a Quantum Computer 43

13 Ion-based quantum computers 46

13.1 Electron in an atom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
13.2 Setup for the ion traps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
13.2.1 Cooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
13.2.2 Unitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
13.2.3 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

14 Universal set of gates 51

14.1 Pauli gates as universal qubit gates? . . . . . . . . . . . . . . . . . . . . . . . . 51
14.2 Rotation gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
14.3 Clifford gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
14.4 Gottesmann-Knill theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

15 Repetition code 54

3
Welcome

These are the lecture notes for the “Introduction to Quantum Computing” lecture held by
Dominique Unruh at RWTH Aachen in the summer term 2024. The lecture notes are updated
throughout the semester and should be viewed as an addition to the handwritten notes and
the lecture recordings.
If you spot an error, please send Jannik Hellenkamp an e-mail. You can contact Jannik by
sending an e-mail to [email protected] (please replace first and lastname
with Jannik’s full name). If you have a question of understanding, please ask it in the Moodle
forum.
These lecture notes are released under the CC BY-NC 4.0 license, which can be found here.

Changelog

Version 0.1.8 (27.07.2024)

• added chapters 4,5,6,7,8 and 14.

• minor error corrections

Version 0.1.7 (09.07.2024)

• finished chapter 12
• added chapter 13

Version 0.1.6 (03.07.2024)

• finished chapter 11
• started chapter 12

Version 0.1.5 (27.06.2024)

• finished chapter 10
• started chapter 11

4
Version 0.1.4 (18.06.2024)

• finished chapter 9
• stated chapter 10

Version 0.1.3 (11.06.2024)

• added/extended 9.4 + 9.5 (Post processing and Beginning of DFT circuit)

• updated 9.3
• added chapter 3 (Quantum systems)
• error correction in chapter 9

Version 0.1.2 (31.05.2024)

• minor changes to chapter 2

• added chapter 9

Version 0.1.1 (16.05.2024)

• Started the lecture notes.

1 Introduction

1.1 Double slit experiment

This section will be updated later on, since there is quite a lot of graphical stuff.

5
1.2 What is a quantum computer?

To start into the topic of quantum computing and to understand the differences from classical
computers, we first need to look at some of the basics of such classical computers.
In a classical computer the information is stored in bits which can either be in the state 0
or the state 1. These bits can be manipulated through different classical operations and we
can look at these bits and read them, without interfering with the system or changing any
states.
In a quantum computer the information is stored in a qubit which can be in a superposition
between the state 0 and 1. Just as with classical computers, we can construct variables from
these qubits to store bigger numbers. For example a 64-qubit integer would be described by
64 qubits which are in a superposition between 0 and 264 − 1. This can be imagined best as a
variable where the universe has not yet decided on its value and therefore the variable has all
possible values at the same time.
We can now use this superposition and manipulate it with different quantum operations. Con-
trary to a classical computer, in a quantum computer these operations are “applied” at all
possible input values at the same time and the result is a superposition of all possible results
of the operation. We call this effect quantum parallelism.

Example: Quantum parallelism

Let’s say you have a quantum variable 𝑥 in a superposition of numbers between 0 and
264 − 1 (all possible 64-bit values) and some function 𝑓(𝑥). You program a quantum
computer to compute 𝑓(𝑥).
The quantum computer would compute 𝑓(𝑥) for 𝑥 = 0, 𝑥 = 1, 𝑥 = 2, ... at the the same
time and the result of this computation is a superposition of all possible values 𝑓(𝑥).

Reading this, one might be tempted to utilize quantum parallelism to run any algorithm on
a quantum computer in order to optimize runtime. Unfortunately there is a big catch with
quantum computers: If we try to look at the state of a qubit (also called measuring), the
universe decides randomly on an outcome and therefore when measuring we only get the
result of one computation and all the rest of the information is lost.

Example (continued): Quantum parallelism

After your quantum computer has calculated a superposition of all possible values 𝑓(𝑥),
you want to get some information on the output and therefore you do a measurement on
the resulting quantum state.
You will receive one random 𝑓(𝑥) and all the other possible solutions are lost.

6
Due to this restriction, naively running established algorithms on a quantum computer will not
work. Fortunately there are some clever tricks to create some “interference” between different
computations before measuring. This will give us useful information in some cases.

2 Probabilistic systems

To describe a quantum computer mathematically, we can do math similar to the known topic
of probabilistic systems. We therefore first look into describing a probabilistic system.

2.1 Deterministic possibilities

At first we need to define all the different possible outcomes of our system. For example, for
a coin flip this could be heads or tails and for a dice this could be the labels of the different
sides. We call these possibilities deterministic possibilities. Note that we will only be using a
finite number of possibilities.

Example: Random 2-bit number

Imagine you have a random number generator, which outputs 2-bit numbers. The deter-
ministic possibilities of this generator are 00, 01, 10 and 11.

2.2 Probability distribution

Next, we need to assign each possibility a probability. We write this as Pr[𝑥] = 𝑝 where
𝑝 ∈ [0, 1] is the probability of the deterministic possibility 𝑥.

Example: Coin flip

1
For a coin flip the probability of heads would be Pr[heads] = 2 and the probability for
tails would be Pr[tails] = 21 .

If we combine all probabilities for all the possible outcomes and write them as a vector, we
get a probability distribution.

7
 Definition 2.1 (Probability distribution). A vector 𝑑 ∈ ℝ𝑛 is a valid probability distri-
bution iff ∑ 𝑑𝑖 = 1 and ∀𝑖 𝑑𝑖 ≥ 0.

This vector has 𝑛 entries, where each entry corresponds to a deterministic possibility 𝑋 and
the probability of 𝑋 is Pr[𝑋] = 𝑑𝑖 . The sum over all probabilities has to be 1 and each entry
needs to be nonnegative in order to be a valid probability.

Example (continued): Coin flip

1
For a coin flip the probability distribution would be 𝑑coin ∈ ℝ2 with 𝑑 = ( 21 )
2

Example (continued): Random 2-bit number

Recall your random 2-bit number generator from above. Imagine your generator outputs
each deterministic possibility with equal probability, except for the possibility 00, which
is never generated. The corresponding probability distribution would be

0
⎛
⎜ 1⎞
𝑑2-bit =⎜ 3⎟⎟
⎜1⎟
⎜ ⎟
3
1
⎝3⎠

2.3 Probabilistic processes

With a probability distribution, we can only describe the probabilities of possibilities without
any knowledge of a prior state. We therefore add another element to our toolbox of probabilistic
systems called a probabilistic process.
A probabilistic process is a collection of 𝑛 probability distributions, where for each determin-
istic possibility 𝑖 there is a probability distribution 𝑎𝑖 . This means that if the system is in
deterministic possibility 𝑖 before the process is applied, the system will afterwards be dis-
tributed according to 𝑎𝑖 . We can write this as a matrix, where each column is a probability
distribution 𝑎𝑖 .

Definition 2.2 (Probabilistic process). A matrix 𝐴 ∈ ℝ𝑛×𝑛 is a valid probabilistic

process iff for every column 𝑎 of 𝐴, 𝑎 is a valid probability distribution.

From Definition 2.1 we know that a valid probability distribution 𝑎 has the properties ∑ 𝑎𝑖 = 1
and ∀𝑖 𝑎𝑖 ≥ 0, therefore a matrix 𝐴 is a probabilistic process iff 𝐴 ∈ ℝ𝑛×𝑛 with ∑ 𝑎𝑖 = 1 and
∀𝑖 𝑎𝑖 ≥ 0 . Such a matrix is also called a stochastic matrix.

8
 Example (continued): Random 2-bit number

Imagine a second device, which receives a 2-bit number as an input and flips both bits
at the same time with a probability of 31 . The probability distributions for each of the
deterministic possibility would then be
2 1
3 0 0 3
⎛
⎜ 0⎟⎞ ⎛
⎜ 2⎞
⎟ ⎛
⎜ 1⎞
⎟ ⎛
⎜ 0⎞⎟
𝑎00 = ⎜ ⎟ , 𝑎01 = ⎜ 1 ⎟ , 𝑎10 = ⎜ 2 ⎟ , 𝑎11 = ⎜ ⎟
⎜ ⎟ ⎜ 3 ⎟ ⎜ 3 ⎟ ⎜
⎜0⎟ ⎜3⎟ ⎜3⎟ ⎜0⎟ ⎟
1 2
⎝3⎠ ⎝0⎠ ⎝0⎠ ⎝3⎠

From this we can construct the process as a matrix from these processes as follows:
2 1
3 0 0 3
⎛
⎜0 2 1
0⎞⎟
𝐴flip = (𝑎00 𝑎01 𝑎10 𝑎11 ) = ⎜
⎜ 3 3 ⎟
⎜0 1
3
2
3 0⎟⎟
1 2
⎝3 0 0 3⎠

Applying a probabilistic process

Having defined probability distributions and probabilistic processes, we can now combine these
two elements and apply a probabilistic process on a probability distribution.

Definition 2.3 (Applying a probabilistic process). Given an initial probability distribu-

tion 𝑥 ∈ ℝ𝑛 and a probabilistic process 𝐴 ∈ ℝ𝑛×𝑛 , the result 𝑦 ∈ ℝ𝑛 of applying the
process 𝐴 is defined as
𝑦 = 𝐴𝑥

Example (continued): Random 2-bit number

Recall the 2-bit number generator and the bit flip from above. Imagine you would first
draw a random 2-bit number from the generator and then run the bit flip device. We
already know that the probability distribution of the generator is 𝑑2-bit . Using 𝐴flip we
can calculate the final probability distribution:
2 1 1
3 0 0 3 0 9
⎛
⎜0 2 1 ⎞
0⎟ ⎛
⎜ 1⎞
⎟ ⎛
⎜ 1⎞
𝐴flip ⋅ 𝑑2-bit =⎜ 3 3 ⎟ ⎜ 3 ⎟ = ⎜ 3⎟⎟
⎜
⎜0 1 2
0⎟ ⎜ ⎟ ⎜ 1 ⎟
⎟ ⎜ 1⎟ ⎜ ⎟
3 3 3 3
1 2 1 2
⎝3 0 0 3⎠ ⎝3⎠ ⎝9⎠

9
3 Quantum systems

With the basics for a probabilistic system defined, we now look into describing a quantum
computer mathematically. In the following table you can see the analogy from the quantum
world to the probabilistic world.

Probabilistic world Quantum world

Probability distributions Quantum states
Probabilities Amplitudes
Deterministic possibilities Classical possibilities
Stochastic matrix as process Unitary matrix as process

3.1 Quantum states

One of the most important element of the quantum world is a quantum state. A quantum
state describes the state of a quantum system as a vector. Each entry of the vector represents
a classical possibility (similar to the deterministic possibilities in a probability distribution).
The entries of a quantum state are called amplitude. In contrast to a probabilistic system,
these entries can be negative and are also complex numbers.
These amplitudes tell us the probability of the quantum state being in the corresponding
classical possibility. To calculate the probabilities from the amplitude, we can take the square
of the absolute value of the amplitude.
This means that for the classical possibility 𝑥 and a quantum state 𝜓 the probability for 𝑥
is Pr[𝑥] = |𝜓|2 . To have valid probabilities, the sum of all probabilities need to sum up to 1.
From this we get the formal definition of a quantum state:

Definition 3.1 (Quantum State). A quantum state is a vector 𝜓 ∈ ℂ𝑛 with

𝑛
√∑𝑖=1 |𝜓𝑖 |2 = 1.

Example: Some Quantum states

The following vectors are valid quantum states with the classical possibilities 0 and 1:

1 0 √1 √1
|0⟩ ∶= ( ) |1⟩ ∶= ( ) |+⟩ ∶= ( √12 ) |−⟩ ∶= ( √21 )
0 1 2
− 2

Note that the symbol |⟩ is not yet introduced, so just understand it as some label at this

10
 point. The probabilities for each state can be calculated as follows:

|0⟩ ∶ Pr[0] = |1|2 = 1 Pr[1] = |0|2 = 0

|1⟩ ∶ Pr[0] = |0|2 = 0 Pr[1] = |1|2 = 1
|+⟩ ∶ Pr[0] = | √12 |2 = 1
2 Pr[1] = | √12 |2 = 1
2

|−⟩ ∶ Pr[0] = | √12 |2 = 1

2
−1 2
Pr[1] = | √2
| = 1
2

We can see here that two different quantum states (|+⟩ and |−⟩) can have the same
probabilities for all classical possibilities.

3.2 Unitary transformation

We now have defined quantum states and need a way to describe some processes, which we
want to apply on the quantum states. In the probabilistic world, we have stochastic matrices
for this, but unfortunately we can not use these matrices on quantum states, since the output
of applying these on a quantum state is not guaranteed to be a quantum state again. We
therefore look for a different property of a matrix for which the outcome of applying that
matrix is guaranteed to be a quantum state. We get this property with unitary matrices.

Definition 3.2 (Unitary transformation). Given a quantum state 𝜓 ∈ ℂ𝑛 and a unitary

matrix 𝑈 ∈ ℂ𝑛×𝑛 , the state after the transformation is a quantum state 𝑈 𝜓.

Lemma 3.1 (Unitary matrix). A matrix 𝑈 ∈ ℂ𝑛×𝑛 is called unitary iff 𝑈 † 𝑈 = 𝐼 where
𝐼 is the identity matrix and 𝑈 † is the complex conjugate transpose of 𝑈 .

A unitary matrix is by this lemma invertible, therefore we can undo all unitary transformations
by applying 𝑈 † .

Example: Some Unitary transformations

The following matrices are examples for unitary transformations:

0 1 0 −𝑖 1 0
𝑋=( ) 𝑌 =( ) 𝑍=( )
1 0 𝑖 0 0 −1

These matrices are called Pauli-matrices, we will get to know them later on.
As an example for applying a unitary on a quantum state, we apply the Pauli 𝑋 matrix
on the quantum state |0⟩:

11
 0 1 1 0
𝑋 |0⟩ = ( ) ⋅ ( ) = ( ) = |1⟩
1 0 0 1

4 Observing probabilistic and measuring

quantum systems

So far we only talked about the description of a probabilistic and a quantum system. We now
look into observing/measuring those systems.

4.1 Observing a probabilistic system

Observing a probabilistic system is the process of learning the outcome from a probability
distribution. If our probability distribution for example represents a coin flip, observing this
distribution is equivalent to actually flipping the coin. In the probabilistic case, an observation
is just about updating our knowledge or beliefs. This will be different in the quantum case.

Definition 4.1 (Observing a probabilistic system). Given a probability distribution

𝑑 ∈ ℝ𝑛 , we will get the outcome 𝑖 with a probability 𝑑𝑖 . The new distribution is then

0
⎛
⎜ ⋮⎞
⎟
⎜
⎜ ⎟
⎜ 0⎟
⎟
⎜ ⎟
𝑒𝑖 = ⎜
⎜ 1⎟
⎟ ← 1 at the 𝑖-th position
⎜
⎜ ⎟
⎟
⎜ 0⎟
⎜⋮⎟
⎜ ⎟
0
⎝ ⎠

The intuition for the new distribution is that we now after observing that 𝑖 is the deterministic
possibility for sure.
When observing a probabilistic system, the observation is just a passive process with no impact
on the system. This means that there is no difference to the end result, whether we observe
during the process or not. We take a look at an example to further understand this.

12
Example: Random 1-bit number

We use a random 1-bit number example similar to the random 2-bit example from Chap-
1
ter 2. We have a distribution 𝑑1-bit = ( 21 ) which represents the probability distribution of
2
2 1
generating a 1-bit number with equal probability. We also have a process 𝐴flip = ( 13 3
2)
3 3
which flips the bit with a probability of 13 .
We look at two different cases: For the first case, we observe only the final distribution
and for the second case we observe after the generation of the 1-bit number and we also
observe the final distribution.

4.1.0.0.1 * Observing the final distribution

From Section 2.3 we know that the final distribution 𝑑 is
2 1 1 1
𝑑 = 𝐴flip ⋅ 𝑑1-bit = ( 31 3) (2)
2 1 = ( 21 )
3 3 2 2

We observe this distribution and will get outcome 0 and the new distribution 𝑑 = 𝑒0 =
1
( ) with a probability of Pr[0] = 𝑑0 = 12 and the outcome 1 and the new distribution
0
0
𝑑 = 𝑒1 = ( ) with a probability of Pr[1] = 𝑑1 = 12 .
1

4.1.0.0.2 * Observing after generation and the final distribution

We now observe the system after the generation of the 1-bit number and also observe the
final distribution. After the generation, we will get outcome 0 and the new distribution
1
𝑑 = 𝑒0 = ( ) with a probability of Pr[0] = 𝑑0 = 12 and the outcome 1 and the new
0
0
distribution 𝑑 = 𝑒1 = ( ) with a probability of Pr[1] = 𝑑1 = 21 .
1
1
We now apply in each case the matrix 𝐴flip . This will give us the outcome 𝐴flip ⋅ ( ) =
0
2 1
0
( 31 ) for the case of the outcome 0 and the outcome 𝐴flip ⋅ ( ) = ( 32 ) for the case of
3 1 3
2
the outcome 1. If we observe the distribution ( 31 ), we will get the outcome 0 and the
3
1
new distribution 𝑑 = 𝑒0 = ( ) with a probability of Pr[0] = 23 and the outcome 1 and
0
0
the new distribution 𝑑 = 𝑒1 = ( ) with a probability of Pr[1] = 13 . If we observe the
1

13
 1
1
distribution ( 32 ), we will get the outcome 0 and the new distribution 𝑑 = 𝑒0 = ( ) with
3 0
0
a probability of Pr[0] = 13 and the outcome 1 and the new distribution 𝑑 = 𝑒1 = ( )
1
with a probability of Pr[1] = 32 .
Combining these probabilities, we get the total probability Pr[0] = 12 32 + 21 13 = 12 for the
outcome 0 and the probability Pr[1] = 21 13 + 12 23 = 12 for the outcome 1. This is the same
as observing the final distribution.

4.2 Measuring a quantum system

Unlike in the probabilistic system, the “observation” of a quantum system is called measuring.
The definition is similar to the observation of a probabilistic system, except that we need
to take the absolute square of the amplitude to get the probability and that the state after
measuring is called post-measurement-state (p.m.s.).

Definition 4.2 (Measuring a quantum system). Given a quantum State 𝜓 ∈ ℂ𝑛 , we will

get the outcome 𝑖 with a probability |𝜓𝑖 |2 . The post-measurement-state (p.m.s.) is then

0
⎛
⎜ ⋮⎞
⎟
⎜
⎜ ⎟
⎟
⎜ 0⎟
⎜ ⎟
𝑒𝑖 = ⎜1⎟
⎜ ⎟ ← 1 at the 𝑖-th position
⎜
⎜ ⎟
⎟
⎜ 0⎟
⎜⋮⎟
⎜ ⎟
⎝0⎠

This is called a complete measurement in the computational basis.

With this similarity to the probabilistic observation in the definition, one might assume that
measuring a quantum state has also no impact on the system. This is not the case, mea-
suring a quantum state changes the system! We can see this effect with an example:

Example: Measuring a quantum system

√1 1 1
Let 𝜓 = ( √12 ) be a quantum state and 𝐻 = √1 (
) be a unitary transformation.
2
1 −1 2

We look at two different cases: First we apply 𝐻 immediately and then measure the
system. As a second case, we do a measurement before the application of the 𝐻 unitary
and then a measurement after applying it.

14
 4.2.0.0.1 * Measure the final state
We first calculate the state after applying 𝐻:

1 1 1 √1 1
𝐻𝜓 = √ ( ) ( √12 ) = ( )
2 1 −1 2
0

Measuring this state will get the outcome 0 with probability Pr[0] = |𝜓0 |2 = 1 and have
1
the post-measurement-state ( ).
0

4.2.0.0.2 * Measure the initial and the final state

Measuring 𝜓 with no further unitary matrices applied can have the outcome 0 or 1. We
will look at the final measurement for each case:
The first measurement will have outcome 0 with probability Pr[0] = |𝜓0 |2 = 21 and the
1
post-measurement-state will be ( ). 𝐻 applied to this post-measurement-state will be
0
√ 1
1
𝐻 ( ) = ( √12 ). When measuring this state, we will get the outcome 0 with probability
0 2
Pr[0] = | √12 |2 = 12 and outcome 1 with with probability Pr[1] = | √12 |2 = 12 .
The outcome 1 will appear at the initial state with probability Pr[1] = |𝜓1 |2 = 21 and
0
the post-measurement-state will be ( ). 𝐻 applied to this post-measurement-state will
1
√ 1
0
be 𝐻 ( ) = ( √21 ). When measuring this state, we will get the outcome 0 with
1 − 2
probability Pr[0] = | √12 |2 = 12 and outcome 1 with with probability Pr[1] = | − √12 |2 = 12 .
So independent of the outcome of the first measurement, at the second measurement
the outcome 0 and 1 have a probability of 21 . This shows that when measuring before
applying 𝐻, we will receive different probabilities for the second measurement, then when
measuring only at the end. This proves that measurements can change the system.

4.3 Elitzur–Vaidman bomb tester

This section will be updated later on.

15
5 Partial observing and measuring systems

In the previous chapter, we looked into observing a probabilistic and measuring a quantum
system. In this approach, we alway looked at the full system. This means that we either have
no measurement at all or we know the exact possibility, in which our system is.
For larger systems, this can become quite complicated, as we might not need the full measure-
ment, but only some partial information. For example if we consider a dice throw, we might
not need the final number of the dice, but we are only interested if it is an even or an odd
number. To archive this, we can do a partial observation on a probabilistic system.

5.1 Partially observing a probabilistic system

To perform a partial observation on a probabilistic system, we first decide on which alternatives

we want to distinguish. Each alternative is described by a set 𝐴 of deterministic possibilities.
By performing the partial observation, we will get for each alternative 𝐴 the probability that
the system is in a state in 𝐴.

Definition 5.1 (Partially observing a probabilistic system). Given a distribution 𝑀 ∈

ℝ𝑁 and a family of alternatives 𝐴1 , … , 𝐴𝑚 ⊆ {1, … , 𝑁 } with 𝐴𝑖 ∩ 𝐴𝑗 = ∅ and ⋃𝑖 𝐴𝑖 =
{1, … , 𝑁 }, the probability of observing the alternative 𝑘 is given by

Pr[outcome = 𝑘] = ∑ 𝑀𝑖 = ‖𝑣(𝑘) ‖1
𝑖∈𝐴𝑘

‖‖1 denotes the 1-norm here. The distribution after the observation of the outcome 𝑘 is
given by the normalized conditional distribution. This is computed by

1. Computing the non-normalized conditional distribution 𝑣(𝑘) denoted by 𝑣(𝑘) ∶=

(𝑣1 , … , 𝑣𝑁 ) with
𝑀 if 𝑖 ∈ 𝐴𝑘
𝑣𝑖 ∶= { 𝑖
0 else
2. Computing the normalized conditional distribution by calculating

𝑣(𝑘)
Pr[outcome = 𝑘]

Note that similar to the full observation of a probabilistic system a partial observation has
no impact on the system. We only get some new knowledge but do not influence the actual
system by our observation.

16
5.2 Partially measuring a quantum system

Similar to the partial observation of a probabilistic system, we can perform a partial measure-
ment on a quantum system.

Definition 5.2 (Partially measuring a quantum system). Given a quantum state 𝜓 ∈ ℂ𝑁

and a family of alternatives 𝐴1 , … , 𝐴𝑚 ⊆ {1, … , 𝑁 } with 𝐴𝑖 ∩ 𝐴𝑗 = ∅ and ⋃𝑖 𝐴𝑖 =
{1, … , 𝑁 }, the probability of the alternative 𝑘 is given by

Pr[outcome = 𝑘] = ∑ |𝜓𝑖 |2 = ‖𝜙(𝑘) ‖2

𝑖∈𝐴𝑘

‖‖ denotes the Euclidean norm here. The post-measurement-state (p.m.s.) of the outcome
𝑘 is computed as follows:

1. Computing the non-normalized post-measurement-state 𝜙(𝑘) denoted by 𝜙(𝑘) ∶=

(𝜙1 , … , 𝜙𝑁 ) with
𝜓 if 𝑖 ∈ 𝐴𝑘
𝜙𝑖 ∶= { 𝑖
0 else
2. Computing the normalized post-measurement-state by calculating

𝜙(𝑘) 𝜙(𝑘)
= (𝑘)
√Pr[outcome = 𝑘] ‖𝜙 ‖

As with the complete measurement for quantum systems, the measurement can change the
system. Note that there exists other types of definitions for a measurement e.g. projective
measurement, generalized measurements, POVMs, … The variant above can best be described
as a “projective measurement in the computational basis”.

6 Composite Systems

So far our probabilistic and quantum systems consist of only one single distribution/state. In
the real world, quantum computers often have several different registers (variables).
In theory, we could use a single very big distribution/state to model multiple qubits.
For example a 10 qubit system could be modeled with the classical possibilities
0000000000, 0000000001, … , 1111111110, 1111111111.

17
Unfortunately the vector for these states gets really big, for 10 qubits, the vector would have
the dimension of 1024. Since this is very inconvenient to write down, we need to look at a
different solution. For this, we compose different probabilistic or quantum systems with each
other.

6.1 Constructing composite systems

Definition 6.1 (Composite systems / Tensor product). Given two probabilistic or quan-
tum systems 𝐴 and 𝐵 with the possibilities of 𝐴 given by 1, … , 𝑁 1 and a distribution/state
𝑎 and with the possibilities of 𝐵 given by 1, … , 𝑀 and a distribution/state 𝑏, the com-
posite system called 𝐴𝐵 has the possibilities

11, 12, … , 1𝑀 , 21, 22, … , 2𝑀 , … , 𝑁 1, 𝑁 2, … , 𝑁 𝑀

and the distribution/state 𝑎𝑏 of 𝐴𝐵 is given by the tensor product

𝑎1 ⋅ 𝑏
⎜ ⋮ ⎞
𝑎𝑏 = 𝑎 ⊗ 𝑏 = ⎛ ⎟
⎝ 𝑎𝑁 ⋅ 𝑏 ⎠
This vector has the size 𝑁 𝑀 .

Note that the definition of combining a probabilistic and a quantum system are the same.

Example: Tensor product

Given two vectors 𝑎 and 𝑏, with

1
10
𝑎=⎛
⎜2⎞⎟ 𝑏=( )
100
⎝4⎠
the tensor product of those vectors is given by

1 ⋅ 10 10
⎛
⎜1 ⋅ 100⎞⎟ ⎛
⎜ 100⎞
⎟
1 ⎜
⎜ ⎟
⎟ ⎜
⎜ ⎟
⎟
10 2 ⋅ 10 20
𝑎⊗𝑏 =⎛
⎜2⎞⎟⊗( )=⎜
⎜
⎜
⎟
⎟
⎟ = ⎜
⎜
⎜
⎟
⎟
⎟
100 ⎜2 ⋅ 100 ⎟ ⎜ 200⎟
⎝4⎠ ⎜ 4 ⋅ 10 ⎟ ⎜ 40 ⎟
⎜ ⎟ ⎜ ⎟
⎝4 ⋅ 100⎠ ⎝400⎠

1
Note that the possibilities are labels 1, … , 𝑁 and do not have be the numbers 1, … , 𝑁. We could also label
these e.g. red, green and blue (or any other label).

18
We now need a way to apply operators on these combined systems. For this we can also con-
struct the tensor product of either two probabilistic processes or two unitary transformations
by using the tensor product of two matrices.

Definition 6.2 (Composite matrices / Tensor product). Given two matrices 𝑆 and 𝑇
with 𝑆 of the size 𝑁 × 𝑁 and 𝑇 of the size 𝑀 × 𝑀 . The tensor product 𝑆 ⊗ 𝑇 of is given
by
𝑆11 𝑇 … 𝑆1𝑁 𝑇
𝑆⊗𝑇 =⎛ ⎜ ⋮ ⋱ ⋮ ⎞⎟
⎝𝑆𝑁1 𝑇 … 𝑆𝑁𝑁 𝑇 ⎠

Overall we can say: If we apply 𝑆 to the system 𝐴 and 𝑇 to the system 𝐵, we apply 𝑆 ⊗ 𝑇 to
the composite system 𝐴𝐵.
If the distribution 𝑑𝐴𝐵 of a given probabilistic system 𝐴𝐵 can be written as a composite of
two distributions 𝑑𝐴 and 𝑑𝐵 , we know that 𝐴 and 𝐵 are independent of each other. If we can
not write 𝑑𝐴𝐵 as two septate systems, the probabilities are depended on each other.
If the quantum state 𝜓𝐴𝐵 of a given quantum system 𝐴𝐵 can be written as a composite of two
different quantum states 𝜓𝐴 and 𝜓𝐵 , the quantum states of 𝐴 and 𝐵 are independent of each
other. If we can not write 𝜓𝐴𝐵 as a tensor product of two quantum systems, the quantum
states depend on each other. We call this entangled.

6.2 Measuring composite systems

To perform a (partial) observation or (partial) measurement on a composite system 𝐴𝐵, we

can compose two separate measurements on the systems 𝐴 and 𝐵 similar as we constructed
the tensor product.

Definition 6.3 (Composite measurements). Given two systems 𝐴 and 𝐵 with possibili-
ties 1, … , 𝑁 and 1, … , 𝑀 and two partial measurements 𝑀𝐴 and 𝑀𝐵 on systems 𝐴 and
𝐵 with alternatives 𝐴1 , … , 𝐴𝑁 ⊆ {1, … , 𝑁 } and 𝐵1 , … , 𝐵𝑀 ⊆ {1, … , 𝑀 }. The measure-
ment 𝑀𝐴 ⊗ 𝑀𝐵 on 𝐴𝐵 is a measurement with the alternatives 𝐶11 , 𝐶12 , … , 𝐶𝑁𝑀 where
𝐶𝑖𝑗 = 𝐴𝑖 × 𝐵𝑗 .
If we only have a set of alternatives for system 𝐴, we can do a measurement 𝑀𝐴 ⊗ 𝐼 with
alternatives 𝐶1 , … , 𝐶𝑁 ∶= 𝐴 ⊗ {1, … , 𝑀 }.

19
7 Quantum Circuits

In the previous chapters, we learned the basics on how to construct a quantum computer. We
will now start constructing quantum circuits from these. Note that we will no longer look into
probabilistic system.
The quantum systems which we consider in the following sections consist of qubits, unless
specified otherwise. A qubit is a quantum state 𝜓 with 𝜓 ∈ ℂ2 .

7.1 Visual language

So far we have only seen the elements of quantum computers in a mathematical form. When
constructing quantum circuits, this can get very unreadable very fast. Therefore we can draw
quantum circuits as a picture, which also helps us to get a better intuition for these circuits.
You can see a very simple example here:

X
U
H H

Figure 7.1: A basic quantum circuit

In this circuit we have two qubits, which are drawn as separate wires. We first apply the
unitary 𝑋 on the top wire and at the same time we apply the unitary 𝐻 at the bottom wire.
Mathematically this can be written as 𝑋 ⊗ 𝐻. Next we apply the unitary 𝑈 , which operates
on both qubits. After this, we apply a unitary 𝐻 on the bottom wire. Since we do not apply
anything on the top wire, we can write this mathematically as 𝐼 ⊗ 𝐻. Finally we measure the
top qubit. This means a complete measurement in the computational basis of the qubit as
described in Section 4.2.

7.2 Important gates

When working with quantum computers, we encounter some of the same unitaries very often.
We distinguish between single qubit gates (unitary transformations ∈ ℂ2×2 ) and gates on
multiple qubits.

20
7.2.1 Single qubit gates

The following gates are relevant single qubit gates:

Definition 7.1 (Pauli matrices). The Pauli matrices 𝑋, 𝑌 and 𝑍 are defined as

0 1 0 −𝑖 1 0
𝑋=( ) 𝑌 =( ) 𝑍=( )
1 0 𝑖 0 0 −1

Note that 𝑋 is also called bit-flip.

Definition 7.2 (Hadamard gate). The Hadamard gate 𝐻 is defined as

1 1 1
𝐻=√ ( )
2 1 −1

1
The Hadamard gate is useful for introducing superpositions as it takes a classical bit ( ) and
0
√1
transforms it into a superposition ( √12 ).
2

7.2.2 Controlled-NOT gate

The gates introduced above only operate on a single qubit. To connect two different qubits,
we need gates which operate on multiple qubits. For this we introduce the controlled-not:

Definition 7.3 (Controlled-NOT gate). The controlled-NOT gate CNOT ∈ ℂ4×4 is

defined as
1 0 0 0
⎜0 1 0 0 ⎞
⎛ ⎟
CNOT = ⎜ ⎜ ⎟
⎜0 0 0 1 ⎟ ⎟
⎝ 0 0 1 0 ⎠
The CNOT gate flips the qubit of the second qubit if the first qubit is 1. We call the
first wire the controlling wire and the second wire the target wire. It can be drawn in a
quantum circuit as follows:

21
 Figure 7.2: Controlled-NOT in a quantum circuit

If the second qubit should be the controlling wire and the first qubit the target wire, we
′
can use CNOT denoted as
1 0 0 0
⎛
⎜
′0 0 0 1⎞⎟
CNOT = ⎜
⎜ ⎟
⎜0 0 1 0⎟⎟
⎝0 1 0 0⎠

7.3 Ket Notation

So far we have only seen vectors as a way to mathematically describe a quantum state. This
can get quite inconvenient if the vector get bigger and also often contains not that much useful
information (e.g. a lot of 0 entries). We therefore introduce a new form of writing quantum
states called the ket notation.
The idea works as follows: We can rewrite a quantum state 𝜓 in the following way

𝜓1 1 0 0
⎛ ⎞
⎜ 𝜓2 ⎟ ⎛
⎜ ⎞
0⎟ ⎛
⎜ ⎞
1⎟ ⎛
⎜0⎞⎟
𝑁
𝜓=⎜
⎜ ⎟ = 𝜓 ⎜ ⎟ + 𝜓 ⎜ ⎟ + ⋯ + 𝜓 ⎜ ⎟ = ∑ 𝜓𝑖 ⋅ 𝑒𝑖
⎜ ⋮ ⎟⎟ ⎜⋮⎟
1⎜ ⎟ ⎜⋮⎟
2⎜ ⎟ ⎜⋮⎟
𝑁⎜ ⎟
𝑖=1
⎝𝜓𝑁 ⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠

The vector 𝑒𝑖 denotes the vector with 0 entries at every position except the 𝑖-th position, where
the entry is 1.
From this notation we already get an advantage, since we can drop out all 0 entries. But we
still have no intuitive mapping from the vector 𝑒𝑖 to the classical possibility represented by 𝑒𝑖 .
For this we use a |⟩ symbol. More precise this means for a classical possibility 𝑥, which is the

22
𝑖-th possibility and is represented by 𝑒𝑖 , we write
0
⎛
⎜ ⋮⎞
⎟
⎜
⎜ ⎟
⎜ 0⎟
⎜ ⎟⎟
|𝑥⟩ ∶= 𝑒𝑖 = ⎜
⎜ 1⎟
⎟ ← 1 at the 𝑖-th position
⎜
⎜ ⎟
⎟
⎜ 0⎟
⎜
⎜⋮⎟⎟
⎝0⎠

Example: Ket notation

Given a quantum system with the classical possibilities 00, 01, 10 and 11, the quantum
𝑇
state 𝜓 = ( √12 0 0 √12 ) can be written as

√1
2
⎜0⎞
⎛ ⎟ 1 1
𝜓=⎜
⎜ ⎟
⎟ = √ |00⟩ + √ |11⟩
⎜0⎟ 2 2
√1
⎝ 2⎠

Written like this, we can see at first glance that this is a superposition of the classical
possibilities 00 and 11.

Note that the ket notation can also be used in a few other ways. We can use it as described
above to describe the classical possibility 𝑥 as |𝑥⟩, but we also use it to emphasize that 𝜓 is a
quantum state by writing |𝜓⟩ (here 𝜓 is not a classical possibility). We also have two special
cases |+⟩ and |−⟩ which are defined as follows:
1 1
|+⟩ ∶= √ |0⟩ + √ |1⟩
2 2
1 1
|−⟩ ∶= √ |0⟩ − √ |1⟩
2 2
Which of the meanings of the symbol |⟩ is meant has to be deduced from the context.

8 Bernstein-Vazirani Algorithm

With all the quantum basics from the previous chapters, we now can start with the first
quantum algorithm. This algorithm is called the Bernstein-Vazirani algorithm.

23
This algorithm tackles the following problem: Given a secret 𝑠 ∈ {0, 1}𝑛 and the function
𝑓 ∶ {0, 1}𝑛 → {0, 1}, defined as 𝑓(𝑥) ∶= 𝑥 ⋅ 𝑠. ⋅ denotes the inner product of two bitstrings here.
This means that for bitstrings 𝑥 and 𝑦 of length 𝑛, the inner product is 𝑥 ⋅ 𝑦 = 𝑥1 𝑦1 + ⋯ +
𝑥𝑛 𝑦𝑛 mod 2.
The goal is to find the secret 𝑠 using as little queries of 𝑓 as possible. By “query” we mean
an evaluation of 𝑓. The word query stems from the fact that we often think of the algorithm
having access to a so-called “oracle” which we can “query” to get 𝑓(𝑥).
Classically we will need at least 𝑛 queries to 𝑓 to get 𝑠 definitely. A classical algorithm with
only 𝑚 ≤ 𝑛 queries will get 𝑠 with a probability of 2𝑚−𝑛 if 𝑠 is uniformly random.
We will now look at a quantum algorithm which will find 𝑠 with only one evaluation of 𝑓. This
algorithm is sketched in the following circuit:

1 2 3 4 s
n n
|0⟩ H ⊗n H ⊗n
Uf
|1⟩ H

Figure 8.1: The quantum circuit for Bernstein-Vazirani

Note that 𝑈𝑓 is defined with the explanation below.

We start with 𝑛 qubits on the top wire. All of these qubits are in the state |0⟩, which we write
𝑛
|0⟩ = |0⟩ ⊗ ⋯ ⊗ |0⟩. The bottom wire is in the state |1⟩. Both wires composed together can
𝑛
be written as 𝜓1 = |0⟩ ⊗ |1⟩, which is the overall starting state of our algorithm (the state at
slice 1). We now perform the following steps

1. First we apply a Hadamard gate on all qubits. This is denoted for the first 𝑛 qubits by
the 𝐻 ⊗𝑛 gate and for the last qubit by the 𝐻 gate on the bottom wire. The resulting

24
 quantum state is calculated as follows:
𝑛
𝜓2 = (𝐻 ⊗𝑛 ⊗ 𝐻) (|0⟩ ⊗ |1⟩)
𝑛
= (𝐻 ⊗𝑛 |0⟩ ) ⊗ 𝐻 |1⟩
⊗𝑛
= (|+⟩) ⊗ |−⟩
⊗𝑛
1 1
= ( √ |0⟩ + √ |1⟩) ⊗ |−⟩
2 2
1
=√ ∑ |𝑥⟩ ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛

Roughly speaking, we are now in the superposition over all classical possibilities on the
top wire and in |−⟩ on the bottom wire at slice 2.
2. Next, we apply the unitary 𝑈𝑓 on both wires. This unitary is defined as

𝑈𝑓 |𝑥, 𝑦⟩ = |𝑥, 𝑦 ⊕ 𝑓(𝑥)⟩

This unitary represents the function 𝑓 and combines the output of 𝑓(𝑥) with the bottom
wire 𝑦. For our quantum states, this means that the state after 𝑈𝑓 at slice 3 can be
calculated as follows:
1
𝜓3 = 𝑈 𝑓 √ ∑ |𝑥⟩ ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛
1
=√ ∑ 𝑈𝑓 (|𝑥⟩ ⊗ |−⟩)
2𝑛 𝑥∈{0,1}𝑛

∗ 1
=√ ∑ (−1)𝑓(𝑥) |𝑥⟩ ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛

1
=⎛
⎜√ ∑ (−1)𝑓(𝑥) |𝑥⟩⎞
⎟ ⊗ |−⟩
𝑛
⎝ 2 𝑥∈{0,1}𝑛 ⎠

25
 Note that the ∗ holds since we can rewrite 𝑈𝑓 (|𝑥⟩ ⊗ |−⟩) as

𝑈𝑓 (|𝑥⟩ ⊗ |−⟩)
1 1
= √ 𝑈𝑓 |𝑥, 0⟩ − √ |𝑥, 1⟩
2 2
1 1
= √ |𝑥, 𝑓(𝑥)⟩ − √ |𝑥, 𝑓(𝑥)⟩
2 2
√1 |𝑥, 0⟩ − √1 |𝑥, 1⟩ 𝑓(𝑥) = 0
= { 12 2
√ |𝑥, 1⟩ − √1 |𝑥, 0⟩ 𝑓(𝑥) = 1
2 2

|𝑥⟩ ⊗ |−⟩ 𝑓(𝑥) = 0

={
− |𝑥⟩ ⊗ |−⟩ 𝑓(𝑥) = 1
= (−1)𝑓(𝑥) |𝑥⟩ ⊗ |−⟩

The bottom wire has not changed and is still |−⟩. But on the top wire, we now have
𝑓(𝑥) somehow encoded into our quantum state. The phenomenon that the output of
𝑓 is encoded as a −1 in the input register is called phase kickback. Measuring this
quantum state would not give us any advantage, since we would just get one random 𝑥.
We therefore perform one final step before measuring.
3. As the final unitary, we perform another 𝐻 ⊗𝑛 on the top wire. We hope that the result of
this unitary transformation is the state |𝑠⟩. To check, whether our hopes become reality,
†
we can calculate (𝐻 ⊗𝑛 ) |𝑠⟩ ⊗ |−⟩ and check if it is equal to 𝜓3 . We do it in this direction,

26
 since these calculations are a bit simpler:
†
(𝐻 ⊗𝑛 ) |𝑠⟩ ⊗ |−⟩ = 𝐻 ⊗𝑛 |𝑠⟩ ⊗ |−⟩
= 𝐻 ⊗𝑛 (|𝑠1 ⟩ ⊗ ⋯ ⊗ |𝑠𝑛 ⟩) ⊗ |−⟩
= 𝐻 |𝑠1 ⟩ ⊗ ⋯ ⊗ 𝐻 |𝑠𝑛 ⟩ ⊗ |−⟩
𝑛
1 1
= ⨂ ( √ |0⟩ + (−1)𝑠𝑖 √ |1⟩) ⊗ |−⟩
𝑖=1 2 2
1 𝑛
= √ ⨂(|0⟩ + (−1)𝑠𝑖 |1⟩) ⊗ |−⟩
2𝑛 𝑖=1
1
=√ ∑ ((−1)𝑥1 𝑠1 (−1)𝑥2 𝑠2 … (−1)𝑥𝑛 𝑠𝑛 |𝑥⟩) ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛
1
=√ ∑ ((−1)∑𝑖 𝑥𝑖 𝑠𝑖 mod 2 |𝑥⟩) ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛
1
=√ ∑ (−1)𝑠⋅𝑥 |𝑥⟩ ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛
1
=√ ∑ (−1)𝑓(𝑥) |𝑥⟩ ⊗ |−⟩
2𝑛 𝑥∈{0,1}𝑛

= 𝜓3

This calculation shows that we have the quantum state |𝑠⟩ ⊗ |−⟩ at slice 4.
4. We now perform a measurement on the top wire and measure 𝑠 as a result.

This concludes the Bernstein-Vazirani algorithm.

9 Shor’s Algorithm

One of the best known quantum algorithm is Shor’s algorithm for finding the prime factors of
an integer. It was developed by Peter Shor in 1994.

9.1 Discrete Fourier Transformation

One of the tools required for Shor’s algorithm is the Discrete Fourier Transformation (DFT).
Generally, a Fourier transformation is a mathematical technique that decomposes a function

27
into its constituent frequencies. We use the DFT to find the period of a vector.
The DFT is defined as follows:

Definition 9.1 (Discrete Fourier Transformation (DFT)). The discrete Fourier trans-
form (DFT) is a linear transformation on ℂ𝑀 represented by the matrix

1
DFT𝑀 = √ (𝜔𝑘𝑙 )𝑘𝑙 ∈ ℂ𝑀×𝑀
𝑀

with 𝜔 = 𝑒2𝑖𝜋/𝑀 , which is the 𝑀 -th root of unity.

This transformation is best imagined as a process, which takes a periodic vector as an input
and outputs the period of that vector. The DFT has some important properties, which help
us later on.

Theorem 9.1 (Properties of the DFT). Here are some properties of the DFT which can
be used without further proof.

1. The DFT is unitary.

2. 𝜔𝑡 = 𝜔𝑡 mod 𝑀 for all 𝑡 ∈ ℤ.
3. Given a quantum state 𝜓 ∈ ℂ𝑀 which is 𝑟-periodic and where 𝑟 ∣ 𝑀 , DFT𝑀 𝜓 will
compute a quantum state 𝜙 ∈ ℂ𝑀 , which has non-zero values on the multiples of
𝑀 𝑀
𝑟 . Note that 𝑟 intuitively represents the frequency of 𝜓. This means, that

√1 , if 𝑀
∣𝑖
𝑟 𝑟
|𝜙𝑖 | = {
0, otherwise

9.2 Reducing factoring to period finding

With the DFT, we have seen, that we can use a unitary to find the period of a quantum state.
We now look into using period finding to factor integers. We first look at the definition of the
two problems:

Definition 9.2 (Factoring problem). Given integer 𝑁 with two prime factors 𝑝, 𝑞 such
that 𝑝𝑞 = 𝑁 and 𝑝 ≠ 𝑞, find 𝑝 and 𝑞.

Note that this definition of the factoring problem is a simplified version of the factoring problem,
where 𝑁 has only 2 prime factors.

28
 Definition 9.3 (Period finding problem). Given 𝑓 ∶ ℤ → 𝑋 with 𝑓(𝑥) = 𝑓(𝑦) iff 𝑥 ≡
𝑦 mod 𝑟 for some fixed secret 𝑟. 𝑟 is called the period of 𝑓. Find 𝑟.

To start the reduction, we need a special case of the period finding problem called order
finding:

Definition 9.4 (Order finding problem). For known 𝑎 and 𝑁 which are relatively prime,
find the period 𝑟 of 𝑓(𝑖) = 𝑎𝑖 mod 𝑁 . We call 𝑟 the order of 𝑎 written 𝑟 = ord 𝑎. (This
is similar to finding the smallest 𝑖 > 0 with 𝑓(𝑖) = 1).

Since the order finding problem is just the period finding problem for a specific 𝑓(𝑥), we know
that if we can solve the period finding problem within reasonable runtime, we can also solve
the order finding problem within reasonable runtime. We now reduce the factoring problem
to the order finding problem:
We have a integer 𝑁 as an input for the factoring problem.

1. Pick an 𝑎 ∈ {1, … , 𝑁 − 1} with 𝑎 relatively prime to 𝑁 .

2. Compute the order of 𝑎, so that 𝑟 = ord 𝑎 (using the solver for the order finding
problem).
3. If the order 𝑟 is odd, we abort.
𝑟 𝑟
4. Calculate 𝑥 ∶= 𝑎 2 + 1 mod 𝑁 and 𝑦 ∶= 𝑎 2 − 1 mod 𝑁 .
5. If gcd(𝑥, 𝑁 ) ∈ {1, 𝑁 }, we abort.
6. We compute 𝑝 = gcd(𝑥, 𝑁 ) and 𝑞 = gcd(𝑦, 𝑁 ).

The output of the reduction are 𝑝, 𝑞, such that 𝑝𝑞 = 𝑁 . This holds, since
𝑟 𝑟
𝑥𝑦 = (𝑎 2 + 1)(𝑎 2 − 1) = 𝑎𝑟 − 1 ≡ 1 − 1 = 0 (mod 𝑁 )

Theorem 9.2 (Probability of an abort). If 𝑁 has at least two different prime factors
and 𝑁 is odd, then the probability to abort is ≤ 12 .

All in all this reduction shows, that if we have an oracle which can solve the period finding
problem within reasonable runtime, we can also solve the factoring problem within reasonable
runtime (since all other operations are classically fast to compute).

9.3 The quantum algorithm for period finding

We now look into an quantum algorithm that solves the period finding problem within rea-
sonable runtime. The quantum circuit for Shor’s algorithm requires a 𝑓 ∶ ℤ → 𝑋 which is
𝑟-periodic. 𝑋 denotes an arbitrary set here. We choose a number 𝑚 which needs to be big

29
enough to encode the values of 𝑋 and choose a number 𝑛 under the condition of 𝑛 ≥ 2 log2 (𝑟)
for the post processing to work. Note that when using this algorithm for factoring, we choose
𝑛 to be 𝑛 ∶= 2|𝑁 |, since 𝑟 ≤ 𝑁 . |𝑁 | denotes the number of bits needed to encode 𝑁 here.
The quantum algorithm for period finding is shown in this figure:

1 2 3 4 5 6
n
|0n ⟩ H ⊗n DFT2n
Uf
m
|0m ⟩

Figure 9.1: Shor’s algorithm (quantum part)

The algorithm works as follows:

1. We start with a |0⟩ entry on every wire.

2. We bring the top wire into the superposition over all entries. The quantum state is then
−𝑛
2 2 ∑𝑥 |𝑥⟩ ⊗ |0𝑚 ⟩.
3. We apply 𝑈𝑓 , which is the unitary of 𝑓 ∶ {0, 1}𝑛 → {0, 1}𝑚 . This calculates the superpo-
sition over all possible values 𝑓(𝑥) on the bottom wire. The resulting quantum state is
−𝑛
2 2 ∑𝑥 |𝑥, 𝑓(𝑥)⟩.
4. To understand the algorithm better, we measure the bottom wire at this point. This
will give us one random value 𝑓(𝑥0 ) for some 𝑥0 . The top wire will then contain a
superposition over all values 𝑥 where 𝑓(𝑥) = 𝑓(𝑥0 ). Since 𝑓 is known to be 𝑟-periodic,
we know, that 𝑓(𝑥) = 𝑓(𝑥0 ) iff 𝑥 ≡ 𝑥0 mod 𝑟. This means,√
that the resulting quantum
state on the top wire is periodic and can be written as √2𝑟𝑛 ∑𝑥≡𝑥 mod 𝑟 |𝑥⟩ ⊗ |𝑓(𝑥0 )⟩. For
0
simplicity we assume, that 𝑟 ∣ 2𝑛 holds.
5. We apply the Discrete Fourier Transform on the top wire. This will “analyze” the top wire
𝑛
for the period and output a vector with entries at multiples of 2𝑟 as seen in Theorem 9.1.
For simplicity we still assume, that 𝑟 ∣ 2𝑛 holds.
𝑛
6. We measure the top wire and get one random multiple of 2𝑟 , which we can denote as
𝑛
𝑎 ⋅ 2𝑟
𝑛
Since we get a multiple of 2𝑟 on each run, we can simply run the algorithm multiple times
𝑛
to get different multiples and then compute 2𝑟 by taking the gcd of those multiples. From
that we compute 𝑟. Unfortunately this only works because we assumed 𝑟 ∣ 2𝑛 . Since this does
𝑛
usually not hold, we only get approximate multiples of 2𝑟 (which is not even an integer) and
thus post processing is a bit more complex.

30
9.4 Post processing

So far we have seen the DFT to analyze the period of a quantum state, we have seen a way to
reduce the factoring problem to the period finding and we have seen a quantum algorithm for
finding an approximate multiple of such a period of a function. We just need one final step to
find 𝑟. For this we start with a theorem:

Theorem 9.3. Iff 𝑓 ∶ ℤ → 𝑋 is 𝑟-periodic, the following holds with probability

Ω(1/ log log 𝑟):
−𝑟 𝑟
≤ 𝑟𝑐 mod 2𝑛 ≤
2 2
where 𝑐 is the output of the second measurement of the quantum circuit described in
Section 9.3 and 𝑛 is the number of qubits on the upper wire of the quantum circuit.

We assume that the theorem holds for our outcome 𝑐 of the second measurement (if that is
not the case, our result will be wrong and we can just run the quantum algorithm again to get
a different outcome):
Then exists an integer 𝑑 such that:
𝑟
|𝑟𝑐 − 𝑑2𝑛 | ≤
2
𝑐 𝑑 1
⟺ | 𝑛 − | ≤ 𝑛+1 | division by 𝑟 ⋅ 2𝑛
2 𝑟 2
𝑐 𝑑 1 𝑐
The fraction 2𝑛 is known, so the goal is to find a fraction 𝑟 that is 2𝑛+1 -close to 2𝑛 .

Since 𝑛 is the number of qubits used in the quantum circuit and was chosen, such that 𝑛 ≥
1
2 log2 (𝑟) and thus 2𝑛 ≥ 𝑟2 holds and from this we know that 2𝑛+1 ≤ 2𝑟12 holds as well.
So if Theorem 9.3 holds, we now | 2𝑐𝑛 − 𝑑𝑟 | ≤ 2𝑟12 also holds. Our task is now rewritten to find
𝑑
𝑟 under this condition. For this we use another theorem:

Theorem 9.4. For a given real number 𝜑 ≥ 0 and integer 𝑞 > 0 there is at most one
fraction 𝑑𝑟 with 𝑟 ≤ 𝑞 and |𝜑 − 𝑑𝑟 | ≤ 2𝑞
1
. In this case, this 𝑑𝑟 is a convergent of the
continued fraction expansion of 𝜑.

This theorem uses the convergent of a continued fraction expansion. A continued fraction
expansion of a number 𝑡 is the number rewritten as a fraction in the form

1
𝑡 = 𝑎0 + 1
𝑎1 + 𝑎2 + 𝑎 1
3 +…

where 𝑎𝑖 always has to be the biggest possible integer. We call [𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 , … ] the continued
expansion of 𝑡. The expansion is finite iff t is rational. For a given continued expansion, a

31
prefix [𝑎0 , … , 𝑎𝑖 ] is called a convergent. Writing this convergent as a normal fraction will give
us an approximation of the number 𝑡.

Example: continued expansion of a fraction

The number 2.3 can be written as

1
2.3 = 2 + 1
3 + 3+0

and the continued fraction expansion of 2.3 is [2, 3, 3]. The expansions [2] and [2, 3] are
convergents of the expansion of 2.3 and written as a fraction will give us the approxima-
tions 2 and 2 + 13 = 2.3.̄
The number 0.99 can be written as
1
0.99 = 0 + 1
1+ 99+0

and the continued fraction expansion of 0.99 is [0, 1, 99]. The expansions [0] and [0, 1] are
convergents of the expansion of 0.99 and written as a fraction will give us the approxi-
mations 0 and 0 + 11 = 1.

Using Theorem 9.4 (with 𝜑 ∶= 2𝑐𝑛 and 𝑞 ∶= 2𝑛 ) we can find 𝑑

𝑟 and from this 𝑟 which is the
period of our function using the following steps:
For each convergent 𝛾 of 𝜑 do the following:

1. Compute 𝛾 as fraction 𝑑𝑟 .
2. Stop if 𝑟 ≤ 2𝑛 and this 𝑑𝑟 is 1
2𝑛+1 -close to 𝑐
2𝑛 and return 𝑟.

Note: It can happen, that the resulting fraction does not have the right 𝑟 in the denominator,
because 𝑑𝑟 was simplified (if numerator and denominator shared a common factor). But the
probability of this happening is sufficiently small and already included in the probability in
Theorem 9.3.
This completes the postprocessing of Shor’s algorithm.

9.5 Constructing the DFT

So far we have described everything necessary for Shor’s algorithm, but only described the
matrix representation of the DFT𝑀 . We will now take a closer look into implementing the
DFT𝑀 as a quantum circuit. Since we only use the DFT𝑀 for Shor’s algorithm so far, we will
only look at 𝑀 = 2𝑛 , which is the DFT applied on 𝑛 qubits.

32
To start the circuit, we recall the definition of the DFT2𝑛 from Definition 9.1: DFT2𝑛 ∶=
√1 (𝜔𝑘𝑙 ) 2𝜋𝑖/2𝑛
2𝑛 𝑘𝑙 with 𝜔 ∶= 𝑒 . To apply the DFT2𝑛 to a quantum state |𝑗⟩ we calculate

1 −𝑛
DFT2𝑛 |𝑗⟩ = √ ∑ 𝑒2𝜋𝑖𝑗𝑘2 |𝑘⟩
𝑛
2 𝑘

We can rewrite this as follows:

1 −𝑛
DFT2𝑛 |𝑗⟩ = √ ∑ 𝑒2𝜋𝑖𝑗𝑘2 |𝑘⟩
𝑛
2 𝑘
1 −𝑙
= √ ∑ … ∑ 𝑒2𝜋𝑖𝑗(∑𝑙 𝑘𝑙 2 ) |𝑘1 … 𝑘𝑛 ⟩
𝑛
2 𝑘1 𝑘𝑛
𝑛
1 −𝑙
= √ ∑ … ∑ ⨂ 𝑒2𝜋𝑖𝑗(𝑘𝑙 2 ) |𝑘𝑙 ⟩
𝑛
2 𝑘1 𝑘𝑛 𝑙=1

1 𝑛 −𝑙
= √ ⨂ ∑ 𝑒2𝜋𝑖𝑗(𝑘𝑙 2 ) |𝑘𝑙 ⟩
𝑛
2 𝑙=1 𝑘𝑙
1 𝑛 −𝑙
= √ ⨂(|0⟩ + 𝑒2𝜋𝑖𝑗2 |1⟩)
𝑛
2 𝑙=1
1 𝑛
= √ ⨂(|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛−(𝑙−1) …𝑗𝑛 |1⟩)
2𝑛 𝑙=1
𝑛
1
= ⨂ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛−(𝑙−1) …𝑗𝑛 |1⟩)
𝑙=1 2
1 1
The expression 0.𝑗 expresses a binary fraction (e.g. 0.101 = 2 + 8 = 58 ).
With this we have shown, that we can write DFT2𝑛 |𝑗⟩ as the following tensor product of
quantum states

1 1 1
√ (|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛 |1⟩) ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛−1 𝑗𝑛 |1⟩) ⊗ ⋯ ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 …𝑗𝑛 |1⟩)
2 2 2

From this rewritten tensor product, we can get an idea on how to construct the quantum
circuit for the DFT2𝑛 . Namely, we can construct a quantum circuit for each element of the
tensor product and from this build the general circuit.
For this, we segment the tensor product into different elements 𝜓 as follows:

1 1 1
√ (|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛 |1⟩) ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗𝑛−1 𝑗𝑛 |1⟩) ⊗ ⋯ ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 …𝑗𝑛 |1⟩)
2
⏟⏟⏟⏟⏟⏟⏟⏟⏟ 2
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟ 2
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
𝜓1 𝜓2 𝜓𝑛

33
We also introduce a new gate 𝑅𝑘 which is defined by the following matrix:

1 0
𝑅𝑘 ∶= ( 2𝜋𝑖/2𝑘 )
0 𝑒

To understand the construction of the circuit from these elements, we will look at an example
for 𝑛 = 3 first:

Example: Construction of the DFT circuit for 𝑛 = 3

We start by building the tensor product for 𝑛 = 3. The input for the DFT circuit is
|𝑗⟩ = |𝑗1 𝑗2 𝑗3 ⟩. Using the formula from above, we can write the result of DFT23 |𝑗⟩ as the
following tensor product:
1 1 1
√ (|0⟩ + 𝑒2𝜋𝑖0.𝑗3 |1⟩) ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗2 𝑗3 |1⟩) ⊗ √ (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 𝑗2 𝑗3 |1⟩)
2
⏟⏟⏟⏟⏟⏟⏟⏟⏟ 2
⏟⏟⏟⏟⏟⏟⏟⏟⏟ 2
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
𝜓1 𝜓2 𝜓3

First we construct the 𝜓3 element. Contrary to the intuition, we use the top wire
containing |𝑗1 ⟩ for this. We use a Hadamad-gate to bring |𝑗1 ⟩ into the superposition
√1 (|0⟩ + (−1)𝑗1 |1⟩) = √1 (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 |1⟩). This looks close to 𝜓 already, we now
2 2 3
need to add the last two decimal places 𝑗2 𝑗3 to the state. For this we use 𝑅2 and 𝑅3 .
We apply 𝑅2 controlled by the wire 𝑗2 and 𝑅3 controlled by the wire 𝑗3 . This means,
that we only apply the 𝑅-gate, if the corresponding wire contains a 1. You can see this
written as a quantum circuit at the figure below. After applying 𝑅2 we have the state
√1 (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 𝑗2 |1⟩) and after applying 𝑅 we have the state √1 (|0⟩ + 𝑒2𝜋𝑖0.𝑗1 𝑗2 𝑗3 |1⟩) on
2 3 2
the top wire. This is the same as 𝜓3 , so we are done on the first wire (We are at slice 3
in the figure below at this point).
The next step is to construct the 𝜓2 state on the middle wire. We again use a Hadamad-
gate to bring |𝑗2 ⟩ into the superposition √12 (|0⟩ + 𝑒2𝜋𝑖0.𝑗2 |1⟩). We now need to include
the last decimal point 𝑗3 , for which we use 𝑅2 again, this time controlled by 𝑗3 . The
resulting superposition is now √12 (|0⟩ + 𝑒2𝜋𝑖0.𝑗2 𝑗3 |1⟩), which is 𝜓2 .
On the bottom wire, we can just do a Hadamad-gate to bring |𝑗3 ⟩ into the superposition
√1 (|0⟩ + 𝑒2𝜋𝑖0.𝑗3 |1⟩). We then have 𝜓 on the bottom wire. The full circuit is described
2 1
in this figure:

34
 1 2 3 4 5 6 7
|j1 ⟩ H R2 R3 ψ1

|j2 ⟩ H R2 ψ2

|j3 ⟩ H ψ3

Figure 9.2: The DTF for three qubits

When applying this circuit, we get the state 𝜓3 ⊗ 𝜓2 ⊗ 𝜓1 as a result. This very close to
our desired state 𝜓1 ⊗ 𝜓2 ⊗ 𝜓3 , just the order of the wires is flipped. To solve this, we
apply a SWAP onto all wires, which flips the order of the wires an delivers the correct
output for DFT23 .

The more general approach to construct the DFT2𝑛 as a quantum circuit with 𝑛 qubits works
as follows:

1. Initialize wires with input |𝑗⟩, so that |𝑗1 ⟩ is on the top wire and |𝑗𝑛 ⟩ is on the bottom
wire. Note, that this is not part of the circuit yet.
2. Start with the top wire. For each wire 𝑗𝑖 do the following:
1. Apply a Hadamad-gate on the wire 𝑗𝑖 .
2. For each wire 𝑗𝑘 below the current wire 𝑗𝑖 (with 𝑖 < 𝑘 ≤ 𝑛), add a 𝑅𝑘−𝑖+1 -gate
controlled by 𝑗𝑘 . Start with 𝑘 = 𝑖 + 1 (if 𝑖 < 𝑛, else stop).
3. Perform a SWAP to flip all the wires. This means, that the first wire is swapped with
the last wire, the second wire is swapped with the second to last wire and so on.

Note: If the the output of the DFT circuit is measured right after applying it (as in Shor’s
algorithm) or if the rest of the algorithm allows for it, it is more efficient to perform the SWAP
classically, since this is considered to be the cheaper operation.
The more general layout of the quantum circuit for the DFT2n with the SWAP is shown in
this figure.

35
 |j1 ⟩ H R2 Rn−1 Rn ψ1

|j2 ⟩ H Rn−2 Rn−1 ψ2

.. .. ..
. . .

|jn−1 ⟩ H R2 ψn−1

|jn ⟩ H ψn

Figure 9.3: The DTF for 𝑛 qubits

10 Grover’s algorithm

Another well known quantum algorithm is Grover’s algorithm for searching. It was developed
by Lov Grover in 1996.
Grover’s algorithm takes a function 𝑓 ∶ {0, 1}𝑛 → {0, 1}, where exactly one 𝑥0 exists, such
that 𝑓(𝑥0 ) = 1. The goal is to find 𝑥0 .
There are a number of interesting problems, which can be reduced to this general definition.
One of these problems is the breaking of a (symmetric) encryption. The function 𝑓 would take
a key as an input and output a 1, if the decryption is successful.
Classically, finding this 𝑥0 takes approximately 2𝑛 steps (when simply bruteforcing the func-
𝑛
tion). Using Grover’s algorithm, we can reduce this runtime to approximately 2 2 steps. As
an example, a 128-bit encryption would only take about 264 steps to break it, instead of about
2128 steps for the classical bruteforce.

10.1 Preparations

To construct Grover’s algorithm, we first need to introduce two new gates 𝑉𝑓 and FLIP∗ .

36
10.1.1 Constructing the oracle 𝑉𝑓

In the previous algorithms, we have learned that we can implement a function 𝑓 as a unitary
𝑈𝑓 with 𝑈𝑓 |𝑥, 𝑦⟩ = |𝑥, 𝑦 ⊕ 𝑓(𝑥)⟩. We construct a different unitary called 𝑉𝑓 from this, which
has the following behavior:

− |𝑥⟩ if 𝑓(𝑥) = 1
𝑉𝑓 |𝑥⟩ = {
|𝑥⟩ else

We can construct 𝑉𝑓 from 𝑈𝑓 using the following circuit:

|x⟩ |x⟩ or − |x⟩

Uf
|−⟩ |−⟩

Figure 10.1: The circuit for 𝑉𝑓

The bottom wire can be discarded, since it always contains a |−⟩ and thus is not entangled
with the upper wire.

10.1.2 Constructing FLIP∗

As a second ingredient for Grover’s algorithm, we define a unitary called FLIP∗ . This unitary
does nothing, if it is applied on the uniform superposition |∗⟩. For any other quantum state 𝜓
with 𝜓 orthogonal to |∗⟩ it maps 𝜓 to −𝜓. The uniform superposition |∗⟩ simply denotes the
𝑛
superposition over all classical possibilities 2− 2 ∑𝑥 |𝑥⟩. We can construct this FLIP∗ by the
following quantum circuit:

H ⊗n FLIP0 H ⊗n

Figure 10.2: The circuit for FLIP∗

37
FLIP0 is here definied by the unitary

|0⟩ if 𝑥 = 0
FLIP0 |𝑥⟩ = {
− |𝑥⟩ else

10.2 The algorithm for searching

The actual algorithm takes a function 𝑓 ∶ {0, 1}𝑛 → {0, 1} and outputs an 𝑥0 with 𝑓(𝑥0 ) = 1.
For simplicity, we assume that there is only one 𝑥0 for which 𝑓(𝑥0 ) = 1 holds and for each
other 𝑥 ≠ 𝑥0 it holds that 𝑓(𝑥) = 0.
With the two new unitaries 𝑉𝑓 and FLIP∗ defined, we can construct the circuit for Grover’s
algorithm, which is shown in the following figure:

repeat t times
n
|0n ⟩ H ⊗n Vf FLIP∗

Figure 10.3: The quantum circuit for Grover’s algorithm

The algorithm works as follows:

1. We start with a |0⟩ entry on every qubit.

2. We bring the system into the superposition over all entries by applying 𝐻 ⊗𝑛 . The
−𝑛
quantum state is then 2 2 ∑𝑥 |𝑥⟩ which we also call |∗⟩.
3. We apply the unitary 𝑉𝑓 .
4. We apply the unitary FLIP∗ .
5. We repeat steps 3 and 4 𝑡 times, and then do a measurement.

The measurement in step 5 will then give us 𝑥0 with high probability.

10.2.1 Understanding the algorithm for searching

When looking at the quantum circuit, it is not completely intuitive why the algorithm gives
the correct result. We therefore now look into what is happening in each step.
The desired quantum state after the algorithm finishes is |𝑥0 ⟩. At the beginning of the algo-
−𝑛
rithm, we bring the system into the uniform superposition |∗⟩ = 2 2 ∑𝑥 |𝑥⟩. We know that

38
|𝑥0 ⟩ is part of this superposition, therefore we can rewrite |∗⟩ as follows

𝑛 1 2𝑛 − 1 1
|∗⟩ = 2− 2 ∑ |𝑥⟩ = √ |𝑥 ⏟0 ⟩ +√ 𝑛 ∑ √ |𝑥⟩
𝑥
𝑛
2 good 2 𝑥≠𝑥0 2 𝑛 − 1
⏟⏟⏟⏟⏟⏟⏟
bad

So the current state can be seen as a superposition of a “good” state good and a “bad” state
bad.
The geometric interpretation of this superposition can be drawn as follows:

good

|∗⟩

θ
bad

Figure 10.4: Geometric interpretation of |∗⟩

The angel 𝜃 denotes, how “good” the resulting outcome will be. If 𝜃 = 0, the state is completely
bad, if 𝜃 = 𝜋2 , the state is completely good.
√
2𝑛 −1
We can calculate cos 𝜃 = |⟨∗|𝑏𝑎𝑑⟩| = √
2𝑛
. From this we can derivate that the angle 𝜃 is
2𝑛 −1
cos−1 √ 2𝑛 at the beginning, which is approximately √ 21𝑛 .

We now apply 𝑉𝑓 on this quantum state. This will negate the amplitude off our desired |𝑥0 ⟩
and not change the amplitude to the rest of the state.

1 2𝑛 − 1
𝑉𝑓 |∗⟩ = − √ |𝑥⏟ 0 ⟩ +√ 𝑛 ∑ |𝑥⟩
2𝑛 good 2 𝑥≠𝑥
⏟ 0

bad

This looks like this in the geometric interpretation:

39
 good

|∗⟩

θ
θ bad

Vf |∗⟩

Figure 10.5: Geometric interpretation after 𝑉𝑓

We can see that by applying 𝑉𝑓 , we mirror the vector across the bad axis.
After 𝑉𝑓 , we apply the FLIP∗ operation on the quantum state. Since FLIP∗ does nothing on
the |∗⟩ entries and negates the amplitude of any vector orthogonal to it, FLIP∗ mirrors the
vector across |∗⟩. This can be seen in the following figure:

good

FLIP∗ Vf |∗⟩

2θ |∗⟩

θ
θ bad

Vf |∗⟩

Figure 10.6: Geometric interpretation after FLIP∗

All in all, we have seen that by applying 𝑉𝑓 and FLIP∗ , we can increase the angle of the
quantum state in relation to the “good” and “bad” states by 2𝜃. Therefore two reflection give
rotation. By repeating this step often enough, we can get the amplitude of |𝑥0 ⟩ close to 1.
To be more precise: Since we know 𝜃 and we know that we will increase the good-ness of our
quantum state by 2𝜃 each time, we can calculate that only 𝑡 iterations are necessary with
𝜋/2
𝜃 −1 𝜋 𝜋 √
𝑡≈ ≈ ≈ ⋅ 2𝑛
2 4𝜃 4

40
 √
Grover’s algorithm therefore takes 𝑂( 2𝑛 ) steps, where an evaluation of the circuit counts as
one step.

11 Quantum Physics

To further understand, how quantum computers work, we take a look at the basics of quantum
physics.

11.1 Wave function

The first concept we look into is the wave function of quantum mechanics. For this we will
look at the experiment “particle in a well”. To keep the math simple, we assume the space to
be 1-dimensional, so the position of the particle is confined to a line.
In this experiment, we have one particle and a potential, which is denoted by a function
𝑉 ∶ ℝ → ℝ. This function maps a position of a particle in ℝ to the energy which is needed to
hold the particle in that position.
Classically a state of a system at time 𝑡 is described by the position 𝑥(𝑡) ∈ ℝ and the momentum
𝑝(𝑡) ∈ ℝ.
In the quantum world, we have a wave function 𝜓𝑡 (𝑥) with 𝜓𝑡 ∶ ℝ → ℂ under 𝑡 ∈ ℝ, which
takes the position of a particle as an input and outputs the amplitude of that particle, with 𝑡
as the time.
To calculate the probability of a particle being in the interval [𝑎, 𝑏] at time 𝑡0 , we can use the
integral over the wave function:
𝑏
Pr[Particle is in [𝑎, 𝑏] a time 𝑡0 ] = ∫ |𝜓𝑡0 (𝑥)|2 𝑑𝑥
𝑎

From this we can see that the integral ∫|𝜓𝑡0 |2 𝑑𝑥 = 1. The momentum is not needed for the
wave function.
The inner product of two wave functions ℝ → ℂ is given by

⟨𝜓|𝜙⟩ ∶= ∫ 𝜓(𝑥) ⋅ 𝜙(𝑥)𝑑𝑥

41
The norm of a wave function is given by

‖𝜓‖2 ∶= ⟨𝜓|𝜓⟩ = ∫|𝜓(𝑥)|2 𝑑𝑥

In general, the wave function can have a different domain, e.g. 𝜓𝑡 ∶ ℝ3 → ℂ for a particle in
3D-space. Everything below works analogously in that case.

11.2 Energy / Hamiltonian

Given a particle in a state, this particle has some energy. Classically this energy is calculated
from the potential and the momentum, with
𝑝2
Energy ∶= 𝑉
⏟ (𝑥) +
2𝑚
⏟
potential energy
kinetic energy

In the quantum world, we can calculate the potential energy using the wave function as
follows:
potential energy ∶= ∫ |𝜓(𝑥)| 2 ⋅𝑉 (𝑥)𝑑𝑥
⏟
probability at pos. 𝑥

The kinetic energy can be calculated as follows:

ℏ 𝜕 2 𝜓(𝑥)
kinetic energy ∶= ∫ −𝜓(𝑥) ⋅ ⋅ 𝑑𝑥
2𝑚 𝜕𝑥2
ℏ is the reduced Planck constant. We will not go further into reasoning for this definition.
From this we can calculate the energy in the quantum context:
ℏ 𝜕 2 𝜓(𝑥)
energy ∶= ∫ 𝜓(𝑥) (− + 𝑉 (𝑥)𝜓(𝑥)) 𝑑𝑥
2𝑚 𝜕𝑥2
= ∫ 𝜓(𝑥)(𝐻𝜓)(𝑥)𝑑𝑥

= ⟨𝜓, 𝐻𝜓⟩

The operator 𝐻 is called a Hamiltonian and is an operator that maps wave functions to wave
functions, such that ⟨𝜓, 𝐻𝜓⟩ is the energy. 𝐻 maps 𝜓 to 𝐻𝜓 which is defined as:
ℏ 𝜕 2 𝜓(𝑥)
(𝐻𝜓)(𝑥) = − + 𝑉 (𝑥)𝜓(𝑥) (11.1)
2𝑚 𝜕𝑥2

Note that ℏ is the reduced plank constant and 𝑚 is the mass. Also note that other physical
systems (e.g. when there are more particles, or when there is not just a simple potential) may
have a different definition of the Hamiltonian.

42
11.3 Schrödinger equation

11.3.1 Time-dependent Schrödinger equation

The time-dependent Schrödinger equation is denoted by:

𝜕𝜓𝑡 (𝑥)
𝑖ℏ = (𝐻𝜓𝑡 )(𝑥)
𝜕𝑡

From this we see that the time development of 𝜓𝑡 is determined by 𝜓𝑡 at that moment (via
𝐻𝜓𝑡 ).

11.3.2 Time-independent Schrödinger equation

For the time-independent Schrödinger equation, we try to find a wave function 𝜓 ∶ ℝ → ℂ, 𝜓 ≠

0 and an energy 𝐸 such that
𝐻𝜓 = 𝐸𝜓
This means roughly that we try to find 𝜓 that has the same energy everywhere. That is that
we try to find a 𝜓 with energy 𝐸 (since the energy is ⟨𝜓|𝐻𝜓⟩ = ⟨𝜓|𝐸𝜓⟩ = 𝐸 ⟨𝜓|𝜓⟩ = 1) and
not a superposition of different energies.
Such a 𝜓 is useful, since by the time-dependent Schrödinger equation, if 𝐻𝜓 = 𝐸𝜓, then

𝜕𝜓𝑡 (𝑥)
𝑖ℏ = 𝐻𝜓 = 𝐸𝜓𝑡0 (𝑥)
𝜕𝑡

Solving this differential equation gives us 𝜓 with

𝜓𝑡 (𝑥) = 𝑒−𝑖𝐸𝑡/ℏ 𝜓𝑡0 (𝑥)

So all in all: If 𝜓0 is a solution of the time-independent Schrödinger equation, then 𝜓𝑡 (𝑥) =

𝑒−𝑖𝐸𝑡/ℏ 𝜓0 (𝑥) is the solution to the time-dependent Schrödinger equation with initial condition
𝜓0 (at time 𝑡 = 0).
Given any 𝜓0 , we can try to rewrite 𝜓0 as 𝜓0 = ∑𝑘 𝑎𝑘 𝜓𝑘 , where 𝜓𝑖 , 𝐸𝑖 are solutions of the time-
independent Schrödinger equation and then the solution of the time-dependent Schrödinger
equation is
𝜓𝑡 (𝑥) = ∑ 𝑎𝑘 𝑒−𝑖𝐸𝑡/ℏ 𝜓𝑘 (𝑥)
𝑘
𝑘
Note that with 𝜓 , 𝑘 is an index and not an exponent.

43
11.4 Infinite square well

Our goal is to solve the time-independent Schrödinger equation for the infinite square well.
The infinite square well is defined to have a potential of 𝑉 (𝑥) = 0 in the range [0, 1] and
𝑉 (𝑥) = ∞ otherwise.
We now try to solve the time-independent Schrödinger equation 𝐻𝜓 = 𝐸𝜓, which for the
Hamiltonian from Equation 11.1 becomes:

ℏ 𝜕 2 𝜓(𝑥)
− + 𝑉 (𝑥)𝜓(𝑥) = 𝐸𝜓
2𝑚 𝜕𝑥2

Since the potential of the particle is ∞ outside of the range [0, 1], we know that 𝜓(𝑥) = 0
outside of [0, 1], because there is no infinite energy. From this we also know that 𝜓(0) = 0 and
𝜓(1) = 0 by continuity.
Since either 𝜓(𝑥) or 𝑉 (𝑥) are always 0 for any 𝑥, we need to solve the term

ℏ 𝜕 2 𝜓(𝑥)
− = 𝐸𝜓
2𝑚 𝜕𝑥2
We assume for simplicity that 𝑚 = 1 and ℏ = 1 and we don’t specify units like meter, seconds,
2
joule etc. All solutions to − 21 𝜕 𝜕𝑥
𝜓(𝑥)
2 = 𝐸𝜓 have the form

𝜓 = 𝐴 sin(𝛾𝑥) + 𝐵 cos(𝛾𝑥)
2
with 𝐸 = 𝛾2 for any 𝐴, 𝐵 ∈ ℂ and 𝛾 ∈ ℝ. Since 𝜓(0) = 0, we know that 𝐵 = 0. Therefore
𝜓 = 𝐴 sin(𝛾𝑥). The scaling factor 𝐴 has to fulfill 𝐴 ≠ 0 since we only look for non-zero wave
functions.
Since 𝜓(1) = 0, we know that 𝐴 sin(𝛾) = 0. Therefore 𝛾 needs to be a multiple 𝑘 of 𝜋 and also
𝑘 > 0 because we want non-zero solutions 𝜓 ≠ 0. So we set 𝛾 ∶= (𝑘 + 1)𝜋 for integers 𝑘 ≥ 0.
2
With 𝐸 = 𝛾2 we get:
(𝑘 + 1)2 𝜋2
𝐸𝑘 =
2
and also that
𝜓𝑘 (𝑥) = 𝐴 sin((𝑘 + 1)𝜋𝑥)
√
For the rest of our lecture, we will set 𝐴 to be 𝐴 = 2 because we are only interested in
normalized wave functions.
So all in all: In the infinite square well the wave functions with no energy-superposition are
2 2
sin((𝑘 + 1)𝜋𝑥) with 𝐸𝑘 = (𝑘+1) 2
𝜋
.
There is one important thing to note here: With the infinite square well, there are discrete
2
energy levels, so for each energy level 𝑘, we have an energy 𝐸𝑘 = (𝑘 + 1)2 𝜋2 and no other

44
 2
energy levels (e.g 1.4𝜋
2 ) exist. 𝐸𝑘 > 0 also holds, so we can never have 0-energy. This means
that, different from the classical case, the particle can never be fully at rest. We will write
|𝑘⟩ ∶= 𝜓𝑘 .
We can now write each state as
∑ 𝑎𝑘 |𝑚⟩ (11.2)
𝑘∈ℕ

If we ignore energies above a certain level, we get a system |1⟩ , |2⟩ , |3⟩ , … , |𝑁 ⟩, where any 𝜓
can be written as ∑ 𝑎𝑘 |𝑘⟩. That is useful if we do not want to think about infinite dimensional
systems.

12 From Quantum Physics to a Quantum

Computer

In the previous chapter, we have learned about the fundamentals of quantum physics. We now
relate this to quantum computers.
So far we have seen solutions of the time-independent Schrödinger equation 𝜓𝑘 (𝑥) =
√ 2 2
2 sin((𝑘 + 1)𝜋𝑥) and 𝐸𝑘 = (𝑘+1)
2
𝜋
. Note that we still assume ℏ = 1 and 𝑚 = 1.
We can now combine physics and quantum computer science by setting

|0⟩ ∶= 𝜓0
|1⟩ ∶= 𝜓1
…

For one qubit, we just look at 𝜓0 and 𝜓1 and ignore all other wave functions. Note that this
can lead to errors, since those other wave functions still exists and interact with our system,
even though they might have a very small probability.
To fully construct our one qubit quantum computer, we need to be able to perform three basic
operations:

1. We need to initialize our qubit with |0⟩. This is also called cooling.
2. We need to be able to apply a unitary on the qubit.
3. We need to be able to measure the qubit.

45
We look into how to construct a unitary on our particle. The cooling and measuring operations
are out of scope od this chapter. We know that the time evolution of our quantum computer
𝜋2 2
is |0⟩ ↦ 𝑒−𝑖 2 𝑡 |0⟩ and |1⟩ ↦ 𝑒−𝑖2𝜋 𝑡 |1⟩.
This can be seen as a unitary 𝑈𝑡 , which is depending on 𝑡 written as the matrix:

𝜋2
𝑒−𝑖 2 𝑡
0
𝑈𝑡 = ( −𝑖2𝜋2 𝑡
)
0 𝑒

Using 𝑡 = 𝜋6 , we get the unitary

−1 0
𝑈6 = ( )
𝜋 0 1
which is equal to the unitary −𝑍. This means that the unitary −𝑍 is applied every 𝜋6 steps
“automatically”. The factor −1 does not make a physical difference as it is a global phase
factor, so the −𝑍 is physically equal to the 𝑍 gate.
But how do we get new unitaries which are not 𝑍? Since 𝑈𝑡 is dependent on the evolution
of 𝜓, which is dependent of 𝐻, which is dependent of the potential 𝑉 (𝑥), we can change the
potential 𝑉 (𝑥) to get a different 𝑈𝑡 .
The problem is that when changing the potential 𝑉 (𝑥), we need to solve the differential
equation again. Luckily, there is a trick for that which avoids thinking about wave functions
to much: If we have wave functions |𝑘⟩ with 𝑘 ∈ {1, … , 𝑁 } and ‖ |𝑘⟩ ‖ = 1 and also ⟨𝑘|𝑙⟩ = 0
for 𝑘 ≠ 𝑙 so |𝑘⟩ and |𝑙⟩ are orthogonal to each other, we can rewrite 𝐻 as a linear operator on
the wave functions written as span{|𝑘⟩ ∶ 𝑘 = 1 … 𝑁 }, therefore we can write 𝐻 as a matrix:
2
𝐸1 0 0 𝜋
2 0 0
⎛ ⎞ ⎛
𝐻 = ⎜ 0 𝐸2 0 ⎟ = ⎜ ⎞
⎜0 2𝜋2 0 ⎟
⎟
⎝0 0 ⋱⎠ ⎝ 0 0 ⋱⎠

𝜋2
For this representation of 𝐻, we immediately get 𝐻 |0⟩ = 2 , 𝐻 |1⟩ = 2𝜋2 and so on, so nothing
has changed except that 𝐻 is represented more nicely.
We can now use a helpful theorem to get a solution for the differential equation.

Theorem 12.1. The differential equation

𝜕𝜓𝑡
𝑖ℏ = 𝐻𝜓𝑡
𝜕𝑡
with 𝐻 as a 𝑁 × 𝑁 matrix and initial state 𝜓0 as an 𝑁 -dim vector has the solution

𝜓𝑡 = 𝑒−𝑖𝐻𝑡/ℏ 𝜓0

46
We use this theorem for our one qubit computer. The goal is to change the potential by some
𝛿𝑉 and from this get a different 𝑈𝑡 .
9𝜋2 1
We try this by changing the potential to 𝛿𝑉 = 16 ( 2 − 𝑥) ⋅ 1000 for 𝑥 ∈ [0, 1] and 𝛿𝑉 = 0 for
𝑥 ∉ [0, 1].
We rewrite 𝛿𝑉 as a matrix. To do so, we try to find a matrix in the base |0⟩ , |1⟩. If 𝛿𝑉 |0⟩ =
𝑎 |0⟩ + 𝑏 |1⟩ and 𝛿𝑉 |1⟩ = 𝑐 |0⟩ + 𝑑 |1⟩, then

𝑎 𝑐
𝛿𝑉 = ( )
𝑏 𝑑

Since |0⟩ and |1⟩ are orthonormal, we know that ⟨0|𝛿𝑉 |0⟩ = ⟨0|𝑎|0⟩ + ⟨0|𝑏|1⟩ = 𝑎 + 0 = 𝑎. We
get 𝑏, 𝑐 and 𝑑 similar and from this the following matrix:

⟨0|𝛿𝑉 |0⟩ ⟨0|𝛿𝑉 |1⟩

𝛿𝑉 = ( )
⟨1|𝛿𝑉 |0⟩ ⟨1|𝛿𝑉 |1⟩

We calculate each of the entries of the matrix separately:

1 √ √
⟨0|𝛿𝑉 |0⟩ = ∫ 2 sin(𝜋𝑥) ⋅ 𝛿𝑉 (𝑥) ⋅ 2 sin(𝜋𝑥)𝑑𝑥 = 0
0
1 √ √
⟨1|𝛿𝑉 |1⟩ = ∫ 2 sin(2𝜋𝑥) ⋅ 𝛿𝑉 (𝑥) ⋅ 2 sin(2𝜋𝑥)𝑑𝑥 = 0
0
1 √ √
⟨1|𝛿𝑉 |0⟩ = ∫ 2 sin(2𝜋𝑥) ⋅ 𝛿𝑉 (𝑥) ⋅ 2 sin(𝜋𝑥)𝑑𝑥 = 1000
0
1 √ √
⟨0|𝛿𝑉 |1⟩ = ∫ 2 sin(𝜋𝑥) ⋅ 𝛿𝑉 (𝑥) ⋅ 2 sin(2𝜋𝑥)𝑑𝑥 = 1000
0

From this we get 𝛿𝑉 written as a matrix with readable numbers:

0 1000
𝛿𝑉 = ( )
1000 0

We can now add this matrix to the Hamiltonian 𝐻 to get the Hamiltonian 𝐻 ′ which is the
Hamiltonian under the changed potential by calculating
𝜋2
1000
𝐻 ′ = 𝐻 + 𝛿𝑉 = ( 2 )
1000 2𝜋2

We now need to solve Schrodinger equation with this new 𝐻 ′ .

47
If we would solve the Schrodinger equation with 𝛿𝑉 as a Hamiltonian using Theorem 12.1, we
𝜋 0 −𝑖
would get the unitary 𝑈𝑡′ = 𝑒−𝑖𝛿𝑉 𝑡 . After 𝑡 = 2000 this would be the unitary ( ) = −𝑖𝑋,
−𝑖 0
essentially an 𝑋 gate.
′
If we now apply 𝐻 ′ = 𝐻 + 𝛿𝑉 as a Hamiltonian, we would get 𝑈𝑡′ = 𝑒−𝑖𝐻 𝑡
and this is
𝜋2
𝑒−𝑖 2 𝑡 𝑒−𝑖1000𝑡
𝑈𝑡′ = ( 2 )
𝑒−𝑖1000𝑡 𝑒−𝑖2𝜋 𝑡

0 −𝑖
so approximately the unitary ( ) = −𝑖𝑋 up to about 2% error.
−𝑖 0

13 Ion-based quantum computers

So far we have looked at the principles of quantum mechanics and how to transfer these
principles to our mathematical description of quantum computing. While there are many
different approaches on how to actually build a quantum computer, which are researched at
the moment, we will only look at one approach. This approach is based on trapped ions.

13.1 Electron in an atom

We look at a single atom with a nucleus with a positive charge and a single electron with
negative charge “orbiting” the nucleus.
The electromagnetic field generated by the nucleus is essentially a potential well for the electron,
since the electron is drawn to the nucleus and the potential of the electron rises with bigger
distance from the nucleus. We simplify a lot here and ignore ,e.g., the spin.
We can solve the time-independent Schroedinger equation for this setup and by solving this,
we will get the wave functions that are the energy eigenstates of the Hamiltonian. These wave
functions are called orbitals.
We can use a single atom as a qubit, where we define one of the energy eigenstates as |0⟩ and
a different eigenstate as |1⟩.
In the following, we will specifically use electrically charged atoms, called ions, because they
are easier to capture.

48
13.2 Setup for the ion traps

The setup for our quantum computer looks as follows:

single ions
vibrating electromagnetic field
tubes which
produce an
electric field

vibrating electromagnetic field

Figure 13.1: Setup for the ion based quantum computer

In the previous chapter, we have learned that we need to be able to perform three different
operations to build a quantum computer:

1. We need to initialize (cool) our qubit.

2. We need to be able to apply a unitary on the qubit.
3. We need to be able to measure the qubit.

13.2.1 Cooling

We first look into cooling our system. For cooling, we use a useful fact: If 𝐸𝑖 < 𝐸𝑗 are different
possible energy levels, an ion is in the energy level 𝐸𝑖 and then hit by a photon that has the
energy 𝐸𝑗 − 𝐸𝑖 , the ion will go to energy level 𝐸𝑗 .

13.2.1.1 Doppler cooling

In our initial setup, we have an ion vibrating back and forth because it has too much energy.
We shine a laser on it with slightly less energy than what is need for a transition. The energy
of the photon of this laser is denoted by 𝐸 = ℏ ⋅ 𝜔. When the ion moves towards the photon,
the photon has a higher frequency from the point of view of the ion (Doppler effect). This
means that the photon has a higher energy and therefore is more likely to be absorbed.
So by shining a laser on the ion, the photons of the laser “push” the ion, when it “swings”
towards the laser similar to a pendulum, where the pendulum gets a pushback with just enough
energy so it stops. This reduces the vibrations energy down to a certain level.

49
13.2.1.2 Sideband cooling

Using the doppler cooling, we have reduced the vibration energy, but the electrons may still be
excited. We now look at another technique called sideband cooling, which will set the energy
of the electrons to a specific energy level 𝐸0 .
The electron can have any energy level 𝐸𝑖 . If this energy level is pretty low, the possibility of a
spontaneous emission of a photon, which would reduce the energy to a lower level is also quite
low. So an electron with energy level 𝐸1 or 𝐸2 will probably not change to level 𝐸0 . If the
energy level is big enough (we will call this energy level 𝐸big ), the probability of a spontaneous
emission of a photon, which would reduce the energy to a lower level is quite high. So when
this spontaneous emission happens, the electron will reach an energy level of ,e.g., 𝐸0 , 𝐸1 or
𝐸2 .
Our goal is to get the energy level to 𝐸0 . We know that the energy level of the electrons
with 𝐸big will come down eventually, so we shine a laser with the energy per photon of 𝐸big −
𝐸1 , 𝐸big − 𝐸2 , … but not with 𝐸big − 𝐸0 . This will “shoot” all the low energy electrons from
𝐸1 , 𝐸2 , … to a higher lever where they will either fall down to 𝐸1 , 𝐸2 , … where they will be
energized again and the process is repeated, or they fall into 𝐸0 which is our desired energy
level.
Using the sideband and the doppler cooling together, we can cool the vibration and electron
excitation. This means that all the ions are in the state |0⟩ and the vibrations energy is also
in the state |0⟩.

13.2.2 Unitaries

Next we look into applying unitaries, also called gates. We first show how to create single
qubit gates and then look into creating multi qubit gates.

13.2.2.1 Single qubit gates

We have already discussed in Chapter 12 that single qubit gates can be created using a different
Hamiltonian. In the ion-trap, if we don’t do anything, we have some Hamiltonian 𝐻 ≈ 0 (For
our purposes we can assume that nothing happens until we apply a laser). If there is a gap
of energy Δ𝐸 between 𝐸0 and 𝐸1 with Δ𝐸 = 𝐸1 − 𝐸0 = ℏ𝜔 and we shine a laser with an
angular frequency of 𝜔 + 𝜑 with 𝜑 close to 𝜔 on it, then the Hamiltonian changes to
0 𝑒−𝑖𝜑
𝐻𝜑 = 𝐶 ⋅ ( )
𝑒𝑖𝜑 0
𝐶 > 0 denotes a constant here. Applying the laser for time 𝑡 will get us the unitary 𝑈𝜑,𝑡
with
𝑈𝜑,𝑡 = 𝑒−𝑖𝐻𝜑 𝑡

50
By choosing the right frequency, we can get all sorts of single qubit gates, especially the 𝐻,
1 0 1 0
𝑋, 𝑌 , 𝑍, 𝑆 = ( ) and 𝑇 = ( 𝑖𝜋/4 ) gates.
0 𝑖 0 𝑒

13.2.2.2 Multi qubit gates

After we have successfully constructed a single qubit gate, we look into creating multi qubit
gates. We specifically look into two qubit gates, since we can create bigger gates from these.
We remember that the initial state of the 𝑘-th ion is described by some quantum system with
basis |0⟩ , |1⟩ , … and the overall vibration is described by another quantum system |0⟩ , |1⟩ , ….
In this case, we focus only on the vibrational states |0⟩ , |1⟩ , |2⟩ , … and internal states |0⟩ , |1⟩.
This means that we have different states (Here we write the vibrational state first)

|00⟩ |10⟩ |20⟩

|01⟩ |11⟩ |21⟩

Consider the energy gap Δ𝐸 = 𝐸20 − 𝐸11 . The angular frequency corresponding to that gap
is 𝜔 = Δ𝐸 ℏ . If we shine a laser with frequency 𝜔 + 𝜑 then some Hamiltonian is applied to
|20⟩ , |11⟩ with
0 0 0 0 0 0
⎛
⎜ 0 0 0 0 0 0 ⎞
⎟
⎜
⎜ ⎟
0 0 0 0 0 0 ⎟
𝐻𝜑 = ⎜⎜
⎜ −𝑖𝜑
⎟
⎟
⎟
⎜ 0 0 0 0 𝑒 0 ⎟
⎜
⎜ 0 0 𝑖𝜑 ⎟
⎟
0 𝑒 0 0
⎝ 0 0 0 0 0 0 ⎠

With 𝜑 = 0 and 𝑡 = 𝜋, we get a unitary

1
⎛
⎜ 1 ⎞
⎟
⎜
⎜ ⎟
⎟
⎜ 1 ⎟
𝑈 = 𝑒−𝑖𝐻0 𝜋 =⎜
⎜ ⎟
⎟
⎜ −1 ⎟
⎜
⎜ ⎟
−1 ⎟
⎝ 1⎠

If we only consider the first 4 entries of this unitary, it represents a C-Z (controlled 𝑍) gate.
The other entries can be ignored, since we only “use” the first two energy levels.
So all in all we have created a controlled 𝑍 gate by applying a laser to the |20⟩ , |11⟩ gap.

51
We now apply a laser to the |01⟩ , |10⟩ energy gap. The resulting hamiltonian has the form

0 0 0 0
⎛
⎜0 0 𝑒 −𝑖𝜑
0⎞⎟
𝐻=⎜
⎜ ⎟
⎜0 𝑒𝑖𝜑 0 0⎟⎟
⎝ 0 0 0 0⎠

With 𝜑 = 32 𝜋 and 𝑡 = 𝜋2 , we get the unitary SWAPPY denoted by

1 0 0 0
⎛
⎜0 0 1 0⎞⎟
SWAPPY = ⎜
⎜ ⎟
⎜0 −1 0 0⎟⎟
⎝0 0 0 1⎠

We call it SWAPPY because it is almost the SWAP gate, except for a minus sign. We can
†
get SWAPPY with 𝜑 = 23 𝜋 and 𝑡 = 32 𝜋
†
So we have created the unitaries C-Z, SWAPPY, SWAPPY . From the single qubit setup, we
can also retrieve the 𝐻 gate.
From these gates, we construct the following circuit, which is equal to CNOT:

j Z

k H H
SWAPPY SWAPPY†
|0⟩

Figure 13.2: Circuit for CNOT

So all in all, we can construct the unitaries CNOT, 𝐻, 𝑋, 𝑌 , 𝑍 𝑆 and 𝑇 using ion based
quantum computers.

13.2.3 Measurements

Finally we now look into performing a measurement on an ion-based quantum computer. So

far we have defined that the quantum state |0⟩ is represented by the energy level 𝐸0 and the
quantum state |1⟩ is represented by the energy level 𝐸1 .

52
To perform a measurement, we also use an auxiliary energy level 𝐸aux > 𝐸0 , 𝐸1 . Let 𝜔 be the
frequency of a photon with energy 𝐸aux − 𝐸0 (𝐸aux − 𝐸0 = Δ𝜔)
We now shine a laser with the frequency 𝜔 on the ion. If the state is |0⟩, the photon gets
absorbed and the electron jumps to 𝐸aux and from there spontaneously back to 𝐸0 .This process
then repeats over and over emitting many photons. This will create fluorescence, which can
be measured by light detectors. If the state is |1⟩, no ions get absorbed and no fluorescence
can be seen.
So all in all, we measure an ion by shining a photon of frequency 𝜔 onto it and then look
whether it lights up.

14 Universal set of gates

So far we have seen a wide variety of different quantum gates, depending on the quantum
computer architecture. We now look further more into which gates are needed to create
arbitrary circuits on a quantum computer.

14.1 Pauli gates as universal qubit gates?

As a warmup recall the Pauli matrices 𝑋, 𝑌 and 𝑍. If we only have access to a 𝑋 and 𝑌 gate,
could we construct the 𝑍 gate from this as well?
We could combine 𝑌 and 𝑋 gate, which gives us the gate

0 1 0 −𝑖 𝑖 0
𝑋𝑌 = ( )( )=( ) = 𝑖𝑍
1 0 𝑖 0 0 −𝑖

So we can get the Pauli 𝑍 gate from the 𝑋 and 𝑌 gate up to a global phase factor. With
simple math, one can show that it is also possible to get a 𝑋 gate from 𝑌 and 𝑍 and also the
𝑌 gate from 𝑋 and 𝑍.
So with this, we might assume that we can create all gates on a quantum computer only by
using two of the Pauli matrices.
Unfortunately this is not true, since we can only manipulate a single qubit using the Pauli
matrices. Therefore a e.g. CNOT is not possible.

53
But maybe we can create all single qubit gates from the Pauli matrices? Unfortunately this is
also not true, since the product of a Pauli matrix is always either another Pauli matrix or the
identity matrix. So we won’t get a universal set of gates from the Pauli matrix and we have
to try a different set of gates.

14.2 Rotation gates

We look at a different type of gates, the rotational gates 𝑅𝑋 ,𝑅𝑌 and 𝑅𝑍 . These gates are
defined by
cos(𝜃/2) −𝑖 sin(𝜃/2)
𝑅𝑋 (𝜃) = 𝑒−𝑖𝑋𝜃/2 = ( )
−𝑖 sin(𝜃/2) cos(𝜃/2)
cos(𝜃/2) − sin(𝜃/2)
𝑅𝑌 (𝜃) = 𝑒−𝑖𝑌 𝜃/2 = ( )
− sin(𝜃/2) cos(𝜃/2)
𝑒−𝑖𝜃/2 0
𝑅𝑍 (𝜃) = 𝑒−𝑖𝑍𝜃/2 = ( )
0 𝑒𝑖𝜃/2

We can obviously not create any multiple qubit gates from this, but is possible to get all single
qubit gates from this. We call this universal for single qubit gates.

Definition 14.1 (Universal set of gates). A set 𝐺 of gates is universal, iff any unitary
can be approximated to an arbitrary precision.
This means that for all unitary 𝑈 ∈ ℂ𝑛×𝑛 , for all 𝑛 and for all 𝜖 there exists a circuit 𝐶
consisting of elements of 𝐺 without auxillary qubits such that for all quantum states 𝜓
it holds that ‖𝑈𝜓 − 𝐶𝜓 ‖ ≤ 𝜖.
We call 𝐺 universal for single qubit gates when this holds for 𝑛 = 1.

Using this definition, we can formalize what is stated above:

Theorem 14.1 (Rotation gates). The set {𝑅𝑋 , 𝑅𝑌 , 𝑅𝑍 ∶ 𝜃 ∈ [0, 2𝜋]} is universal for
single qubit gates.

When adding a CNOT to the set of universal single qubit gates, we get a general set of universal
gates.

Theorem 14.2 (Single qubit gates and CNOT). The set of

{all single qubit gates, CNOT} is universal.

Corollary 14.1 (Rotation gates and CNOT). The set of {𝑅𝑋 , 𝑅𝑌 , 𝑅𝑍 , CNOT ∶ 𝜃 ∈
[0, 2𝜋]} is universal for all 𝜃 ∈ [0, 2𝜋].

54
14.3 Clifford gates

We look at another set of gates called Clifford gates. This set consists of CNOT, 𝐻 and 𝑆.
While there are many gates, which can be construct from the set of Clifford gates, the set
is not universal. For example, there is a gate called 𝑇 , which can not be constructed from
Clifford gates. 𝑇 is denoted by
1 0
𝑇 =( )
0 𝑒𝑖𝜋/4
Note that 𝑇 2 = 𝑆 and 𝑆 2 = 𝑍 and 𝑍 2 = 𝐼.
But while the Clifford gates are not universal, there is a different useful fact, which we can
especially use without access to a quantum computer:

Theorem 14.3 (Gottesmann-Knill theorem). A quantum circuit only using Clifford gates
can be efficiently simulated on a classical computer.

However if we add 𝑇 , we get a universal set:

Theorem 14.4 (Clifford gates and 𝑇 ). The set of all Clifford gates and 𝑇 is universal.

There is also one more example of a universal set:

Theorem 14.5 (Toffoli and 𝐻). The set of {Toffoli, 𝐻} is universal.

14.4 Gottesmann-Knill theorem

We take a closer look into why Theorem 14.3 works.

First we look into stabilizer states. Given a set of unitaries 𝑀 , 𝜓 is stabilized by 𝑀 if for all
𝑈 ∈ 𝑀 is holds that 𝑈 𝜓 = 𝜓. The state |0⟩ is for example stabilized by {𝑍}, since 𝑍 |0⟩ = |0⟩
and it is the only state (up to global phase) stabilized by {𝑍}, since e.g. 𝑍 |1⟩ = − |1⟩.
Let 𝑃 be the set of all 𝑛-qubit tensor products of 𝑋, 𝑌 , 𝑍, 𝐼 and a factor ±1 and ±𝑖. For 𝑛 = 4
𝑃 contains for example 𝑋 ⊗ 𝐼 ⊗ 𝑍 ⊗ 𝑍 and −𝑖𝑋 ⊗ 𝑌 ⊗ 𝐼 ⊗ 𝐼.
We call 𝜓 a stabilizer state if there exists a set 𝑀 ⊆ 𝑃 such that 𝜓 and only 𝜓 is stabilized by
𝑀 up to a global phase.

55
 𝑛
Example: Stabilizing |0⟩
𝑛
The quantum state |0⟩ = |0⟩ ⊗ ⋯ ⊗ |0⟩ is stabilized by 𝑀0 = {𝑍 ⊗ 𝐼 ⊗ ⋯ ⊗ 𝐼, 𝐼 ⊗ 𝑍 ⊗ ⋯ ⊗
𝑛
𝐼, 𝐼 ⊗ 𝐼 ⊗ ⋯ ⊗ 𝑍} and therefore the quantum state |0⟩ is a stabilizer state and |𝑀0 | = 𝑛.

The big trick is now that if 𝜓 is stabilized by 𝑀 , it follows that 𝑈 𝜓 is stabilized by 𝑀 ′ for
some 𝑀 ′ . But what is 𝑀 ′ ?
We know that if 𝐴 ∈ 𝑀 it holds that 𝐴𝜓 = 𝜓. So it follows that 𝑈 𝐴𝑈 † = 𝑈 𝜓 and therefore
𝑈 𝐴𝑈 † is a stabilizer of 𝑈 𝜓. The converse also holds. So 𝑀 ′ = {𝑈 𝐴𝑈 † ∶ 𝐴 ∈ 𝑀 }.
Now we can use a useful fact: For any Clifford gate 𝐺, if 𝑀 contains “Pauli tensors”, then
𝑀 𝐺 also contains “Pauli tensors”.
The simulation algorithm to simulate Clifford gates basically works as follows:
𝑛
1. 𝑀 ∶= 𝑀0 , which is the stabilizer for |0⟩ .
2. For each gate 𝐺:
𝑀 ∶= 𝑀 𝐺
3. To calculate the measurement outcomes, do linear algebra (not further specified here).

Since 𝑀 will always be a set of 𝑛 tensor products of 𝑛 Pauli matrices, this gives a polynomial
time algorithm for simulation Clifford circuits.

15 Repetition code

56