BetaBenj sent us the latest update from
TechWeb concerning the latest advances in solid quantum computing. Recently, there have been a couple key advances bringing us closer-but we're still a ways out. Still, the ramifications of it are
almost as staggering as nanotech. Almost.
Slashdot Mirror
You miss my point - QC might *not* do this any better than standard computers.
First, we do not believe that quantum computers could solve NP problems (QP != NP in CS speak). If I remember correctly QP is strictly contained in #P (really P^#P). This means that a public key cryptosystem based on NP complete problems instead of factoring numbers could be secure against a quantum computer.. except that many many cases of an NP complete problem are easy to solve.. but if we can't use factoring numbers because of the preasence of quantum computers then this might be an acceptable alternative.. it could mean you would need to upgrade you're key (and software to generate keys) frequently to keep up with advances in mathematics and CS.
I geus a cheezy way to describe the limitations of cuantum computing is to say that you get a lot of really powerfull parallelism, but since you only read out one answer you can not directly take advantage of it. The quantum algorithms ``make the wrong answers cancel out.'' Currently all the quantum mechanical algorithms which provide exponential speedup (like factoring) work by finding the period of some function by useing a Foruer transform.
The Christian religion has been and still is the principal enemy of moral progress in the world. -- Bertrand Russell
No.
No, No, No.
NP-complete problems are hard.
All of them.
Equally hard.
That is, if you can solve one NP-complete problem, you can use it to do the others in polynomial type. A Hamiltonian oracle can solve 3-coloring, circuit-sat, traveling salesmen, and the others, fast
...
I don't really know if quantum computers can solve NP problems, or even factoring for that matter, since I don't know how to phrase algos in quantum computable terms....although, like parallel algorithms, it'll be a booming area of research, you can bet.
>This is getting quite repetitive.
'Twas meant to be a joke -- the "OW!" was meant to be my response to someone smacking me upside the head for saying this...
Ooh, a sarcasm detector. Oh, that's a real useful invention.
Now that the theoretical is no longer so difficult to achieve physically, maybe we can focus more on the practical uses of QC. Check out openqubit.org, they are currently working on QC models, ways to implement Shor's algorithm, and other interesting things.
Great. We will shortly (20 yrs?) have quantum computers. But is this a good thing.
Yeah, it would be great for all sorts of things (just imagine the speed boost for things like ray-tracing, searching, and sorting) but it would also make a brute force attack on any encryption algorithm a simple matter, rather than a computational nightmare.
Now, it would be fair if everybody had their nondeterministic turing machines to chug out quantum encryption, but how much is this going to cost. I'm thinking that quantum computing, and all of it's benefits, will be the realm of governments and large corperations, at the expense of everybody else.
You might note that you posted to the wrong article... but as a side issue:
With quantum computing does that mean we could only view the contents of a Micros~1 Word document or modify them but not both?
This space for sale
I'm not sure about that. The current applications that are being proposed for QC are of a fundamentally different nature. QC speeds up things like searches, but I can't see a way for it to easily speed up things like rendering or kinetics simulations. At the very least, a very different approach to those problems would have to be thought of.
Does anyone else have more information on what kinds of problems quantum computing will and will _not_ be good at?
the technical details described in the article, but I do have (imho ;) a decent understanding of the computational principle behind quantum computing. I've seen some pretty wrong (or just confused) things in the comments...and /. discussions of encryption/complexity related issues frequently get mired in BS ;)
Quantum computers do not really translate to higher FPS in Quake3 or more realistic flightsims. You don't get quantum computers that have amazing SPECfp numbers.
Quantum computers do operations that normally take one order of magnitude in a much lower order time. Example: searching a list of items for a value on von Neumann machine is O(n) (length of the list), since you have to look at each element till you find the one you want. You can do this in O(1) on a parallel machine. This is a significant improvement. IIRC there was a quantum computer that could search a 4-element list in O(1).
Obviously, that's a pretty trivial problem. Even for very long lists, O(n) isn't bad, and you can do it in parallel.
What about fundamentally much more complex problems, such as factoring, or better, something NP-complete such as circuit-sat or Hamilton paths (that's what the article was talking about, I think. Those guys think their quantum computer is a Hamilton oracle, if I'm right. So you have to pose questions in the form of graphs...not a serious problem since all NP is orthogonal). A parallel machine doesn't help there. But a quantum computer can take NP problems from exponential to polynomial time.
All of a sudden factoring (not NP, just decently hard) goes from taking 100 trillion years to taking hours.
Yes, all encryption that uses factoring as a trapdoor (one-way function) would be toast.
No, it wouldn't necessarily be any better at running first person shooters.
Still, an NP oracle machine IMHO would be much more significant than some bloody nanotech robots.
No one has suggested how awesome a Beowulf cluster of these would be...OW!
Ooh, a sarcasm detector. Oh, that's a real useful invention.
I'm an engineer, not a physicist, so I don't completely understand quantum mechanics, but from an engineering standpoint it makes sense.
:)
In a combinatorial set of data, operations are order independent. Because of this, you can configure the quantum hardware in such a way that all of the appropriate electron jumps can happen in one clock cycle, since thousands of electron jumps can happen in less time than we can clock (we're talking femtoseconds here).
Only when operations are order dependent (1 + 2 * 3) must we be sure one thing has completed before we begin another, and this is the reason we use clock cycles. For (1 * 2 * 3 / 4) order doesn't matter.
Each operation takes a certain amount of time to complete (due to propagation delays, gate time, etc). You can't hit the next clock cycle until results have stabalized. Right now we are working to make conventional gates faster so that we can drive clocks at a higer rate. Imagine a single gate system that could do thousands of order independent operations at the "same time" (one clock cycle). So this "single operation" is really many many multiplications and divisions, but it can happen in one clock cycle.
Make sense?
It doesn't to me
-Alison
Unfortunately openqubit.org is nothing but a "coming soon" sign. :( While we're waiting for that to open up we can go to www.qubit.org, particularily the "Introductions & Tutorials" page.