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