9 ms·

Review of Vivek Wadhwa’s Washington Post Column on Quantum Computing

64 points by jashkenas 9y ago

dvfjsdhgfv 9y ago
A very interesting exchange in the comments section. I actually find Vivek Wadhwa's explanations (in the comments) reasonable and convincing. He seems like a honest guy who did the homework and asked the right people (contrary to what he's accused of) BUT he didn't give them the final version of the article to read so that they could correct errors and misunderstandings. This is actually common practice and I hate it - they interview you, you do your best explaining what you're asked, and then you see it in print completely skewed. Technically, sometimes these are your own words, but taken out of context they make little sense or can just be completely wrong. That's the case here, I think. In light of Vivek Wadhwa's responses, Aaronson's attack seems really petty. I'd love to read a technical summary of all mistakes made by Wadhwa though.
- tptacek 9y ago
  Aren't there really basic things that are wrong with Wadhwa's article? For instance, "quantum supremacy" doesn't mean "finally building a quantum computer that is more powerful than any existing supercomputer". For that matter, isn't it really misleading to suggest that a "50 qubit" IBM prototype would even be of the same practical utility as existing computers of any sort, from supercomputers to iWatches? The cryptographic content of the article gets even worse from there. I don't think it's "petty" to call out someone as high-profile as Vivek Wadhwa for apparently taking to the pages of the Washington Post to write about a topic he has no conversance with at all.
- emtel 9y ago
  Here is a direct quote from one of Vivek's comments: "Please give me 1-2 sentences that your children could understand that explains the possibilities of quantum computing and I will use these in future articles. I acknowledge that I am not as smart as most of you are. I struggle with the concepts of quantum computing, these just don’t make sense to me." Is there any other field in which someone would profess complete ignorance about a topic, and go on to write about it in a national newspaper anyway?
  - bb611 9y ago
    > Is there any other field in which someone would profess complete ignorance about a topic, and go on to write about it in a national newspaper anyway? Yes, this happens in every field. This isn't a problem specific to computing, it's specific to journalism.
    - emtel 9y ago
      I don't think so. Yes, journalists make errors in every field, sometimes big ones. What's weird here is the professed ignorance. You won't find a middle east correspondent saying "I'm sorry, could you give me 1-2 sentences on the difference between Sunni and Shia again? I just can't understand this stuff."
      - dvfjsdhgfv 9y ago
        "These are two sects of Islam fighting with each other for centuries, mainly over dogmatic issues: all Muslims believe in the Sunnah, but for the Sunni the Sunnah is of primary importance. There are also other differences between the two." This is what I'd explain to a child, and I believe it's more or less correct. Once they get more interested, they'll be able to consult more precise although less accessible descriptions.
        gus_massa 9y ago
        The problem is that this looks like an explanation but it doesn't explain anything, After reading it, the reader is as confused as before. For example, if you replace "Sunnah" with "Jesus" this is an explanation of the difference between Muslim and Christians.
  - shaki-dora 9y ago
    I would take Vivek's line to indicate not "ignorance" but humility, or, possibly, a slightly sarcastic jab at what he may perceive as arrogance from his critics. There's also a difference between complete ignorance, and the ability to perfectly frame a field's possible impact in language that the general public can understand. Considering that he is unlikely to be so humbled by this experience to immediately change careers, the wish to improve journalism may be best channeled not at trying to take this guy down, but to actually acquiesce and simply provide him that summary he is asking for. I, for one, would be interested.
- openasocket 9y ago
  I'm honestly hard pressed to find something in his post that IS accurate. I'd also add that he said in the comments that "I’ll start by admitting that I struggle with the concepts of quantum computing." If you don't fundamentally understand quantum computing, maybe you shouldn't write an Opinion piece about the future of quantum computing.
- j45 9y ago
  Vivek's polite mic drops in the comment threads were enjoyable to read for the same reason. He was one of the few people I recall following on Twitter. I was also surprised then by how accessible he was to chat with, as is shown in this.
