Hacker News Reader

Comment by w0000t | Hacker News Reader

http://www.dwavesys.com/press-releases/d-wave-systems-breaks...

This announcement, claims:

Every additional qubit doubles the search space of the processor. At 1000 qubits, the new processor considers 2^1000 possibilities simultaneously, a search space which dwarfs the 2^512 possibilities available to the 512-qubit D-Wave Two.

Since we still aren't able to factor any large numbers with it, those 2^1000 bits don't really work like they say they do. I'm guessing there are many caveats behind their description.

I would appreciate any explanation from an expert.

View on HN

The D-Wave computer is called a quantum computer because it uses some quantum properties when running a simulated annealing kind of algorithm (which is a well known classical algorithm so find sub-obtimal solutions to combinatorial problems, aka NP-Complete problems). But it is NOT a universal quantum computer in which one could run Shor's or Groover algorithms. In order to do that, you need to keep a quantum system with entangled qubits, something that is extremely difficult to achieve due to quantum decoherence, etc.

So, saying that "the new processor considers 2^1000 possibilities simultaneously" is basically a ton of bullsh. Even a real quantum computer cannot do that effectively.

Nevertheless, I think D-Wave is doing a great work and is definitely taking steps towards a real QC.

It is not a conventional quantum computer. You cannot use it to factor numbers. You use it to find approximate solutions to optimization problems.

Well, I will tell one relevant problem that can be annihilated with this: ads placement. Google advertisement adwords is all based on a auction mechanism at the end of which you have to find the best allocation of ads to bidders (to slots) - which has an evident combinatorial nature, to find optimum you should try all possibile combinations. This is typically solved in approximated ways. It may not be a "conventional quantum computer" but it's pretty usefull anyway:) I can't wait to toy with one..

So in a way it's similar to the analog computers that were around for decades (or, really, for millennia). It's just smaller and faster than most.

https://en.wikipedia.org/wiki/Analog_computer

The statement is also a common fallacy that Scott Aaronson has addressed many times. While some exponential speedups are possible, there are no indications that they are possible in general for problems in NP, and even if they were, we know that they would have to use the structure of the problem and not merrely "consider possibilities simulatenously"

I also would love to hear someone who works in the space explain this.

The paper is pretty accessible:

http://www.dwavesys.com/sites/default/files/ttt_arxiv_v1.pdf

The money quote:

"a D-Wave computation is both quantum and analog, with nothing resembling a discrete instruction or basic operation that can be counted"

So it's not really a quantum computer at all in the sense that the term is usually understood nowadays. It's an analog computer. And if you believe Scott Aaronson (and I do) it's a classical analog computer.

Reply on news.ycombinator.com