The most primitive element of quantum computation is the quantum bit or q-bit. To begin with, I shall try to explain what a q-bit is. Then, I shall construct an artificial example of quantum computation, just to show what it is all about. It's not something that one can actually build, or would want to build, since it is non-efficient.

Necker Cubes

Each time you look at the diagram only one possibility comes true. To get a different one you have to look aside for a moment before returning to it again. In a sense, all four options "exist" together in this experiment but when you make a visual "measurement" (look at the diagram) it collapses into just one option. This is the essence of the quantum superposition.

According to quantum mechanics, a particle can be in a superposition of two or more "states". Each time you measure the particle, you see it in one of the states. The probability of 'falling' into one state or another is somehow written into the superposition.

Try now to look again at the diagram below. It will probably change the possibilities to fall into each of the four basic states.

90 degrees turned Necker cubes

Suppose now e is a two-state particle, let us call the first state 0, and denote it by |0>, the second state 1, to be denoted |1>. We write the superposition as:

The coefficients a and b are connected to the probability of finding the particle e in the state |0> or |1> after measurement.(In fact, the particle has |a|² probability to be seen in state |0> and |b|²   probability to be seen in state |1> where |a| is the absolute value of the complex number a, |b| the absolute value of b). These coefficients (a and b) are called the 'amplitudes' of the superposition. For example, the particle e could be an electron and the states |0> and |1> could be its spin state. Note that we used the + sign to denote that both states are considered as happening together. This is quantum physics.                                                                                                                                                                                                     
This superposition is called a q-bit since it resembles a classic bit. In a sense, the q-bit can be in both states 1 and 0 at the same time whereas a classic bit can hold only one value at any given moment. The q-bit is the most basic component of the quantum computer.

We now look at the following (classic) logic gate. 

XOR logic gate

A logic gate is a primitive (electronic) circuit that can implement a (binary) logic function. Our gate here has two inputs and two outputs. It is called XOR gate. It emulates the XOR function of the two inputs: that is, if the input X holds the value 1 and the input Y holds the value 0 (or vice versa), then the output is also 1(the lower one, the reason there is another output X, is to make the gate reversible, which is a property demanded by the physics of quantum computers). But if both X and Y inputs are 1 or if both are 0 then the output holds the value 0 (all this is defined by the notation X+Y which is called a summation modulo 2). This is the most basic gate of classic computers.

Now let the superposition: |0>|0> + |0>|1> + |1>|0> + |1>|1> be the input to this gate. Then we can use the above definition of XOR to compute the output superposition: |0>|0> + |0>|1> + |1>|1> + |1>|0>. We did this by putting in each input separately and computing the corresponding output, but note that the quantum computer is doing it all-together.

Such quantum gates can be physically realized. Operating the gate on a superposition of 4 inputs means that this gate computes all 4 computations in parallel. Similarly, for 3 q-bit gates, 8 computations are being processed in parallel, and for n q-bit gates 2ⁿ computations are being processed simultaneously. In this way we can save much time.

So far we took a classic gate or a classic primitive computer and turned it into a primitive quantum computer. We benefit from the fact that the quantum gate is computing all inputs simultaneously. In a similar way we can take a general classic computer and transform it into a quantum computer. This we do by decomposing the classic computer into primitive gates (we can always do it by a well known theorem in computer science) and transforming each primitive gate into its quantum counterpart.

An Example of a Quantum Algorithm: 

Suppose we are asked to find all the prime factors of a big number c(c can have a few hundred figures, such numbers appear in military or bank codes). Suppose we have a computer that can check if a certain number b divides c or not. The computer has a flag holding the value 1 if b divides c, and the value 0 otherwise. We would like to use the advantage of parallel computation. Let the input of such a quantum apparatus be the superposition of all numbers from 2 to c^1/2. Then, what would the output be? 

what would the output be?

The output may look like this:

|2>|1> + |3>|1> + |4>|0> +. . . . .  

This means that 2 divides c, 3 divides c, 4 does not, and so on. But this outcome is a superposition, how do we get the answer?

We can measure the superposition as we did in the case of Necker's boxes. This measurement yields a number d, with the information 1 or 0. We now know that d divides c or does not. We can not control the number d we get, because we can not control the state into which the superposition collapses. Since the majority of the numbers we checked do not divide c, we will probably end up with some useless information.

Image of the first "commercial" quantum computer developed by the Canadian Company D-Wave equipped with 16-qubit processing power (Credit: D-Wave)

The probability amplifier must be operated before measurement. Only then the measurement will probably yield some number that divides c. Knowing a number d that divides c we can reduce the problem to c/d.

D.Deutsch, The Fabric of Reality, Penguin Books, 1998.