RyanZAG 9y ago
> Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now? How does it happen that the Washington Post publishes a quantum computing piece filled with errors that would embarrass a high-school student doing a term project (and we won’t even count the reference to Stephen “Hawkings”—that’s a freebie)? I'd recommend reading the Washington Post with a bit more skepticism. You're only noticing their mistakes on this article because it's something you're familiar with, but they make many mistakes in their other articles too. You probably just don't pick it up as you're not an expert in those other fields, and it sticks out in this one like a sore thumb because you are.
- shaki-dora 9y ago
  If you find factual errors in article by the Washington Post you can submit those on their website. The policy is spelled out at https://www.washingtonpost.com/policies-and-standards/?utm_term=.5f4ed5bc94c3#correctionspolicy https://www.washingtonpost.com/policies-and-standards/?utm_t... and it includes provisions to correct errors across all channels of distribution, including alerts and social media posts. Corrections are prominently added at the top of the article. See https://www.washingtonpost.com/news/made-by-history/wp/2018/02/08/how-three-of-americas-biggest-companies-might-undo-decades-of-conservative-health-care-policy/ https://www.washingtonpost.com/news/made-by-history/wp/2018/... for an example.
  - RyanZAG 9y ago
    That sounds like crowdsourcing the core focus of the business then. The ability of people to point out factual errors should be kept for small details, not the all too common practice of posting articles without first getting them checked by experts. Why should unpaid experts have to go and spend hours posting corrections of the articles in Washington Post? Washington Post should be finding and paying experts to do this pre-publication. There needs to be some level of quality control at the Washington Post if they want to keep their reputation -- which they have tarnished very poorly since their push for the Iraq War and the role they had to making that war happen.
- ClintEhrlich 9y ago
shaki-dora 9y ago
I think the comments show a real desire on the author's part to learn about any possible inaccuracies in his editorial, and I would have wished for a slightly more constructive response by Scott. As it is, his main points seem to be: - The Y2K comparison, which, eventually, he seems to agree may indeed be accurate. - The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that it's inaccurate for TSP, but possibly right for problems that are better structured to use the technology(?) - An off-topic criticism of the author's previous article calling bitcoin a Ponzi scheme. That article may have been premature in its predictions, but seems accurate on the facts. Who would be miffed of being warned of a ponzi scheme too early? - That matrix multiplication bit, which indeed appears to be mostly gibberish. Although my take-away from the sentence would mostly be the existence of "quantum-resistant" algorithms, which seems accurate (and would also hint at the non-universality of the claims of speedups.) I guess Scott may be unwilling to "do the author's work for them", so to speak. And it's laudable that he mentions some of the good work the WP has been doing, instead of succumbing to the nihilistic cynicism so common these days. But for as long as someone is showing a good-faith effort to improve, I think it's worth for experts in a field to engage constructively with them. Quantum Computing is niche enough that it's entirely plausible that someone with plenty of expertise on computing and the best intentions could end up writing such an article just from a few misunderstandings in their communications with the experts they found.
- cycrutchfield 9y ago
  Scott's post was not meant to be an honest critique of Vivek's op-ed, as he alluded to by referencing the famous Pete Wells review of Guy Fieri's restaurant. It's intended to be a semi-humorous polemic.
- rspeer 9y ago
  > The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that it's inaccurate for TSP, but possibly right for problems that are better structured to use the technology(?) From what I gather from Scott's comments (and the tagline of his entire blog), this common explanation is basically always incorrect. Quantum algorithms do not try all solutions simultaneously. That's a description of the theoretical model of nondeterministic computing (like where "NP" comes from), not of quantum computing.
kirrent 9y ago
Interestingly, Vivek Wadhwa said that his source for quantum computing being useful for travelling salesman by trying all possibilities in parallel was from the researcher Michelle Simmons in a Ted talk. I decided to watch it to see how he'd misinterpreted it and he hadn't! From 4:30 Simmons brings out the laundry list of quantum computing misconceptions. These are that the TSP scales poorly for classical computers and implies it doesn't for QC, implies that there's an efficient quantum algorithm for list lookups because the list can be read in parallel, and says the power of QC is partially because you can store so much information in the superposition (which is, at the very least, misleading). Then she starts comparing the power of QC and classical computers, saying that a 300 bit QC would be more powerful than all the computers in the world put together. In a section that's about what quantum computers will be useful for she includes as examples economic and climate modelling, which is news to me. The slides even include the phrase - 'Quantum computer- can check many different possibilities in parallel'. All in all, I'm not surprised that Wadhwa was confused. https://www.youtube.com/watch?v=cugu4iW4W54 https://www.youtube.com/watch?v=cugu4iW4W54
- shaki-dora 9y ago
  > useful for she includes as examples economic and climate modelling, which is news to me These are just rather generic examples of computationally-expensive fields of study.
  - OscarCunningham 9y ago
    I don't think that there's any evidence at all that quantum computers will provide a speedup on generic problems.
