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. INTRODUCTION TO COMPUTABILITY AND TRACTABILITY ------------------------------------------------------------------------ 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 fundamentally 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 classical 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 classical 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 vaguely 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 possible because 'qcl' is a simulator. Real quantum bits cant be observed without irrevocably altering their values. More on this later. Many of the primative quantum operators provide by 'qcl' are familiar from classical 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 classical computing--have to be modified for use in QC. Fortunately, there's a straightforward formula for converting irreversible 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 classical 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 possible 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 reversible 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-classical function; which means that if we hand it a classical bit (0 or 1) as an argument, it will return a classical bit. There are exactly 4 possible 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 possible functions. After we put the above code snippet 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 whose 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 a lot 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 (classical) 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 classical algorithm takes, on average N/2 iterations to search such a list. CONCLUSIONS ------------------------------------------------------------------------ One of the tasks of classical 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). Unfortunately this technology probably won't scale up to a usable size. So when will the first scalable 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 A.M.Turing. "On Computable Numbers, with an Application to the Entscheidungsproblem", _Proceedings of London Mathematics Society_ 2, 42:230, 1936. A reprint can be read at: http://www.abelard.org/turpap2/tp2-ie.asp (was http://www.abelard.org/essaie/tp2-ie.asp) _Quantum Computation and Information_ by Michael A. Nielsen (Cal Tech) and Isaac L. Chuang (IBM Almadan) is hands down the best text book on on quantum information theory to date. It includes an excellent introduction to QM and CS as well as a review of Linear Algebra. Portions may be read online at: http://www.squint.org/qci/ If you have a Real Audio plugin for your web browser, there is an excellent series of "WebSeminars" at: http://www-brims.hpl.hp.com/websems/quantum/home.html. _Introduction to Quantum Computation and Information_ is a good collection of articles, prior to Nielsen and Chuang it was probaly the best available book on the subject. 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 ABOUT THE AUTHORS ------------------------------------------------------------------------ Brad Huntting wonders how many parallel worlds it takes to screw in a light bulb. He may be reached at huntting@glarp.com. {Picture of Author: http://gnosis.cx/cgi-bin/img_dqm.cgi} 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.