Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Quantum Programming, Now

By rusty in News
Sun Jun 25, 2000 at 07:24:23 PM EST
Tags: Software (all tags)
Software

Damian Conway, a senior lecturer in computer science at Monash University in Australia, spoke to a packed auditorium at YAPC 19100 about the mechanics of quantum computing and what the future might hold in store. I can't do his talk justice here, but I will try to boil it down to the essential points. He called it Quantum Superpositions and the First Virtue, I call it a tiny glimpse of what the future of programming might look like.


The absurdly simplistic conceptual summary

One of the basic features of quantum physics that are of interest to computer scientists is the fact that a particle can be in more than one state at a time, and the state of a particle can only be determined by looking at it. Shroedinger's infamous thought-experiment with the cat conceptually summarizes this. The basic principle is, say you have a particle, which we'll call "Bob". It can have two states, called state A and state B. How can you tell what state your Bob particle is in? Well, you have to look at it. Seems pretty obvious, right?

But what state is Bob in when you're not looking at it? What quantum mechanics tells us is that it is in all of its possible states, at once! This is called a quantum superposition, and is meant as literally as possible. It isn't in one state or the other, and we just don't know which-- it is literally in all possible states, at the same time.

What interests computer scientists about this is, what if you tied information to the states of your Bob particle? Say, state A represents a one, and state B represents a 0. So your particle can store one bit of information. But when you're not looking at it, is it a one, or a zero? In fact, it is both at once.

What this means is that you could create a particle with a large number of possible states, and use this superposition to represent, for example, all the numbers smaller than the square root of a very large number. Then, to calculate the factors of this number, you merely need to look at the particle, at which point it will collapse into one of its "eigenstates" or allowed "real" states, which will represent the factors.

Why do computer scientists, not to mention the NSA, care?

Anyone who has dabbled in cryptography will probably see where this is going by now. What this means, ultimately, is that you can factor arbitrarily large numbers in constant time. If the length of a number doubles, the time it will take you to factor it remains the same. If it triples, the time it takes to factor it still remains the same. Currently, the time it takes to factor a number is a fairly steep exponential, which is the entire basis of public-key cryptography. The keys used are the product of two very large prime numbers, and if you can get the factors of a public key, you can break the encryption. To a quantum computer, the difference between a 56 bit key and a 128 bit key is negligible. Yes, the development of working quantum computers will basically make a big chunk of our current crypto infrastructure totally irrelevant.

But despite this somewhat unfortunate side-effect, there are a lot of advantages for a programmer working with quantum computing. Imagine you have two lists of things, and you want to find out what things are in both lists. The easiest way to do this is to compare every member of each list to every member of the other list. Unfortunately this is also an exponential time algorithm. But a quantum computer could do it in constant time, by simply comparing a superpostion of one list to a superposition of the other, and seeing what eigenstates fall out. That's just one example of what might be possible.

I thought you said we could do this now...

All along, Conway had posited a perl module called Quantum::Superposition, which would add a couple new operators to perl, the any(), all(), and eigenstates() operators, and overload the basic unary and binary math and logic operators to work on quantum superpositions as well as ordinary scalars. Then he dropped the bomb. This module exists. He actually wrote it.

Now, can it really do all that in constant time? No, because as he put it, perl has not yet been ported to run on a pair of supercooled, quantum-entangled calcium ions. But it will simulate the behavior of quantum superpositions in perl, right now. We can actually play with the concepts of quantum computing, without even having a working quantum computer. This module includes some of the cleverest coding I've ever seen, as an afterthought, and will be available on CPAN in the very near future.

Like one of Conway's other perl modules, Coy, which prints out error messages in haiku, Quantum::Superposition was written as a "ha, ha, only serious" kind of joke. But also like Coy, people immediately started thinking of ways to actually use it. When asked to speculate on how long before we'll see functional quantum computers, Conway answered "one to five years" with no hesitation. He did guess that it would be more like 20 or 25 before we're all walking around with quantum laptops, and that initially it would be likely that only large governments would have this technology. But even without the hardware that will ultimately acheive the great speed increase, coders can start hacking pseudo-quantum computing into their code right now. We can only wonder what they'll manage to come up with.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o Damian Conway
o Quantum Superpositions and the First Virtue
o CPAN
o Coy
o Also by rusty


