Quantum Computing

With the invention of computers in the twentieth century, complex information processing could be performed outside human brains. The history of computing technology has evolved from one type of physical realization to another - from gears to relays to transistors to integrated circuits which resulted in smaller, faster and cost-effective computing machines. Today's advancement in lithography technology allows the chip makers to squeeze fraction of micron wide logic gates and wires onto the surface of a silicon chip. The conventional means of pushing hordes of electrons around in order to do calculations has been working well. But the current technology is going to run into fundamental physical barriers (size and cost) around the year 2010. That is, the process of miniaturization being accomplished through various technologies available today is set to reach a dead end soon. Intel founder Moore more than 25 years ago predicted that till year 2010 or at the most 2020, the number of transistors the industry could place on a silicon chip would double every year or two and this time limit is fast approaching. That will mean the end of the growth of this semiconductor electronics industry and the end of a lot of companies and national economies unless we can figure out a way forward.

Also to go for further miniaturization, chip makers will have to employ new x-ray fabrication techniques, which will be expensive to implement. But even with better chip fabrication technology, experts see an eventual breakdown in that trend as the size of silicon logic gates shrinks down to the size of atoms. Further more, the computing industry has started to fret over the future of microchips. How many calculations per second would be ultimately possible, how much heat would this produce, and could silicon survive the constant baking?. Therefore researchers decided to explore somewhat non- Boolean approach that is based on the complex states of quantum matter. In emphasizing, on the atomic scale, matter obeys the rules of quantum mechanics, which are quite different from the classical rules that determine the properties of conventional logic gates. The point to be noted here is that quantum technology can offer much more than cramming more and more bits to silicon and multiplying the clock-speed of microprocessors. It can support entirely new kind of computation with qualitatively new algorithms based on quantum principles. Thus the world can expect a quantum leap in computing in the days to come and this altogether spurred the attention of a host of researchers towards thinking about the ways and means of designing computers using quantum logic circuits and developing theoretical algorithms based on quantum mechanics principles.

The story of quantum computing started in 1982, when physicist Richard Feynman considered the possibility of simulating quantum systems not with conventional digital computers but with other quantum systems constructed as machines for this purpose. Three years later, David Deutsch of the University of Oxford published a theoretical paper in which he described a universal quantum computer. In 1993, Lloyd brought the mathematical abstractions down to earth when he showed how quantum computation could be carried out by qubits arranged in a regular array. Peter Schor from AT & T' Bell Laboratories in New Jersey came out in 1994 with a path-breaking discovery of the first applicable quantum algorithm. The Schor algorithm can solve the factorization problem, which belongs to the category of computationally hard problems, much more efficiently than conventional computers. This achievement of solving a sort of killer application using quantum algorithm rejuvenated the field to expand rapidly in the days that followed.

This development may be the best evidence to date that an architecture based on atoms and nuclei can solve multi-step problems that overwhelm even the most powerful of traditional computers. Most of the current works are being concentrated on accomplishing how quantum information theory can be used as the model for constructing a quantum computer and development of appropriate algorithms that will run on these yet-to-be-realized machines. A quantum computer can be built by the utilization of quantum logic gates integrated into quantum circuits. The challenges ahead are to develop ways that actual quantum systems can be used as logic gates and subsequently to link these logic gates into a circuit through wires.

The two of the greatest revolutions that occurred in the last century are quantum mechanics and information science including computer science. The marriage of these two landed us today in realizing what is called quantum computing. Quantum computing allows a kind of parallelism a classical computer can not hope to match. Firstly regarding information representation, in standard classical computing framework, the voltage between the plates in a capacitor represents a bit of information: a charged capacitor denotes bit value (state) 1 and an uncharged capacitor bit value 0. Thus any part of the internal logic, whether a single 0 or 1 or a whole string of such bits, represents a specific numerical single state. Also the two states are separated by a large energy barrier so that the value of the bit can not change spontaneously. But if we choose an atom as a basic physical bit then quantum mechanics tells us that apart from the two distinct electronic states the atom can be ! ! also prepared in a coherent superposition of the two states. In other words, an atomic nucleus can be spinning clockwise and counterclockwise at the same time. The basic physical unit (qubit) can be any two-state system, like the photon's paths, two orbits of an electron, nucleus (protons and neutrons that have spin) of an atom, quantum dots. Thus in quantum computing, a qubit can represent two states simultaneously, a really novel and vital feature. That is, a half-up, half-down state with both 0 and 1 at the same time.

