by Larry Ketchersid

The interest and occasional media frenzy over quantum computing is partially due to the widespread interest in some of the more malleable characteristics of quantum mechanics itself. Theorems such as the Many Worlds Theory and the Heisenberg Uncertainty Principle get translated into the popular press into works like The Secret (e.g., The Law of Attraction, the power of positive thought and visualization), currently number one on many bestseller lists. And then science fiction writers, further fictionalize quantum mechanics and quantum computing, making many impossible actions sound possible.

Despite its sexy press image, quantum computing, as currently seen, will probably only be good for certain types of problems such as factoring and searching - problems that have a particular mathematical structure suited to how quantum computers work. These theories are still being proven out in academia and labs.

That said, D-Wave Systems, Inc. of British Columbia has announced the creation of a 16-qubit quantum computer. What this event means is being debated and discussed in quantum mechanical papers and blogs. (For continued discussion, education and insights into many quantum mechanical topics see the Founder and CTO of D-Wave Systems, Dr. Geordie Rose's blog and Dr. Scott Aaronson's blog, Shtetl Optimized.

A little computer history

When ENIAC, the first large-scale reprogrammable digital computer was launched in 1946, computer operations and programming were quite different than today. ENIAC had more than 17,000 vacuum tubes and a main operations task was determining when one of these failed and replacing it. For programming it used an IBM Card Reader (for those of you too young to remember, yes, we used to punch holes in cards with programming instructions on them and feed them into a card reader). Will quantum computing require miniature physicists to run around and change the photon emitters (shedding better light on the subject)? Probably not. But it most certainly will require a new level of abstraction for a new generation of quantum programmers and computer administrators.

The advent of classical computing brought the languages of classical physics (electricity and magnetism) and married it into a new group of people later called computer scientists. Like most technologies, classic computers like ENIAC started out under the purview of engineers and moved to a shared services environment (where companies could buy time on the computer). With the help of a common simplified language and operational contexts, classical computing moved from the scientific/government realm to usage by large enterprises, until it reached what could be deemed general availability for both content (data and program) creators and content consumers.

The beginning of the simplified language for classical computing was the definition of the bit, the smallest of information representation. The bit was a language of abstraction, a representation of electrical and/or magnetic physical properties. The bit was zero when voltage was off and one when voltage was applied. Bits can be used to represent data or commands. To produce commands, voltages were combined in different ways called gates (AND, OR, NAND and COPY making up the complete classical set). These were physical representations (i.e., combinations of voltages) of logic command structures to combine bits in different ways.

As programming moved up this evolutionary chain, not only were certain items on lower foundation layers abstracted, but new languages of representation were created. Today it is safe to assume that a Java programmer using an object oriented program does not concern himself with how the bits are flipped.

The advent of quantum computing is – so far – following much the same course as classical computing. Soon we will have a new generation of engineers and programmers called quantum computer scientists.

The current Quantum Information Science and Technology Roadmap from ARDA (Advanced Research and Development Activity) suggests that quantum computing is still far from a shared services environment, aiming to have an experimental 50 qubit quantum computer by 2012 (Click here for the roadmap).

We can assume that quantum computing will follow a similar path of abstraction, specifically so that the massive numbers of existing programmers can ply their wares in the relatively new world (pun intended) of quantum computing. However the current language of quantum mechanics is complex mathematics, which will obviously not be the lingua franca used by most programmers. Some of these layers of abstraction have already been created or proposed, but there is yet no common language to move quantum computation into mainstream computing.

So just what is a qubit?

Dr. Chris Fuchs notes in his excellent paper "Quantum Mechanics as Quantum Information" that as far as quantum computing is concerned, "The task is not to make sense of the quantum axioms by heaping more structure, more definitions, more science-fiction imagery on top of them, but to throw them away wholesale and start afresh. We should be relentless in asking ourselves: From what deep physical principles might we derive this exquisite mathematical structure? Those principles should be crisp; they should be compelling. They should stir the soul."

Unfortunately the nature of quantum physics is that it is elegant but counter-intuitive and thus hard to understand. Explaining how to apply quantum mechanics to computer applications is equally, if not more arduous. Fuchs may advise, "Until we can explain quantum theory's essence to a junior-high-school or high-school student and have them walk away with a deep, lasting memory, we will have not understood a thing about the quantum foundations." But this is easier said than done. In other words, hold onto your hats for the next few paragraphs as we delve into the strange world of quantum computing and the qubit.

Unlike computers today which use bits, binary representations of data such as "0/1", ("yes/no"), quantum computers use quantum bits, or qubits. A qubit is represented as a quantum object's nuclear spin (rotation). Similar to a bit, a qubit can represent a 1 or a 0 (spin "up," spin "down"); and the values of "spin" correspond to waves. A qubit can also represent a combination of the waves, a superposition of 1 and 0. Superposition is a strange quantum mechanical "state" that permits particles to be in multiple places simultaneously. Bizarre as it sounds, aggregates as large as molecules have been recorded in laboratories as residing in multiple locations simultaneously. In a computer application, superposition is a quantum characteristic concerning the addition of the amplitudes of waveforms (state vectors).

In classical computing, bits have definite values. In quantum computing, qubits contain superpositions of all of the possible classic values. In other words, due to the nature of quantum mechanics, a quantum register of qubits describes a wave function containing the probabilities of each possible classic state. Three main characteristics of a qubit register will impact how future abstractions are explained to future programmers: (1) a quantum register can encode a number of classical bit states that grows exponentially with the number of qubits in the register; (2) quantum computations are probabilistic; after being acted upon by gates and algorithms, what will be read from the qubit register is the probability of a particular answer; and (3) the act of quantum measurement destroys the stored state; no classic structured "IF THEN ELSE" logic allowed.

Theoretically, the ability of a qubit or quantum register to hold all possible outcomes implies quantum parallelism. But quantum parallelism is only applicable to certain types of problems, not all. Factoring is one of the types of problems quantum computation may be good for.

While bits are physically represented by changes in magnetism or voltage, qubits are of course represented by quantum particles. Photons, electrons, quantum dots and the current flow across weakly coupled superconductors (Josephson Junctions) are a few of the quantum materials tried as qubits. With the definition of qubits, gates and algorithms are needed to act on qubits and quantum registers to move up the layers of abstraction.

In classical computing, gates transform bits, either one bit at a time or combined together. Gates can be used alone, or combined in series or parallel. This is formed from the basis of Boolean Logic, providing a common and somewhat easy to understand abstraction language. George Boole showed more than 150 years ago that any logical expression can be built from AND, OR, NOT and COPY gates.

In quantum computing, quantum gate logic runs smack into the problem of observation. In quantum mechanics, measurement disturbs the system being measured. If you run qubit or quantum registers through a quantum gate, and you observe the answer too soon, what is observed will be random. The simplest gate is a "bit flipper," hitting a photon-based qubit with a beam of light as an example (see, miniature physicists changing light bulbs!). But, with the above mentioned observation problem, the quantum logic circuit must not measure for the answer "too soon" or it will impact the result. This is the quantum measurement problem, and brings us to the problem of "destructive interference".

"A quantum computer can in some sense do exponentially many calculations in parallel," says Dr. Aaronson. "The trouble is that, when you measure the computer, you get a 'random' outcome -- not the particular outcome you want. Therefore, all quantum speedups must be based on 'destructive interference' between positive and negative amplitudes -- the one thing about quantum mechanics that makes it genuinely different from ordinary randomness. This is really the key point about quantum computing. Destructive interference means that, among all the different 'computational paths' you have to sum over to calculate an amplitude for some measurement result, some can have positive phase and others have negative phase, so that on the whole they cancel each other out. If so, then the final amplitude for that measurement outcome will be close to zero -- so when we perform a measurement, we'll see that outcome only with negligible probability.

The goal in quantum computing is to create destructive interference among the various computational paths leading to wrong answers, so that those answers are not observed with high probability. By contrast, the computational paths leading to right answers should mostly have the same phase -- thereby creating 'constructive' interference, hence 'large' amplitudes, hence 'high' probability of observing those answers."

Quantum algorithms have appeared on the scene only in the last decade or so, but because of the particular circumstances of the mathematics involved there are very few of them. These algorithms are based on probability; in other words, they will give the correct answer with high probability and repeated running of the algorithm will increase the probability of obtaining a correct answer. Two of the most visible are Shor's algorithm for using quantum logic to factorize integers (again, a problem quantum computers are uniquely equipped to solve) and Grover's algorithm for searching an unsorted database.

Algorithms return us to the basic assumption that, in order to enter mainstream computer science (vs. research) a quantum computer must be shown to do useful work, i.e., work that a classic computer cannot do or work in a much shorter period of time than a classic computer. Factoring, as mentioned in the opening paragraph, is a prime target for quantum computation, and has potential commercial usage in cryptography. RSA, one of the largest cryptography companies, has issued the RSA factoring challenge offering prizes for the factoring of very large numbers. The most recent successful factoring was 193 decimal digits long. By contrast, using the above mention Shor's algorithm, recent experiments have been conducted using quantum computation that factor the numbers 15 and 21, two decimal digits long. While these experiments do represent major milestones in the ongoing research of quantum computing, they do demonstrate a huge disparity between the work products of current classical computers vs. quantum computers.

Finally, quantum computing programming languages, based on these foundational aspects of qubits, quantum gates and quantum algorithms are beginning to be proposed and developed, but are still quite a ways away from being usable by computer scientists at large. For an excellent survey of these, see this paper by Dr. Simon Gay of the University of Glasgow

Larry Ketchersid is an entrepreneurial technologist and currently the CEO of Media Sourcery, Inc., a security software company. He is a martial artist, rugby player, writer, and family man. His first novel is Dusk Before the Dawn.