Quantum Computing poised to take a Quantum Leap

The year 2001 is on us, and HAL, the ultimate thinking computer created by Arthur C Clarke in his book "2001, A Space Odyssey" still remains fictional and a distant dream. Yet, computers and computing technology has moved ahead by leaps and bounds in the recent past. As we step into the new millennium, we are up against yet another revolutionary technology, that of Quantum Computing, observes C.S. Vinod.

What is quantum computing? The foundations of this field are buried in the recent science of quantum physics, which explains the behavior of matter in a novel manner. Based on the Heisenberg Uncertainty Principle, the quantum theory was originally given by Erwin Schroedinger. Quantum computing is based on the same concept applied in the computing arena.

Quantum theory works on the hypothesis that observable quantities do not vary continuously, but discreetly, in chunks or quanta. That is what makes any computations possible. But wait, what is "observable quantities"? It means that when an observation or a measurement is made, a system goes into one of its possible states, and nothing in between. Each of the possible states of the system is called an eigenstate. But, what happens when no observations are being made? The system will be in a state of superposition of all its possible states! Only when an observation is made does the system collapse into a particular eigenstate and continues to be in that eigenstate.

The idea is illustrated with the help of Schroedinger’s cat. Here is the problem in Schroedinger’s own words:

"One can even set up quite ridiculous cases. A cat is penned up in a steel chamber, along with the following diabolical device (which must be secured against direct interference by the cat): in a Geiger counter there is a tiny bit of radioactive substance, so small that perhaps in the course of one hour one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter tube discharges and through a relay releases a hammer which shatters a small flask of hydro cyanic acid.

If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed. The first atomic decay would have poisoned it. The Psi function for the entire system would express this by having in it the living and the dead cat (pardon the expression) mixed or smeared out in equal parts."

One now wishes to know whether it is dead or alive. To do that, one would have to resort to direct observation and the action of looking into the box will trigger the cat to go into one of the states: dead or alive.

But we don’t see such things happening in everyday life. The effect is more pronounced at the microscopic level. This theory is therefore used more in explaining the behavior of atoms and molecules, although it encompasses every other theory in physics (except the general theory of relativity).

The quantum theory has sparked an enormous amount of interest in the computing world. What quantum physics was to classical physics, quantum computing is to classical computing. Let us delve a little deeper to find out what makes this field so powerful.

Just as bits can represent any state in a classical computing system, in a quantum system there are qubits, or quantum bits, to represent quantum states. Mathematically, the state space (i.e., the set of all the states) of a quantum system can be represented by a finite-dimensional complex vector space with an inner product. This is the superposition of all the individual eigenstates of a system. A qubit, the simplest quantum state, can represent any two dimensional vector in the physical world. As a simple example, the spins of an electron (clockwise and counterclockwise) can be thought of as qubits in a two-dimensional complex vector space.

Qubit mathematics presents a number of interesting features:

• Every measurement on a system places its qubits in certain states.
• Qubits can be placed in what is called an entangled state, where a measurement on one qubit affects all the other qubits in the system.
• Arbitrary (unknown) qubits in a system cannot be cloned or duplicated. They can only be placed in an entangled state. This is known as the No Cloning Principle. Of course, known qubits can be duplicated.

The dynamics of qubits involve the concept of logic gates for the transformation of quantum systems from one state to another, just like in classical computing. We know that all the classical computing circuits can be restructured to contain only the reversible NOT gates and the AND gates. Both these gates are possible using qubits, and therefore, theoretically, quantum computers can be built. These computers would be able to match the capabilities of any classical computer in terms of what they can do.

But quantum computers can be much more powerful than just that. A quantum system grows exponentially with a linear increase in size. An n-qubit system corresponds to a 2n dimensional state space. A series of transformations of a quantum system from one state to another can be thought of as a quantum algorithm. These algorithms can exploit the rate of growth of a quantum system to give unparalleled productivity. The applications of quantum algorithms include mathematical transformations, factoring algorithms, search algorithms and cryptography algorithms. In fact a factoring algorithm developed by Peter Shor has put the world of cryptography into a state of red alert, as most encryption algorithms rely on improbability of factorization of a large number within a decent space of time. By far the most interesting feature is that all quantum systems, by their very nature, support parallel processing. Now that is something that most classical computers don’t have. Moreover, present machines that have a parallel architecture can also benefit from quantum parallelism.

What does a quantum computer look like? The fact that quantum physics works at the micro level makes atoms and molecules the ideal candidates for quantum systems. The energy levels of electrons, cryogenic ion traps, NMR spectroscopy systems, and even nuclei of select isotopes, all have been used as quantum systems. Systems of up to five qubits have been built and quantum algorithms run fine on them.

The primary obstacle to building a practical quantum system is de-coherence of information due to interaction with the environment. Since the atoms in the environment are unavoidable, they, together with the system of concern, act as another part of a bigger quantum system in an entangled state. The solutions vary from carrying out more computational steps before significant de-coherence, to designing algorithms that model the errors due to de-coherence.

More work has to done on the physical realization of a bigger and more practical system. The same is the case with the algorithms - currently there exist only a handful of them. Yet, the future is definitely bright. This is the dawn of a completely new paradigm in computing, with quantum physics forming the basis of it. Who knows, one day you will have a cup of coffee in front of you and call it a computer!

C S Vinod
MTS, High Performance Business Computing Group.
He is presently working on Financial Modeling of Capital Markets.