Secondly regarding information storage, Consider a register composed of three physical bits. Any classical register of that type can store in a given moment of time only one of out of eight different numbers, that is, the register can be in only one out of eight possible configurations such as 000, 001, ..., 111. A quantum register with three qubits can store in a given moment of time all the eight numbers in a quantum superposition. If we keep on adding qubits to the register, we can increase its storage capacity exponentially. That is, 4 qubits can store 16 different numbers at once. In general, L qubits can store 2^L numbers at the same time.

Finally on the computing performance, since the register is prepared in a superposition of different numbers, one can perform all the operations required by a digital computer on all of the inputs at the same time. This can be attained at the subatomic level by manipulating the magnetic environment of electrons or by routing photons through an array of polarizers, mirrors, and beam splitters. Thus, a quantum computer can, in only one computational step, perform the same mathematical operation on 2^L different input members encoded in coherent superpositions of L qubits. In order to accomplish the same task, any classical electronic computer has to repeat the same computation 2^L times or one has to use 2^L processors working in parallel. Because a quantum computer explores all the possibilities simultaneously, it reaches the same result in a single effortless step. Thus, a quantum computer offers an enormous gain in the usage of computational resources such as time and memory. Such is the potential of quantum computing that the list of companies funding research programs sounds like a roll call of the world's biggest telecommunications and computer businesses. They include HP, IBM, AT & T, Lucent Technologies, MagiQ Technologies and Microsoft.

The architecture of a quantum computer is conceptually very similar to a conventional electronic computer: multiqubit or multibit registers are used to input data; the contents of the registers undergo logical-gate operations to effect the desired computation under the control of an algorithm; and finally, a result must be read out as the contents of a register.

A conventional computer is a decidedly classical machine. It relies on electric currents acting as the 0s and 1s of a binary arithmetic system, and those 0s and 1s have to influence each other in absolutely predictable and dependable ways if they are to generate all manner of complex calculations and manipulations.

In a quantum computer, the internal calculations and operations take place through a series of entirely predictable interactions of quantum states. Everything depends on making sure the qubits retain their incredibly fragile quantum-mechanical mix of 1 and 0-what physicists refer to as staying "coherent". Thus quantum computers can carry out a calculation in a reliable way in a perfect environment, just as an electronic computer does if there is no random uncontrolled occurrences of any perturbations.

Electronic computers store information in physical states, each state representing either 0 or 1. These binary digits are called bits, the vehicle by which computational information is represented and manipulated. A quantum computer stores information in subatomic systems called quantum bits or qubits.

Electronic computers operate by flipping millions of tiny electronic switches from off to on and back again to produce calculations and other information. The quantum computer exploits the property that at the levels of atoms or their components, matter can be in many different places at the same time, or in different states. That is, a classical computer processes some definite input state according to its program to produce the corresponding output. But the input state of a quantum computer could be a superposition of many different classical inputs and consequently the quantum computer would process this state to produce a superposition of outputs.

A typical electronic computer can accommodate millions of electronic switches, while a 7-qubit quantum computer contains just seven molecules (atomic switches).

Classical parallelism can also increase the number of values handled simultaneously, but long before reaching the amount of parallelism achievable by a quantum computer, a classical system runs out of space. For classical systems, the amount of parallelism increases in direct proportion to system size; for quantum systems, it increases exponentially with size. Quantum systems can operate in entangled states - states in which parts of the system correlate in ways that have no classical analog. Entangled states are responsible for most of the parallelism and this quantum parallelism is often called entanglement-enhanced information processing.

