Closer to quantum computing
(appeared in Mar 2016)

(link to main website)

One long stride has been taken on the march to quantum computing, says S.Ananthanarayanan.

The physics of very small objects has features that make uncanny things possible. One of these is that outcomes of interactions are not clearly one or another, but a probability of each of different possible ways. A particle within a nucleus, for instance, has a probability of being outside the nucleus as well, which is why radioactivity is possible. The undisturbed state of the particle, in fact, is both within and outside, till a measurement is made. This quality, of things being in more than one state at once, unlike the usual condition of one or the other, suggests a new mechanism that can consider different possible values of the same variables in a calculation and a number of computations, all at once.

It was legendary Richard Feynman who, as early as 1982, had the insight to think of think of such a device. The idea was of using an object, like an electron, which could have a spin ‘up’ or ‘down’, in the same way as an electronic gate, which could be ‘open’ or ‘shut’, to represent the digits ‘0’ or ‘1’ of binary arithmetic. The idea held promise, as the electron could be in both states at once, unlike the electronic device, but for many years there was no method to actually use this property for computation. Finally, there was progress, first in proposed computational methods and then in actual devices, but the devices are rudimentary. Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph and Geoff J. Pryde of Griffith University and the University Queensland in Australia and the Université of Bordeaux in France report in the journal, Science Advances, the development of a more complex unit to process quantum states, which would simplify the challenge of implementing an actual quantum computation of reasonable complexity.

The way the regular computer deals with binary digits is with electronic gates, or devices that can pass electricity, or not, the two states to represent ‘0’ or ‘1’. Pairs of such devices can then make logical decisions, or ‘OR’ or ‘AND’ and pairs of these devices could be connected to add binary numbers.

Figure 1 shows two kinds of gates and the figures, 2 and 3 show how the two kinds of gates can add two binary digits, and also ‘carry over’ a digit to the next place, if the sum needs another digit to be expressed. In figure 1, the sum of A and B, for their 4 possible values, is 0, 1, or 2, which is written as ‘10’ in binary arithmetic. The table then shows the rightmost digit of the answer under ‘sum’ and the carry over of ‘1’, in the fourth case. If there is a carry digit to be added from a previous addition, this is done by using another two gates, as in figure 3.

In quantum computing, in place of electronic components or gates, we use states of atomic assemblages, or properties like the nuclear spins in molecules, which can be either aligned or counter aligned, to represent the numbers ‘0’ and ‘1’, and each such unit is called a ‘qubit’. The qubits are manipulated using magnetic fields, radio frequency pulses or NMR (nuclear magnetic resonance). Qubits, however, are very sensitive to disturbance, which destroys the condition of being in ‘all possible states at once’, as disturbance acts as a measurement, which causes the qubit to ‘commit’ to one of its possible states and it the thenceforth in that state.

The physical quibit is hence a great challenge in implementing quantum computing. In principle, if we set up a system of say a hundred particles to be in either of two states, then we can mimic the action of a conventional computer with 2100 components. 2100 is a number with 30 zeros or an unimaginable huge number and our quantum computer of a 100 particles would be able to do the most complex computation in a trice. But the best that we have been able to do, with sophisticated arrangements, is a 4-particle system, which can manipulate a 24 =16 states.

Algorithms

But even if we find ways to manage qubits, it is misleading to suppose that quantum computers would directly lead to high computing. Let is take a typical problem, say comparing two sets of a thousand numbers to find duplicates. In the normal way, this would take 1000 x 1000 = 1 million comparisons. But with a quantum computer, we could have two components in 1000 states each at the same time and carry out the comparison at once! True, but the system will still carry out a million comparisons and would not pick out the match, when found, and present it to us.

The possibility of quantum computing looked promising only after clever methods were discovered to extract actual information from the ‘massive parallel’ process of the quantum system. A famous one is the Shor algorithm for finding the two factors of a number generated by multiplying together two large prime numbers. This is a formidable task when the primes are, for instance, 64 binary digits long and the product is 128 digits long. One way of doing this is by dividing the number by all primes from the number, 2 onwards, to see which one produces no remainder. Conceivably, a quantum computer could carry out this check in reasonable time, but, as in the case of finding duplicates, there is no way to say which division resulted in no remainder.

The Shor algorithm essentially restates the problem so that the result of quantum computing is not all the possible solutions together, but only the one of interest. It first relies on an old result that was known since the eighteenth century, about cycles in division of a series of powers of the number 2. Let us consider a series like this: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,.. Now, we list out the remainders when we divide each of these numbers by the number, 15, which is the product of prime numbers, 3 and 5. We get: 2, 4, 8, 1, 2, 4, 8, 1, 2, 4,… What do we notice? That the remainders form a sequence of 4 numbers that repeat. Well the 1760s result is that the number of remainders that repeat must be a divisor of the product of one less than the two prime numbers involved. In our case, the primes were, 3 and 5. Now 2 x 4 = 8, and we see that the number, 4, in the sequence of remainders, is a divisor of the number, 8. The reader could try it out with the number 21, which is the product of the primes, 3 and 7. The number of remainders that repeat are 6, and (3-1) x (7-1) = 12, which is a multiple of 6.

In the case of the factorising problem, then, a quantum computer could quickly find the periodicity of remainders and hence a divisor of the product of the two primes, less one. This is still not the answer, but a step closer. The Shor algorithm then relies on the properties of quantum mechanical states that result in remainders and finds that all these ‘wrong answer’ states would cancel and not appear in the solution, which would then contain only the correct answer!!

Fredkin gate

The work of the Science Advances authors is regarding an arrangement like the quantum mechanical ‘AND’ or ‘OR’ gate, in the actual computation. These gates are challenges by themselves and for a problem of any complexity, we would need a very large number of them. There is hence an advantage in creating single, more complex modules, to reduce the total numbers required in practice. "Similar to building a huge wall out lots of small bricks, large quantum circuits require very many logic gates to function. However, if larger bricks are used the same wall could be built with far fewer bricks," says Dr Raj Patel, from the Griffith’s Centre for Quantum Dynamics at Brisbane.

Just as there are the ‘AND’ and ‘OR’ gates, there is a gate called the Fredkin gate, whose action is to switch the states of two qubits depending on the state of a third quibit. In binary arithmetic, switching states of binary units like qubits is a real arithmetic operation, as also a logical one. The Fredkin gate is thus a useful unit in more complex computations and it takes the place of a number of other devices. Implementing a Fredkin gate is thus a means of eliminating many others, and hence simplifying the whole task.

“Although the salient features of quantum computer have been shown in proof-of-principle experiments, difficulties in scaling quantum systems have made more complex operations intractable. This is exemplified in the classical Fredkin (controlled SWAP) gate, for which, despite theoretical proposals, no quantum analog has been realised,” say the authors. The team has now demonstrated the quantum Fredkin gate using photons, or particles of light, which can be in two distinct states of polarisation, or plane of vibration of electro magnetic waves. The team is able to generate stable three-photon states, where the state of a two qubit system can be controlled. This “paves the way for larger controlled circuits to be realised efficiently,” the authors say.

------------------------------------------------------------------------------------------

Do respond to : response@simplescience.in