A Working Quantum Computer in 3 Years? 292
prostoalex writes "Vancouver, BC-based D-Wave Systems got $17.5 mln from Draper Fisher Jurvetson to work on a preliminary version of a quantum computer, Technology Review reports. Delivery date? Within three years: 'It won't be a fully functional quantum computer of the sort long envisioned; but D-Wave is on track to produce a special-purpose, "noisy" piece of quantum hardware that could solve many of the physical-simulation problems that stump today's computers, says David Meyer, a mathematician working on quantum algorithms at the University of California, San Diego.'"
Re:Quantum is just another buzzword (Score:2, Informative)
I think that will be the idea. Unfortunately we can't even do that!
Re:Quantum is just another buzzword (Score:5, Informative)
With a (good enough) quantum computer it is possible to factor large numbers (Shor's algorithm) and to break various public key cryptography. (RSA, Elliptic curve crypto). So I would say that it is clear why people want to build one.
(Though it is expected to take a while before the quantum computers are good enough. A few years ago they built one that was able to factor the number 15...)
Re:Speeds? (Score:5, Informative)
Re:Quantum is just another buzzword (Score:1, Informative)
Re:Atoms?? (Score:3, Informative)
the one is a dererministic computing device (call it "pentium" or similar...
the other is a whole new kind of devices. these are devices where bits of information are not represented by small elecrtronic components meaning either '0' or '1', but by quantum mechanical systems (say: atoms, molecules or even photons) that are both '0' and '1' at the same time (each of them with a certain probability).
the very moment you try to find out in what state a given quantum bit (say: qubit) is, it "decides" whether it wants to be '0' or '1'. but until then, it is _both_ (it's not like it's either one or the other, but you just don't know... it's really _both_ of 0 and 1 at the same time!)
so the big advantage of the latter is that instead of, for example, multiplying two numbers, then multiplying other tho numbere, than others and so on, you can really multiply _all_ numbers with _all_ numbers in a single computation step (ok, that's a very simplified description, but that basically is it).
thus, it reduces the computation time for certain numbers (like cracking RSA-based encription keys) from "exponential" to "constant", or to say it in numbers: from "1000 times the age of the universe" to "5 seconds"
but all this only with a given probability -- a quantum computer is not a deterministic device, so don't imagine firing up mozilla on your brand new QC
QCL (Score:5, Informative)
The documentation that comes with it is really interesting, and gives some good insights into how quantum computing works and how to write programs for a quantum computer.
Re:Quantum Computing... (Score:2, Informative)
from the wikipedia article
"A yottahertz (YHz) is a unit of frequency equal to a septillion hertz or a thousand zettahertz. "
http://en.wikipedia.org/wiki/Yottahertz [wikipedia.org]
10^24
Re:NP-complete problem solver? (Score:4, Informative)
A little searching on arXiv.org [arxiv.org] brought up:
Quantum Algorithm for SAT Problem and Quantum Mutual Entropy [arxiv.org]
So at least the first half of that title relates to your question.
Re:Quantum is just another buzzword (Score:3, Informative)
Re:got my hopes up (Score:4, Informative)
It sounds like what they're describing is actually a set of Josephson junctions. People think those might be able to be used a viable qubits; however, the trick is having and maintaining coherence. This is what allows quantum computation. From the description they give of this system, it sound like they're not concerned with long term coherence, only with using tunneling to perform a sort of "annealing" algorithm to find the lowest energy state. So I think the grandparent it right, this is not a quantum computer in the ordinary sense.
Re:Quantum is just another buzzword (Score:1, Informative)
Re:Speeds? (Score:4, Informative)
Clock speeds still do mean something in quantum computers. Arguably they're even more important than in classical computers, since in quantum computers you need to get operations done at least 10^4 times faster than the system's decoherence [wikipedia.org] time for quantum error correction to be robust. Decoherence times can be as short as microseconds, meaning that multiGHz operations could be important. Of course, if you're building a quantum computer, you want to work with a system with as long a decoherence time as possible....
Or how about getting a grip (Score:1, Informative)
The hardest problems are the family of non-computable "Busy Beaver" functions. Rather than being merely very hard, or intractable, they are actually non-computable. Indeed they measure the very boundaries of computation itself, so it's no surprise that they're larger than any other problem. (n) = 4, 6, 13, 4098* and then just keeps accelerating. [* subject to further discoveries]
"PKE is based on the idea that some math problems are harder to solve than to verify. Given a large enough quantum computer, that really is no longer the case."
There is no reason to believe that for any _finite_ Quantum computer, even the fiercest scientific proponents of quantum computing do no more than "suppose" that it might be true, mainstream thought in this area is that BQP is clearly smaller than NP, and therefore some problems which are worse than polynomial time problems on a classical computer are also worse than polynomial time on a quantum computer, despite the fact that they can be verified in polynomial time on both machines.
Re:Quantum is just another buzzword (Score:3, Informative)
Re:Solve the travelling salesmen problem in second (Score:4, Informative)
See, the problem in quantum computing is that you can have multiple states in parallel, but you can only 'read' one and lose all other states. This is like having a book with 400 pages, but when you open it, it selects (with a certain probability) a specific page and the whole book becomes that page, you lose all other pages.
We need to make the system converge/interfere in a meaningful way to the correct solution, and in its own way, this is the challenge of QC. In the end, if our algorithm works, we will be able to get the answer to the travelling salesman problem with a probability (depending how good our convergence is). Just like our book above, we need to increase the chance of opening the book on the page with the correct solution. This is non-trivial.
The thing is, the 'weight' of that convergence/meaningful interference, in problems like the travelling salesman, is usually as high as the time it takes to run the normal algorithm in classical computing. We end up not having much gains, it's not that fast. So, yes, if they are that good, we can solve the travelling salesman dilema in seconds... with a certain, probably very low %. Probably even a meaningless %.
However, in problems like finding if a function is unanimous(f(x)=0 or f(x)=1 for all x) or balanced (f(x)=0 for exactly half of x and f(x)=1 for exactly the other half of x) could be done in quantum computer with no errors and very fast, while in classical computing you'd have to try each value of x. If you however allow a certain % of error, the classical way with a stochastic computer would work best (test only a certain pool of value).
Re:Total Agreeness (Score:3, Informative)
By the way, it's extremely false myth that Einstein was bad at math.
Re:Quantum is just another buzzword (Score:3, Informative)
(2) Some things are deterministic, even in quantu m mechanics. There are times when a particle will have exactly one energy, for example. Without you knowing quantum mechanics, I can't construct an example of this for you, but I assure you it is possible. There is one case that I can argue that I think you will find plausible (and is also related to point (1)): imagine a particle that can be in one of two wells (just holes in the ground if you would like to think of them that way): call them the left state or the right state. Now, apply an elecric field, a really strong one. If the particle is charged (and low in energy), it will move almost entirely to the right well (if that's the direction the electric field "pushes"). Only a very small amount stays in the left state. So one can get arbitrarily deterministic results this way.
The techniques in quantum computing are a little more complicated, but not entirely fundamentally different.
Re:Solve the travelling salesmen problem in second (Score:2, Informative)
This is parially true, and is exploited in Shor's factoring algorithm. But note that Shor's algorithm would not work if it relied only on doing brute force calculations in parallel. Shor's algorithm works because it reduces the problem of factorization to a series of steps that can be done in parallel, then passed through the QFT to yeild the correct result with high probability. You could not, on a quantum computer, factor a large number by trying all combinations of numbers in parallel, because you would have no way (at least no way that is known) to arrive at the answer with high probability...you would just get some random answer as you described in your book analogy.
The point here is that no one has been able to reduce an NP problem to a series of steps that can be run in parallel on a quantum computer to yield an answer with high probability. If you can do this, you will be very rich and famous