Quantum Computing

I still subscribe to some DTMs, (dead tree magazines) and every so often they pile up and I go back though and check them for missed articles, then off to the recycler they go.  Well I ran across an article in The New Yorker that described quantum computing.  What?  Quantum computing!  Never heard of it. 

Unfortunately, unless you are a subscriber to The New Yorker or have a nearby library that retains old periodicals, you will not be able to read this article, they did not post it on their open webpage, which is truly a shame, it is a really good article.  (You can buy digital access to the article from The New Yorker for one year for $5.99, but Hmmmm?  OK I liked the article but is it worth six bucks?) Why don't they keep the good articles on the open webpage and only throw the fashion and the arts articles on the subscriber's

archive?

May 2, 2011 Issue

Actually the only reason why I am posting this is so that I could in good faith include the cover image, it is so cool, but hopefully not all that true.  I am sort of hoping that Kate and Will tell the family to go bugger off.  Alas I stray, but I do love this cover.  

The article at hand is:

The New Yorker, May 2,2011, Dream Machine, Rivka Galchen.

The above link will take you to an abstract.  If you are a subscriber, you can click into their online archive, or, if not a subscriber, you can click to buy access to the article.  Again $6 for a general info article seems a bit stiff.  Damn I wished they had it on the open site!

So what the hell is a quantum computer?  Well first it may be helpful to know what a normal digital computer is.  Deep in the bowels, of the contraption on which you are reading this post, are a vast collection of transistors which are grouped to form packets of data called bytes, which is the basic unit of information in our digital world. Each byte is 8 transistors laid out in parallel.  Ohhhh this is sounding complicated.  Not really, well not just yet...it can't get too complicated, because I am too damned dumb.  Each transistor acts simply as a switch that can be turned on or off very easily.  It is nothing more than the light switch in your house, except instead of using your fingers to turn it off or on, you use a small voltage.  Transistors are very small, very fast, and don’t consume a lot of power.  So the transistor is either OFF equating to a Binary digIT of zero, or ON equating to a Binary digIT of one.  So what do we mean by Binary digIT.  The famous BIT.  Again the best way to understand this is to think of something more familiar.  Think of the odometer in your car, the old kind that was a series of rotating drums with the numerals 0 to 9 painted on each one (to keep it simple, forget about the tenths off to the right side).  Each drum is a decimal digit.  Hmmmm. Decimal digit?  It works in the same number system, base 10, that we humans work in, something to do with 10 fingers perhaps.  So the odometer in your car is a base 10 register that can indicate any combination of numbers from 00000 to 99999.  Each one of its digits can be anything from 0 to 9, so each digit has 10 possible states, and the entire register has 100,000 possible combinations...00,000 to 99,999.  

You could have a base 10 computer, but it would require a switch with 10 distinct states providing 10 discrete signal levels.  That gets complicated real quick.  If you are working with electricity, what can be more simple than ON or OFF?  So what you do is change your number system from base 10 to base 2, the binary number system.  The binary system only uses two numerals, one and zero. which conveniently equates to the ON and OFF of the transistor!  A byte of memory is simply 8 transistors laid side by side and each transistor can either be a one or a zero.  So lets count in binary.  Note I put a space between 4 digits to make it a bit easier to see.

0        0000 0000

1        0000 0001

2        0000 0010

3        0000 0011

4        0000 0100

5        0000 0101

6        0000 0110

7        0000 0111

8        0000 1000

9        0000 1001

10   0000 1010

11   0000 1011

12   0000 1100

13   0000 1101

14   0000 1110

15   0000 1111

16   0001 0000

On up it goes all the way  to 1111 1111 which equals a equivalent to a decimal 255.  So an 8 bit binary register (one byte) can represent 256 combinations 0000 0000  to 1111 1111.  One byte of memory certainly can not hold very much information, but the magic is that it can be rapidly stored, manipulated, and retrieved.  The operating system and the various programs assign different meanings to the byte of data, and handles multiple bytes in parallel operations.  So even though one byte can only be a series of ones or zeros, the computer can use the byte to store part of a number, a letter, a shade gradient in a photograph or part of the address to another byte of memory that contains something relevant to the task at hand. 

