(full article with pictures can be found on www.nice-ventures.com)

Quantum Computing – Impossible Dream or Coming Boom?

Introduction
To most people the term “Quantum Computer” quite reasonably suggests an ultra-small, ultra-fast device that uses single electrons to carry out its logic operations. Indeed, back in the early 1980’s this is about where the idea started. Today, the concept has evolved to mean something that can be quite different. The basic idea is to use not the presence or absence of a single electron to designate the digital state or “1” or “0” but rather the quantum state of that electron (or photon, or proton) to do this. But quantum states are “weird”, and their unique “weird” behaviour offers a potential for computers of undreamed power and capability.
Background
Ever since the advent of the digital computer in the 1940’s, computer circuit speed has been increasing by around 40% per year. Combined with this, the size of components (logic circuits) has been reducing at much the same rate. Today, we can build a conventional logic gate on a silicon chip using a surface area 0.1 micron (point one of a micron) square. Chips of about 2 cm by 3 cm can contain up to about 100 million logic gates. And “Moore’s Law” (the “law” that says this rate of progress should continue) seems inexorable. Industry people have the next five years improvements mapped out, scientists perhaps the next ten. But ever since Gordon Moore first stated his “law” in 1971 there have been many people who said: “yes, this progress will continue for the next two or three years but after that progress will come to a halt because…” And yet progress continues.

In today’s world the best conventional computer logic elements use groups (pulses) of a few thousand electrons to represent a “1” logic state. As circuits become smaller and faster we use fewer and fewer electrons to perform a basic logic operation. In the world of very high speed optical communications we can do a lot better. Systems that register a “one” bit (at the receiver) using a pulse consisting of as few as 20 photons are commercially available . While there are many, many barriers to the ultimate miniaturisation of using just a single electron in a logic circuit, it would take a very brave person to say unequivocally that “it can’t be done”. The industry has a long history of proving such people wrong.

The Basic Concept
The idea of a “Quantum Computer” started life in the early 1980’s as something like the “single-electron” computer discussed above. However, today it has come to mean something quite different. In a classical computer the states of “1” or “0” are represented by the presence or absence of a group (pulse) of electrons. In a quantum computer “1” or “0” is may be represented not by presence or absence but by the quantum state of a single electron (or perhaps even a group of electrons). On first thought this doesn’t seem to have a lot of advantage. After all, light travels at the same speed in the subatomic world as it does in the classical world. If we just mimic classical computers using quantum processes it would seem that there is not a lot to gain. However, the idea goes much further than this. The concept is to use the unique (perhaps bizarre) features of quantum behaviour to create a new, very different type of computer which may perform some tasks many millions of times faster than classical computing could ever achieve.

In principle there are a number of potential particles and quantum states you could use to represent a bit:

Electron orbits:
When an electron is bound within a single atom or molecule it can take only a finite, limited, number of energy states. To change state, it must acquire or give up a fixed amount (or quantum) of energy.

Some years ago, many suburban electric trains had manually operated doors which were often left open for ventilation. Sometimes you found yourself unintentionally on a train that did not stop at your station. For many schoolchildren the challenge then was to see if you could jump off the moving train without getting killed or injured. There are only two energy states open to you: moving or stopped. To get off the train you have to give up a lot of energy very quickly. Hopefully not into a post! An electron has just the same “all or nothing” problem when it goes to change orbital positions.

Within a molecule, electrons have many possible available energy states but in switching between them the electron has to acquire or give up a quantum of energy. Often you can “promote” an electron from a lower energy state to a higher one by forcing it to interact with a photon of the right energy. When it “decays” to a lower energy state it will often give up its energy also in the form of a photon. Potentially we could use these energy states as switches and the quantum of energy that must be acquired or lost as the means of either switching or detecting the switch operation.

Electron or Proton “Spin”
Electrons are always spinning around their own axis. Although at any moment the axis can be aligned in any imaginable direction, when we go to detect “spin” there are only two states possible: Spin “UP” and Spin “DOWN”.

Polarisation of Photons
Optical polarisation offers us two orthogonal states which could be used to represent “1” or “0”.

Qubits
Without the slightest idea of how a quantum computer might be implemented in practice, many theoreticians have gone ahead anyway to develop a theory for QC and to explore the potential capabilities of such a device.

A key concept is that of the Qubit (Quantum Bit). A qubit is any subatomic particle situated in such a way that there are two quantum states available to represent “1” and “0”. Theoreticians then went on to describe kinds of logic gate that could be used with qubits. Several workable designs have emerged.

