OSNews

*starts bottlecap collection*

Dude, only just now? I've been collecting bottle caps ever since I learned to walk.

Oh, and a zombie survival kit. Can't forget that one.

When talking to a friend in the park I was dilighted after spotten three bottlecaps in the sand. Only after I got them out of the sand I realised that I might be playing a little too much Fallout.

When I first started Fallout 3 last year... After a 10 hour Fallout 3 session on a Sunday I left my house in the evening, and the first things I thought as I closed my front door behind me were "Duck, and where's my Chinese Assault Rifle?"

I felt like such an idiot.

Well, thanks for taking the time to tell us that!

I'm not sure you quite have that right. Then again, I'm not sure I have it quite right, either.

At the very least your sentence "Things that are O(N!) or O(2**N) become suddenly turn into O(N) where N is the number of Q-bits." is misleading. Only -certain- problems are improved, and the way you've worded the second part seems to suggest that the more qubits available, the more complex the problem, which seems intuitively to be the opposite of what would happen.

My best recommendation to attempt to understand both the complexities of quantum computing and the implications, is to read wikipedia's article on Shor's algorithm: http://en.wikipedia.org/wiki/Shor's_algorithm

Basically, Shor's algorithm allows for integer factorization in polynomial time, ~O(logN) vs ~O(2^N) for non-quantum computing. One of the possible implications of this is the breakage of most existing cryptographic systems.

At least, that's how I understand it.

One way to explain the basics of quantum computing is as a master state machine. Where you have numerous addressable qubits arranged in a grid/array ( doesn't really matter ).

First you setup an initial state, an algorithm in reality. Then you feed it data. As each data is fed, a new state emerges in the qubit array.

Reading the array is destructive, therefore a read can only be made once from the array without starting over, due to the observer effect.

The final solution is, perhaps obviously, the entire state of the quantum array.

What those results mean is up to the interpreting algorithm, based upon alterations of the programmed initial state of the qubit array ( the result of the data fed into the pre-configured array ).

Example:

You have a list of objects which have interlinking states. These states can be anything. Such as whether or not a given object is "on" or "off." Changing these states can be very time consuming, taking O(N^2) in most implementations. In a quantum setup it should take O(1) ( not even O(N) ).

This is to say that it will take only as long as it takes to set the state of one object as it does to adapt the state of all other objects, in fact they occur at the same instance due to quantum entanglement (super-position).

The performance benefit depends mostly on the cost of configuring the qubit array, if done programmatically, and the cost of interpreting the results ( if needed ).

In the beginning, we will see dedicated qubit arrays designed to solve a very specific problem quickly.

Imagine having three bits: 101

Now, we pass data 110

The result is 201, where 2 is both 0 & 1 and neither, depending on the interpreting algorithm. Imagine being able to do such things so fast we can't figure out how long it took ( the answer is ready EXACTLY when the data is fed ).

Furthermore, as the technology advances, we should, theoretically, be able to create wireless network cards which communicate via arrays of particles which are kept in superposition of the other, regardless of distance. There will be no time delay. No lag.

You will buy a chip to access Youtube or Google video without ever needing to worry about a delay. You will buy another chip to ensure absolutely secure communications between two points.

There are many other advantages to this technology I don't have time to discuss, nor all the knowledge needed to explain. Indeed, much of this is merely flying by the seat of our pants...

Hope this helps someone understand the technology and some of the likely benefits.

--The loon

Disclaimer: I'm an autodidact, not a quantum physicist. Physics is just one of my many favorite topics ;-)

On the communications part of your post, I do not think that is actually possible. See: http://en.wikipedia.org/wiki/Ansible specifically, the "In Reality" section. Of course, saying something is impossible is generally a bad idea in science, so maybe someone will figure out faster-than-light communication. :-)

The "No Cloning Theorem" is devised out of the mere fact of collapse of the quantum state held within the qubit array when observed. A device capable of repositioning the qubits into superpositions of a peer device at a distance and creating a common initial state would be capable of communication.

The biggest problems to solve involve error checking and reliability of reading the quantum state with enough accuracy. Probability is only good for so much. We may well need to do everything in triplicate, otherwise we can create error correction using an interpreting algorithm.

Even if performance suffered significantly ( which it will - at least at first ), the technology will still be very useful.

--The loon

I should also state that the theorems are assuming a pure quantum mechanical solution, which is not possible based upon current theory ( which is just theory, still - and I still agree more with Einstein ).

Given current conventional quantum mechanical theory:

Conventional electronics will need to feed the qubit array with data at a specified rate, receiving a reply for each and every transfer. If the reply is the sender's previous message after a specified timeout, there is a transfer glitch. The time interval will be set by speed requirements, quantum restrictions, and electronics limitations.

To deal with quantum entanglement's sustainability across time issue, the data should be written numerous times at a predetermined interval, and the receiver will receive at compatible rate. These data issuances can provide a means for error control and high error counts over several packets will show snooping or interference.

Granted, this is only good for point-to-point but not doable for broadcast and is a gross simplification.

Of course, if this guy ( http://www.wbabin.net/mathis/mathis23.htm ) is right, we will be able to accurately measure the qubit array, and even be able to make clones ( allowing broadcasting ).

Ahh.. the joy of theoretical science.

--The loon

Our languages just need to be updated to take that into account. With things like Erlang and Scala, we are only now starting to hammer down how to do concurrency properly, I would expect quantum languages to follow the same sort of route.

Languages will come about when we have a general purpose quantum processor / co-processor that can be programmed. A long ways away.

Here is what quantum processors can do basically.
* Searching very big databases almost instantly. You could have google at home in a small box.
* Brute forcing RSA keys in seconds. This will obsolete all our current cryptography.
* Encrypt with quantum algorithms that will replace RSA.
* Beat anyone and any current computer at chess.
* Many other things creative people will invent.

Edited 2009-06-30 08:14 UTC

...unless it takes hundreds or thousands of years to construct quantum computers capable of the computation needed.

Twenty years ago, I read an article saying that flash memory was going to be the next great thing. It finally took off, what, a couple of years ago? and even then we haven't yet replaced hard drives.

Also twenty years ago, fuzzy logic was going to be the next great thing. One guy even wrote a book talking about how it showed the backwardness of Western ways of thinking. A hilarious article in one electronics engineering magazine described a project by a couple of researchers, paid for with a hefty grant from the government (I believe the number was in the millions of dollars), that accomplished what the author could do at the time with $2 worth of analog equipment. I understand that it is used, but it seems (to me) that it was definitely over-hyped at the time. In any case, I'm not sure that after two decades it has yet reached the level of development as flash drives.

So quantum computing may pan out, but I wouldn't hold my breath.

I would be kind of funny if all the advantages of such incredible computer power would be lost because of the need of insanely large encryption keys.