cs702 9y ago
Well-run media outlets like the Washington Post face a difficult challenge: how to explain science to the general public, when both most editors and journalists and a majority of the general public are extremely poorly educated in the ways and language of science. This broad lack of education opens the door for people like Mr. Wadhwa to write articles about subjects like quantum computing that are wrong in many important ways, rankling people who actually know a lot about the subject, like Aaronson. Every article in a mainstream publication I've read on a technical subject about which I actually know something is wrong in important ways. I doubt there's a short-term solution for this problem.
- eru 9y ago
  The Economist usually does pretty well on science and technology. Not sure whether you count them as mainstream.
- smitherfield 9y ago
  I’ve been impressed (read: found few/no obvious factual errors, which puts it in a minority of one among non-industry-specific news services I read) by Bloomberg’s technology reporting lately.
Animats 9y ago
Oh, Wadhwa again. He promotes himself as an expert on a huge range of subjects. His real business was automatically upgrading COBOL programs for Y2K fixes; he did a startup for that.[1] Now he's a pundit. He has vague affiliations with various academic institutions, but he's not a real academic. The traveling salesman problem isn't hard. It's one of those things that's NP-hard only for pathological cases, as is linear programming. Solutions to the TSP which produce a near-optimum result, and the optimal result most of the time, are easy. (Connect nodes arbitrarily. Then randomly cut two links to split path into three sections, try all ways to reconnect the three sections, pick the best. Repeat until no improvement for a while. Bell Labs, 1960s.) Now, if quantum computing could help with factoring, we'd have a problem. [1] https://books.google.com/books?id=tTkEAAAAMBAJ&pg=PA40&lpg=PA40#v=onepage&q&f=false https://books.google.com/books?id=tTkEAAAAMBAJ&pg=PA40&lpg=P...
- MrMoenty 9y ago
  Well, funnily enough, quantum computing CAN help with factoring, and likely not with TSP. Factoring is one of those rare problems in NP that is not known to be NP-complete, but for which we also don't know a polynomial algorithm. In 1994, Peter Shor came up with a quantum algorithm that solves factoring in polynomial time [1]. On the other hand, it is generally not believed that quantum computers would be able to solve NP-complete problems such as TSP in polynomial time. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm
  - randomsearch 9y ago
    I think that was a joke...
    - jacquesm 9y ago
      I think he improved on it.
- eru 9y ago
  Linear programming is in P. Perhaps you are talking about Integer Linear Programming?
bobthechef 9y ago
To quote the ornery David Bentley Hart, “Journalism is the art of translating abysmal ignorance into execrable prose.” I find it odd that Scott holds the Pravda on the Potomac in such high esteem [0], though I have no personal animus toward Vivek, only the usual confusion about why journalists insist on expounding on topics they have no basic comprehension of. The mass media must always be read in the same spirit one might read a less vulgar version of the National Inquirer. In this regard, Vivek’s article does not depart in terms of quality from the standard fare of popular science books and magazines. [0] Crichton’s “Gell-Mann Amnesia” quote is fantastically apropos in this regard, and certain kinds of specialists ought to recall it so that it might temper snobbery and inspire a more charitable response. I can’t tell you how often specialists, often competent in their own narrow areas of expertise, produce some of the most absurd and ignorant nonsense ever put to paper when they falsely presume to have anything of value to say about topics outside of their fields.
whack 9y ago
Copy-pasting most of Vivek's response (from the above article's comments): ------------- Scott, I just watched your fascinating and excellent TedX talk and really appreciate your perspectives. I’ll start by admitting that I struggle with the concepts of quantum computing and found it very hard to simplify these. I have read your criticisms of journalists who have had the same issue and your frustrations with the deficiency. As far as the traveling salesman problem goes, the person I learned of this from, a few years ago is Michelle Simmons, director of the Centre for Quantum Computation & Communication Technology, University of NSW. This TedX talk that she gave was brilliant and I wrote to her to thank her for opening my eyes: https://www.youtube.com/watch?v=cugu4iW4W54 https://www.youtube.com/watch?v=cugu4iW4W54. She repeated this example in a recent piece in ZDNet: http://www.zdnet.com/article/australias-ambitious-plan-to-win-the-quantum-race/ http://www.zdnet.com/article/australias-ambitious-plan-to-wi... I also consulted a couple of other gurus and no one raised issue with this example. If you give me a better way of explaining how quantum computers work I will surely use that. But I find your comparison of this to my criticism of Bitcoin’s demise as a digital currency to be unprofessional and petty. Surely you don’t have to resort to such nastiness. ------------- That was a pretty great response, and he's right. Scott does come across as petty, and as someone you would never want to work with. Vivek might have been wrong, but he had done a reasonable amount of homework on this - far more than Scott had mistakenly assumed. This discussion would have been far more productive if Scott had dedicated a thousand words towards educating people about QC, rather than belittling someone personally.
- gone35 9y ago
  Scott does come across as petty, and as someone you would never want to work with. Please don't let his (admittedly sometimes aggressive, unabashed) writing style detract from the man himself. From personal experience, he's unfailingly generous, kind, and amazing to work with.