Superposition
The whole key to the excitement surrounding the concept of the Quantum Computer is the concept of “Superposition” and what it might mean for the computation process. The effect that we want to exploit here is that you can put a qubit into a state where it is half-way between 1 and 0. This does not mean point five. When you go to discover the state you get either 1 or 0. You can’t detect any state between 1 and 0. If you repeat the operation many times you will get a 1state 50% of the time and a 0 state 50% of the time. In a very real sense the qubit is in both the 1 state and the zero state simultaneously!

What then if we construct a 4-qubit register and set all 4 qubits into this state of both 1 and 0. The register would then represent all numbers from 0 to 15 (0000 to 1111). If you then did a calculation with this register, the result you would get would be another register containing a superposition of calculation results as though the calculation had been performed 16 times and the results superimposed on one another in the result register. This starts to get exciting when you realize that if you have a 32-bit register the number of different calculations performed and results obtained is something over four trillion (4 x 109)!

The problem is how to read out the results. You get a lot of potential results in a “register”. When you read one result the other results disappear. In addition, you have no way of working out which input created the particular result you are looking at. On the surface this does not appear very promising. However, many problems don’t require multiple answers or even sometimes direct answers at all. Is this number prime? Answer yes or no. I don’t need to know the results of all the attempted divisions that were performed in order to find the answer to the question. I just need to know enough to have confidence in the result. What are the divisors of this number? Again I only need a very few numbers as answers. I don’t need to know about the numbers that are not divisors.

Entanglement
Two qubits are said to be entangled if the measurement of one is strongly correlated with the result of a measurement of the other. This gives rise to difficulties. For example, when you send two entangled photons along different paths, doing something to one of them appears to affect the measurement of the state of the other instantly – i.e. faster than the speed of light! Entangled states are routinely created and experimented with in the laboratory. Careful use of entangled states can enable us to relate a particular result to the inputs that created it.

Interference
Interference is a wavelike phenomena but it can be used to allow multiple results to be extracted without “collapsing” the superposition of results.

Power Consumption
As each new generation of computer logic circuitry arrives a single logic gate inevitably takes less power than the generation before. But then, we use more circuits on a single chip and we run the chip faster. The dominant computer technology today is “CMOS”. In the steady state, CMOS (theoretically) does not consume any power but when any logic state is changed power is consumed. So power consumption in the CMOS world is linear with circuit speed. Of course, when power is consumed heat is generated. Getting rid of this heat is one of the significant challenges for current system designers.

It has been proven in theory that a quantum computer could operate using no power at all! Understanding this is a challenge to most of us. The key is that the calculation performed needs to be “reversible”. Quantum operations are inherently reversible, so with careful design it might be possible to build a device that could need a few orders of magnitude less power than a comparable conventional computer.

A Practical Quantum Computer
There are many possible schemes for building a quantum computer and some of them are being actively and successfully experimented with.

• Operation on a single atom, molecule or ion while it is trapped in a magnetic field. Operations can be performed with lasers to change the state of selected electrons. In a particular single molecule you could perhaps have many qubits in different orbits.
• Nuclear magnetic resonance techniques have been used to address, modify and detect changes in states of protons in a nucleus.
• Photons look promising as a medium for qubits and in fact people have developed and demonstrated quantum encryption systems that have many of the characteristics of quantum computers. However, it is quite difficult to synchronize individual photons in such a way that enables them to interact with one another with any reliability.
• Of course, mechanically you can manipulate individual atoms today using a modification of the scanning electron microscope, although there seem to be no reports of this being used for QC yet.
• The great dream is to be able to build a molecular structure where each element is able through its inherent structure to perform QC operations. This could perhaps be done using techniques similar to those currently used to build very pure semiconductors. Another way might be to build a molecule a bit like DNA that had an ability to perform calculations but could also reproduce itself biologically.

The last two techniques on the above list seem at the present time to be dreams. However, the first two techniques have been made to work to the extent of performing logic operations on qubits in a laboratory situation. Very rapid progress has been made in the last five years and in the next five we may well see the first very limited prototype. If we do it is likely to have the following characteristics.

• It will not be a general purpose stored program computer that in any way resembles traditional computers.
• It seems likely that it will be a QC “module” that will be operated and controlled from outside by a conventional computer.
• The QC module will be able to perform a fixed type of mathematical operations many thousands or millions of times faster than any conventional computer.

