Quantum Computers
The memory of a classical computer is a string of 0s and 1s, and a classical computer can do calculations on only one set of numbers at once. The memory of a quantum computer is a quantum state which can be in a superposition of many different numbers at once. A classical computer is made up of bits, and a quantum computer is made up of quantum bits, or qubits. A quantum computer can do an arbitrary reversible classical computation on all the numbers simultaneously, and also has some ability to produce interference, constructive or destructive, between various different numbers. By doing a computation on many different numbers at once, then interfering the results to get a single answer, a quantum computer has the potential to be much more powerful than a classical computer of the same size.
The most famous example of the extra power of a quantum computer is Peter Shor's algorithm for factoring large numbers. Factoring is an important problem in cryptography; for instance, the security of RSA public key cryptography depends on factoring being a hard problem. Despite much research, no efficient classical factoring algorithm is known.
Shor actually solved a related problem, the discrete log. Suppose we take a number x to the power r and reduce the answer modulo n (i.e., find the remainder r after dividing xr by n). This is straightforward to calculate. It is much more difficult to find the inverse - given x, n, and y, find r such that xr = y (mod n). For factoring, all we need to do is consider y=1 and find the smallest positive r such that xr = 1 (mod n). Shor's quantum algorithm to do this calculates xr for all r at once. Since xl+r = xl (mod n), this is a periodic function with period r. Then when we take the Fourier transform, we will get something that is peaked at multiples of 1/r. Luckily, there is an efficient quantum algorithm for the Fourier transform, so we can then find r.
There are many proposals for how to build a quantum computer, with more being made all the time. The 0 and 1 of a qubit might be the ground and excited states of an atom in a linear ion trap; they might be polarizations of photons that interact in an optical cavity; they might even be the excess of one nuclear spin state over another in a liquid sample in an NMR machine. As long as there is a way to put the system in a quantum superposition and there is a way to interact multiple qubits, a system can potentially be used as a quantum computer. In order for a system to be a good choice, it is also important that we can do many operations before losing quantum coherence. It may not ultimately be possible to make a quantum computer that can do a useful calculation before decohering, but if we can get the error rate low enough, we can use a quantum error-correcting code to protect the data even when the individual qubits in the computer decohere.
Quantum states are very delicate. The primary difference between a quantum state and a classical state is that a quantum state can be in a superposition of multiple different classical states. However, any measurement of the superposition will collapse the quantum state into one of its component classical states. In fact, most interactions with the environment will act just like a measurement and will collapse the state. This is the reason the world at a human scale looks classical - big objects are very likely to interact at least a little bit with their environment, so they are constantly collapsing into classical states. This process is known as decoherence.
This is a big problem for a quantum computer. If we cannot stop it from interacting with the environment, it will be no better than a classical computer. It turns out that stopping decoherence is the same problem as stopping general noise, such as a coherent bit flip. The solution to the problem is to use a quantum error-correcting code.
The simplest classical error-correcting code is the repetition code. We encode a 0 as 000 and a 1 as 111. Then if only one bit is flipped, we might get the state 011, and we can deduce that the original state was 111.
For a quantum code, we need a bit more. The signs of states in a quantum superposition are important, so we need to be able to correct sign errors as well as bit flip errors. To do this, we could use nine qubits instead of three:
|0> -> (|000> + |111>) (|000> + |111>) (|000> + |111>)
|1> -> (|000> - |111>) (|000> - |111>) (|000> - |111>).
Then by comparing qubits within blocks of three, we can detect bit flip errors, and by comparing the signs of the three blocks, we can detect sign errors. Using this code, we can correct an arbitrary single-qubit quantum error.
This is just the simplest quantum code. Many more are known, and there is a well-developed theory of quantum error-correcting codes. Most quantum codes can be described by their code stabilizers, which is much simpler than writing out the full state in ket notation.
If we want to preserve a quantum state for a long time without doing any calculations, or if we want to send it through a noisy communications channel, we can just encode the state using a quantum code and decode it when we are done. If we want to do computation on a state using noisy gates, we need to know how to perform operations on states that are already encoded. Furthermore, we need to do it in such a way that we do not introduce more errors than we can correct. In other words, we need the computation to be fault-tolerant.
Stabilizer Codes
A quantum error-correcting code is a carefully chosen subspace C of the Hilbert space of the computer such that single-qubit errors (and perhaps errors on multiple qubits) acting on any state in C will produce distinguishable states. For instance, suppose E is some operator, such as a single bit flip. If E |psi> is orthogonal to |psi> for any |psi> in C, then we can always make some measurement which will tell us if current state has the form |psi> or the form E |psi>. This measurement will therefore tell us whether or not the error E has occurred.
In order to be able to correct the state, we actually need to not only distiguish error E from no error, but also from any other error F. Otherwise, we might try to correct error E when actually error F occurred, and now we have two errors instead of one. We can formalize this in a sufficient condition for an error-correcting code:
< i | EF | j > = 0.
If this condition is satisfied for all possible distinct errors E and F and all basis states |i> and |j> (also i equal to j) for C, then C is an error-correcting code. The possibilities for E and F should include the identity (no error).
One way to ensure that this condition is true is to pick C so that it lies in the +1-eigenspace of some operator M. Then if EF anticommutes with M, EF will take states from the +1-eigenspace of M to the -1-eigenspace of M, which is orthogonal to the +1-eigenspace:
< i | EF | j > = < i | EF M | j >
= - < i | M EF | j >
= - < i | EF | j > = 0.
It is convenient to pick M to be the tensor product of Pauli spin matrices, because then other products of Pauli matrices will always either commute or anticommute with M. By choosing C to be in the +1-eigenspace of enough M's, we can make sure that EF will anticommute with one of the M's for any pair of E and F.
We are not completely free to choose the M's however we like. We want C to be in the +1-eigenspace of all the M's. For this to be possible, the M's must commute with each other. In addition, if C is in the +1-eigenspace of M1 and M2, then it is also in the +1-eigenspace of M1 M2. Therefore, the set S of tensor products of Pauli matrices for which C is in the +1-eigenspace is an Abelian group. In fact, it will always have order 2n-k, where n is the number of qubits in the full Hilbert space and k is the number of qubits encoded by C. S is called the stabilizer of the code.
Not all codes can be described by a stabilizer. However, the vast majority of known quantum codes can be. In addition, stabilizer codes have more structure than non-stabilizer codes, which makes them easier to find and easier to work with than non-stabilizer codes. For instance, to figure out what error has occurred, we only have to measure the n-k generators of the stabilizer and do some classical processing. Stabilizer codes are related to classical codes over the finite field GF(4), so many classical results can be directly applied to them. Also, any stabilizer code can be used to perform fault-tolerant computation.
As I final example, below I give the generators for the stabilizer of the five-qubit code. This is the smallest possible quantum code to correct one general error.
X Z Z X I
I X Z Z X
X I X Z Z
Z X I X Z
You can check for yourself that any two-qubit product of Pauli matrices will anticommute with at least one of these four operators.
Fault-Tolerant Computation
To use a quantum error-correcting code to improve the performance of a noisy quantum computer, we need to be able to do operations on encoded states without causing the uncontrollable spread of errors.
Consider the controlled-NOT, a very simple and common two-qubit operation. If the first bit is a 0, nothing happens. If the first bit is a 1, the second bit is flipped. This means that if, before the CNOT, there is a bit flip error in the first bit, then, after the CNOT, the second bit is wrong as well, since it gets flipped exactly when it is supposed to stay the same. The error has propagated from the first bit to the second bit.
This much is true classically. However, in a quantum computer, we also have to worry about sign errors. Consider what the CNOT does to the state
(a |0> + b |1>) (|0> + |1>).
When the first qubit is 1, the second qubit is flipped, which has no effect on this state, so after the CNOT, the state is still
(a |0> + b |1>) (|0> + |1>).
If there has been a sign error on the second qubit, so the state is actually
(a |0> + b |1>) (|0> - |1>),
then when the first qubit is 1, the second qubit gets an overall sign of -1. There is no sign change when the first qubit is 0, so in this case, after the CNOT the state is
(a |0> - b |1>) (|0> - |1>).
The sign error has propagated from the second qubit to the first qubit.
The possibility of error propagation is a major concern when attempting fault-tolerant computation. If we are doing CNOTs willy-nilly, a single error in a block can propagate to other qubits in the block, becoming two or three or even more errors. If we are using a code that can only correct a small number of errors, we will move from a situation we can handle (one error) to a situation we cannot. In order to avoid this eventuality, we should set up our fault-tolerant algorithm to only do CNOTs between corresponding qubits in different blocks.
The other concern for fault-tolerant computation is performing operations which take valid codewords to valid codewords. A particularly good code for this purpose is the seven-qubit code. The 0 and 1 of this code are superpositions of the odd and even parity states, respectively, of the seven-bit classical Hamming code. Its stabilizer is given below:
X X X X I I I
X X I I X X I
X I X I X I X
Z Z Z Z I I I
Z Z I I Z Z I
Z I Z I Z I Z
Suppose we take the Hadamard transform, which maps
|0> -> |0> + |1>
|1> -> |0> - |1>,
and perform it on each qubit of the seven-qubit code. The Hadamard transform effectively interchanges X and Z. Therefore, when applied to the seven-qubit code, it switches the first three generators of the stabilizer with the last three generators. Since the states of the code are exactly those states which are +1-eigenvectors of all six operators, after the Hadamard transform, they are still +1-eigenvectors of these same six operators, so they are valid codewords. In fact, it turns out that the new codeword is just the (encoded) Hadamard transform of the original codeword.
There are a number of basic operations which, like the Hadamard transform, convert Pauli matrices into other Pauli matrices or tensor products of Pauli matrices. Because of the symmetry of the stabilizer of the seven-qubit code, any such operation will just permute the elements of the stabilizer. Therefore, any of these operations can be used to get a fault-tolerant operation on the seven-qubit code. This gives a large set of operations, but not quite enough for universal computation. A more complicated construction allows us to complete the set of basic operations, producing universal fault-tolerant computation for this code and similar codes.
For the more general stabilizer code, most operations will not permute elements of the stabilizer. However, by preparing certain ancilla states, using those operations that do work, and performing carefully chosen measurements, we can still do universal fault-tolerant computation.
Therefore, by choosing a suitable quantum code and performing fault-tolerant operations, we can reduce the effective noise in a quantum computer. We perform fault-tolerant error correction to clean up existing errors alternately with fault-tolerant operations to advance the calculation. Of course, errors are occuring even during error-correction, so there is a race between the appearance of new errors and our ability to correct them. If the error rate per gate is low enough, we can correct errors faster than they appear, and we can keep the error rate lower than it would be without error-correction.
Now, sooner or later, there will be a real error anyway. Just by chance, it is possible that a large number of errors will all occur at about the same time. Our code can only handle so many, and if there are more than it can handle, the result will be an error in the data. The more errors that need to occur for this to happen, the less likely it is to happen. However, typically codes to correct more errors require more effort to work at all, so it is not clear we can ultimately win by using a larger code. As it happens, if we pick the right kind of larger code, we can correct more errors with only a modest increase in the complexity of the error-correction step. The result is that if the basic error rate is below some threshhold, we can do arbitrarily long computations by choosing a sufficiently large code.
Threshhold for Fault-Tolerant Computation
Suppose we have a noisy quantum computer and we want to perform a long computation. We could encode the data using the seven-qubit code, for instance, and perform the computation fault-tolerantly. The seven-qubit code corrects a single arbitrary error, so in order for the computation to fail now, two errors need to happen in the time between error correction steps. If the original error rate per step was p, the new effective error rate per step is C p2 for some constant C. Before, we could perform about 1/p operations before the computer is likely to fail; now we can perform about 1 / (C p2). If p is small, this can be quite a bit more. The constant C will depend on how many operations we do between error corrections and on how many operations are required to perform an error correction (since new errors can occur while we are attempting to fix old ones).
But suppose we want to do an even longer calculation. What options do we have? We could use a different code. However, that code might require more effort to correct errors, so even if it can correct more errors, it might not be an improvement. A better choice is to encode the data a second time using the seven-qubit code. Now each logical qubit in the computer is encoded using 49 physical qubits. In order to have an error on the data encoded at level 2, there need to be two level 1 errors in the time between error correction steps. The error rate now goes from C p^2 to C (C p^2)^2, or C^3 p^4.
If even this error rate is not enough, we can add a third or fourth level of concatenation. In general, if we use L levels of concatenation, the effective error rate will be (C p)^(2^L) / C. As long as p < 1/C, the effective error rate per step will rapidly go to 0 as we add levels. 1/C is thus the threshhold error rate below which arbitrarily long quantum computations are possible.
One nice feature of concatenated codes is that we do not need very many levels of concatenation to get a big reduction in the error rate. Suppose we want to do a calculation requiring T steps. We should reduce the error rate to about 1/T in order to have a good chance of finishing the calculation without an error. Since the error rate is a double exponential in the number of levels, we only need about log(log T) levels to get this error rate.
Of course, the number of qubits we need goes up exponentially with the number of levels (there are 7L qubits per block). For short calculations, we can probably find a smaller code that will work. For long calculations, the exponential kills one of the logarithms, but that still means we only require (log T)k qubits per block, which is an acceptably slow rise in overhead.
In order to make the best use of this scheme, we should try to make C as small as possible. This is largely done by optimizing the error-correction step. Depending on how detailed an analysis you are willing to do and on how good an optimization you have done, you can get a number of different possible results. Right now, it appears the threshhold can be brought above 10^-4, possibly even above 10^-3. This means that if we can make a quantum computer which has an error once per ten thousand steps or so, we can use it to do arbitrarily long quantum computations. While this is a challenging technical problem, it is by no means an inconceivable goal.