An Introduction To Quantum Computing
A Guide to Solving Intractable Problems Simply

Brad Huntting, University of Colorado
David Mertz, Ph.D., Gnosis Software, Inc.
June 2001
 

In the next few decades, quantum computers are likely to move out of science fiction and elite research labs (largely at IBM), and into practical applications. There is a class of problems surrounding complex combinatorics that are intractable, or at least impractical, on traditional deterministic computers that can be solved efficiently on QCs. By way of practical illustration, this article presents examples from the GPL tool qcl. Using qcl allows developers to simulate and examine a "virtual" quantum computer. Basic elements of using qcl are explained in the course of an introductory explanation of the concepts of quantum computing. An assumption is made that readers have a basic knowledge of the mathematics of vectors.

Alan Turing invented the programable computer in 1936 (see Resources) as a thought experiment to show that certain mathematical problems were not computable. Implicit in his argument was the idea that a computer, armed with sufficiant resources, is capable of realizing any reasonable algorithm.

Since that time, the computer industry has managed, not only to build programable computing machines, but they've managed to outdo themselves by doubling the capabilities every 18 months or so. However despite these frenetic advances in computer technology, modern computers are still unable to make significant dents in hard problems. Problems who's solution requires exponential resources (compared to the size of the problem itself), remain as intractable today as they were in 1936.

In 1982 Richard Feynman sugested that the venerable Turing machine may not be as powerful as people thought. You see, Feynman was trying to simulate the interaction of N particles with quantum mechanics. But try as he might, he was unable to find a general solution without using exponential resources. The problem seemed intractable on modern computing hardware.

Yet somehow, nature is able to "simulate" this mathematical problem using only N particles. The conclusion was inescapable: Nature was capable of building a fundementally superior computing device, and that meant that the Turing machine was not the all purpose computer people had thought.

Visualizing A Quantum Computing Problem

Thinking about QC algorithms involves thinking in terms of probabilistic factors, which is a conceptual change for current programmers. In some ways, this is like the conceptual shift involved in using OOP, or functional programming, or multi-threading, for the first time; but in another sense the shift is more fundamental since it opens up a whole new class of (probably) non-equivalent problems.

Let's imagine a problem: we need to find a path through a complicated maze. Every time we follow one path, we soon come across new branches. Even knowing there is some path out, it is easy to get lost. A well-known "algorithm" for walking a maze is the "right hand rule"--follow the right hand wall until you are out (including around dead-ends). This may not be a very short path, but at least you will not repeat the same corridors. In computer terms, this rule is also known as "recursive tree descent."

Now let's imagine another solution. Stand at the entrance to the maze, and release a sufficient quantity of colored gas to fill every corridor of the maze simultaneously. Have a collaborator stand at the exit. When she sees a whiff of colored gas come out, she simply "asks" those gas particles what path they travelled. The first particle she queries will most likely have travelled the shortest possible path through the maze.

Naturally, gas particles are not entirely wont to tell us about their travels. But QC's act in much the manner of our scenario: fill the whole problem space, then only bother asking for the correct solution (leaving all the dead-ends out of the answer space).

The Qcl Quantum Computer Simulator

Simulating a quantum computer on a traditional clasical computer is a hard problem. The resources required increase exponentially with the amount of quantum memory under simulation to the point that simulating a QC with even a few dozen quantum bits (qubits) is well beyond the capability of any computer made today.

qcl only simulates very small quantum computers, but fortunately, it's just powerful enough to demonstrate the concept behind some useful QC algorithms.

Like the supercomputers of yesteryear, the first QC's of tomorrow will probably consist of some exotic hardware at their core which stores and manipulates the quantum state machine; surrounding this will be the life support hardware that sustains it and presents the user with a reasonable programing environment. qcl simulates such an environment, by providing a clasical program structure with quantum data types and special functions to perform operations on them.

Let's start with some familiar operations from classical computing using qcl. Since qcl is an interactive interpreter with a syntax vaguly similar to C, we can just fire it up and start entering commands into it. To make our examples more readable we'll restrict the number of quantum bits under simulation to 5.

