Quantum Computing Is Real, and D-Wave Just Open-Sourced It (Wired)

Actually finding the global minimum of a QUBO problem is NP-hard for classical computers, but we seem to have effective algorithms for classical computers that *usually* give *reasonable* approximations of the minimum in reasonable time. (Though in the case of QUBO I don't think we know just how good the approximation is; nor do we know how to test if a particular solution is the optimum. We know both of those things about polynomial-time approximations to some NP-Complete problems, such as the way to use the polynomial Minimum Spanning Tree algorithm to find an approximation to the Traveling Salesman that is no more than 2x the best possible)

Qbsolv's contribution is a portion of an overall QUBO algorithm that is useful to execute on classical computers: It first selects a sub-problem of a given QUBO; then, it uses any method (classical or quantum) to solve or approximate the solution to the sub-problem; finally, using that sub-problem solution, update the best solution to the whole QUBO, and repeat until a goal (specific value, or number of iterations) is reached. Either way, even if your solutions to the QUBO sub-problems are exact, this still does not have any guarantee of letting you arrive at the exact optimal solution to the full QUBO problem instance.

Thus, Qbsolv can be used as one step of a fully classical QUBO approximation, or together with D-Wave hardware, where the sub-problems are solved using Quantum Annealing. (or both; the paper discusses using D-Wave hardware gets a low-precision answer that "may not be global or even local optima"; pairing it with their tabu solver which runs on classical hardware is a "complementary" step)

(On the other hand, something like Qbsolv is critical for using D-Wave hardware effectively if your program sizes don't directly fit in the hardware, because it lets you repeatedly work on sub-problems which *do* fit in D-Wave, automatically)

Finally, I am a bit baffled by their "performance" section, which is all about running Qbsolv+tabu on classical hardware (not using any D-Wave hardware). They compare numbers gathered in 2012 on a "Pentium 2.83GHz" running Windows XP and compare it to numbers gathered in 2016(?) on a "Core i7 2.3GHz" on a MacBook Pro (unspecified OS, but we can assume MacOS), then announce the ratio of the times ("56% of the total wall-clock time") as though it was a useful number! I don't know about the availability of the code from the other paper ("Path relinking for unconstrained binary quadratic programming", http://leeds-faculty.colorado.edu/glover/438%20-%20Path%2...) — if they simply can't obtain a copy to run on their own hardware it's forgivable, but 4 years means useful advances in CPU throughput, compiler quality, etc., and it makes it harder to believe this is an "apples to apples" comparison.

I've followed the Arstechnica D-Wave coverage for years, and I've also seen a presentation at my employer (I work at a major HPC vendor) by D-Wave on how quantum computing is the future. I didn't expect the presentation to give me much to go on, but it was still infuriating.

It was an hour. 50 minutes were pure fluff about how quantum computing is going to revolutionize everything, comparing it to past historical changes in computing, etc. And implying D-Wave has built such a machine. The last 10 minutes included some very vague details and then questions, which went, essentially, unanswered. But they're revolutionizing everything by building a quantum computer!

Except they haven't done that. What they've built isn't a quantum computer as traditionally defined, and you can read a LOT of their stuff without ever knowing that.

While they've built something really cool, they try really hard to make people believe it's something it isn't, and... ugh. Their degree of spin turns me off, badly.