- mroll 9y ago
  Scott has poured many more than one thousand words into the cause of educating people about quantum computing. The point here is that this journalist didn't do his due diligence. Reading the tag line on Scotts blog would have made him question one of the core assumptions he made in his piece.
rdtsc 9y ago
Now I was wondering about TSP why it was mentioned at all and if there were any new results since I dabbled in quantum computing. It seems with some constraints on vertex degrees, which seems to be practical, it's possible to do have some speedup (not polynomial of course). For example https://arxiv.org/abs/1612.06203 https://arxiv.org/abs/1612.06203 claims O(1.3^N) for 4 nodes vs O(1.6^N) for classical. For example with N=500 that's 1e57 vs 1e102. But yeah still wouldn't have picked it as _the_ example to use. Not on topic but since Scott had to mention it... > Would you agree that the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance? Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now? No, no, I don't. They are better then MSNBC and CNN in that they do some actual legwork as opposed to talking about ice-cream scoops and extra long hand shakes, but certainly have gotten the "Russian hackers" fever and can't let go of it: https://theintercept.com/2017/01/04/washpost-is-richly-rewarded-for-false-news-about-russia-threat-while-public-is-deceived/ https://theintercept.com/2017/01/04/washpost-is-richly-rewar...

64 points by jashkenas 9y ago

A very interesting exchange in the comments section. I actually find Vivek Wadhwa's explanations (in the comments) reasonable and convincing. He seems like a honest guy who did the homework and asked the right people (contrary to what he's accused of) BUT he didn't give them the final version of the article to read so that they could correct errors and misunderstandings. This is actually common practice and I hate it - they interview you, you do your best explaining what you're asked, and then you see it in print completely skewed. Technically, sometimes these are your own words, but taken out of context they make little sense or can just be completely wrong. That's the case here, I think. In light of Vivek Wadhwa's responses, Aaronson's attack seems really petty. I'd love to read a technical summary of all mistakes made by Wadhwa though.

tptacek 9y ago
Aren't there really basic things that are wrong with Wadhwa's article? For instance, "quantum supremacy" doesn't mean "finally building a quantum computer that is more powerful than any existing supercomputer". For that matter, isn't it really misleading to suggest that a "50 qubit" IBM prototype would even be of the same practical utility as existing computers of any sort, from supercomputers to iWatches? The cryptographic content of the article gets even worse from there. I don't think it's "petty" to call out someone as high-profile as Vivek Wadhwa for apparently taking to the pages of the Washington Post to write about a topic he has no conversance with at all.
emtel 9y ago
Here is a direct quote from one of Vivek's comments: "Please give me 1-2 sentences that your children could understand that explains the possibilities of quantum computing and I will use these in future articles. I acknowledge that I am not as smart as most of you are. I struggle with the concepts of quantum computing, these just don’t make sense to me." Is there any other field in which someone would profess complete ignorance about a topic, and go on to write about it in a national newspaper anyway?
- bb611 9y ago
  > Is there any other field in which someone would profess complete ignorance about a topic, and go on to write about it in a national newspaper anyway? Yes, this happens in every field. This isn't a problem specific to computing, it's specific to journalism.
  - emtel 9y ago
    I don't think so. Yes, journalists make errors in every field, sometimes big ones. What's weird here is the professed ignorance. You won't find a middle east correspondent saying "I'm sorry, could you give me 1-2 sentences on the difference between Sunni and Shia again? I just can't understand this stuff."
    - dvfjsdhgfv 9y ago
      "These are two sects of Islam fighting with each other for centuries, mainly over dogmatic issues: all Muslims believe in the Sunnah, but for the Sunni the Sunnah is of primary importance. There are also other differences between the two." This is what I'd explain to a child, and I believe it's more or less correct. Once they get more interested, they'll be able to consult more precise although less accessible descriptions.
      - gus_massa 9y ago
        The problem is that this looks like an explanation but it doesn't explain anything, After reading it, the reader is as confused as before. For example, if you replace "Sunnah" with "Jesus" this is an explanation of the difference between Muslim and Christians.
