## Sunday, 8 September 2013

### Qubits

The theoretical model of quantum computation, despite having some additional resources, is essentially analogous to the classical computational model. However, now the fundamental postulates of quantum mechanics are at play in governing the state and action of the quantum computer. In general, a classical computer functions on a register of some finite number of bits applying appropriate operations (Boolean functions) that change all or some of the bits in order to yield a desired output. Quantum computation can be conceived similarly. First, we define the unit of information in the quantum theory of computation which is analogous to the classical bit---the quantum bit, or qubit for short.

The basic unit of information in the classical theory of computation is the bit, which has the ability to be in one of two states often labeled as $0$ and $1$. The important thing here is that a bit can only be in one of these two states and not both. Similarly, a quantum bit or qubit is a two-level system which can be in one of two states, or both states simultaneously. We will not be concerned here with the actual physical realizations of qubits and instead focus on them in the abstract context only. However, essentially any quantum mechanical system that has two distinguishable states can be used as a qubit in principle. This quantum mechanical property of qubits, referred to as superposition, is unique to quantum computation, and is exploited to accomplish tasks that are otherwise impossible in the classical realm.

In order to make this more precise within the quantum mechanical formalism, a qubit is defined to be any state $\left|\psi\right>$  in the two dimensional Hilbert space $\mathcal{H}^2$. By letting $\left|0\right>$ and $\left|1\right>$ be orthonormal basis vectors of $\mathcal{H}^2$ an arbitrary qubit state can be represented as $\left|\psi\right>=\alpha\left|0\right>+ \beta\left|1\right>$, where $\alpha$ and $\beta$ are complex numbers subject to the normalization constraint $|\alpha|^2+| \beta|^2=1$. Here, the basis vectors $\left|0\right>$ and $\left|1\right>$ are referred to as the computational basis states and correspond to the classical bit states 0 and 1, respectively. The general state $\left|\psi\right>=\alpha\left|0\right>+ \beta\left|1\right>$ is a consequence of the superposition principle and is responsible for notion of a qubit being in some mixture of both basis states simultaneously. When $\alpha=1$ and $\beta=0$, or when $\alpha=0$ and $\beta=1$, the qubit is in the definite state of either $\left|0\right>$ or $\left|1\right>$, respectively. These are the special cases in which the state of the qubit corresponds to one of the two states of ordinary classical bits.

Qubits are the basic entities of information that are manipulated by quantum computers. Just as in the classical case, quantum computers can operate on a register of multiple qubits. The postulates of quantum mechanics allow one to consider joint systems of qubits. The state space of $n$ qubits is given by the joint system consisting of the tensor products of the individual state spaces of each qubit involved. This yields another Hilbert space $\mathcal{H}=\bigotimes_{i=1}^n\mathcal{H}^2$ of dimension $2^n$. Note that the size of the space is exponential in the number of qubits $n$. Here lies an essential feature of quantum computation, which may seem to give increased computational power over classical computation. Consider an $n$ bit classical computer. In general, these $n$ bits can represent $2^n$ different numbers when expressed in binary (base 2). However, any configuration of a classical computer can only represent one of these $2^n$ different states at any given time. Likewise, in the quantum case $n$ qubits can also represent $2^n$ different states, but now the superposition principle implies that a general state of this system can represent all $2^n$ different states simultaneously. Thus, an arbitrary state of a quantum computer can, in a certain sense, be said to contain exponentially more information than its classical counterpart. However, we ought be a little more careful with the language here, and this notion of quantum states "containing" exponentially more information. Naively, this seems to be the case, but as we better understand the nature of quantum mechanics and quantum algorithms it will become more evident how subtle this property really is.

As an illustrative example, consider two qubits $\left|\psi\right>, \left|\varphi\right>\in\mathcal{H}^2$ with
$\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$
and
$\left|\varphi\right>=\alpha'\left|0\right>+ \beta' \left|1\right>.$
Then we can construct $\left|\psi\right>\otimes \left|\varphi\right> \in\mathcal{H}^4$ as follows:
$\begin{eqnarray} \left|\psi\right>\otimes \left|\varphi\right> &=& (\alpha\left|0\right> +\beta\left|1\right>)\otimes (\alpha'\left|0\right>+\beta'\left|1\right>) \nonumber \\ &=& \alpha\alpha'\left|00\right>+ \alpha \beta' \left|01\right>+ \beta\alpha' \left|10\right>+ \beta\beta'\left|11\right> \nonumber \end{eqnarray}$
The states  $\left|00\right>, \left|01\right>, \left|10\right>, \left|11\right>$ form an orthonormal basis of the space $\mathcal{H}^4$ and correspond to the four possible bitstrings of length two $\{00, 01, 10, 11\}$.