Initializing QCL and dumping a qubit

$ qcl --bits=5 [0/8] 1 |00000> qcl> qureg a[1]; qcl> dump a : SPECTRUM a: |....0> 1 |0>

Here we have allocated a 1 qubit (boolean) variable from the qcl quantum heap. The quantum state of the machine, |00000>, is initialized to all zeros. The |> characters signify that this is a quantum state (sometimes called a "ket"), while the string of 5 0's (one for each bit in the quantum heap) form the label for the state. This is known as the Dirac notation (a.k.a. "bra-ket") for quantum mechanics. Its main advantage over traditional mathmatical notation for linear algebra is that it's much easier to type.

"qureg a[1]" allocates a one bit variable a from the quantum heap. The dump a command gives us some information about a. The SPECTRUM line shows us where the qubits for a have been allocated in the quantum heap; in this case the 0-bit of a is the rightmost qubit in the heap. The next line tells us that, were we to measure a, we would see "0" with probability "1".

Of course the ability to peek at quantum memory is only posible because qcl is a simulator. Real quantum bits cant be observed without irrevocably altering their values. More on this latter.

Many of the primative quantum operators provide by qcl are familiar from clasical computing for example the Not() function flips the value of a bit.

A Boolean function on a qubit

qcl> Not(a); [2/8] 1 |00001>

Not() applied again to the same qubit will undo the effect of the first which is exactly what we would expect from classical computing.

The CNot(x,y) operator tests the value of y and if it is 1, it flips the value of x. This is equivalent to the statement x^=y in C.

Some more qubit operators (CNot)

qcl> qureg b[2]; qcl> Not(b[1]); [3/8] 1 |00100> qcl> CNot(b[0], b[1]); [3/8] 1 |00110> qcl> dump b[0]; : SPECTRUM b[0]: |...0.> 1 |1> qcl> dump b[1]; : SPECTRUM b[1]: |..0..> 1 |1>

The CNot() operator, like the Not() operator is its own inverse; apply it a second time and it reverses the effect of the first leaving you in the same state as when you started.

This idea of reversability is critical for quantum computing. Theoretical physics tells us that every operation on quantum bits (except for measurement) must be undoable. We must always keep enough information to work any operation backwards. This means that operations like assignment (x=y), AND (x&=y), and OR (x|=y)--which we take for granted in clasical computing--have to be modified for use in QC. Fortunately, there's a straightforward formula for converting irreversable classical operations into quantum operations.

First we never overwrite a quantum bit; instead of assignment (x=y) we can do this:

Reversible simulation of Boolean AND

nomadic$ qcl --bits=5 [0/8] 1 |00000> qcl> qureg c[3]; qcl> Not(c[1]); [3/8] 1 |00010> qcl> Not(c[2]); [3/8] 1 |00110> qcl> dump c : SPECTRUM c: |..210> 1 |110> qcl> CNot(c[0], c[1] & c[2]); [3/8] 1 |00111> qcl> dump c : SPECTRUM c: |..210> 1 |111>

The CNot(x, y & z) will flip the value of x if y and z are 1. So if x is initialized to 0 before we start, this is effectively the same thing as calculating y&z and storing the value in x. It's a subtle distinction, but one that is critical for quantum computing.

Now let's look at some operations that have no classical analogues. The most striking, and at the same time one of the most useful, is the Hadamard function which is appropriately labled Mix() by qcl. Mix() takes a computational basis state like |0> or |1> state and turns it into a quantum superposition. Here's a one qubit example:

Superposing states with Mix()

[0/8] 1 |00000> qcl> qureg a[1]; qcl> dump a; : SPECTRUM a: |....0> 1 |0> qcl> Mix(a); [1/8] 0.707107 |00000> + 0.707107 |00001> qcl> dump a; : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1>

Here we have exploited the quantum mechanics principle of superposition. According the dump a, if if we were to measure a, we would see 0 or 1 with equal probability 0.5 (0.707107^2).

If you've never been exposed to this concept of superposition before it can be a little confusing. Quantum mechanics tells us that a small particles, such as electrons, can be in two places at once. Similarly a quantum bit can have two different values at the same time. The key to understanding this all is vector arithmetic.

