Most inaccurate media number ever?
In 2012, the Telegraph and other UK papers were off by five orders of magnitude when they said there were only 100 adult cod in the North Sea. The Washington Post beats that easily.
Quantum computers are straight out of science fiction. Take the “traveling salesman problem,” where a salesperson has to visit a specific set of cities, each only once, and return to the first city by the most efficient route possible. As the number of cities increases, the problem becomes exponentially complex. It would take a laptop computer 1,000 years to compute the most efficient route between 22 cities, for example. A quantum computer could do this within minutes, possibly seconds.
As mathematician Bill Cook pointed out on Twitter, his iMac can solve a 22-city problem in 0.005 seconds, roughly six trillion times faster than the Washington Post claims. It looks as though the writer has assumed there is no more efficient algorithm than just trying all the possible routes, one at a time. At one billion attempts per second, that would take on the order of a thousand years. In fact, there are more efficient algorithms, it’s just that these algorithms also get very slow as the number of points increases. Prof Cook estimates in the twitter thread that 1000 CPU-years might allow a 100,000-point problem to be solved: six trillion times more computing gets you only a 5000-fold increase in the number of points.
For the cryptographic problems that are the actual point of the story, fast quantum algorithms are known. If large enough quantum computers can be built, these security protections are toast. And as the story says, there’s research going on now to find replacements if/when they’re needed (though what the story says about those algorithms is almost completely unhelpful). But the travelling salesman problem is not one of the ones for which fast quantum algorithms are known. On the contrary, there are reasons to suspect fast quantum algorithms don’t even exist for “NP-complete” problems such as the travelling salesman.
Update: Scott Aaronson, who knows from quantum, is Not Impressed.
Thomas Lumley (@tslumley) is Professor of Biostatistics at the University of Auckland. His research interests include semiparametric models, survey sampling, statistical computing, foundations of statistics, and whatever methodological problems his medical collaborators come up with. He also blogs at Biased and Inefficient See all posts by Thomas Lumley »
Its strange that the article would get it wrong as its not just specialist writer at WaPo but a Professor at ‘Carnegie Mellon University Engineering at Silicon Valley’ . Comments in the article seem to suggest hes confused about some other other computing terms such as RSA.
6 years ago
Interestingly, in the comments below the blog post of Scott Aaronson, the author of the Washington Post article, Vivek Wadwha claims that his example of traveling salesman was taken from Michelle Simmons, who is a “director at the Centre for Quantum Computation and Communications Technology (CQC2T)” – she is quoted in the following ZDNet article: http://www.zdnet.com/article/australias-ambitious-plan-to-win-the-quantum-race/
>> Simmons said today organisations are faced with what is called the travelling salesman problem — a dilemma near impossible in the classical computing world.
“This is a real problem companies face to try and minimise their fuel costs, or optimise their distribution systems,” Simmons explained. “This is one example … where massively paralleled computing, if it comes in, will start to solve that in real-time.”<<
Therefore, I wouldn't blame him – Simmons is a professor of quantum computing.
6 years ago