So our standard binary computer is nothing but a collection of transistors, or magnetic blips on a hard drive surface, or chinks burnt into the surface of CD or DVD.  No matter what it is, the basic unit is ON or OFF, one or zero, stored in a parallel packet of eight bits, called a byte.   

So what is a quantum computer?  Instead of using transistors which are relatively big and power hungry, you use an element from quantum mechanics, the physics of the tiny world on the other side of Alice’s looking glass. We are talking sub-atomic particles--very tiny!   Why would we want to replace a good old transistor computer with a quantum computer?  Well to borrow a few reasons from the article:

"With one millionth of the hardware of an ordinary laptop, a quantum computer could store as many bits of information as there are particles in the universe." 

"To factor a number of two hundred digits or more would take a regular computer many lifetimes…With Shor’s algorithm (for finding prime factors of huge numbers) , calculations that would take a normal computer longer than the history of the universe would take a sufficiently powerful quantum computer an afternoon." 

So in a quantum computer, the transistor (giving the bit, the zero or one, OFF or ON) is replaced by some quantum particle and yields what is known as the Qbit (for quantum bit).  A Qbit can be zero, it can be one, or it can be both! A property known as superposition.   Both! How can it be both?  Well to understand that, which we ordinary folks with classical brains, will never be able to do, it may help to think about cats.  CATS!  Yes cats. 

Typical classical cats that live in our world, the big everyday world where the sun comes up and goes down and computers use transistors, can be in one of two states: alive or dead.  So like a transistor, the cat has two states alive, a digital one, or dead, a digital zero.  (OK, I know unlike transistors, cats when dead remain dead, but let’s not confuse the issue.)  A quantum cat however is both live and dead!  About now you are thinking that I have lost my mind.  Well in this stuff, I ain’t smart enough to lose my mind, so all I can do is tell you what the smart guys say. 

 Erwin Schrödinger

One of those smart guys was physicist who did a lot of work with quantum mechanics back in the 1930s and he found that some of properties of quantum mechanics to be troubling.  Certain aspects of quantum mechanics exists as probabilities rather than hard fast facts.  So in a quantum system of two states, will the photon be absorbed or reflected, both states exist simultaneously until someone observes the action.  Erwin Schrödinger found this a bit hard to swallow and he posed this thought experiment. 

Wikipedia, Schrodinger's Cat

In Schrödinger’s own words from Wikipedia:  

"One can even set up quite ridiculous cases. A cat is penned up in a steel chamber, along with the following device (which must be secured against direct interference by the cat): in a Geiger counter, there is a tiny bit of radioactive substance, so small that perhaps in the course of the hour, one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter’s tube discharges, and through a relay releases a hammer that shatters a small flask of hydrocyanic acid. If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed.  The psi-function of the entire system would express this by having in it the living and dead cat (pardon the expression) mixed or smeared out in equal parts.

Wanted Dead Or Alive,  Schrödinger's Cat 

It is typical of these cases that an indeterminacy originally restricted to the atomic domain becomes transformed into macroscopic indeterminacy, which can then be resolved by direct observation. That prevents us from so naively accepting as valid a "blurred model" for representing reality. In itself, it would not embody anything unclear or contradictory. There is a difference between a shaky or out-of-focus photograph and a snapshot of clouds and fog banks."

Note!  This is a thought experiment.  No cats were actually harmed by this experiment.

So poor old Schrödinger’s cat is both dead and alive until we come along, open the box and observe the condition of the cat.  As soon as we do so, we collapse the quantum wave form and the hard reality of either a dead cat or a live cat presents it self.  Yes, Schrödinger was trying to show this as an absurd paradox.  In our world perhaps, but not in the world of quantum mechanics.  This is a well established theory, and the quantum computers not only will use this property, but the existing quantum computers already do use it.