You see, unlike a clasical computer where the state of the machine is merely a single string of ones and zeros; The state of a QC is a vector with components for every posible string of ones and zeros. To put it another way, the strings of ones and zeros form the basis for a vector space where our machine state lives. We can write down the state of a QC by writing out a sum like so:

The vector state of a quantum computer

a|X> + b|Y> + ...

Where X, Y, etc are strings of ones and zeros, and a, b, etc are the amplitudes for the respective components X, Y, etc. The |X> notation is just the way physicists denote a "vector (or state) called X".

The Mix() operator (Hadamard operator) when applied to a bit in the |0> state will transform the state into sqrt(0.5)(|0>+|1>) as in the example above. But if we apply Mix() to a bit that's in the |1> state we get sqrt(0.5)(|0>-|1>). So if we apply Mix() twice to any qubit (in any state) we get back to where we started. In other words, Mix() is it's own inverse.

If we have two qubits a and b (initialized to zero) and we perform a sequence of quantum operations on a and then do the same to b, we would expect to wind up with a and b having the same value, and we do.

Independent superposed qubits

qcl> qureg a[1]; qcl> Not(a); [1/8] 1 |00001> qcl> Mix(a); [1/8] 0.707107 |00000> + -0.707107 |00001> qcl> qureg b[1]; qcl> Not(b); [2/8] 0.707107 |00010> + -0.707107 |00011> qcl> Mix(b); [2/8] 0.5 |00000> + -0.5 |00010> + -0.5 |00001> + 0.5 |00011> qcl> dump a : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1> qcl> dump b : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

In this example, a and b are completely independent. So if we measure one it should have no effect on the other

Measurement independent qubits

qcl> measure a; [2/8] -0.707107 |00001> + 0.707107 |00011> qcl> dump b : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

As expected, the spectrum of b was unchnaged by measuring a.

If the operations were more complicated than a simple Not();Mix(), we might be tempted to perform them only once on a and then copy the value from a to b. Ok, we can't really copy (because it's not a reversable operation), but we can initialize b to zero and CNot(b,a) which accomplishes the same goal.

Alas, this doesn't do what we would expect. Let's just try it and see:

Attempting a qubit-copy operation

qcl> qureg a[1]; qcl> Not(a); [1/8] 1 |00001> qcl> Mix(a); [1/8] 0.707107 |00000> + -0.707107 |00001> qcl> qureg b[1]; qcl> CNot(b,a); [2/8] 0.707107 |00000> + -0.707107 |00011> qcl> dump a; : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1> qcl> dump b; : SPECTRUM b: |...0.> 0.5 |0> + 0.5 |1>

The spectrum of a and b look correct. And indeed if we were to measure just a or b we would get the same result as above. The difference lies in what happens when we measure both a and b.

qcl has a built-in operator for measuring qubits, so let's use it. Now keep in mind, the outcome of a measurement is random, so if you're repeating this experiment, your mileage may vary.

Measurement collapsing qubit superposition

qcl> measure a; [2/8] -1 |00011> qcl> dump b : SPECTRUM b: |...0.> 1 |1>

By measuring a, we have collapsed the superposition of b. This is because a and b were "entangled" in what physicists call an "EPR pair" after Einstein, Podensky, and Rosen who used this in an attempt to show that quantum mechanics was an incomplete theory. John Bell, however later demonstrated entanglement in real particles by experimental refutation of the "Bell Inequality" (which formalized the EPR thought experiment).

What happens when you try to copy one quantum variable onto another is that you wind up with is entanglement rather than a real copy.

Deutches Problem

Suppose we are given a function that takes a one bit argument and returns one bit. And to keep things on the up and up, let's require that this be a pseudo-clasical function; which means that if we hand it a clasical bit (0 or 1) as an argument, it will return a classical bit.

There are exactly 4 posible functions that fit this requirements.

All four possible Boolean unary functions

f(x) -> 0             # constant zero result f(x) -> 1             # constant one result f(x) -> x             # identity function f(x) -> ~x            # boolean negation