- shaki-dora 9y ago
  I would take Vivek's line to indicate not "ignorance" but humility, or, possibly, a slightly sarcastic jab at what he may perceive as arrogance from his critics. There's also a difference between complete ignorance, and the ability to perfectly frame a field's possible impact in language that the general public can understand. Considering that he is unlikely to be so humbled by this experience to immediately change careers, the wish to improve journalism may be best channeled not at trying to take this guy down, but to actually acquiesce and simply provide him that summary he is asking for. I, for one, would be interested.
openasocket 9y ago
I'm honestly hard pressed to find something in his post that IS accurate. I'd also add that he said in the comments that "I’ll start by admitting that I struggle with the concepts of quantum computing." If you don't fundamentally understand quantum computing, maybe you shouldn't write an Opinion piece about the future of quantum computing.
j45 9y ago
Vivek's polite mic drops in the comment threads were enjoyable to read for the same reason. He was one of the few people I recall following on Twitter. I was also surprised then by how accessible he was to chat with, as is shown in this.

RyanZAG 9y ago

> Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now? How does it happen that the Washington Post publishes a quantum computing piece filled with errors that would embarrass a high-school student doing a term project (and we won’t even count the reference to Stephen “Hawkings”—that’s a freebie)? I'd recommend reading the Washington Post with a bit more skepticism. You're only noticing their mistakes on this article because it's something you're familiar with, but they make many mistakes in their other articles too. You probably just don't pick it up as you're not an expert in those other fields, and it sticks out in this one like a sore thumb because you are.

shaki-dora 9y ago
If you find factual errors in article by the Washington Post you can submit those on their website. The policy is spelled out at https://www.washingtonpost.com/policies-and-standards/?utm_term=.5f4ed5bc94c3#correctionspolicy https://www.washingtonpost.com/policies-and-standards/?utm_t... and it includes provisions to correct errors across all channels of distribution, including alerts and social media posts. Corrections are prominently added at the top of the article. See https://www.washingtonpost.com/news/made-by-history/wp/2018/02/08/how-three-of-americas-biggest-companies-might-undo-decades-of-conservative-health-care-policy/ https://www.washingtonpost.com/news/made-by-history/wp/2018/... for an example.
- RyanZAG 9y ago
  That sounds like crowdsourcing the core focus of the business then. The ability of people to point out factual errors should be kept for small details, not the all too common practice of posting articles without first getting them checked by experts. Why should unpaid experts have to go and spend hours posting corrections of the articles in Washington Post? Washington Post should be finding and paying experts to do this pre-publication. There needs to be some level of quality control at the Washington Post if they want to keep their reputation -- which they have tarnished very poorly since their push for the Iraq War and the role they had to making that war happen.
ClintEhrlich 9y ago

shaki-dora 9y ago

I think the comments show a real desire on the author's part to learn about any possible inaccuracies in his editorial, and I would have wished for a slightly more constructive response by Scott. As it is, his main points seem to be: - The Y2K comparison, which, eventually, he seems to agree may indeed be accurate. - The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that it's inaccurate for TSP, but possibly right for problems that are better structured to use the technology(?) - An off-topic criticism of the author's previous article calling bitcoin a Ponzi scheme. That article may have been premature in its predictions, but seems accurate on the facts. Who would be miffed of being warned of a ponzi scheme too early? - That matrix multiplication bit, which indeed appears to be mostly gibberish. Although my take-away from the sentence would mostly be the existence of "quantum-resistant" algorithms, which seems accurate (and would also hint at the non-universality of the claims of speedups.) I guess Scott may be unwilling to "do the author's work for them", so to speak. And it's laudable that he mentions some of the good work the WP has been doing, instead of succumbing to the nihilistic cynicism so common these days. But for as long as someone is showing a good-faith effort to improve, I think it's worth for experts in a field to engage constructively with them. Quantum Computing is niche enough that it's entirely plausible that someone with plenty of expertise on computing and the best intentions could end up writing such an article just from a few misunderstandings in their communications with the experts they found.