Display: Sort:
Quantum Programming, Now | 21 comments (18 topical, 3 editorial, 0 hidden)
Other Links (none / 0) (#3)
by Yzorderex on Sun Jun 25, 2000 at 10:55:38 PM EST

Quantum Computing can efficiently compute a 4 way result in one clock cycle. Longer word lengths improve this.
Here's one way to do it using MRI
And an elegant view of our DNA using quantum computing in sorting base pairs. Very computationally efficient.
And (drifting off topic a bit) if you're into QM and consciouness this guy has a rather amazing view.
Quantum Computing is just the beginning. DNA sequences, molecules, and other macro events, like people, may have a QM accessible tag, so its not just for little tiny particles collapsing.

Constant versus linear time (5.00 / 1) (#5)
by isenguard on Mon Jun 26, 2000 at 09:41:08 AM EST

> Anyone who has dabbled in cryptography will probably see
> where this is going by now. What this means, ultimately,
> is that you can factor arbitrarily large numbers in
> constant time. If the length of a number doubles, the
> time it will take you to factor it doubles.

Correct me if I'm wrong, but doesn't this describe linear time (i.e. O(n)), rather than constant time or (i.e. O(1))?

Lyndon

--
Lyndon Drake
Re: Constant versus linear time (none / 0) (#10)
by Anonymous Hero on Mon Jun 26, 2000 at 03:00:45 PM EST

The person writing the article dose not seem to really know what they are talking about. They describe constant time and linear time at diffrent points in the article.

Clearly, the algorithms is NOT constant time. It requires at least O(log(n)) just to access the necissary memory to store the numbers, but I seem to remember the algorithm had more time consumpution aspects (maybe up arround O(n^2) or something). Remeber, you can not run a quantum algoithm just once! You must run it many time to increase the probability of getting a good answer. Also, this specific algorithm dose not get the correct answer, but a small multiple of the answer, so you need a classical factoring algorithm to remove the small multiple too (but that may be constant time if they can bound the size of the small multiple).


[ Parent ]
Re: Constant versus linear time (none / 0) (#11)
by rusty on Mon Jun 26, 2000 at 03:03:34 PM EST

The person writing the article dose not seem to really know what they are talking about.

True enough. As mentioned elsewhere, I suck at math. Perhaps you can explain linear time vs. constant time? I'm just quoting Conway when I say "constant time" and he didn't provide a good explanation of what that meant. Help me out here!

____
Not the real rusty
[ Parent ]

Re: Constant versus linear time (none / 0) (#14)
by madams on Mon Jun 26, 2000 at 04:37:23 PM EST

True enough. As mentioned elsewhere, I suck at math. Perhaps you can explain linear time vs. constant time?

The "growth" or "running time" of an algorithm is a measure of how long an algorithm will take to run given an input of certain length or size.

For example, looking up the first character of a string will always take the same amount of time, no matter how long the string is. So we call this constant time.

On the other hand, printing a string out takes linear time, one step for each character in the string. Longer strings take a longer time to print. The length of the string and the time it takes to print it grow at the same rate, so we call this "linear growth".

Now, there are other rates of growth besides linear and constant; for instance, logarithmic, geometric, and exponential. However, it is much easier to think of in terms of the "order" of growth.

Constant growth is "order 1", or O(1), in so called "Big-O Notation" (that's a capital letter 'o', not a zero). Think of this as "it takes 1 step to do it".

Linear growth is "order n", or O(n). In other words, "it takes n steps to print out a string, where n is the number of characters in the string".

If anyone is interested, I can give examples of algorithms that have "orders" other than constant or linear.

--
Mark Adams
"But pay no attention to anonymous charges, for they are a bad precedent and are not worthy of our age." - Trajan's reply to Pliny the Younger, 112 A.D.
[ Parent ]

Re: Constant versus linear time (none / 0) (#17)
by rusty on Tue Jun 27, 2000 at 10:45:39 AM EST

Ok, I think I fixed it. IANACS. :-)

____
Not the real rusty
[ Parent ]
hehehe, only perl... (none / 0) (#6)
by Alhazred on Mon Jun 26, 2000 at 09:44:47 AM EST

Only perl would have a module like that, hehehe. In the old days they'd have done it in FORTH, sadly a dead language now.

QC indeed is the wave of the future. Not only can you quantum compute, you can also perform quantum data transmission under the proper conditions.

A single 32 qbit machine running at 500 mhz would have considerably more raw computation power than all the conventional machines ever made.

The real question? How on earth are we ever going to write software that will do it justice? Certainly not by hand coding every line. Its time we started serious development of "programming languages" (for lack of a better term) which allow machines to solve tasks on their own.
That is not dead which may eternal lie And with strange aeons death itself may die.
Quantum programming languages (none / 0) (#9)
by mbrubeck on Mon Jun 26, 2000 at 02:30:55 PM EST

QCL is a programming language for quantum computation. From the home page:
Despite many common concepts with classical computer science, quantum computing is still widely considered as a special discipline within the broad field of theoretical physics. One reason for the slow adoption of QC by the computer science community is the confusing variety of formalisms (Dirac notation, matrices, gates, operators, etc.), none of which has any similarity with classical programming languages, as well as the rather "physical" terminology in most of the available literature.

QCL (Quantum Computation Language) tries to fill this gap: QCL is a high level, architecture independent programming language for quantum computers, with a syntax derived from classical procedural languages like C or Pascal. This allows for the complete implementation and simulation of quantum algorithms (including classical components) in one consistent formalism.



[ Parent ]
Re: Quantum programming languages (none / 0) (#12)
by Alhazred on Mon Jun 26, 2000 at 03:50:10 PM EST

Useful, but what I'm saying is that we program at TOO LOW A LEVEL.

The reasons for this and the solutions are however a bit out of the scope of a discussion here.
That is not dead which may eternal lie And with strange aeons death itself may die.
[ Parent ]
Re: Quantum programming languages (none / 0) (#13)
by rusty on Mon Jun 26, 2000 at 04:13:52 PM EST

The reasons for this and the solutions are however a bit out of the scope of a discussion here.

No they're not! I'd like to hear them, personally.

____
Not the real rusty
[ Parent ]

Re: Quantum programming languages (none / 0) (#19)
by Alhazred on Tue Jun 27, 2000 at 05:14:11 PM EST

Hehehe, well I guess maybe what I meant was I'm slightly hung over and thus perhaps they are out of the range of what my brain cells can squeeze out today... ;o)
That is not dead which may eternal lie And with strange aeons death itself may die.
[ Parent ]
Re: hehehe, only perl... (none / 0) (#16)
by Anonymous Hero on Tue Jun 27, 2000 at 03:14:32 AM EST

I think forth is used quite a bit for embedded applications. At least there's still a big user community.

[ Parent ]
Cryptography (none / 0) (#7)
by Anonymous Hero on Mon Jun 26, 2000 at 10:26:50 AM EST

Sounds like we'd better figure out a public key algorithm that a quantum computer won't break. I've heard that the NTRU algorithm fits the bill but can't verify that. On the bright side, Bruce Schneier claims that applying a quantum computer to a symmetric algorithm only has the effect of halving the number of bits, so if you use a 256-bit key you'll be all right. (But of course all the really cool applications require public key.)

Before anyone brings up "quantum cryptography," be aware that it's not really cryptography at all, it's a way of using quantum superposition to detect any eavesdropping on your communication. Since it requires that the superposition be maintained end-to-end, it's hard to see how it could work if it has to pass through a bunch of routers.

Re: Cryptography (none / 0) (#8)
by Anonymous Hero on Mon Jun 26, 2000 at 10:50:15 AM EST

From the NTRU website:

"It is worth pointing out that the process of breaking a key pair does not seem to have much chance of being significantly improved by the use of many computers working in parallel. This technique can be effective in attacks on an RSA key - using the quadratic or number field sieve to factor a large number. It is also done in searches for secret keys - for example the recent use of several thousand computers to break a 56 bit secret key to RC5. The reason it is not likely to be useful to an attacker of an NTRU key pair is that the LLL algorithm is a recursive process: one step must be completed before the next is begun. It is not inconceivable that the process of completing one step could be speeded up by a factor of about N by using N processors, (though this has never been tried), but even this would only reduce the time by an insignificant factor of N."

I've seen NTRU and related algorithms referenced in enough places that it doesn't appear to be just one company's snakeoil. Their website also mentions some analysis:

"Since its introduction at Crypto '96, NTRU has been subject to constant scrutiny by top cryptographers, including a EuroCrypt '97 security analysis by Adi Shamir and Don Coppersmith. NTRU has been publicly presented at top cryptographic conferences, has been described through publication in refereed journals and conference proceedings, and has been reviewed by outside experts....Further, the Tumbler implementation (C and Java) of the NTRU cryptosystem by Tao Group, Ltd. has been reviewed by Counterpane Systems, a well-known and highly respected company specializing in security evaluations of cryptographic products."

[ Parent ]

Intellectual dishonesty (none / 0) (#15)
by Anonymous Hero on Mon Jun 26, 2000 at 04:39:50 PM EST

I believe that there is quite a bit of intellectual dishonesty surrounding quantum computing. First let me say that though I'm not a worker in the field I have a pretty good knowledge of what quantum computing is about. I had one of the first web pages about quantum computing (here) and one of the first freely available quantum computer simulators.

My complaint is this: a large part of the physics community believes that quantum computing simply cannot work because of decoherence. There are quite simply basic physical objections to getting quantum computing to work. Getting a quantum computer to work is probably as difficult as cooling a room using Maxwell's Demon (actually...harder). The quantum computer enthusiasts counter that quantum error correction solves these problems. But this simply isn't true. Quantum error correction algorithms make very specific assumptions about the way physical systems behave (more specifically assumptions about what's called the 'Hamiltonian'). The assumptions are basically contrived to make quantum error correction work and there is no reason to believe that these are physically plausible.

Quantum computers are a wonderful new computing paradigm. They appear to show that there really is a theoretical model of computing that is an alternative to the Turing machine. This is very exciting theoretical work and quantum algorithms are fun to devise. But I, and many others, believe that the difficulty of building a computer grows exponentially with the number of bits. This makes them completely impractical except for certain very specific fields (such as quantum cryptography).

Unfortunately nobody wants to publicise the voice of the sceptics because, lets face it, it's not very exciting. But the sceptics aren't simply arguing "this is difficult. I can't imagine it working." They have some pretty sound theoretical arguments. The exponential increase in difficulty means that we shouldn't be getting all that excited when someone announces a 2, 3 or even 10 bit quantum computer. Lets see how long it takes to build, say, a 128 bit one!

Re: Intellectual dishonesty (none / 0) (#18)
by Alhazred on Tue Jun 27, 2000 at 05:12:50 PM EST

Uh, a 10 bit quantum machine would STILL be an enormously powerful system!

Also I disagree with you fundamentally. While working error correction systems have not yet been demonstrated in realistic situations people HAVE performed small numbers of quantum operations, demonstrating that the concept itself is sound. If you have kept up with the latest work in the field it appears to me as a non-expert that the fundamental theoretical objections have been addressed successfully. The problems now are essentially practical in nature and thus tractable. It might require a LOT of engineering, but we're damn good at that!

Besides, even at a cost of 1 BILLION DOLLARS PER BIT, that 128 bit quantum machine would be worth every penny since it would have performance levels on many valuable algorithms FAR beyond what could be achieved by a Turing machine even if it were the size of the entire universe...
That is not dead which may eternal lie And with strange aeons death itself may die.
[ Parent ]
Re: Intellectual dishonesty (none / 0) (#20)
by Anonymous Hero on Tue Jun 27, 2000 at 07:01:04 PM EST

Well, 10 bits wouldn't be all that powerful. It just means you can do 2^10 operations in parallel. That's 1024, accomplished by a conventional machine in the blink of an eye. But 2^128 operations in parallel would indeed be far more powerful than any conventional machine possible--if you can apply the whole algorithm without performing an observation midway. This caveat is why you can't instantly break 128 bit encryption with a quantum computer--all you can do is effectively cut the number of bits in half (according to Bruce Schneier, anyway).

[ Parent ]
Re: Intellectual dishonesty (none / 0) (#21)
by Alhazred on Wed Jun 28, 2000 at 02:01:19 PM EST

Yes, and I wouldn't be willling to say that we know exactly how well quantum computing is going to pan out. It may be that reality will impose enough limitations that it is simply a niche technology. On the other hand the promise is so huge that it seems worth quite a bit of research.

I think I can understand your doubts, but I don't think it rises to the level of dishonesty. I see the same sort of hyperbole in the nano-tech arena, and in molecular computing, and in fact in a slightly different way in the business plans of dot coms...
That is not dead which may eternal lie And with strange aeons death itself may die.
[ Parent ]
Quantum Programming, Now | 21 comments (18 topical, 3 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!