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.
What Is a Q-bit?
There is a well known psychological test of perception, named after the 19th century Swiss crystallographer Louis Albert Necker, where one is given the following diagram:
|
Looking at the diagram one can identify one of four possibilities: Either both squares are protruding forward or both backwards or one forward and the other backwards, try it.
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.
|
The rotation you have just made is very similar to some quantum computation. You get the impression that the rotation evolves the whole superposition from some initial state to a final state, it does not effect each state separately. Only when you finish rotating you can measure again and ‘fall’ into one of the states. Note also that the rotation is continuous, so quantum computation could be continuous.
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|2 probability to be seen in state |0> and |b|2 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.
How to Build a Quantum Computer
We now look at the following (classic) 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 2n 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 c1/2. Then, 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.
|
Although we saved a lot of time computing things at parallel we can not ‘read’ the results. What we need is a “probability amplifier”. We need to amplify all the states in the superposition where the flag held the value 1. This must be done without harming the superposition, i.e. without measurement. It looks as if one has to know the answer to the problem if one wants to build such an amplifier, but this actually isn’t the case. Such an amplifier has to identify the set of all places where the flag is 1, without checking them one by one. Remember that a quantum gate operates on all inputs together. It does not separate the inputs from each other. Such probability amplifiers or ‘amplitude amplifiers’ exist in quantum physics. This can be done by playing with the coefficients of the superposition. As in the case of one q-bit, if the coefficient ‘a’ grows while ‘b’ is attenuated then the probability to fall into state |0> increases. In our example above (the Necker cubes), by rotating the page we probably enhanced several coefficients and attenuated the others. This is very similar to such amplitude amplification.
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.
Conclusion:
Quantum computation is about using quantum physics to compute mathematics. It’s parallel computation, but more than just parallel, it can produce effects that are harder to get in classic computers. It has some continuous properties also. There are several known quantum algorithms that show better efficiency than their classic counterparts, among them a quantum algorithm to compute the Fourier transform.
D.Deutsch, The Fabric of Reality, Penguin Books, 1998.
M.Nielsen, I.Chuang, Quantum Computation and Quantum Information, Cambridge 2000.
About the author: Boaz Tamir holds a Ph.D. degree in Mathematics from the Weizmann Institute of Science. In 2008 he recived a second Ph.D. from the department of History and Philosophy of Science at the Bar Ilan University.