cycrutchfield 9y ago
Scott's post was not meant to be an honest critique of Vivek's op-ed, as he alluded to by referencing the famous Pete Wells review of Guy Fieri's restaurant. It's intended to be a semi-humorous polemic.
rspeer 9y ago
> The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that it's inaccurate for TSP, but possibly right for problems that are better structured to use the technology(?) From what I gather from Scott's comments (and the tagline of his entire blog), this common explanation is basically always incorrect. Quantum algorithms do not try all solutions simultaneously. That's a description of the theoretical model of nondeterministic computing (like where "NP" comes from), not of quantum computing.

kirrent 9y ago

Interestingly, Vivek Wadhwa said that his source for quantum computing being useful for travelling salesman by trying all possibilities in parallel was from the researcher Michelle Simmons in a Ted talk. I decided to watch it to see how he'd misinterpreted it and he hadn't! From 4:30 Simmons brings out the laundry list of quantum computing misconceptions. These are that the TSP scales poorly for classical computers and implies it doesn't for QC, implies that there's an efficient quantum algorithm for list lookups because the list can be read in parallel, and says the power of QC is partially because you can store so much information in the superposition (which is, at the very least, misleading). Then she starts comparing the power of QC and classical computers, saying that a 300 bit QC would be more powerful than all the computers in the world put together. In a section that's about what quantum computers will be useful for she includes as examples economic and climate modelling, which is news to me. The slides even include the phrase - 'Quantum computer- can check many different possibilities in parallel'. All in all, I'm not surprised that Wadhwa was confused. https://www.youtube.com/watch?v=cugu4iW4W54 https://www.youtube.com/watch?v=cugu4iW4W54

shaki-dora 9y ago
> useful for she includes as examples economic and climate modelling, which is news to me These are just rather generic examples of computationally-expensive fields of study.
- OscarCunningham 9y ago
  I don't think that there's any evidence at all that quantum computers will provide a speedup on generic problems.

cs702 9y ago

Well-run media outlets like the Washington Post face a difficult challenge: how to explain science to the general public, when both most editors and journalists and a majority of the general public are extremely poorly educated in the ways and language of science. This broad lack of education opens the door for people like Mr. Wadhwa to write articles about subjects like quantum computing that are wrong in many important ways, rankling people who actually know a lot about the subject, like Aaronson. Every article in a mainstream publication I've read on a technical subject about which I actually know something is wrong in important ways. I doubt there's a short-term solution for this problem.

eru 9y ago
The Economist usually does pretty well on science and technology. Not sure whether you count them as mainstream.
smitherfield 9y ago
I’ve been impressed (read: found few/no obvious factual errors, which puts it in a minority of one among non-industry-specific news services I read) by Bloomberg’s technology reporting lately.

Animats 9y ago

Oh, Wadhwa again. He promotes himself as an expert on a huge range of subjects. His real business was automatically upgrading COBOL programs for Y2K fixes; he did a startup for that.[1] Now he's a pundit. He has vague affiliations with various academic institutions, but he's not a real academic. The traveling salesman problem isn't hard. It's one of those things that's NP-hard only for pathological cases, as is linear programming. Solutions to the TSP which produce a near-optimum result, and the optimal result most of the time, are easy. (Connect nodes arbitrarily. Then randomly cut two links to split path into three sections, try all ways to reconnect the three sections, pick the best. Repeat until no improvement for a while. Bell Labs, 1960s.) Now, if quantum computing could help with factoring, we'd have a problem. [1] https://books.google.com/books?id=tTkEAAAAMBAJ&pg=PA40&lpg=PA40#v=onepage&q&f=false https://books.google.com/books?id=tTkEAAAAMBAJ&pg=PA40&lpg=P...