The first two of the above functions are "constant", meaning it outputs the same value regardless of it's input. The second two are "balanced" meaning the output is 0 half the time and 1 half the time. Classically there's no way to determine if f() is constant or balanced without evaluating the function twice.

Deutches problem asks us to determine wheather f() is constant or balanced by evaluating f() only once. Here's how it works.

First, we have to construct a pseudo-classic operator in qcl that evalutes f(x). To do this we'll define a qufunct with arguments for input and output. For example:

Defining a quantum function in qcl

qufunct F(qureg out, quconst in) {     CNot(out, in);     Not(out); }

If "out" is initialized to 0, calling this function will change out to f(x)=~x. You can comment out either the CNot() or Not() lines to get one of the other 3 posible functions. After we put the above code snipit in a file called f_def.qcl we can test F() to make sure it does what we want:

Interactively importing and testing F()

qcl> include "f_def.qcl"; qcl> qureg in[1]; qcl> qureg out[1]; qcl> F(out,in); : f(x)= ~x [2/8] 1 |00010> qcl> dump out; : SPECTRUM out: |...0.> 1 |1> qcl> reset [2/8] 1 |00000> qcl> Not(in); [2/8] 1 |00001> qcl> dump in : SPECTRUM in: |....0> 1 |1> qcl> F(out,in); : f(x)= ~x [2/8] 1 |00001> qcl> dump out : SPECTRUM out: |...0.> 1 |0>

Now let's reset the quantum memory, and run Deutches algorithm. It works by first putting the in and out bits into a superposition of 4 basis states.

Deutches algorithm (line numbers added)

(01)  qcl> reset; (02)  qcl> int result; (03)  qcl> Not(out); (04)  [2/8] 1 |00010> (05)  qcl> Mix(out); (06)  [2/8] 0.707107 |00000> + -0.707107 |00010> (07)  qcl> Mix(in); (08)  [2/8] 0.5 |00000> + 0.5 |00001> + -0.5 |00010> + -0.5 |00011> (09)  qcl> F(out,in); (10)  : f(x)= ~x (11)  [2/8] 0.5 |00010> + 0.5 |00001> + -0.5 |00000> + -0.5 |00011> (12)  qcl> Mix(in); (13)  [2/8] 0.707107 |00011> + -0.707107 |00001> (14)  qcl> Mix(out); (15)  [2/8] -1 |00011> (16)  qcl> measure in, result; (17)  [2/8] -1 |00011> (18)  qcl> if (result == 0) { print "constant"; } else { print "balanced"; } (19)  : balanced

With lines 1-7 we put the in/out bits into a superposition of 4 base states with positive amplitudes +0.5 for states where out=0 and negative amplitudes -0.5 where out=1. Note that even though we have 4 non zero amplitudes, the sum of the squares of the absolute values of the amplitudes always adds up to 1.

At line 9 we run the quantum function F() which XORs the value of f(in) into the out qubit. The function F() is pseudo-classical, meaning it swaps basis vectors around without out changing any amplitudes. So after applying F() we still have two amplitudes with value +0.5 and two with the value -0.5.

By applying the F() function to a superposition state, we have effectively applied F() to all four basis states in one fell swoop. This is what's called "quantum parallelism" and it's a key element of QC. Our simulator will, of course, have to apply F() to each of the basis states in turn, but a real QC would apply F() to the combined state as a single operation.

The Mix() functions at lines 14 and 16 flip the machine state out of a superposition and back into a computational base state (|00011>). If we had not run F() at line 9, this would have brought us back to the state we had at line 4 (this is because Mix() is its own inverse). But because we swapped amplitudes with F(), undoing the superposition puts us into a different state than where we were at line 9. Specifically the in qubit is now set to 1 rather than 0.

