Computation with Qubits
Consider a traditional computing machine, one can think of it as a construction of simpler, more elemental components. These basic parts are the AND, OR, and NOT gates that are conglomerated to carry out incrementally more complicated processes. This is obviously only a semantic distinction, we can easily regress further to the transistor level or even the elemental particle level should we be so inclined. I have chosen the Boolean logic level as a sort of delineation point where we consider traditional computation to be occurring. Quantum computers too are built on such a foundation. In the quantum case we can reduce the logic to a slightly simpler controlled-NOT element shown below.
Figure 1. A graphical representation of a controlled NOT element. c represents the control qubit and x the qubit to be conditionally NOTted. In the absence of a control qubit the element acts like a traditional NOT gate by inverting the state of x.
The qubit is used to control the NOT operation, a results in inversion of the qubit , and a passes unscathed. Mathematically, the controlled NOT can be represented by the following matrix.
Multiplying the two qubits by a controlled NOT matrix carries out the conditional action. For example, if we want to NOT the qubit we set the control bit to . This is just the multiplication of the column vector representation of by the conditional NOT matrix.
The resulting column vector has swapped the state of to a , as expected. Had the control qubit been the state of would have been left unchanged. By gathering up a mess of conditional NOTs it is a pretty straightforward task to make the more traditional gates of Boolean lore. For example, an AND gate can be created using one conditional NOT with two conditional inputs.
Figure 2. Left: A quantum AND gate created using a conditional NOT with two control qubits. Right: A quantum OR gate created from two standard NOTs and a conditional NOT.
Obviously from here you can expand your palette of operations even further by aggregating the gates into more sophisticated assemblies. As it turns out, quantum versions of gates such as the AND and OR above have a very important difference from their classical counterparts. A normal gate operates in an absolute fashion for a given input while its quantum sibling, by nature of the superposition of multiple states of its inputs, takes on several state pathways over the temporal duration of the computation. At the end of the computation these pathways recombine and, due to the phase information present, interfere with each other either constructively or destructively to produce a definite state. It is this feature of qubits that permitted Peter Shor  to devise a quantum prime factorization algorithm that operates in polynomial instead of exponential time.
Quantum algorithms are important topics in computer science at present but these algorithms are, of course, only theoretically realized since there is no actual quantum hardware to actually perform them on. Furthermore, two major stumbling blocks lie in the way of a physical realization of a quantum computer: the error correction and decoherence problems. For some problems error correction is trivial, such as in the prime factorization case. The reversibility of the process by multiplying the factors together gives a simple check to the algorithm. Other nontrivially reversible or irreversible problems require more robust error correction. Decoherence is another kettle of metaphorical fish--the quantum computation needs to take place in isolation from the outside environment, lest it be affected by its quantum dynamics. This contamination would cause damage to the phase information, which is critical to the eventual constructive/destructive reconstitution of the qubits at the end of the computation.
Converted by Mathematica