MrMoenty 9y ago
Well, funnily enough, quantum computing CAN help with factoring, and likely not with TSP. Factoring is one of those rare problems in NP that is not known to be NP-complete, but for which we also don't know a polynomial algorithm. In 1994, Peter Shor came up with a quantum algorithm that solves factoring in polynomial time [1]. On the other hand, it is generally not believed that quantum computers would be able to solve NP-complete problems such as TSP in polynomial time. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm
- randomsearch 9y ago
  I think that was a joke...
  - jacquesm 9y ago
    I think he improved on it.
eru 9y ago
Linear programming is in P. Perhaps you are talking about Integer Linear Programming?

bobthechef 9y ago

To quote the ornery David Bentley Hart, “Journalism is the art of translating abysmal ignorance into execrable prose.” I find it odd that Scott holds the Pravda on the Potomac in such high esteem [0], though I have no personal animus toward Vivek, only the usual confusion about why journalists insist on expounding on topics they have no basic comprehension of. The mass media must always be read in the same spirit one might read a less vulgar version of the National Inquirer. In this regard, Vivek’s article does not depart in terms of quality from the standard fare of popular science books and magazines. [0] Crichton’s “Gell-Mann Amnesia” quote is fantastically apropos in this regard, and certain kinds of specialists ought to recall it so that it might temper snobbery and inspire a more charitable response. I can’t tell you how often specialists, often competent in their own narrow areas of expertise, produce some of the most absurd and ignorant nonsense ever put to paper when they falsely presume to have anything of value to say about topics outside of their fields.

whack 9y ago

Copy-pasting most of Vivek's response (from the above article's comments): ------------- Scott, I just watched your fascinating and excellent TedX talk and really appreciate your perspectives. I’ll start by admitting that I struggle with the concepts of quantum computing and found it very hard to simplify these. I have read your criticisms of journalists who have had the same issue and your frustrations with the deficiency. As far as the traveling salesman problem goes, the person I learned of this from, a few years ago is Michelle Simmons, director of the Centre for Quantum Computation & Communication Technology, University of NSW. This TedX talk that she gave was brilliant and I wrote to her to thank her for opening my eyes: https://www.youtube.com/watch?v=cugu4iW4W54 https://www.youtube.com/watch?v=cugu4iW4W54. She repeated this example in a recent piece in ZDNet: http://www.zdnet.com/article/australias-ambitious-plan-to-win-the-quantum-race/ http://www.zdnet.com/article/australias-ambitious-plan-to-wi... I also consulted a couple of other gurus and no one raised issue with this example. If you give me a better way of explaining how quantum computers work I will surely use that. But I find your comparison of this to my criticism of Bitcoin’s demise as a digital currency to be unprofessional and petty. Surely you don’t have to resort to such nastiness. ------------- That was a pretty great response, and he's right. Scott does come across as petty, and as someone you would never want to work with. Vivek might have been wrong, but he had done a reasonable amount of homework on this - far more than Scott had mistakenly assumed. This discussion would have been far more productive if Scott had dedicated a thousand words towards educating people about QC, rather than belittling someone personally.

gone35 9y ago
Scott does come across as petty, and as someone you would never want to work with. Please don't let his (admittedly sometimes aggressive, unabashed) writing style detract from the man himself. From personal experience, he's unfailingly generous, kind, and amazing to work with.
mroll 9y ago
Scott has poured many more than one thousand words into the cause of educating people about quantum computing. The point here is that this journalist didn't do his due diligence. Reading the tag line on Scotts blog would have made him question one of the core assumptions he made in his piece.

rdtsc 9y ago

Now I was wondering about TSP why it was mentioned at all and if there were any new results since I dabbled in quantum computing. It seems with some constraints on vertex degrees, which seems to be practical, it's possible to do have some speedup (not polynomial of course). For example https://arxiv.org/abs/1612.06203 https://arxiv.org/abs/1612.06203 claims O(1.3^N) for 4 nodes vs O(1.6^N) for classical. For example with N=500 that's 1e57 vs 1e102. But yeah still wouldn't have picked it as _the_ example to use. Not on topic but since Scott had to mention it... > Would you agree that the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance? Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now? No, no, I don't. They are better then MSNBC and CNN in that they do some actual legwork as opposed to talking about ice-cream scoops and extra long hand shakes, but certainly have gotten the "Russian hackers" fever and can't let go of it: https://theintercept.com/2017/01/04/washpost-is-richly-rewarded-for-false-news-about-russia-threat-while-public-is-deceived/ https://theintercept.com/2017/01/04/washpost-is-richly-rewar...