1  Introduction

1.1 Double slit experiment

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

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 \(2^{64}-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. Contrary 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 \(x\) in a superposition of numbers between \(0\) and \(2^{64}-1\) (all possible 64-bit values) and some function \(f(x)\). You program a quantum computer to compute \(f(x)\).

The quantum computer would compute \(f(x)\) for \(x=0,x=1,x=2,...\) at the the same time and the result of this computation is a superposition of all possible values \(f(x)\).

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 \(f(x)\), 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 \(f(x)\) and all the other possible solutions are lost.

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.