The Quantum Memory Register

We have considered a two state quantum system, a qubit. However a quantum system is by no means constrained to be a two state system. Much of the above discussion for a 2 state quantum system is applicable to a general $n$ state quantum system.

In an $n$ state system our Hilbert Space has $n$ perpendicular axes, or eigenstates, which represent the possible states the system can be measured in. As with the two state system, when we measure our $n$ state quantum system, we will always find it to be in exactly one of the $n$ states, and not a superposition of the $n$ states. The system is still allowed to exist in any superposition of the $n$ states while it is not being measured.

Mathematically if two state quantum system with coordinate axes $x_{0}$, $x_{1}$ can be fully described by:

$$\vert X \rangle = w_{0} * \left\vert x_{0} \right\rangle + w_{1} * \left\vert x_{1} \right\rangle \equiv (w_{0},w_{1})$$

Then an $n$ state quantum system with coordinate axes $x_{0}, x_{1},\ldots, x_{n-1}$ can be fully described by:

$$\vert X \rangle = \sum_{k = 0}^{n-1} w_{k} * \left\vert x_{k} \right\rangle$$

In general a quantum system with $n$ base states can be represented by the $n$ complex numbers $w_{0}$ to $w_{n-1}$. When this is done the state may be written as:

$$\left\vert X \right\rangle = \left( \begin{array}{c} w_{0} \\ w_{1} \\ \vdots \\ w_{n-1} \end{array} \right)$$

Where it is understood that $w_{k}$ refers to the complex weighting factor for the $k$'th eigenstate.

Using this information we can construct a quantum memory register out of the qubits described in the previous section. We may store any number $x$ in our quantum memory register as long as we have enough qubits, just as we may store any number $x$ in a classical register as long as we have enough classical bits to represent that number. The state of the quantum register with $n$ states is give by the formula above. Note that in general a quantum register composed of $m$ qubits requires $2^{m}$ complex numbers to completely describe its state: an $m$ qubit register can be measured to be in one of $2^{m}$ states, and each state requires one complex number to represent the projection of that total state onto that state. In contrast a classical register composed of $m$ bits requires only $m$ integers to fully describe its state.

This means that is some sense one can store an exponentially greater amount of information in a quantum register than in a classical memory register of the same number of (q)bits. Here we see some of the first hints that a quantum computer can be exponentially more powerful than a classical computer in some respects. Recall that from our discussion of complexity that problems whose best known algorithms yield a solution in polynomial time are generally thought of as being tractable, and that problems whose best known algorithms take exponential time are thought of as intractable. If a quantum computer really is exponentially faster than a classical computer, then some intractable problems may become tractable! This is a large part of the motivation for the study of quantum computing.