Existing quantum computers?  Yep!  There is a two Qbit machine at Yale and an 8 Qbit machine in Oxford.  But get this, an outfit called D-Wave Systems sold a 128 Qbit computer to Martin Marietta Corporation.

    Yes! You can have one! 

All you need is a cool $10 million, 10 cubic meters of space that your not doing anything with, and a bunch of really smart people to run the damn thing.  For now, keep your Facebook page up to date on your old Dell. 

There may be something a little fishy about this whole D-Wave enterprise.   Cold fusion, comes to mind.  There seems to be a number of nay-sayers about what D-Wave really has.  I ain’t smart enough to say one way or another, but some folks are asking serious questions about how this computer runs.  I would like to think that Martin Marietta would know what their doing, so let’s give everyone the benefit of the doubt.  But from what I have read, D-Wave’s claims of having a true quantum computer are questionable. 

But getting back to our Q-bits.  This indeterminate state of the bits, this superposition, is part of the power of the computer.  The only trouble is, you can’t look at a calculation in progress.  Like a shy newly wed couple, the hanky panky must go on in the dark, unobserved. Why?  The wave form collapses when observed, ergo the computer halts the calculation before it is done.  Cool.  But here is another problem, the Qbits are quite delicate.  The slightest interference from the outside world can knock them awry.  It helps if you keep them really cold and really isolated from the rest of the world.  A little hunk of dust or zap of RF can throw your Qbits into oblivion.  So yes with one millionth of the hardware of a laptop, you can break every credit card security code on the face of the Earth in afternoon, you just need a big assed refrigerator, one that goes down to less than one degree Kelvin, and a lot of empty space. 

Graphic Representation of a Qbit

Now if you want to find out more about Qbits, read the following discussion.  This guy explains them using two pairs of polarized sunglasses and a pair of 3D movie glasses (the new ones, not the old red and blue jobs).  He does a very good job of explaining this.  Qbits are described in 3 axes, and the value must fall somewhere on a sphere surrounding those axes.  Yeah that don’t seem to difficult.  Then he says  “consider that single-qubit states can be represented by a point inside a sphere in 3-dimensional space. Two-qubit states, in comparison, need to be represented as a point in 15-dimensional space. Huhhh?   One can be mapped in sphere, but 2 require a 15 dimensional polyhedron?  Not 15 sides mind you, 15 dimensions, you know like up/down, left/right, in/out and 12 more.  You can visualize that. Well if you are a hell of lot smarter than me, this guy can help you understand how a Qbit works.  I found myself nodding my head saying Um Huh, Um Huh.  If you do that a lot, you can convince yourself that you are really smart enough to understand this crap.  

ars technica, A tale of two qubits: how quantum computers work By Joseph B. Altepeter

So these things are decidedly odd, yet wait, we haven’t talked about entanglement.  Take Schrödinger’s cat.  Get another identical cat & experimental apparatus 15 billion lights years away.  Run the experiment.  What happens to the cat on this side of the universe, happens to the cat on the other side, simultaneously, no need for worries about the speed limits from the velocity of light and all that relativistic nonsense.  Cat A does the same thing as Cat B.  Right now, same instant!  Cool, but how the hell does that work?  Beats the hell out of me.  But from our computer's point of view, some how you can use this entanglement to have all the Qbits work for you instantaneously.  

The Pride Of 1976, Not The Computer,
Seymour's Suit

What keeps them from becoming all 1s or all zeros is beyond me, but this entanglement is part of the promise of quantum computers.  Instant communication to all the Qbits.  Remember those old Cray super computers that was built in a semi-circle to keep the wire length and the bus transistion time down.  You know those slow old electrons that move almost the speed of light?  Not a problem here!  Instantaneous, well at least the Qbit portion of the machine.  

