Hacker News new | comments | show | ask | jobs | submit login
Review of Vivek Wadhwa’s Washington Post Column on Quantum Computing (scottaaronson.com)
64 points by jashkenas 6 months ago | hide | past | web | favorite | 49 comments



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


> 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.


I don't think that there's any evidence at all that quantum computers will provide a speedup on generic problems.


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.


> 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.


In fact both quantum computers and nondeterministic computers can perform a computation on all possible inputs simultaneously. The difference is in what happens afterwards.

A nondeterministic computer halts in the "success" state if any of the individual threads halted succesfully. This turns out to be tremendously useful.

A quantum computer run on a quantum superposition of all possible inputs gives you a superposition of the outputs. If you we're to measure it directly you would just get one of the outputs chosen at random. This not useful. But sometimes (on particular problems with a suitable structure) further work can be done on the superposed state before measuring it, in such a way that the results of the measurement are useful.


> If you we're to measure it directly you would just get one of the outputs chosen at random.

The point is that not all the outputs are equally probable and (in the interesing cases) you will get the “right” answer with high probability.


My point is that if you do it the naive way then they are all equally likely. You need to do something extra to make the ones you want more likely. And this only works in some cases. (I guess Grover's algorithm works in all cases, but it's not a exponential speedup.)


I thought that something extra was part of “running a quantum computer”.


Always, except when you are confronted with a “problem having a structure that lets you set up a pattern of constructive and destructive interference, so that different contributions to each wrong answer cancel each other out while the different contributions to the right answer(s) reinforce.”

In particular “factoring and other problems important for public-key cryptography,” which is the subject of the article.


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.


> 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?

Obviously, someone who's already bought in but hasn't cashed out yet.


> 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.


You've just described the Gell-Man Amnesia effect:

"Briefly stated, the Gell-Mann Amnesia effect works as follows. You open the newspaper to an article on some subject you know well. In Murray’s case, physics. In mine, show business. You read the article and see the journalist has absolutely no understanding of either the facts or the issues. Often, the article is so wrong it actually presents the story backward-reversing cause and effect. I call these the “wet streets cause rain” stories. Paper’s full of them. In any case, you read with exasperation or amusement the multiple errors in a story-and then turn the page to national or international affairs, and read with renewed interest as if the rest of the newspaper was somehow more accurate about far-off Palestine than it was about the story you just read. You turn the page, and forget what you know." - Michael Crichton, Why Speculate (26 April 2002)


What's particularly interesting is that Scott specifically says that "the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance" but anyone who has been following Seth Abramson knows that the Washington Post and the New York Times are still a huge part of the problem in keeping up with the whole Russia investigation.


The Washington Post's most prominent claim to fame in that regard is David Fahrenthold's reporting on the Trump Foundation's various ethical (and probably legal) problems, including self-dealing (spending donated money for functions at his Golf Courses), misappropriations (buying a self-portrait from foundation money) and outright fraud (not paying out promised donations, lying about the amounts Trump himself contributes to the foundation) etc. His articles are at https://www.washingtonpost.com/people/david-a-fahrenthold/

Regarding Seth Abramson, it's important to note that there is ample criticism of his rather sloppy methods. A nice summary of him and similar "independent journalists" is at https://thinkprogress.org/blue-detectives-collapse-trump-rus.... If ThinkProgress thinks some criticism of Trump may be too close to conspiracy theories than comfortable, it would seem to be rather suspect.


Wait, Seth Abramson's problem with the Washingon Post is that they're not willing enough to believe batshit Russians-under-our-beds stories?


I think the summary of Seth Abramson's contributions is:

1. He's insane

2. 2016-2018 has been insane

3. They've often been materially insane in the same way. But sometimes not.

Russians are, in fact, under our collective beds, getting at our voting.


But is he keeping track of their plot to sap and impurify our precious bodily fluids?

You ever see a Putin drink a glass of water?


Steele report hinges on a few things, among them some women's precious bodily fluids...


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_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/... for an example.


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.


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=P...


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


I think that was a joke...


I think he improved on it.


Linear programming is in P.

Perhaps you are talking about Integer Linear Programming?


There is a pathological case for linear programming which requires exponential time.[1]

[1] https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube


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. She repeated this example in a recent piece in ZDNet: 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.


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.


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.


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.


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.


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?


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.


They have provided those summaries multiple times over. And Wikipedia has some of them too.


> 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.


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."


"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.


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.


I take it that theoretical physics tends to get similarly butchered.


Math, probably.


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.


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.


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.


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.


The Economist usually does pretty well on science and technology. Not sure whether you count them as mainstream.


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.


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 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-rewar...




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: