Quantum Codes
There is a fundamental problem with quantum computers: any possible speed-up requires quantum entanglement and superpositions. These are vulnerable to environmental noise.
For example, consider a state of the form
$$
|\psi\rangle= \alpha|\uparrow\rangle+ \beta |\downarrow\rangle,
$$
where $\alpha$ and $\beta$ are arbitrary numbers. The states $|\uparrow\rangle$ and $|\downarrow\rangle$ could, for example, be spin states of a defect in silicon. A stray magnetic field in the $\hat z$ direction would cause this state to evolve under the Hamiltonian
$$
H=\left(\begin{array}{cc}\epsilon&0\\0&-\epsilon\end{array}\right).
$$
As you know from all of the homework problems, after some time $t$ the state would become
$$
|\psi\rangle\to \alpha e^{-i\phi}|\uparrow\rangle+ \beta e^{i\phi} |\downarrow\rangle,
$$
where $\phi=\epsilon t/\hbar$. The phase relation is messed up.
Similarly, a stray field in the $\hat x$ direction would cause this state to evolve under the Hamiltonian$$
H=\left(\begin{array}{cc}0&\epsilon\\
\epsilon&0\end{array}\right).
$$
The time evolution here is harder, but you have done this in your homework as well, and the result is
$$
|\psi\rangle\to \left(\alpha\cos\phi-i\beta\sin\phi\right)|\uparrow\rangle +\left(\beta\cos\phi-i\alpha\sin\phi\right)|\downarrow\rangle.
$$
Again, $\phi=\epsilon t$.
Of course $\epsilon$ is random and varies with time. But you get the picture, the state gets messed up pretty quick.
We need a strategy to protect the quantum state from the environment. There are two principles that we will apply. First, we somehow want to add redundency. Second, we want the information to be stored in a non-local manner. In classical information theory we would describe such a way of storing information as an "encoding." Thus we describe this strategy as using "quantum codes".
The simplest example of a quantum code is the "3-qbit" flip code. It stores one bit of information in three spin-1/2's. The Hilbert space for these three spins is spanned by the 8 states: $\uparrow\uparrow\uparrow,\uparrow\uparrow\downarrow,\uparrow\downarrow\uparrow,\uparrow\downarrow\downarrow,
\downarrow\uparrow\uparrow,\downarrow\uparrow\downarrow,\downarrow\downarrow\uparrow,\downarrow\downarrow\downarrow$. We use only two of these, $|0\rangle = |\uparrow\uparrow\uparrow\rangle$, and $|1\rangle=|\downarrow\downarrow\downarrow\rangle$, and the encoding of an arbitrary qbit is
$$
|\psi\rangle= \alpha|0\rangle+\beta|1\rangle.
$$
Clearly we are using three times the resources that we need to. The benefit is that we can detect and correct any "bit-flip error". In particular, imagine a cosmic ray comes and flips the first bit,
$$
|\psi\rangle\to |\psi^\prime\rangle= \alpha |\downarrow\uparrow\uparrow\rangle + \beta|\uparrow\downarrow\downarrow\rangle.
$$
We can detect this catastrophic event by measuring three operators: $\sigma_{z1}\sigma_{z2}$, $\sigma_{z1}\sigma_{z3}$, and $\sigma_{z2}\sigma_{z3}$. The original state is an eigenstate of each of these with eigenvalue $1$. Thus measuring these operators does not change the state. $|\psi^\prime\rangle$ is also an eigenstate, but it is a $-1$ eigenstate of both $\sigma_{z1}\sigma_{z2}$, and $\sigma_{z1}\sigma_{z3}$. It is a $+1$ eigenstate of $\sigma_{z2}\sigma_{z3}$. The measurement of $--+$ is referred to as a "syndrome" -- in analogy with a set of symptoms used to detect a disease. It tells us that the most likely error is a bit flip on the first bit. If we get such a syndrome we simply flip the first bit, and can feel relatively confident that we have fixed the error. Similarly, we can detect and correct a bit flip on the second or third bit.
At this point you should complain that these are pretty specific kinds of errors. What about something more realistic, like a stray magnetic field in the $\hat x$ direction which influences the first spin. Here time evolution gives
$$
|\psi^\prime\rangle = \alpha\cos \phi |\uparrow\uparrow\uparrow\rangle-i\alpha \sin\phi |\downarrow\uparrow\uparrow\rangle
+\beta\cos\phi|\downarrow\downarrow\downarrow\rangle-i\beta\sin\phi|\uparrow\downarrow\downarrow\rangle.
$$
Suppose we now measure $\sigma_{z1}\sigma_{z2}$. This is an operator whose eigenvalues are +1 or -1. In fact, we can write
$$
|\psi^\prime\rangle = \cos(\phi) |\psi\rangle + \sin(\phi) |\bar\psi\rangle
$$
where
$$
|\psi\rangle= \alpha|\uparrow\uparrow\uparrow\rangle+\beta|\downarrow\downarrow\downarrow\rangle
$$
and
$$
|\bar\psi\rangle= \alpha|\downarrow\uparrow\uparrow\rangle+\beta|\uparrow\downarrow\downarrow\rangle.
$$
Each of these are normalized eigenvectors of $\sigma_{z1}\sigma_{z2}$. Thus we get $+1$ with probability
$$
P_+=\cos^2\phi.
$$
If I measure $+1$, immediately afterward the state becomes $|\psi\rangle$. The very act of measuring has fixed the error.
Conversely, we get $-1$ with probability
$$
P_-=\sin^2\phi.
$$
If we measure $-1$, then we have converted this error into a bit-flip error -- which we know how to correct.
This feature is referred to as the "discretization of errors". If we can detect and correct bit flip errors, we can also correct the errors which come from a stray field in the $\hat x$-direction. The connection is that the operator the causes a spin flip is exactly $\sigma_x$.
This 3-qbit code is not protected against "phase errors"
\begin{eqnarray}
|\uparrow\rangle &\to& |\uparrow\rangle\\
|\downarrow\rangle &\to&- |\downarrow\rangle.
\end{eqnarray}
Or more generally, it is not protected against a stray field in the $\hat z$ direction. It is not hard to imagine, however, that one can construct such codes. The smallest encoding that can correct any single qbit error requires 5 physical spins for each logical bit. Generally the more spins you have, the more robust you can make the code.
Universal Quantum Computing
Working definition: A universal quantum computer can apply an arbitrary unitary operation to the input state.
From the perspective of computer science this is a bit problematic. The space of unitary operators are continuous, and computer scientists prefer discrete things. With continuous operations you always have to talk about the fidelity of the operation. Thus most models of quantum computers use a discrete gate set, and a universal quantum computer is typically taken to be one where one can approximate an arbitrary unitary operator to arbitrary precision.
It is kind of silly, but the basic reasoning is the same one you would use if you wanted to be able to turn a dial an arbitrary angle. If you can have just one operation -- which turns the dial some angle which is not a rational fraction of $2\pi$, then by applying the operation enough times you can get arbitrarily close to any desired angle. Seems pretty inefficient to me, but nonetheless it is a well defined mathematica question.
Not surprising, it suffices to use 1-qbit and 2-qbit operations (referred to as ``gates"). Apparently the minimal gate set consists of two single-qbit gates: the Hadamard and the $\pi/8 phase gate$, and one 2-qbit gate, the control-not. We define these gates by what they due to basis states. In the language of spins, the Hadamard is a rotation by $\pi/4$ about the $y$-axis. It turns a $\hat z$ eigenstate into a $\hat x$ eigenstate,
\begin{eqnarray}
H|\uparrow\rangle&=& \frac{1}{\sqrt{2}}\left( |\uparrow\rangle+|\downarrow\rangle\right)\\
H|\downarrow\rangle&=& \frac{1}{\sqrt{2}}\left( |\uparrow\rangle-|\downarrow\rangle\right)
\end{eqnarray}
The phase gate is equivalent to a rotation by $\pi/4$ about the $\hat z$ axis. Spins aligned with the $\hat z$ axis remain alined with that axis, spins in the $\hat x-\hat y$ plane rotate into one-another
\begin{eqnarray}
\hat T |\uparrow\rangle &=& |\uparrow\rangle\\
\hat T |\downarrow\rangle &=& e^{i\pi/4}|\uparrow\rangle.
\end{eqnarray}
Applying this gate four times to an $\hat x$-eigenstate yields
$$
\hat T^4 (|\uparrow\rangle + |\downarrow\rangle)=(|\uparrow\rangle-|\downarrow\rangle).
$$
which is a rotation by $\pi$.
Finally, the control-not, written "cX" gate is often described by looking at a "truth table" -- which is a table that shows what you get for different basis vectors.
$$
\begin{array}{c|cc}
cX&|\uparrow\rangle&\downarrow\rangle\\
\hline
|\uparrow\rangle&|\uparrow\downarrow\rangle&|\uparrow\uparrow\rangle\\
|\downarrow\rangle&|\downarrow\uparrow\rangle&|\downarrow\downarrow\rangle
\end{array}
$$
This can also be expressed as a matrix equation
$$
cX\left(\begin{array}{c}|\uparrow\uparrow\rangle\\
|\uparrow\downarrow\rangle\\
|\downarrow\uparrow\rangle\\
|\downarrow\downarrow\rangle
\end{array}\right)
=
\left(
\begin{array}{cccc}
0&1\\
1&0\\
&&1\\
&&&1
\end{array}
\right)
\left(\begin{array}{c}|\uparrow\uparrow\rangle\\
|\uparrow\downarrow\rangle\\
|\downarrow\uparrow\rangle\\
|\downarrow\downarrow\rangle
\end{array}\right)
$$
In practice one it is likely to introduce more gates than these -- but if you are doing a "proof-of-principle" -- then you only need to implement these three gates.
Measuring Operators
One typical trick used in quantum computing is a slick way to use measurements of single spins to effectively measure more complicated operators.
