**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 toolqcl. Usingqclallows developers to simulate and examine a "virtual" quantum computer. Basic elements of usingqclare 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> |

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()` 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> |

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

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

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

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

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

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

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

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

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

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.htmlA.M.Turing. "On Computable Numbers, with an Application to the Entscheidungsproblem",

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

http://www.squint.org/qci/If you have a Real Audio plugin for your web browser, there is an excelent series of "WebSeminars" at:

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 huntting@glarp.com.

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