Quantum effects give sub-molecular computers greater power. Still, quantum computers may never be general-purpose computing devices and more likely to be targeted at some vital specific problems such as massive number-crunching problems and provably secure key distribution for cryptography. The problem of finding the prime factors of a large number has acquired considerable urgency in the realm of code-making and breaking. That is, finding the factors of large numbers is so difficult for classical computers that code-makers rely on this weakness of them to protect their sensitive data. With the development of quantum computers, these codes will face the danger of manipulation or destruction by hackers easily. This will land governments and militaries into trouble as their vital data become unsafe. Also searching huge databases, especially the rapidly growing biological databases, and quantum simulation are the other important computational tasks that can be handled by quantum! ! computers in a better and efficient manner due to its nature of simultaneous processing.

Grover shows that quantum computing can do certain search problems at a quadratically faster exponential speed than one intuitively would expect in classical computing. Shor shows that factoring and other interesting problems can be done in polynomial time in the quantum model. In the recent past, IBM Scientists furthered the cause of quantum computing by announcing that they had solved an order-finding mathematical problem in a single cycle using fluorine atoms instead of the usual silicon gates as the computing elements. There are a number of mathematical and computational problems that are categorized as intractable ones by present-day classical computing methodologies. The quantum computing theory is poised to bring about a radical change in visualizing and solving these hard problems.

Once the calculation has finished, the answer must be obtained. Here comes the trouble. A simple measurement destroys the superposition, leaving the system in one state or another. It is very difficult to determine in advance which state this will be. The goal is to ensure that the measurement produces the answer of interest and it can be reached by exploiting the phenomenon of quantum interference. Each of the superposed states has a probability associated with it that has a wavelike behavior, that is, it can interfere with the probabilities of other states destructively or constructively. Getting the desired answer to a calculation means processing the information in such a way that undesired solutions interfere destructively, leaving only the wanted state, or a few more or less wanted states, at the end. This process is known as a quantum algorithm. A final measurement then gives the desired answer, or in the case of a few final states, a series of measurements gives their ! ! probability distribution from which the desired answer can be calculated.

Quantum algorithms promise to be dramatically faster than their conventional counterparts. Lov Grover designed a quantum algorithm for searching through lists. The problem is to find a person's name in a telephonic directory, given one's phone number. If the directory contains N entries, then on average, he would have to search through N/2 entries before he find it. Grover's algorithm needs to check only N ^1/2 entries before arriving at the answer. This algorithm works by creating a superposition of all N entries in which each entry has the same probability of appearing in response to a measurement made on the system. The, to increase the probability of a measurement producing the required entry, the superposition is subjected to a series of quantum operations that recognize the required entry and increase its chances of appearing.

Albert Einstein including a few other researchers devised a thought experiment towards finding holes in the theory that the universe was built as quantum mechanics claimed. This experiment revolves on the behavior of pairs of particles that, according to quantum theory, are joined together, that is, entangled, in a profound way that has no analog in the classical computing world. On prodding one particle, the other one feels the influence, no matter how far away it might be. Hence the researchers came to the conclusion that this process would have to involve a faster-than-light signal passing between the said particles and this is an impossibility. This is called as the EPR paradox and the entangled particles are known as EPR pairs. Later John Bell, a theorist at CERN proved that the EPR pairs behave in the way predicted by quantum mechanics and there is no faster-than-light signal. Also they showed that entanglement can not be used for superluminal communication. But EPR pair! ! s share the same existence and the same destiny. Thus entanglement became one of the key phenomena in quantum information processing.

Ordinary interactions with the environment destroy qubits and the information they contain, a process known as decherence. Its opposite, coherence, is the ability of a qubit to maintain such quantum characteristics as superposition. If the quantum information is to pass into the world of computer science, a process of error correction is needed to protect against decoherence. In the beginning, physicists doubted about the existence of such a technique because detecting and correcting errors would mean measuring the state of a quantum system and so destroying the information it contained according to the quantum mechanics principles. To overcome this, there came a couple of quantum error-correction algorithms. The idea is as follows: Construct a message in one place and reproduce the same at another place. If the message is sent over a channel or stored in a place noisy enough to distort some of the bits in the sequence, how the receiver recognize the exact message. By adding  redundancy to the message so that the receiver can correct bits that have been distorted.