When you think about it, this is what we need: Something to handle the seriously computation-intensive tasks while a regular computer does what it does best. In the meantime it might be a good idea to start thinking about new cryptographic regime that doesn’t yield to “brute force” attack or prime number factorization.

Potential Applications
It seems that a practical QC will be able to perform a relatively fixed, pre-determined class of calculations with lightning speed. There are plenty of applications that can benefit:

Encryption and Security
Most existing data security is based on encryption of data using one or other scrambling algorithm and a secret key. Both communicating parties need to know the key in order to communicate. But this kind of security can be broken by “brute force”. All you have to do is try every key combination exhaustively and you are bound to find the right key. This of course assumes that you know the form of the data you are looking for, because you need to be able to recognise the moment when you have found the key you want. The Data Encryption Standard (DES) algorithm has been broken by this method by students using “programmable hardware” (gate array) technology in a few hours. To combat this users try to change keys relatively frequently (in cash dispenser systems, every 15 minutes or so). But the new keys have to be exchanged and this is done also using DES under the control of a master key. Users respond by adopting versions of DES using longer keys.

Another method of encryption involves using the so-called “Public Key Encryption” system. Basically you distribute a key that people can use to send you data. They encrypt using that key and you are the only person that can decrypt the data. In principle everyone could have their own unique pair of keys – the public one which everyone knows and the secret one which is the only one that can be used to decrypt the data. This is a great idea. The problem is that decrypting the data is very computer intensive and so it is really unsuitable for large volume data transmission. But it is excellent as a means of exchanging keys for a secret-key system like DES. The exposure of public-key systems is that your public key (the one that people use to send information to you) is usually a very large (perhaps 150 decimal digit) product of two (unknown) prime numbers. Anyone finding the prime factors can decode your secret information. However, finding the factors of a number as large as 150 digits using a current supercomputer could take a time comparable with the age of the universe. But a QC might well factor such a number in a few minutes! The very existence of a QC would put practically every data transmission system on earth at risk. Of course there are many government agencies which would love to own such a device (especially if nobody else had one…).

The “Travelling Salesman” Problem
A salesman has to visit all the 50 state capitals in America. Assuming that there is a direct air service between each pair of cities, calculate the shortest route someone could take between all cities. Sounds easy, just explore every route using a computer. Unfortunately, while the programming is easy you would probably have to wait a few thousand years for your result. The number of routes you have to calculate is factorial 50. That is: 50 x 49 x 48 x 47…. x 1 – divided by two! This is a very, very large number.

Of course, in the real world there is only a small finite set of possible routes and we can reduce the size of the problem significantly by intelligent segmentation of the problem.
The challenge is that there are lots of problems around that are very similar to this one, and they grow at a hyper-exponential rate, rapidly becoming unsolvable. In the Internet the routers dynamically and continuously calculate the best routes on which to send data. They use a hierarchical structure and searches are truncated, but as the Internet grows this will become a much larger problem.

Computational Chemistry and Physics
In recent years the understanding of subatomic particles and interactions has improved to such a degree that you can simulate basic chemical reactions very accurately in a computer. In physics, you can do basic simulations of nuclear structure. But in both of these disciplines the amount of computation required grows very rapidly with the size of the problem being studied. We are told that chemists today are very pleased to be able to simulate molecules of 5 atoms. An increase to 6 will require waiting several years for a new generation of supercomputers.
Nuclear “codes” are detailed simulations of the operation of nuclear reactors or nuclear weapons. This is one of the earliest applications of computers and goes back to the 1950’s. In today’s world with a nuclear test ban treaty in place you can’t test bombs anymore, so to develop new ones you have to simulate them. The problem here , just as in computational chemistry and physics, is that the complexity of the simulation, and hence the run time needed, grows hyper-exponentially with the size of the entity being simulated.

Transform Processing
Recently researchers have developed an algorithm that could be implemented on a QC to process “Fourier Transforms”. The potential here makes all other applications recede into the twilight of insignificance. This will be more fully described in a future article. Possible applications include:

• DSL
• Spread Spectrum Radio
• Advanced Radar and Sonar processing
• Medical Imaging
• Visual Pattern Recognition, speech recognition, language processing


Conclusion
From its genesis around 1980 to today the field of Quantum Computing has developed at unprecedented speed. At first many people (even/especially physicists) saw it as at best an impossible dream at worst a silly joke. Today it is no joke. There are some very small practical experiments being performed. Theoretical work has confirmed that the principles are sound and that such a device “should” be possible.

It should not be a surprise if we see the first very limited and expensive but useful devices arrive within the next five years or so.