more details the reader is advised to read [Karafyllidis (2005a)], [Gruska (1999)] or 
[Nielsen & Chuang (2000)]. 

## 2. Quantum Computation Basics

The quantum analog of a bit is called a quantum bit or *qubit*. Its physical implementation can be the energy state of an electron in an atom, the polarization of a photon, or any other bi-state quantum system. When a qubit is *measured* (or *observed*), its state is always found in one of two clearly distinct states, usually transcribed as |0> and |1>. These are direct analogs of the 0 and 1 states of a classical bit but they are also orthogonal states of a 2-dimensional Hilbert space and they are called *basis states* for the qubit. Before the qubit is measured, its state can be in a composition of its basis states denoted as: 

$$\mathbf{(1)}$$. 
$$\left|\mathbf{q}\right\rangle=\mathbf{a}\left|0\right\rangle+\mathbf{b}\left|1\right\rangle=\mathbf{a}{\left[{\begin{array}{l}{1}\\ {0}\end{array}}\right]}+\mathbf{b}{\left[{\begin{array}{l}{0}\\ {1}\end{array}}\right]}={\left[{\begin{array}{l}{\mathbf{a}}\\ {\mathbf{b}}\end{array}}\right]}$$

In Eq.1 a and b are complex numbers called *probability amplitudes*; |a|2 is the probability of the qubit to appear in state |0> when observed, and |b|2 is the probability to appear in state |1>. Equation 1 also presents the *matrix notation* of the qubit states. 

A series of qubits is called a *quantum register*. An n-qubit quantum register is denoted as: 

$$Q_{n}\rangle=c_{0}\left|0\cdots000\right\rangle+c_{1}\left|0\cdots001\right\rangle+\cdots+c_{2^{n}-1}\left|1\cdots111\right\rangle=\sum_{i=0}^{2^{n}-1}c_{i}\left|i\right\rangle\tag{2}$$

It has 2n observable states, corresponding to the basis states of Eq.2, each one having a probability of |ci| 2 when measured. Again, this can be considered as a vector of an n-

$${\mathrm{\boldmath~\space~\space~\space~\space~}}\sum_{i=0}^{2^{n}-1}\bigl|c_{i}\bigr|^{2}=1\,.$$
dimensional Hilbert space with 1
A single qubit can be considered as a trivial quantum register with n=1. When n>1 the quantum register can be considered as a series of qubits: 

$$\left|Q_{n}\right\rangle=\left|q_{n-1}\right\rangle\otimes\left|q_{n-2}\right\rangle\cdots\left|q_{i}\right\rangle\cdots\left|q_{1}\right\rangle\otimes\left|q_{0}\right\rangle=\left|q_{n-1}q_{n-2}\cdots q_{i}\cdots q_{1}q_{0}\right\rangle\tag{3}$$

where ⊗ denotes the *tensor product*. 

Quantum systems are able to simultaneously occupy different quantum states. This is known as a *superposition* of states. In fact, the state of Eq.1 for the qubit and the state of Eq.2 for the quantum register represent superpositions of the basis states over the same set of qubits. A quantum register can be in a superposition of two or more basis states (with a maximum of 2n, where n is the number of its qubits). The qubits of the 