Quantum physics is essential to the manufacture of increasingly small or complex devices, and it directly underlies chemistry. Suppose we wish to micro-fabricate or nano-fabricate a complicated, highly precise nano-scale device. We will need to understand a host of subtle quantum effects even to design the device. Thus quantum physics directly concerns with building quantum computers, whose building blocks are nano-scale devices. The first 3-qubit quantum computer was created at Los Alamos National Laboratory. It used NMR technology and a trichloroethylene (TCE) molecule. Lately the researchers there have created a 7-qubit quantum computer, the most robust quantum computer ever, by manipulating the nuclei of seven molecules in a test tube of trans-crotonic acid, hence 7-qubit. Like a spinning magnet, the molecules' nuclei can be lined up with electromagnetic pulses from the nuclear magnetic resonance (NMR) spectrometer. These activities at the research labs clearly indicates that the concept is rapidly moving from theory to practice and could create the most powerful computing devices ever dreamed of in the near future.

Though there are a number of ways for generating qubits, nuclear qubits have been appealing for several reasons. One can make a perfectly fine qubit out of any nuclear isotope that has a spin and this is the most coherent system in the universe. Every nucleus is being protected from outside interferences by its dense cloud of electrons. That means that once we get its spin lined up, it will stay on that way for hours and days. Also nuclear qubits are incredibly easy to assemble. Nature gives us a lot of different molecules to be used for nuclear qubits. Moreover, the nuclear spins inside a molecule tend to interact nicely. Finally, the technology for manipulating these nuclear spins is the popular NMR.

There are a number of competing technologies such as solid state quantum computing, ion-trapping quantum computers and nuclear magnetic resonance computing, for designing quantum computers. The latest breakthrough is linear optics quantum computation that uses really simple things that are out there every where, such as lenses, semi-silvered mirrors and optical fibers.

Of those, those exploiting NMR have been the first to demonstrate nontrivial quantum algorithms with small numbers of qubits to establish benchmark experiments that are independent of the underlying physical system, and that demonstrate reliable and coherent control of a reasonable number of qubits. The quantum computer uses NMR to manipulate nuclei in the hydrogen and the four carbon atoms. The nuclei are like tiny bar-magnets spinning in a magnetic field that can be lined up by applying an electromagnetic pulse from the NMR device. This lining up of spinning nuclei in positions either parallel or counter to the magnet field allows the quantum computer to mimic and improve on the information encoding of bits by zeros and ones in classical digital computers. NMR sounds like the dream solution to a thorny problem. Nuclei are naturally isolated from the the noise of the outside world and so can maintain coherence for many seconds, enough time to perform hundreds of logic opera! ! tions. In addition, NMR is a mature technology, having been used over many years for imaging and chemical analysis. But the technique has some severe limitations. Single molecules do not produce a signal strong enough to be observed. Instead, NMR experiments must involve hugh numbers of molecules of the order of 10 ²³ so that their combined magnetic induction signal is large enough to be picked up.

A few researchers have recently hit upon the idea of using the individual atomic spin states within molecules. Single protons, the nuclei of hydrogen atoms, have spins that can point up and down relative to the spin of some other nucleus in a molecule. Pulses of radio waves with the right frequency can flip these spins up and down, and the spins of different nuclei on the same molecule interact in predictable ways. This could form the basis for a quantum computer: the spins would store the information and the radio waves would make them flip according to plan to carry out one's calculations.

Researchers in Los Alamos are developing an ion trap quantum computer experiment using calcium ions instead of fluid liquids with the ultimate objective of performing multiple gate operations on a register of several qubits and possibly small computations in order to determine the potential and physical limitations of this technology.

It is generally believed that a quantum computer's central processor could be nothing more than a beaker of some suitable liquid, whose molecules would include a variety of atomic spin states specially chosen to perform a set task. Another possibility is to use a silicon chip etched with dots and doped with atoms whose spins would be the computer's qubits. No electric currents would flow in this chip: instead spins would nudge each other along, dot to dot, passing along their message according to the dictates of quantum logic.

Quantum computers could be enormously powerful. However, there are some difficulties with exploiting their capacity for massively parallel calculations. The principal obstacles to constructing a practical quantum computer are (1) the difficulty of engineering the quantum states required; (2) the phenomenon of decoherence, which is the propensity for these quantum states to lose their coherence properties through interactions with the environment; and (3) Extracting the results of the massive parallel computations has proved tricky.

