# D-Wave promises chip that could search the whole universe

The 1,000-qubit chip promised by D-Wave last year has landed. The 1,000-plus-qubit device was originally planned for the end of 2014. The doubling of qubits over its previous processor, the company says, gives it a 21000 search space – not only dwarfing the previous 2512 search space, but containing “far more possibilities …

1. The qubit count is up (better than double, it's 125% more) and the performance is supposedly better (colder, less noise), so I'd like to see some action with this. Let's see it do something that the classical computing naysayers can't. Let's see Google/Lockheed/NASA use it for more than just tests to see if it works at all.

1. You left out NSA and GCHQ, I'm sure that they are active customers as well. Searching more than the observable universe sounds exactly like something they would be doing (maybe the CIA will buy a few dozen as well). But they will probably just stick to what they are currently doing, running Shor's Algorithm.

1. #### Well now...

Better Shor's Algorithm than Zola's

If there was any real chance of them getting 1000 qubits working, the interest level would be about 1000 times higher than it is.

3. Am I right in thinking that the largest factorisation carried out on a quantum computer using Shor's algorithm remains at 4 qubits (143 = 11 x 13)? How about a real challenge, 4,288,678,063 (65,479 × 65,497)?

4. #### Lets see it working then

So, if I had one of these devices in front of me now and I set it to solve a 1000-node travelling salesman problem, would it be able to spit the answer straight back?

1. #### Re: Lets see it working then

So, if I had one of these devices in front of me now and I set it to solve a 1000-node travelling salesman problem, would it be able to spit the answer straight back

As I understand it, a perfect 1024-qubit quantum computer ought to be able to do that. (My own belief is that our attempts to build such a device will always fail, and will tell us something interesting about the nature of the universe once the reasons for failure are well-understood).

Clearly these devices are imperfect. I think there's some debate over whether they are actually quantum computers at all in any meaningful sense. But if they can outperform a conventional compute cluster eating a few megawatts and as much financial capital as it takes, I should think that's good enough for the time being.

1. #### Re: Lets see it working then

Actually, quantum computers are not known to be able to solve NP-Complete problems (e.g travelling salesman) in polynomial time. There is a small number of problems for which the only known polynomial-time algorithms are for quantum computers; but these problems are not NP-Complete.

2. #### Re: Lets see it working then

No, quantum computers are only known to do better than classical computers in some quite special situations, and NP-complete problems (such as travelling salesman) are not one of those situations (in fact, the belief, although there isn't much evidence, is that they don't gain much for such problems). However some of the problems they are known to do better on are game-changingly important, such as factorisation (read: working quantum computation blows away much of the cryptographic basis for e-commerce).

What D-Wave promise is not a general purpose quantum computer, though - even if it meets their claims, it is not known possible to (and probably it is not possible to) run Shor's algorithm (the factorisation thing). It does some things which are potentially useful, what's maybe more important is that a different design using the same ideas might do more (assuming it works...). What's interesting is they try to sidestep a big problem 'decoherence' with the standard academic approach to building general purpose quantum computers. It's not clear if this is even theoretically possible, but they are going for the try-and-find-out approach rather than trying to work on the theory.

What seems to be clear is that there is something quantum going on in the current versions: there is definitely entanglement, the problem they want to solve definitely gets solved, and it seems reasonable to believe this solution really comes out of a quantum effect. Which is pretty cool. But, there is also (at least for now) quite a lot of reason to believe that this specific quantum effect is something a classical computer can simulate efficiently (there is a known algorithm whose performance appears to be similar, it's not easy to be definite due to a mixture of D-Wave holding trade secrets and that we don't really know how to look at the workings of the chip even if we wanted to). What is certainly true is that the results aren't anything to write home about in terms of computational power. Unless you're reading this on a cheap mobile phone, then you have more computational power in your hands than anything D-Wave demonstrated. Of course, as they point out, you also have more power (by a much greater factor) than the Colossus machines had, and quantum computing today probably should be compared to that.

1. #### @PeteMaths

Thanks for the detailed and helpful post - the sort that makes ElReg worthwhile. If I may be permitted a quibble, it's a slight exaggeration to claim that "working quantum computation blows away much of the cryptographic basis for e-commerce".

Asymmetric ('public key') cryptography is mainly used for exchanging the secret keys - 99% of Internet cryptography is carried out using symmetric ('private key') methods, such as AES, and their effectiveness isn't affected by quantum computing. For the asymmetric part, there are numerous alternatives that don't use factorisation as their 'trapdoor' function (easy to do one way, hard to do the other), and at least some of these should be immune from exploitation using quantum computers.

So if there were working quantum computers powerful enough to break standard asymmetric crypto, we'd just need to implement a new algorithm for key exchange; There would be a problem if someone had captured lots of old, encrypted traffic (I wonder who might do that), as they would be able to decrypt it easily (rather than, as at present, with great difficulty).

5. #### Can it compute?

So can we see it actually doing something? Just for fun?

<see title>

7. #### To steal & butcher a well-known phrase...

... I reckon that any quantum computer indistinguishable from a conventional one is... not all that "quantum" at all. Successfully doing something intractable by conventional means would go a long way towards credibility here - "we got 42 out of the machine, let's quickly find a question that fits that answer and pretend we asked it" doesn't really cut it...

8. #### The true test.

How well will it run Crysis?

1. #### Re: The true test.

It'll finish every level with a perfect score in every possible way simultaneously.

Still won't manage to do it on very high quality though.

9. If something is so much better, to the extent that a user really can't tell whether it's actually any better or not (apart from costing a fortune, looking techy and "What Qbit" liking it), to make viable commercial sense of their business model the manufacturer should really branch out into building audiophile hi-fi equipment ...

10. #### Factor some public keys already. Geesh.

It would be trivial to prove that these things actually work.

As far I know, they've not bothered to prove it yet.

Stinks.

1. #### Re: Factor some public keys already. Geesh.

I don't think a quantum annealer can run Shor's algorithm

1. #### Re: Factor some public keys already. Geesh.

Correct (about quantum annealers) and (as pointed out above) the largest number currently to have been factorised by a quantum computer (using Shor) is 143. Some way to go before we have to worry about RSA-4096.

11. #### Laundry?

Can we expect the manufacturers to receive a visit from Bob Howard *before* their evil devices open up a hole in the universe and let the Great Old Ones snack on our brains?

If you can do amazing things with a Palm Pilot just think what these can do..

12. #### Meanwhile...

machine: "@!#?@!"

user: "My word! This quantum computer is swearing at me."

IT: "Let's have a look. Ah, I see the problem. You got the 1000 Q*bert model, not the 1000 qubit one."

13. #### So I started wondering if it could potentially mine bitcoins really really fast...

I know better than to post lay speculation where experts hang out, so I googled it and answerd my own question with "No". I dare say a lot of you already knew that, but for everyone else, a very detailed answer why, which frankly went way over my head can be found here:

http://www.bitcoinnotbombs.com/bitcoin-vs-the-nsas-quantum-computer/

14. #### Still can't write a fucking sentence though

Honestly,

"the most complex superconductor integrated circuits ever successfully yielded"

Yielded? - did they break it in half or something?

Oh, and it's "integrated circuit" not circuits.

Let's hope it's clever enough to teach the ignorant bastards some grammar.

1. #### Re: Still can't write a fucking sentence though

Far be it from me to do down a bit of pedantry but in the context 'Oh, and it's "integrated circuit" not circuits' is wrong. The context is that the sentence starts with "The processors". So circuits needs to be plural to match.

15. #### factoring and beer...

This is not "quantum computing as we know it, Jim".

In other words, it is definitely a really good fridge, but only possibly a quantum computer.

P.

16. #### Calling it a 1000 qubit board is flatly false

The last time I looked, the world's verified record number of qubits in a single entanglement was 13. The number of superimposed states in a 13 qubit entanglement is 8192.

To call it a 1000 qubit board, the board should be able to superimpose 1000 qubits in a single entanglement. The number of superimposed states in a 1000 qubit entanglement would be about 10 raised to the 301 power superimposed states.

In other words the following number would be about the number of superimposed states in our 1000 qubit entanglement, about 1 with 301 zeros after it:

10,715,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000

Is this what the DWave board does? I think not.

17. #### More Confused by the Day

I know I'm far from alone in this, but all this quantum computer stuff seems to get more confusing by the day:

* On the one hand, half the articles I read seem to treat Quantum Computing as a barely more than theoretical concept, with talk of quantum entangled particles and our old mates Alice & Bob simultaneously observing the same effects at opposite sides of the globe.

* On the other hand, the other half of the articles I read [like this one] seem to be suggesting Quantum computing is real and here today and manufacturers are actually building multi-qubit processors which will be "coming to a gadget near you, soon!"

Anyone know what's really going on?

1. #### Re: More Confused by the Day

> Anyone know what's really going on?

It's uncertain. We can know the speed of a quantum computer or its current position in the supply chain, but not both.

18. Were we able to fold proteins before the Dwave 512. I've poured through all news pertaining to the Dwave on a weekly basis since there 8 qubit machine. It was years after the folding of a protein that I believe the Dwave 512 was instrumental in accomplishing was completed before I learned of anything the Dwave had had been used for. Nassa has had A.I. hooked to 512 for years and if I was to guess they more then likely have it hooked to the 2048 chip Dwave was boasting about earlier in the year. The point is, ever since Lockheed Martin became involved the Dwave has been the bullseye for disinformation and secrecy.

## POST COMMENT House rules

Not a member of The Register? Create a new account here.