Another way to represent or to code a bit of information could be two different electronic states of an atom But an atom can also have a superposition of two states. If a bit can exist in either of two states then it can also exist in a superposition of the two states. In other words, if we want to chose an atom as a physical bit, then it's possible to have more than 2 states. It can have both the value 1 and 0 and also any value in between. To understand the idea of a quantum object being in 2 states at once here is a very simple experiment.
Fig1 A
Fig1 B Fig1 C
Fig 1 C
This conclusion, in more technical terms, could be rephrased as fallow: the photon is in a coherent superposition of being in the transmitted beam and the reflected beam. In the same sort of manner, the atom can be prepared in a superposition of two different electronic states. Such a quantum system with two states is called a quantum bit, or a qubit and it can be prepared in superposition of its 2 logical states 0 and 1. [2]
If we take a very simple example. Let's say we have 3 bits. With the classical computation methods, we can store in these 3 bits one of all 3 digit numbers in base 2 at a time. For example: 001, 010, 011 and so on. In total there are 23 = 8 possible numbers which can be stored in this 3 bit register. But a similar quantum 3 bit register would be able to store all these 8 numbers at the same time. So, a N bit quantum register would be able to store numbers 2N numbers at the same time. And the best thing about this is that operations can be performed on all of them at the same time. One way in which we could do this, is by taking quabits as atoms and then with tuned laser pulses we would be able to affect the atomic electronic states. In this way, we would be able to operate on all of them at the same time. During the operation all the numbers in the superposition are affected. This is a parallel computation. In this way it would be able to perform in one computational step 2N classical operations. To get the same result with a classic computer, it would have to do the computations 2N or one would have to use 2N processors which are working in parallel at the same time. [1]
The parallelism comes for free with quantum computing. The output of the algorithm would be the constructive interference between the parallel computations. [4]
Comparison between the two computational systems
All this may not seem very exciting. All it is saying is that the classic computer would have to work more and faster in order to catch up with the quantum computer. But the main idea is that the quantum computer is exponentially faster than the classic computer. Let's take an example. Let's assume that we have a set with N elements and we want to generate all the subsets of the given set. The smallest important step of a classic algorithm which would have to solve the problem, would be to generate one subset. Because there are 2N subsets of a set with N elements, the complexity of such an algorithm would be O(2N ). So it would take 2N steps to solve the problem. Let's say that N is 100. Then the total number of operations would be 2100 steps. A modern computer does apx. 3 million basic operations per second and about 1 million complex operations per second. Let's do some calculations to see how long it would take for a "normal" computer to solve the problem:
The number of steps required to solve the problem is:
2N = 1267650600228229401496703205376 steps
If, a computer can perform 1 million complex operations per second, then it would take:
2N / 1000000 ~ 1267650600228229401496703 seconds
That would take:
(2N / 1000000) / (60 * 60 * 24 * 7 * 365) = 5742419548761639 years
Having this it's easy to see that it would take more than 5 million billion years to complete all the operations. But, using a quantum computer with a N bit register, all these steps (2N steps) can be done in one go.