It's also instructive to note that the ampitude of -1 in line 15 is unimportant. A quantum state is a vector who's overall length is of no interest to us (as long as it's not zero). Only the direction of the vector, that is the ratios between the component amplitudes, are important. So, by keeping quantum states as unit vectors, the transformations are all unitary. Not only does this make the theoretical math alot easier, it keeps the errors incurred doing numerical calculations on classical computers from snowballing out of control.

Controlled Phase Transformation

The original goal of quantum computing was to simulate the behaviour of arbitrary quantum systems using a small set of basic components. So far we have discussed the Not(), CNot() and Mix() functions. To round out the set and allow for universal quantum computation, we need the Controlled Phase function, CPhase().

CPhase() takes a (clasical) floating point number as its first argument and a qubit as it's second argument. CPhase(a,x) alters the component amplitudes of the base states of the machine as follows: The amplitudes for base states where x is |0> are unchanged, while the amplitudes for base states where x is |1> are multiplied by exp(i*a)=cos(a)+i*sin(a). In other words, the coefficiants for the machine states where x=1 are rotated in the complex plain by a-radians. For example:

Demonstrating the CPhase() Function

$ qcl --bits=5 [0/5] 1 |00000> qcl> qureg a[1]; qcl> Mix(a); [1/5] 0.707107 |00000> + 0.707107 |00001> qcl> CPhase(3.14159265, a); [1/5] 0.707107 |00000> + -0.707107 |00001> qcl> reset [1/5] 1 |00000> qcl> Mix(a); [1/5] 0.707107 |00000> + 0.707107 |00001> qcl> CPhase(0.01, a); [1/5] 0.707107 |00000> + (0.707071,0.00707095) |00001> qcl> dump a : SPECTRUM a: |....0> 0.5 |0> + 0.5 |1>

Since exp(i*pi)=-1, CPhase(pi,x) will flip the sign of the |1> component. CPhase(0.01, x) rotates the phase of the |1> component by one one hundredth of a radian in the complex plane. The parenthasized tuple (0.707071,0.00707095) is the 'qcl representation of the complex number exp(0.01*i)=0.707071+i*0.00707095.

Bigger Problems And Solutions

Deutches problem and it's N-bit generalization, the Deutch-Jhosa problem may be interesting, but they don't have much practical value. Fortunately, there are other quantum algorithms that promise bigger payoffs.

Shor's algorithm, for example, is able to find the period of a function of N bits in polynomial time. While this doesn't sound like a big deal, the difficulty of factoring and finding a discrete logarithm, form the basis of most if not all public-key cryptography systems.

Less spectacular, but much easier to implement is Grover's algorithm which searches an unordered list of N items in O(sqrt(N)) time. The best clasical algorithm takes, on average N/2 iterations to search such a list.

Conclusions

One of the tasks of clasical computers since their inception as been to simulate electrical circuits to help design faster computers. This feedback loop has helped fuel half a century of explosive growth in the computer industry. Quantum Computing has the potential to shift this explosive growth into an even higher gear as QC's are used in the creation of faster and more powerful quantum computing elements.

In Aug 2000, Isaac L. Chuang of the IBM Almaden Research Center announced that he and his collaborators had constructed a 5 qubit machine using a molecule with 5 Fl atoms (see Resources). Unfortunatly this technology probably wont scale up to a usable size.

So when will the first scaleable quantum computer be built? There are several candidate technologies for storing, manipulating and moving qubits. A complete list is beyond the scope of this article, but it's probably safe to say that the first usefull QC is probably still one or two decades away.

Resources

QCL, the "programming language for quantum computers," discussed throughout this article, may be downloaded from:

http://tph.tuwien.ac.at/~oemer/qcl.html

http://www.abelard.org/turpap2/tp2-ie.asp

http://www.squint.org/qci/

http://www-brims.hpl.hp.com/websems/quantum/home.html.

A discussion of the 5 qubit machine built by IBM Almaden Research Center can be found at: Vandersypen, L.M.K., et al. Preprint. "Experimental realization of order-finding with a quantum computer." Available online at:

http://xxx.lanl.gov/abs/quant-ph/0007017

Brad Huntting WORDS HERE... He may be reached at [email protected].

David Mertz believes that God had really better check Himself into Gamblers Anonymous. David may be reached at [email protected]; his life pored over at http://gnosis.cx/publish/. Suggestions and recommendations on this, past, or future, columns are welcomed.