If a public company is having this success, can we assume that certain shadier (government) organisations are already ahead of the game and are routinely cracking public key cryptography?

# D-Wave wins the quantum-classical horse race, kind of

It's official, it seems: the D-Wave isn't a “real” quantum computer, but it does handle some classes of problems a lot faster than a classical desktop computer. That's the result of the first attempt to benchmark the company's adibiatic quantum computer, but it comes with caveats. But first, some background. D-Wave is a …

No we can't because this isn't a quantum computer, it's an analog computer doing annealing problems which does not help in factorization at all.

*something quantum-like is happening in the D-Wave*

Sounds like a sprinkle of magic dust from the sales department. If "something quantum-like" is happening, what is it? What is the Hamiltonian? Where are the undead cats?

Note also that

*The tests were run on various problems that fall into the NP-Hard category*

sounds fishy this context - Quantum computers are NOT better than classical computers at solving (i.e. finding the best solution to) those kind of problems. However, optimization algorithms (and specially designed analog computers) may *more quickly* find a *approximate* solution, though not the optimal one. A good chunk of the "neural network" computers do that kind of optimization. Of course, there are problems in which even finding an approximately good solution is unfeasible.

Maybe one should write

*something neural-network-like is happening in the D-Wave*

but that's too 80s.

#### In general

If a company or an individual claims some scientific breakthrough, it's safe to expect it's a hoax. Companies only very rarely provide an environment to foster innovation. Although it may be possible for a company to have a breakthrough, it's very unlikely that they research in that direction and are able to research.

*Factoring is almost certainly not NP Hard.*

Right. And for those reading along at home, Shor's algorithm, cited by Eadon as a quantum algorithm for improved performance on NP Hard problems, is an integer-factoring algorithm, and is thus almost certainly irrelevant to the claim that QC offers improved performance on NP Hard problems.

The arXiv link in Eadon's second post is a bit better - it claims sub-exponential growth in time and energy for certain AQC (adiabatic quantum computation) algorithms for NP-Complete problems (specifically TSP, but they're all isomorphic anyhoo). It looks a lot better than the D-Wave press release (it's all about the Hamiltons, as DAM requested), but I admit I just read the abstract and skimmed a couple of pages, and I have no idea what's been done since the paper was written (2006) in this area.

**But:** Solving NP-Complete problems quickly is no guarantee of faster performance on NP-Hard ones, in general. An NP-Hard problem can be derived in PTIME from an NP-Complete problem - not the other way around. NP-Hard problems are potentially "harder" than anything in NP. NP-Complete is "the worst of NP", informally; NP-Hard is "NP-Complete and worse stuff". The Halting Problem is NP-Hard but not NP-Complete.

Also, remember that stuff in PTIME may still take an infeasible amount of time (and ditto storage for stuff in PSPACE). Matt Skala wrote a joke once in his comic strip about a PTIME algorithm of ridiculously large order - I don't recall the exponent but it was so big that any non-trivial problem was going to be intractable - and then mentioned in the comments that it was based on a real algorithm he'd discovered, which did something useful (clustering points in n-space, I think) in theory, but not of course in practice.

Given the published research I've seen on QC, adiabatic and otherwise, I'm inclined to think DAM is correct: D-Wave have an analog computer that's optimized for certain kinds of problems. Analog machines can converge very quickly on probably-correct solutions for many sorts of problems. Often they're limited more by space requirements than time requirements (as with eg Adleman's DNA computation experiment).