There are some interesting formulations to overcome the first obstacle. But the all-important decoherence is hard to beat. It takes enormous care and effort to create quantum states in the lab. Any kind of random disturbance or interaction, such as one bump from a stray air molecule, one twitch in the magnetic field, one ricochet of a random photon, will destroy the exquisitely delicate mix of coexisting quantum states, forcing a single classical state to emerge instead. Maintaining the integrity of a quantum computer would therefore be incredibly hard. A whole array of complex and importantly different states would have to be created, sustained, and made to interact in a prescribed manner.

The final problem is more subtle. Accessing results obtained through quantum parallelism requires measuring the final state of the qubits. Any measurement instrument registers a single result, even though the quantum computer may be storing a superposition, possibly huge, of different values. Nature resolves this paradox by destroying the other values in the superposition whenever a measurement is made, transforming the state from a possibly complex superposition to a simple state consisting of the single value read. Essentially, we can ask one, and only one, question about results generated by quantum parallelism before having to redo the computation. Moreover, the sort of question we can ask is restricted and is a subject of active research. Peter Shor found a single question to ask in attacking the factoring problem, but researchers have found such a situation for only a few problems.

1. Qubit="quantum"+"bit"

Digital information appears mundane stuff. The 0s and 1s of binary code can be easily measured, copied, and moved around. But assign a piece of information to a quantum particle, and it takes on the bizarre characteristics of the quantum world. The fundamental unit of quantum information is called a quantum bit, or qubit. A qubit is exactly what it sounds like: a bit of information represented by a quantum object, such as the spin of an electron, a property that can be imagined as the spin of a top with its axis pointing either up or down. The up or down spin can correspond to a 0 or 1. But the electron can also be placed in a ghostly duel existence, known as a superposition of states, in which it is both up and down, a 0 and a 1, at the same time. That is, any two-state system can represent a qubit. This is the difference between a classical and a quantum computer, which theoretically allows quantum computers to be much more efficient at solving certain types of problems.

2. Orthogonal Quantum States

The examples of photons with vertical ("V") or horizontal ("H") polarization introduce the concept of orthogonal quantum states. A "V" photon will never pass a test for "H" polarization (and vice versa), and so using the language of vectors, we say that "V" and "H" are two orthogonal quantum states of a photon. It is a remarkable property of photons that any other single-photon polarization state can be formed from a suitable linear combination of "V" and "H" states, possibly with complex coefficients. It is said that a single-photon polarization is a two-state quantum system, and that "V" and "H" form a basis for the space of polarizations.

Quantum information processing offers potentially great advantages over classical information processing, both for efficient algorithms and for secure communication. The quantum mechanical superposition principle enables a quantum computer to perform certain computations very much more efficiently than any classical computer. For example, suppose a quantum computer holds two registers: a left register that contains the argument of function; and a right register that will hold the value of the function at the argument of the left register, after computation of the function. Now suppose that the left register is composed of L qubits and we create a quantum circuit (collection of quantum logic operations) that evaluates the function at any one of the argument values, copying its value into the right register. We can equally well replace the function's argument with a superposition of all 2^L values and in one operation evaluate all values of the function (in superposition in the right register). Thus it appears that a quantum computer could perform exponential computational work in one operation, which gives us a hint of the underlying power of the method. However, we should note that this power is not universally useful, because if we were interested in the function's values we would only be able to recover one of the 2^L values per measurement on the right register. So, we would have to repeat the function evaluation and measurement 2^L times to obtain all of the values. But, if we are instead interested in some joint property held by all the function values, such as the function's period, this quantity can be extracted by an additional efficient quantum procedure known as the quantum Fourier transform. Therefore, any problem that can be reduced to finding the period of some function is a candidate for efficient solution by quantum computer. Integer factorization is such a problem.

1. Quantum algorithms and quantum algorithmic complexity

2. Error-correcting codes and fault tolerant computation

3. Entanglement and non-locality

4. Quantum teleportation and distributed computing

5. Quantum communication and channel capacities

6. Quantum cryptography

7. Foundational aspects of quantum computing

8. Experimental realizations of quantum computers and feasibility studies

1. Quantum Cryptography

