(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.

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

Quantum Computing and “Transforms”

Introduction
A previous article introduced the concept of the quantum computer. However, unfortunately, the QC lacks that great flexibility of the conventional stored program computer. It seems that a practical QC will be able to perform a relatively fixed, pre-determined class of calculations with lightning speed. For some people this suggests that QCs will have limited usefulness. However, there are many applications that are marginal with current computers that may become very practical should a QC become available.

Recently researchers have developed an algorithm that could be implemented on a QC to process “Fourier Transforms”. The potential offered by a device that could perform generalized transforms (not just Fourier) is immense. The potential makes all other applications recede into the twilight of insignificance. These possible applications of such a processor include:

• Factorization of large numbers
• DSL
• Spread-spectrum radio
• Advanced radar and sonar processing
• Medical imaging
• Visual pattern recognition, speech recognition, language processing

Fourier’s Transform
Fourier’s Theorem says that any repeating waveform (or signal) is composed of (and can be broken down into) a series of pure sine waves where the frequency of each is an integer multiple of the lowest frequency present. That is, you can represent any repeating waveform by a mathematical series of the form:

a Sin (x) + b Sin (2x) + c Sin (3x) + d Sin (4x) +.....

This representation works even for isolated pulses and for segments of apparently “random” signals. All you do is take the section you want to analyse and assume that it repeats infinitely! (After all we don’t know what might happen in the future and it might indeed repeat!)

A Fourier Transform takes an equation representing a repeating waveform and gives you a set of coefficients (a, b, c, d… from the expression above) that represents the amplitude of each Sin wave component of the signal. While this is useful for theoretical analysis, it doesn’t help much in the operational sense. (When you are receiving a radio signal for example, it is somewhat difficult to construct an equation to represent it in real time.)

A Discrete Fourier Transform (DFT) takes a series of digitized signal amplitudes (just the digitized signal) and processes this to give us the coefficients (a, b, c, d.. etc.). That is, it gives us the amount of each sine wave component present in a practical waveform expressed in digital form. It’s exactly the same process as a prism performs on a beam of sunlight. You get a “rainbow” of frequencies as the output. Of course, a prism is an analogue device and a DFT does the job digitally but the result is the same.

The mathematics needs to take account of phase and so it requires integration of a series in complex numbers but the basic principle involved is very simple:


1. First we assume the truth of Fourier’s Theorem (that is, every signal can be expressed as an infinite series of sine waves). This is proven so assuming it to be true is no problem.
2. We know that the integral of Sin(x) over one cycle (from 0 to 2pi) is zero. So the integral of the series must also be zero.
3. We also know that the integral of Sin(x)Sin(y) is also zero, provided that x does not equal y.
4. If x = y we get the integral of Sin2(x) which is definitely not zero!

So you take a segment (set of digital measurements) of a signal, assume that it is a full cycle (0 to 2pi), and multiply it by Sin(x), (x is chosen to represent the frequency we are looking for). Then you integrate it (just add up the results carefully taking note of the sign) over the full period. The answer you get represents the amplitude of the sine wave you are looking for within the source set of measurements. Then you double “x” and repeat the process. Then you replace “x” with “3x” and do it again. Then you keep going until you run out of significance. You now have a sequence of coefficients that represent the amplitudes of all the frequency components of the waveform. (Like a spectrum.)

The amazing thing is that if you repeat the process using the coefficients you have just derived as input (changing a sign or two) you get back the original set of numbers (representing the original waveform) that you started with. This is called an Inverse Discrete Fourier Transform (IDFT). So, if you think of it in theory, you have a set of readings of a signal that varies with time (said to be “in the time domain”). You can change this into a series of frequencies (said to be “in the frequency domain”) using a DFT and back again using an Inverse DFT.

It seems obvious that doing this requires a very large number of arithmetic operations (mainly multiplications). Usually when a DFT is performed on a computer we use an algorithm called an FFT (Fast Fourier Transform). Basically this is just a DFT performed using several short cuts in the math that reduces the amount of processing required.

Thinking about the basic operation (that of correlation of sine waves) above we might perform this as shown below. This device is called a “Standing Acoustic Wave” (SAW) filter and is widely used in consumer electronic devices (such as TV sets).


Figure 1 SAW Filter Principle

You take an input electronic signal and change it into mechanical vibrations on a piece of ceramic. This is done to slow the signal down so we can sample it at different times. Then you take samples at regular intervals along the ceramic and make the samples electronic. Ideally the output of the “taps” gives you a series of copies of your input signal, each one of

them delayed by a fixed amount of time. Each signal is then multiplied (amplified) by a “factor” (the set of factors might represent a full sine wave over one period, for example). The signals are then added up arithmetically (you have to take account of the minus sign here). What you get at the output is a signal that varies in amplitude with the amplitude of the selected sine wave present in the input signal. Thus you have filtered out all the extraneous “noise” and demodulated (recovered the variations in) the signal all in one step. Simple filters of this kind as used in consumer electronics can detect and process a signal from within a band of signals up to one thousand times stronger than the signal being detected. In very high quality, specialist equipment you can recover a signal from amongst “noise” of perhaps a million times stronger.

Now, what if you take a large number of SAW filters and connected them in parallel (that is to the same input). If you set up the multiplication factors in the first SAW filter to represent a particular frequency of sine wave, the factors in the second filter to represent twice this frequency, the third filter three times the frequency and so on then you get a series of outputs that are the coefficients of a Fourier Transform. The important difference is that the output here is continuous.

Then, if you wanted to detect a pulse of a particular shape you could multiply each output by a factor and sum them again and presto you could detect any pulse shape (or pattern) you liked. Of course there are mathematical ways (short cuts) for simplifying this process significantly.

So far we have only considered this process for signals that vary in time. It works just as well for signals that vary in space. That is, if you scan the surface of a picture in a straight line you can recognize variations and perhaps extract meaning. Do it in two dimensions and you are on the first step of a path towards full feature recognition.

Now consider a series of devices similar to SAW filters connected in a “cascade arrangement (the output of one feeding the input of the next). This bears an uncanny resemblance to a neural network. When you look at the human nervous system, the “synapse” (connection between nerves) seems a lot like one of the little amplifiers we used to “multiply by a factor”. The cell itself can clearly sum the inputs from dendrites. The axons act like wires to hook it all together.


Figure 2 Neuron (Schematic)

There are up to 100 billion neurons (nerve cells) in the human brain. The elementary structure is shown in the schematic above. Neurons perform the functions of signal transmission, signal processing and memory. The dendrites receive signals from the axons of other neurons and/or

from sense organs. The axon, which can be very long and which branches off in many directions, can carry signals to many other neurons. Axons from one neuron connect to dendrites of other neurons at the synapse. The synapse acts both as a connecting point and as an amplifier/attenuator of the signal.
From the structure here it is easy to see what is happening:
1. The nervous system is NOT performing Fourier Transforms exactly – but it is performing a very similar transform process albeit in an “analogue” way. The principles have to be much the same.
2. Memory can exist in the form of amplification factors in either synapses or the cells themselves.

Applications for a very fast “Transform Processor”
In practice there are many other types of transform (such as cosine transforms) around that work in much the same way as Fourier. The potential list of applications for a hyper-fast transform processor is almost endless:

“Associative” Memory
When you locate information in a conventional computer memory a binary address is fed through wired logic to activate a particular storage “word” and retrieve it. An “associative memory” is very different. It is accessed by using a “key” rather than an address. Such a memory is really just a table. A list of changeable keys is matched to a set of storage locations. When such a memory is accessed, a “table look-up” is performed on the table of keys and the corresponding memory word is located and read out. The important feature is that such memories are specially wired so that when an access is made each memory key is accessed and compared to the presented access key simultaneously. The result is usually available in a single memory cycle. Small memories of this type are used in most computers today to administer high-speed buffer memories and “virtual memory” systems. However, very high-speed lookup of large databases and tables is critical in many modern database and information storage systems. If a QC could be built to administer memory access for a conventional computer these systems could be significantly improved.

Encryption and security

The encryption schemes that are used today for securing data for transfer over communications links and the Internet rely absolutely on the difficulty of finding the factors of very large numbers. Often the number chosen is the product of only two prime factors. If you can find the factors you can break the code and read the contents of the message. A QC that can perform transforms can also factor large numbers very quickly indeed. The existence of a QC would almost negate all existing encryption algorithms.

Radar and sonar

Today’s military radar and sonar systems use sophisticated transform processing of radar echoes received to analyze the received pulse and to build a useful image. The amount of data to be handled is vast and it must be handled in real time. Specialized conventional computers are available that are designed to do transform processing. These are around 100 times as fast as the best “general purpose” supercomputers around. It is perfectly possible to pay over a million dollars (US) for a processor like this. The more capable transform processing you can perform, the more effective your radar system. Processors of this kind are currently used in advanced terrestrial radar systems, military aircraft, ships and especially submarines.


Medical imaging
Many Medical Imaging systems (ultrasound, CT, MRI) require almost exactly the same kind of processing as sonar or radar. These could be improved by faster transform processing.

ADSL and DMT
When people connect to the Internet using “Broadband” from home over existing telephone wire they are usually using a protocol called ADSL . At the transmission level there are two options for implementation but the most popular is a protocol called DMT. DMT is revolutionary because it actually uses an IDFT to build the signal to be transmitted and a DFT to decode it at the receiver. The processing involved requires around twelve million arithmetic operations per second at the transmitter and the same at the receiver. Here the DFT is used for the actual transmission and reception of a real-time signal not just for the theoretical analysis of it. The principles used in DMT could be used at much higher speeds and in many other contexts, but its usefulness is limited by the availability of suitable transform processing hardware.
Spread spectrum communication - CDMA
Traditionally, when we use radio communication each user tries to minimize the frequency space used. The broadcast spectrum is a shared medium and we need to use it efficiently. Gaps (called “guard bands”) are left between frequencies (channels) to minimize interference between them.

Spread-spectrum communication does just the opposite. Many signals are transmitted in the same band at the same time, “over the top” of one another. You send each signal over a wide “spread” of frequencies rather than in a traditional narrow one. There are a large number of advantages in doing this. In the mobile telephone world a major advantage is that it reduces the effects of reflections and hence reduces the incidence of poor reception. In Code Division Multiple Access (CDMA) you send a digital signal. Each bit is sent as a stream of many bits. For example a single “1” bit might be sent as a unique pattern of perhaps 1000 bits, a “0” as a different pattern. Other users of the same frequency band do the same thing but each uses their own unique bit patterns “orthogonal” (uncorrelated) with those of any other user.

At the receiver, co relational filters are used to recover a single transmission from under the “noise” (signals) of the other users. This principle is in use today in some mobile telephone systems. Our interest here is really in the principle it illustrates. So long as you know the characteristics of a signal you can recover it from underneath a massive amount of “noise”. But what if we applied this principle to computer memory? What if we used analogue storage locations that were able to superimpose multiple different pieces of information on top on one another? You could use co relational filtering to recover the contents.

Pattern Recognition and Neural Networks
The above discussion of “transforms” was intended to show the potential of simulating neural networks using the digital processing of transforms. This offers the potential radical improvement of many existing computer applications and opens the door to a number that are impractical or impossible at the present time.

1. Recognition of faces in crowds
2. Making “sense” out of a photograph
3. Reading handwriting
4. Language translation


Conclusion
From its genesis around 1980 to today the field of quantum computing has developed at unprecedented speed. It seems that quantum computers are indeed possible and may indeed become practical within a few years. If this is true, then the “killer application” will probably be the processing of transforms.