One other factor we must consider, before you decide to pony up that $10 million for a spiffy new D-Wave One to store your wedding photos and to hack into the NSA and see what’s up.  Decoherence!  Yes decoherence!  OH NO, NOT DECOHERENCE!   The wonder of the qbit is that the element is tiny, the spin on a single electron, or the magnetic brouhaha of an atom.  Ahhhh, but this cat is extremely delicate and short lived.  When the wave form collapses, the cat is either dead or alive but not both.  And if you didn’t get your calculation done before the box springs open and behold the cat!--well tough shit, you don’t have an answer.  This really is going to make dial up problematic.  So how long do you get before the Qbit decoheres?  One microsecond!  One millionth of second, then your computing elements turn to quantum mush.  Oh sure you can fire them back up again, but you still must get your calculation done in less than a millionth of second.  Partial results are not permitted.   

David Deutsch

So what is going on here?  Again it beats the hell out of me.  Who thought this crap up?  A guy named David Deutsch.  

Wikipedia, David Deutsch

Why did he think it up?  Well not because he wanted to check his friends in Facebook faster.  He thought it up because some guy from IBM asked him how to do some idealized comparison of the speed of computers.  Deutch told him not to bother, there is no ideal Turing machine, the perfect computer.  The guy said sure there is.  Physics.  Physics is the ideal Turing machine.  Deutch thought about this and then wrote a paper.  Physics is the ideal Turing machine, but not classical physics, Newton’s Laws and all that.  It has to be quantum physics.  Quantum physics can provide the ideal perfect computer. 

OK, so you think things have been weird, with dead and live cats at the same time, and cats acting over steller distances instantaneously?  Well it is going to get a whole lot weirder!  Deutsch is a many world theorist.  Does he give a damn whether Google can reverse ID an image in a second, or someone can factor a 500 digit number in an hour?  No!  Deutsch is using the quantum computer as a thought experiment proof for the many worlds theory.  Many worlds theory? 

Well there is this thorny problem with the Copenhagen Interpretation of Quantum Mechanics, this Schrodinger cat superposition about how something can exist in two paradoxical states at the same time.  So how do you solve this problem?   Simple!  Everytime a quantum event occurs the universe splits, one has a live cat, one has a dead cat.  Flip a coin, bingo two new universes, one heads one tales.  This is the Many Worlds Interpretation of Quantum Mechanics theorized by Hugh Everett in 1957.  

 Roll the dice, tadah!  Thirty six new universes, one for each combination.  Trying to conceive?  Ahhh don't worry about it. Have a little fun, and then just make sure you pop into one of the half a billion new universes, each with a different baby!  There is only one without a baby, your chances are a half billion to one!  Hmmm!  It don't seem to work that way.  OK that’s stretching it, and I am not sure sex or rolling dice qualifies as a quantum event.  But if those examples seem ridiculous, consider how many quantum events are taking place through out our universe every moment (and quantum moment is quite short—a thing called a jiffy about 5.4 × 10⁻⁴⁴ seconds) and by God you got a universe assembly line that Henry Ford would have been proud of.  Now bear in mind all these other universes continue to split on and on they go.  In the time it takes you to read the word “jiffy” the umpteen bazillion infinities of ever splitting infinite universes became the X times umpteen bazillion infinities of more infinite splitting universes.  Personally, I give this theory about 22 bazzilion orders of magnitude  less of chance of being correct than astrology.  And believe me I think astrology is pure hogwash.  But hey!  I am stupid!  Ergo it very may well be true.  There is no doubt in Deutsch’s mind, and he is pretty damn smart.  Many worlds is a valid theory, not a vastly popular one, but valid.  A lot of smart people believe it.  A lot of smart people and one stupid one don’t believe it.  And there are some other damned smart people who don’t give a shit either way.  All they want is a functioning quantum computer. 

But for Deutsch, the computer is a proof of this theory.  He said this regarding running Shor’s algorithm for factoring a huge numbers, quoted from The New Yorker article:

“When we run such an algorithm, countless instances of us are also running it in other universes.  The computer then differentiates some of those universes (by creating a superposition) and as a result they perform part of the computation on a huge variety of different inputs.  Later those values affect each other, and thereby all contribute to the final answer, in just such a way that the same answer appears in all the universes.”   