Quantum cryptography covers several ideas, of which the most firmly established is quantum key distribution. This is an ingenious method in which transmitted quantum states are used to perform a very particular communication task: to establish at two separated locations a pair of identical, but otherwise random, sequence of binary digits, without allowing any third party to learn the sequence. This is very useful because such a random sequence can be used as a cryptographic key to permit secure communication. In sharp contrast to the behavior of an ideal classical system, the state of a quantum system cannot be determined without randomly and irreversibly changing it, even ideally. Thus by sending data using individual quantum systems, such as photons, two people can unambiguously identify the action of any eavesdropper. This establishes the principle of a secure communication channel. Given the progress in quantum physics experiments over the last few years, the practical implementation of such communication channels is now in sight. So there are people researching and evaluating quantum cryptographic protocols and hardware.

2. Quantum Teleportation

The problems in scaling up many of these ideas have persuaded many scientists that if quantum computing is to become useful any time soon, it will have to involve networking small quantum computers together. But sending quantum information from one place to another is tricky. One option is to physically move the qubits, but then they would be liable to decoherence. There came a spark called teleportion.

A typical bizarre property of qubits is immensely useful. Suppose a physical process that emits two photons (packets of light), one to the left and the other to the right, with the two photons having opposite orientations (polarizations) for their oscillating electrical fields. Until detected, the polarization of each of the photons is indeterminate. But at the instant a person could measure the polarization for one photon and the state of the other becomes immediately fixed. This exciting phenomenon allows quantum systems to develop a connection, referred to as entanglement. This effectively serves to wire together the qubits in a quantum computer. This helped some researchers to realize quantum teleportation. Teleportation utilizes the deep link that entanglement sets up between one point in the universe and another. This is being described that entanglement could act as a kind of phone line down which to send quantum information, that is, create an entangled pair of particles and send one of them to the receiver while keeping the other. This process links these two points in a way that allows the

If quantum computers were to become a reality, there would be a need for the faithful transportation of quantum states between machines. Simply measuring a quantum bit and transmitting the result as a classical bit is no good because in general the measurement will irreversibly change the state and information will be lost. However, by utilizing a supply of previously shared entangled quantum systems, the two correspondents can teleport an unknown quantum state from one place to another using only classical bits. Conventional error checking can be applied to these classical data; this fails disastrously if it is applied directly to the quantum state. Michael Nielson on the Los Alamos team made a suggestion of implementing quantum teleportation with liquid state NMR. The scientists there could demonstrate complete quantum teleportation over interatomic distances. Their experiment hints at the real utility of quantum teleportation for reliable transmission of information between the bits of a quantum computer.

It is suggested that teleportation could become the basis of a kind of quantum Internet. It is by sending entangled photons over optical fibers to nodes containing cold atoms that would absorb the photons and so store the entanglement. This entanglement could then be used for error correction, teleportation and various other valuable applications. The research groups concentrating on this hope to have a three-node network running within 10 years. Some scientists even predict greater things from entanglement, believing it will be so useful that it will one day be traded as a currency over the quantum Internet.

Despite the remarkable resilience of present day chip fabrication technologies, constant evolution is a hard reality that marks any technology. Progression is natural and unstoppable. That is because transistors and electrical wiring can not be made slimmer than the width of an atom. Also the fact that information is physical means that the laws of quantum mechanics can be used to process and transmit it in ways that are not possible with the existing computing mechanisms. Further more, fundamental quantum physics experiments have progressed in leaps and bounds over the last few years. The use of quantum physics could revolutionize the way we communicate and process information. The marriage of quantum physics and information technology has the potential to generate radically new applications and corresponding information processing devices. The applications include quantum communication, cryptography and computation and the devices include quantum cryptosystems, which provide guaranteed secure communication and quantum computers, which manipulate data quantum mechanically. In return, these technological considerations lead to a better intuitive understanding of basic issues such as entanglement and the meaning of information on the quantum level. Such advancements in knowledge led to new technologies and applications in the past and surely will do so again - to those who are already there and to those yet undreamed of.

Click here for a review paper titled as Quantum Automata, Languages and Grammar

This article was prepared as a part of the JST's Quantum Computation and Information project.