So here is his proof from his book The Fabric of Reality:

“To those who still cling to a single – universe world view, I issue this challenge: explain how Shors’ algorithm works.  I do not merely mean predict that it will work, which is merely a matter of solving a few uncontroversial equations.  I mean provide an explanation.  When Shor’s algorithm has factorized a number, using 10⁵⁰⁰ or so times the computational resources than can be seen to be present, where was the number factorized?  There are only about 10⁸⁰  atoms in the entire visible universe, an utterly minuscule number compared with 10⁵⁰⁰ .  So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it then?  How, and where, was the computation performed?"

So what we are talking about here is parallel processing across parallel universes, because our universe don't have enough stuff in it to do the calculation.  Cool! Yeah, its easy to prove parallel universes on a machine that doesn't exist with an algorithm that may or may not work. Well actually it is not, but it is one thing to claim it and quite another to do it. So when you guys get the machine built and start factoring some really huge numbers, maybe I will believe it then, but probably not.  I am not going to hold my breath waiting. 

And what about the small quantum computers?  The 2 or 8 Qbit machines actually working now, not to mention the D-Wave 128 Qbit machine?  Are they running in parallel universes as well?  Sure they are little but if the big guys have to do it, should not the little ones be able to do it?  And how would we know?  Shouldn’t we be able to somehow worm hole over to one of these other universes?  Perhaps use Q-Twitter to have a chat with the you from yesterday who split out 18 bazzillion splits ago.  It all sounds a little out of this world to me.

EDIT 7-2-2011:  Browsing about looking for information on my next post I ran into this tidbit:

"Haggar Physicists Develop ‘Quantum Slacks,’ ” read a headline in the satirical weekly the Onion. By exploiting a bizarre  “Schrödinger’s Pants” duality, the article explained, these non-Newtonian pants could paradoxically behave like formal wear and casual wear at the same time. Onion writers were apparently spoofing the breathless articles about quantum computing that have filled the popular science press for a decade."

The problem with quantum slacks is that they would be subject to Heisenberg's Uncertainty Principle where you can know either the position of the pants or the velocity of the pants but not both--because both quantities do not exist simultaneously in nature. Hence trying to put the pants on would be a real pain in the ass.  If you knew for a moment (just a quantum moment BTW)  where the pants are, you would not know how to grab them because you would have no idea how fast and what direction they are traveling, and if you knew how fast they are traveling you wouldn't know where to grab them.  Ergo I respectfully submit quantum slacks to be impractical and would suggest to the reader to simply wear blue jeans. Failing in that then one must still purchase a pair of classical formal slacks and a pair of classical casual slacks if he every actually intends to wear the slacks. But I digress.  Here is an interesting article that may put some of this wackiness into a better perspective:

http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

And if you read the above article and think you are feeling your intellectual oats, here is the author of the above article's blog.  I now realize that I am far more vastly stupid than my initial assessment at the beginning of this post would suggest:

Shtetl-Optimized, The Blog of Scott Aaronson

And here is an hour and ten minute lecture that Aaronson gave at Carnegie-Mellon University:

YouTube, Quantum Computing and the Limits of the Efficiently Computable - 2011 Buhl Lecture

Image Credits;

New Yorker Cover:  The New Yorker, May 2,2011, Dream Machine, Rivka Galchen.

Schrödinger and the Cat Diagram:  http://en.wikipedia.org/wiki/Schrodinger

Qbit Diagram:  http://en.wikipedia.org/wiki/Quantum_computer

Cray 1 Computer:  http://gizmodo.com/5602574/this-cray+1-pc-replica-has-200000-times-the-power-of-the-original-cray+1

David Deutsch: http://en.wikipedia.org/wiki/David_Deutsch

Many Worlds Theory: http://abyss.uoregon.edu/~js/ast123/lectures/lec19.html

Book Cover, The Fabric of Reality:  http://www.goodreads.com/book/photo/177068.The_Fabric_of_Reality