Speaking Truth to Parallelism at Cornell
This week I was at my alma mater, Cornell, to give a talk at the 50th anniversary celebration of its computer science department. You can watch the streaming video here; my talk runs from roughly 1:17:30 to 1:56 (though if you’ve seen other complexity/physics/humor shows by me, this one is pretty similar, except for the riff about Cornell at the beginning).
The other two things in that video—a talk by Tom Henzinger about IST Austria, a bold new basic research institute that he leads, closely modeled after the Weizmann Institute in Israel; and a discussion panel about the future of programming languages—are also really interesting and worth watching. There was lots of other good stuff at this workshop, including a talk about Google Glass and its applications to photography (by, not surprisingly, a guy wearing a Google Glass—Marc Levoy); a panel discussion with three Turing Award winners, Juris Hartmanis, John Hopcroft, and Ed Clarke, about the early days of Cornell’s CS department; a talk by Amit Singhal, Google’s director of search; a talk about differential privacy by Cynthia Dwork, one of the leading researchers at the recently-closed Microsoft SVC lab (with a poignant and emotional ending); and a talk by my own lab director at MIT, Daniela Rus, about her research in robotics.
Along with the 50th anniversary celebration, Bill Gates was also on campus to dedicate Bill and Melinda Gates Hall, the new home of Cornell’s CS department. Click here for streaming video of a Q&A that Gates did with Cornell students, where I thought he acquitted himself quite well, saying many sensible things about education, the developing world, etc. that other smart people could also say, but that have extra gravitas coming from him. Gates has also become extremely effective at wrapping barbs of fact inside a soft mesh of politically-unthreatening platitudes—but listen carefully and you’ll hear the barbs. The amount of pomp and preparation around Gates’s visit reminded me of when President Obama visited MIT, befitting the two men’s approximately equal power. (Obama has nuclear weapons, but then again, he also has Congress.)
And no, I didn’t get to meet Gates or shake his hand, though I did get to stand about ten feet from him at the Gates Hall dedication. (He apparently spent most of his time at Cornell meeting with plant breeders, and other people doing things relevant to the Gates Foundation’s interests.)
Thanks so much to Bobby and Jon Kleinberg, and everyone else who invited me to this fantastic event and helped make it happen. May Cornell’s CS department have a great next 50 years.
One last remark before I close this post. Several readers have expressed disapproval and befuddlement over the proposed title of my next book, “Speaking Truth to Parallelism.” In the words of commenter TonyK:
That has got to be the worst title in the history of publishing! “Speaking Truth to Parallelism”? It doesn’t even make sense! I count myself as one of your fans, Scott, but you’re going to have to do better than that if you want anybody else to buy your book. I know you can do better — witness “Quantum Computing Since Democritus”.
However, my experiences at Cornell this week helped to convince me that, not only does “Speaking Truth to Parallelism” make perfect sense, it’s an activity that’s needed now more than ever. What it means, of course, is fighting a certain naïve, long-ago-debunked view of quantum computers—namely, that they would achieve exponential speedups by simply “trying every possible answer in parallel”—that’s become so entrenched in the minds of many journalists, laypeople, and even scientists from other fields that it feels like nothing you say can possibly dislodge it. The words out of your mouth will literally be ignored, misheard, or even contorted to the opposite of what they mean, if that’s what it takes to preserve the listener’s misconception about quantum computers being able to solve NP-hard optimization problems by sheer magic. (Much like in the Simpsons-visit-Australia episode, where Marge’s request for “coffee” is misheard over and over as “beer.”) You probably think I’m exaggerating, and I’d agree with you—if I hadn’t experienced this phenomenon hundreds of times over the last decade.
So, to take one example: after my talk at Cornell, an audience member came up to me to say that it was a wonderful talk, but that what he really wanted to know was whether I thought quantum computers could solve problems in the “NP space” in linear time, by trying all the possible solutions at once. He didn’t seem to realize that I’d spent the entire previous half hour answering that exact question, explaining why the answer was “no.” Coincidentally, this week I also got an email from a longtime reader of this blog, saying that he read and loved Quantum Computing Since Democritus, and wanted my feedback on a popular article he’d written about quantum computing. What was the gist of the article? You guessed it: “quantum computing = generic exponential speedups for optimization, machine learning, and Big Data problems, by trying all the possible answers at once.”
These people’s enthusiasm for quantum computing tends to be so genuine, so sincere, that I find myself unable to blame them—even when they’ve done the equivalent of going up to Richard Dawkins and thanking him for having taught them that evolution works for the good of the entire species, just as its wise Designer intended. I do blame the media and other careless or unscrupulous parties for misleading people about quantum computing, but most of all I blame myself, for not making my explanations clear enough. In the end, then, meeting the “NP space” folks only makes me want to redouble my efforts to Speak Truth to Parallelism: eventually, I feel, the nerd world will get this point.
Update (Oct. 4): I had regarded this (perhaps wrongly) as too obvious to state, but particularly for non-native English speakers, I’d better clarify: “speaking truth to parallelism” is a deliberate pun on the left-wing protester phrase “speaking truth to power.” So whatever linguistic oddness there is in my phrase, I’d say it simply inherits from the original.
Another Update (Oct. 7): See this comment for my short summary of what’s known about the actual technical question (can quantum computers solve NP-complete problems in polynomial time, or not?).
Another Update (Oct. 8): Many commenters wrote to point out that the video of my talk at Cornell is now password-protected, and no longer publicly available. I wrote to my contacts at Cornell to ask about this, and they said they’re planning to release lightly-edited versions of the videos soon, but will look into the matter in the meantime.
Follow
Comment #1 October 3rd, 2014 at 5:27 pm
I think it’s a good title.
Comment #2 October 3rd, 2014 at 5:31 pm
Thanks, Vadim! 🙂
Comment #3 October 3rd, 2014 at 6:37 pm
Sure, this shows that “speaking truth to parallelism” is a good task, but that doesn’t address whether it is a good title. I think it’s a red flag if your audience needs to be convinced of your point to even understand your title.
Comment #4 October 3rd, 2014 at 6:38 pm
Thought you might like to know that reading your blog has sufficiently sensitized me to this misconception that when it showed up in Neal Stephenson’s “Anathem”, it jarred me completely out of the story and I never quite regained my suspension of disbelief for the remainder of the book. So… thanks?
I also like the title.
Comment #5 October 3rd, 2014 at 6:55 pm
Jeez, why not go the whole hog – “Quantum Computing is Really Boring”
Peeps want to believe in a little magic in the world, even for a short time, why bother to publish such a depressingly downbeat overview of the field? BICEP2 may not have discovered inflation, but my god they got a lot of people excited about the entire subject. Can’t imagine a book “Speaking Truth to CMB Polarization” would be very popular.
Comment #6 October 3rd, 2014 at 7:12 pm
Dan #4: Awesome, thanks for letting me know!
(Personally, I got jolted out of Neal Stephenson’s Cryptonomicon when I encountered a passage about “factoring huge prime numbers,” and couldn’t continue reading. It was sort of a shame, since I’d been enjoying the novel up till that point…)
Comment #7 October 3rd, 2014 at 7:23 pm
James #5: Well, the reality of how quantum computers would work is still pretty incredible! Indeed, you could argue that it’s more incredible than the popular misconception, precisely because it’s so subtle, and so different from what one would’ve imagined a-priori was even on the table as a logical possibility. I.e., who woulda thunk that the true laws of physics would allow factoring to be solved in polynomial time, but not NP-complete problems? What science-fiction writer would’ve called that one?
(Incidentally, I feel the same way about Bell inequality violation: the fact that you can do this thing that all your prior intuition tells you would logically imply faster-than-light signaling, yet you still can’t use it to send faster-than-light signals, is even more incredible than if you could send such signals.)
So in summary, I feel like the truth can at least put up a pretty good showing against fantasy, in terms of its capacity to inspire people.
Comment #8 October 3rd, 2014 at 7:26 pm
Just before reading this I saw NOVA: Rise of the Hackers. The “trying every possible answer at once” idea of quantum computing was only reinforced. It seems an up hill battle.
Comment #9 October 3rd, 2014 at 7:42 pm
Scott #7
yes, the truth is not bad. 🙂
I’d like to see another Nobel award in Quantum Computing science this year.
Comment #10 October 3rd, 2014 at 7:44 pm
Phil #8: I guess the one consolation is that, if this particular misconception sticks around for the rest of my life, then at least I’ll have something to skewer to entertain talk audiences for the rest of my life. But really I’d prefer that the misconception die, and I be forced to update my standup routine…
Comment #11 October 3rd, 2014 at 8:00 pm
Scottm #7: (Incidentally, I feel the same way about Bell inequality violation: the fact that you can do this thing that all your prior intuition tells you would logically imply faster-than-light signaling, yet you still can’t use it to send faster-than-light signals, is even more incredible than if you could send such signals.)
Is there a conspiracy of Nature?
Comment #12 October 3rd, 2014 at 8:02 pm
If your goal is to win over your audience, you have to first get them in the door.
I would gently recommend,
“You Don’t Understand Quantum Computers: Dispatches from the Frontier of Quantum Computing Theory”
or even better,
“Everything You Believe About Quantum Computing is a Lie.”
Alerting the reader of their ignorance is a nice hook, they will be intrigued and feel challenged to pick up the book. I don’t anticipate many people outside of your existing fan base would pick up a copy of “Speaking Truth to Parallelism”, but “Everything You Believe About Quantum Computing is a Lie” would be irresistible to a wide range of nerds, including those who don’t know anything at all about quantum computing. Get them in the door!
Comment #13 October 3rd, 2014 at 8:05 pm
I would like to give a little feedback from the point of view of a non native speaker of English. For me the expression “speaking truth to parallelism” does not immediately suggest that “parallelism” as an explanation should be a wrong idea, rather, it suggests that it will be a subject of scrutiny whether or not it is and the result of it will be revealed.
GIVEN WHAT IS AT STAKE, it may worth checking out if some other people may read the proposed title like this?
Reading what you wrote about the widespreadness of this misconception, I totally agree that it is worth fighting against it already in the title, but then maybe some even more direct statement could not be better? (even if it is less colorful or original, like: “It’s not the parallelism, stupid”)
Comment #14 October 3rd, 2014 at 8:10 pm
An added benefit of “Everything You Believe About Quantum Computing is a Lie” is that when people keep repeating the same misperceptions, ad nauseam, you can just point to the title of your book with a big stick and save your energy for more useful things 🙂
Comment #15 October 3rd, 2014 at 8:12 pm
J #12: Thanks for the useful suggestion! Will take under advisement. On the other hand, the literalist in me rebels against a title like “Everything You Know About Quantum Computing Is A Lie.” For not only are there potential readers for whom that’s far from true, but every potential reader presumably knows something about quantum computing that’s not a lie: for example, that the field’s name starts with a “Q.” 🙂
Comment #16 October 3rd, 2014 at 8:27 pm
Phil #11:
Is there a conspiracy of Nature?
No, I’d tend to say: only a mathematical elegance to it. That, for example, you can violate the Bell inequality but not send superluminal signals, or can get an exponential speedup for period-finding but not for unordered search, might sound conspiratorial, until you see how these are the inevitable consequences of simple starting postulates. It only looks like a “conspiracy” if you keep flipping back to imagining that the postulates of QM were false: as soon as you keep consistently in your head that the postulates are true, these particular conspiracies vanish.
Comment #17 October 3rd, 2014 at 8:40 pm
“Fighting Lies About Quantum Computers: Dispatches from the Frontier of Quantum Computing Theory”
“Killing Cherished Misconceptions About Quantum Computing”, or if that’s too violent, “Speaking Truth to Cherished Misconceptions About Quantum Computing”. Shorter titles are probably better though, and violence sells from what I have heard (among other things). Which leads me to, “We All Know Quantum Computers Are Sexy, but Let’s Not Get Ahead of Ourselves” 🙂
Comment #18 October 3rd, 2014 at 9:02 pm
I think the problem is the general impenetrability of the subject for lay people such as myself. I’m sure to the readers of this blog, QC’s limited applicability seems elementary and obvious. But without the theoretical underpinnings firmly in mind (and perhaps without the same intellectual bandwidth), non-scientists like me have only what we read to go on, and there is indeed an awful lot of hype out there to read.
Learning is a process, not a destination. 🙂
I think the title is perfect. Thanks to Scott and scientists for keeping everyone educated …
Comment #19 October 3rd, 2014 at 9:32 pm
The type of novel the world is waiting for is about a brilliant MIT computer science professor who gets a call late one night, in which he is asked to solve a gruesome murder which turns out to have been perpetrated by a secret cabal in the Vatican that possess a D-Wave quantum computer. With the help of a beautiful French mathematician woman, our professor saves the world from certain destruction by quantum parallelism.
Comment #20 October 3rd, 2014 at 9:46 pm
Well, it is not nearly as meaningful as any of the other suggestions, but if only to get attract the eye of people who like bad puns I would suggest “Quantum Computing: Thinking Cats out of the Box”.
Comment #21 October 3rd, 2014 at 11:05 pm
Scott, I don’t have a suggestion for the title (not that you were asking for one), but the fact that people keep suggesting better ones for this book, while no one argued with the title of your last book speaks volumes. Certainly it is not nearly as attention-grabbing as Quantum Computing since Democritus (…what? Democritus? but… quantum… there were no Quantum Computers in ancient Greece… there were no computers in ancient Greece at all! Computers are not even 100 years old, what on earth does the author mean? Better check it out!)
Whereas “Speaking Truth to Parallelism” makes my initial reaction “who is parallelism and why do you need to tell him the truth? No, that makes no sense… Does he mean “Speaking truth about parallelism”, just phrased unusually? Why? OK, if the title makes no sense, why bother reading any further… Pass.”
Comment #22 October 4th, 2014 at 4:01 am
Don’t call it “Speaking Truth to Parallelism”. It is a terrible title. Not only does it hardly make any sense, no one will have any idea what the book is about. Try wondering around MIT asking people what they think a book with that title would be about as an experiment.
Why not call it something simple like “The Truth about Quantum Computing” or in the modern fashion “Quantum Computing. Why much of what you think you know isn’t true and how the truth is even more exciting”
Comment #23 October 4th, 2014 at 5:59 am
I’m not a native speaker, so I can’t speak with any real authority here, but “speaking to parallelism” sounds really ugly to me too. I can see how you can speak to a person (“speaking to Fred”) or a collection of people (“speaking to the world”), but how do you speak to an abstract concept? Does the title mean “speaking out against parallelism” – that at least makes sense to me.
Comment #24 October 4th, 2014 at 7:38 am
I like Wiggy’s second suggestion for a title.
Comment #25 October 4th, 2014 at 8:43 am
Carlos #23: I second your non-native speaker’s opinion. Actually, “speaking truth about parallelism” would make a lot more sense to me.
Comment #26 October 4th, 2014 at 8:55 am
Sometimes in titles a little obscurity or non-clarity is actually a good thing.
It actually catches their attention and then you always have the blurb to do the more detailed explaining.
Comment #27 October 4th, 2014 at 9:16 am
This is of course a universal experience among STEAM researchers. It is natural to respond by answering — with maximal clarity and accuracy — the STEAM-questions that citizens literally ask.
But is this the best mode of answering?
An alternative response — that arguably is better — is to answer instead the STEAM-questions that citizens should be asking. In this regard, the attention of Shtetl Optimized readers is directed toward David Eggers’ thought-provoking novella Your Fathers, Where Are They? And the Prophets, Do They Live Forever? (2014).
STEAM Theme When doubting Thomases fix STEAM-researchers to the wall — quantum STEAM-researchers in particular — and demand to know “what is this research good for?” perhaps it is best (but hardest) to begin by framing better questions sympathetically, and only then answering those questions truthfully.
Further readings The sympathy-accuracy STEAM-theme takes center-stage not only in Your Fathers, Where Are They? (2014), but also in Eggers’ previous two books, A Hologram for the King (2012) and The Circle (2013).
Summary David Eggers’ recent books encourage the STEAM community to reflect upon the adverse consequences of not asking the right questions.
Hopefully Speaking Truth to Parallelism will address these concerns by both suggesting good questions (with sympathy) and by giving good answers (with accuracy).
Achieving both of these objectives together is of course far more challenging than achieving either of them alone.
Comment #28 October 4th, 2014 at 10:38 am
John #27: I do try whenever possible to “error-correct” vague or poorly-worded questions, to whichever question the speaker meant to ask. I admire people who are good at that (Bill Gates being one example), and I hope to get better with practice.
However, the case we’re discussing is not one of a vague or poorly-worded question. It’s more like: people asking a good, clear question (“could QCs solve NP-hard problems instantly by simply trying all the answers in parallel?”), but then not wanting to hear the answer! Or better: me giving talks, writing articles, etc. whose whole point is to explain why the answer is “no”—and well-meaning people attending the talks and reading the articles (and telling me they liked them), yet still believing that the answer is “yes” and that I probably agree with them, or coming up to me to ask the same question, as if for the first time.
From which I can only conclude that either that (a) I failed cataclysmically at making myself clear, or (b) the mistaken, “try-every-answer-in-parallel” view of QC has become so ingrained from 20 years of popular-science writing, that my explaining its falsehood creates a cognitive dissonance that many people can only resolve by assuming they misunderstood me, or I mispoke, or I didn’t really mean what I said, or I was just trying to be funny, or I was just advocating a minority opinion, or what I said was “true for complexity theorists but not true for the real world.” Or something like that.
Comment #29 October 4th, 2014 at 10:42 am
MIT Press Logo is a bunch of parallel lines
Comment #30 October 4th, 2014 at 11:00 am
PS. Did anyone ask Bill Gates about those layoffs?
Comment #31 October 4th, 2014 at 11:33 am
Rahul #30: Nope. The only Q&A was with Cornell undergrads, and the Microsoft SVC layoffs are unlikely to have been foremost on their minds. (And in any case, Gates could plausibly respond that he’s no longer in charge of such things.)
Comment #32 October 4th, 2014 at 11:49 am
Re update: thanks, I like the title now I understand the pun. 🙂 Maybe this (your post + update + #7) would do great as foreword or back cover.
#7: (+1!)
Comment #33 October 4th, 2014 at 12:42 pm
if your goal is to address people in the computer theory and quantum businesses, then “speaking truth to parallelism”, with your recognized name as author, will do the job.
if your goal is to attract a wider audience i think most people won’t have a clue as to the contents of the book, and without that initial hook, won’t even bother with the blurb. they’ll move on.
although “everything you know about quantum computing is wrong” is an exaggeration, i think people will forgive the hyperbole. anyone interested, even in a vague way, in quantum computing might then have their interest piqued when they see your ACADEMIC CREDENTIALS [since they won’t know your name] on the cover. “hey, this is a reputable guy saying what’s out there about quantum computers is mostly wrong.”
as another commenter said, you’ve got to get them through the door.
Comment #34 October 4th, 2014 at 12:49 pm
ps do a search on amazon on “quantum computing.” you run into your first t-shirt about 3/4 down the 2nd page. prior to that is all books. virtually every one has “quantum computer/computing” in the title. a few have only “quantum.” [“democritus” is #2] there are NO hits without the word “quantum.”
do you want a general reader who decides to learn something about quantum computing to be able to find your book?
Comment #35 October 4th, 2014 at 12:54 pm
Great talk Scott – entertaining and funny as always.
Quick question about the soap bubble optimization experiment – you say that if it worked, it would solve an NP-hard problem in “polynomial time”. But a polynomial number of what, seconds? (I mean maybe it is an exponential number of Planck intervals or something, so it just seems short…)
Comment #36 October 4th, 2014 at 1:09 pm
An Eggers-mode analysis of comment #27 is that the points made are not wrong, but rather express only one-half of a duality that in full asserts:
Doesn’t history provide us with abundant examples of both sides of this duality? … as do the radical citizen-voices of Melville, Twain, Kafka, Pessoa, Wittgenstein, Grothendieck, Goodall, Thurston, Pinker, Stephenson, and now Eggers … to name only a few (in chronological birth-order)?
Summary The 21st century’s extension of STEM to STEAM requires mutually sympathetic, creative, and even outright transgressive listening of both the “A”-team and the “STEM”-team.
Corollary Even the most scrupulous explication of the doctrines of the “Church of the Larger Hilbert Space” — and the perceived implications of those doctrines for quantum computing and quantum information technologies — cannot in itself suffice to sympathetically illuminate the legitimate STEAM concerns — and the transgressive STEAM enterprises — of the 21st century’s citizenry.
Comment #37 October 4th, 2014 at 2:41 pm
Scott #15:
How about “Mostly Everything You Know About Quantum Computing Is A Lie.”? 🙂
Comment #38 October 4th, 2014 at 3:55 pm
I like the title Speaking Truth to Parallelism. (I’m a native English speaker who’s heard “speaking truth to power” many times.) Have you considered subtitles? A choice like Speaking Truth to Parallelism: The Myths, Mysteries and Magic of Quantum Computers would have the added advantage of employing a technical term. 🙂
Comment #39 October 4th, 2014 at 4:20 pm
Regarding the title, doesn’t the phrase “speaking truth to power” treat “power” as an entity–so that we might translate it to more usual terms as something like “speaking truth to the ones in power”?
By analogy, then, I would interpret the phrase “speaking truth to parallelism” as similarly speaking *to* parallelism. But I gather your intent with the book is to speak truth *about* parallelism, not to any entity or group of entities that constitute parallelism, whatever that would mean.
I know “to speak truth to power” carries a sort of connotation of “protesting against or defying the very idea of power”, so in that sense it doesn’t directly address “beings in power” or whatever; and indeed, that particular part makes more sense to convert to “protesting against (the very idea of parallelism in quantum computing)”. But I feel like the title as a whole still comes across wrong and/or confusing to me. I feel too much conflict between that connotation and the more denotative reading of the phrase “speaking truth to parallelism”.
Comment #40 October 4th, 2014 at 4:35 pm
How about: “Don’t Write Articles About Quantum Computing Until You Read This Book”? 🙂
Comment #41 October 4th, 2014 at 4:49 pm
“I had regarded this (perhaps wrongly) as too obvious to state, but particularly for non-native English speakers, I’d better clarify: “speaking truth to parallelism” is a deliberate pun on the left-wing protester phrase “speaking truth to power.” So whatever linguistic oddness there is in my phrase, I’d say it simply inherits from the original.”
I realize this is ultimately a matter of taste but, it isn’t even a good pun and I like puns. The idea behind “speaking truth to power” is that you have some interaction with power and it takes great courage to stand up to it. “power” represents a person or an institution you communicate with directly. In the current situation, “parallelism” isn’t something you are suggesting we talk to or even stand up to lest it oppresses us. It doesn’t represent a person or an institution and its not even a concept you would like us to resist. As I understand it, you would like us to stand up to those who are spreading misinformation about the supposed magic parallelism of quantum computing but that would be “speaking truth to those who claim that quantum computing gives us magic exponential parallelism”, a somewhat less attractive title. The title “speaking truth to parallelism” simply doesn’t say that. It is basically linguistically and semantically all wrong, especially to a native speaker. I recommend some urgent market research or a focus group 🙂
This is quite apart from the other reason I don’t like it that I mentioned above. I’ll stop there.
Comment #42 October 4th, 2014 at 4:52 pm
#38 I do like “The Myths, Mysteries and Magic of Quantum Computers “
Comment #43 October 4th, 2014 at 7:49 pm
I suggest just a title/subtitle like this:
Quantum Computing: What it is, and why it does not try every solution in parallel.
Comment #44 October 4th, 2014 at 8:23 pm
Rahul #37: Perhaps more accurately, “What most of you think you know about quantum computing is a lie.”
Comment #45 October 4th, 2014 at 9:00 pm
I concur with everyone who’s said that “Speaking Truth to Parallelism” is a terrible title. (I also strongly suspect Scott already knows this really. And I’m quite sure his publisher will never let it go out with that title.)
It will completely mystify anyone who hasn’t encountered the term “speaking truth to power”. I’d guess *many* of the potential audience have encountered that term, but the fact that Scott had to put up his clarification indicates that not all have.
It’s semantically wrong, for approximately the reason Wiggy describes: “parallelism” and “power” are not, er, parallel.
Even for potential readers who recognize the reference it will be mystifying (and not, I think, in the sort of good way that will make them think “oh, that’s intriguing; let me pick up this book to find out more”) unless they *already know* what Scott is hoping to tell them. “Speaking truth to parallelism? Huh? Is this guy opposed to parallel computing? Does he want Intel to stop making multi-core chips and go back to cranking up the clock speed?” Or even “Speaking truth to parallelism? Does this guy have some problem with ancient Hebrew poetry?”.
(In case of suspicion that dislike of the title comes only from people who didn’t understand it: It was instantly obvious to me when I saw the title what Scott meant by it; I still think it’s terrible.)
Scott@15: If you find “Everything You Know About Quantum Computing Is A Lie” unacceptable because it overstates, then I think you should feel almost the same way about “Speaking Truth to Parallelism”: after all, what’s wrong with the popular narrative about quantum computers *isn’t* exactly the bit about parallelism. For instance, each step of Grover’s algorithm does, precisely, do an operation — the same operation — in parallel on all the candidates being searched, and something different happens to the “good” one. The difficulty — and the reason why the algorithm needs multiple steps and doesn’t get an exponential speedup — is in turning this parallel computation into something that’s (so to speak) consistently visible in all wavefunction branches.
Comment #46 October 4th, 2014 at 10:30 pm
The problem with “speak truth to power” is that it only makes sense to Americans. I think of myself as a native speaker of English (though I am Indian) and after 13 years in the US, for many of which I have known the meaning of that expression, it still sounds strange to me. And frankly, I even wonder sometimes what fraction of Americans it makes sense to.
Comment #47 October 4th, 2014 at 10:33 pm
It’s pretty clear that the titles “What you know about X is wrong” are quite bad; I don’t know why people are suggesting them.
But I have to agree with everyone at not being overjoyed by the current title.
Maybe something more cute and copying Terry Tao’s style – “A quantum sampling – Notes from the frontier of quantum complexity theory”, “A quantum tasting plate – …”, there are probably better ideas.
Scott – Out of interest, can you see any way to changing your mind on the title? Or are you sufficiently convinced that you *need* to firstly and foremostly have a book whose title tries to attack the idea that quantum computers can try all solutions in parallel? (I’ll admit that part of why I don’t like the title is that it seems like a good way to actually *further* the perputation of the “myth”; i.e. people will associate “quantum” things with “parallel” things; but I also admit that I think the best way to “fix” this problem is not by talking about it, but instead talking about what is actually true; and I might be completely wrong about that.)
Comment #48 October 4th, 2014 at 11:05 pm
How about some pun on the world parallel? Here is a really poor suggestion: Quantum Computing: An Unparalleled View.
Comment #49 October 4th, 2014 at 11:07 pm
When I first saw the title, I did not get it, but had no doubt there was a clever interpretation. Now that I know, I vote: “Great title”.
All the better that it builds on a left wing slogan. I oscillate between being more annoyed by far left wingers and far right wingers. I am of course exactly in the center, as measured by knowing equal numbers of people who think I am a left winger as think I am a right winger.
Comment #50 October 5th, 2014 at 3:03 am
Since the book is an anthology of blog posts, was getting rid of the parallelism misconception a central theme of your blog? What fraction of posts or comments are on this over the years?
I get the feeling that a lot of interesting discussion was from people or about people grossly beyond the simple parallelism misconception? On topics or disagreements deeper than that?
Like take the DWave saga. Is that also under the parallelism rubric? Or Boson Sampling? Or the Many Worlds business. Those were very interesting and a key theme over the last two years weren’t they?
Comment #51 October 5th, 2014 at 3:26 am
Shakespeare possessed of age of efficient quantum entanglement of quantum computing machines in that.
Yes … what we don’t know about these theories for journalists! It is NOT take it isn’t strictly positive maps, and a state-space geometry is trying to the pulled back to assimilate (a “wildly successful” leader in computing the premodern Jews and experimental evidence that |Per(A1)|2,…,|Per(Ak)|2 are quite a smaller than has been given in practice, renormalization-entanglement effects).
STEM debate about Bell with a big leagues of experimental datasets, and machine in humor. Not wishing to Spiderman III. Today’s obituary of the Clay Millennium Prize’s Navier Stokes Conjecture, owe them to watch them … and imaginative researchers, the bad economic sphere.
Comment #52 October 5th, 2014 at 7:38 am
I agree with Douglas Knight in that it’s a bad title.
I don’t know what a good title would be, nor how to educate people to forget that misconception in general.
Comment #53 October 5th, 2014 at 8:07 am
@Sidlesbot:
(a) You need fancy Latex formatting (b) Please add some obscure references & links. 🙂
Comment #54 October 5th, 2014 at 8:38 am
John Sidlesbot is a fraud. The REAL John Sidles has for some reason taken to writing “STEAM” these days, rather than “STEM”, his old mainstay.
Comment #55 October 5th, 2014 at 9:51 am
Brilliant talk, really enjoyed it! One comment: as far a I understand, at present those who model the brain seem to think of it as a finite-state automaton, not a Turing machine. If indeed it is a Turing machine, then it is not clear where the program is stored.
Comment #56 October 5th, 2014 at 10:45 am
luca #55: Well, a Turing machine is a finite-state automaton—it’s just one that happens to be able to both read from and write to a tape, and move in both directions along it! 🙂
More broadly, by “the Church-Turing Thesis holds for the brain,” one should understand something like:
“given the requisite initial data, a brain can be simulated by a Turing machine in a ‘natural’ way, where ‘natural’ means, not just by caching an enormous lookup table—the program needs to be reasonably succinct. So in particular, a brain is not a physical system that we can use to solve the halting problem, or any other standard uncomputable problem, with any degree of reliability.”
Crucially, there’s no claim here that the brain’s internal architecture resembles that of a “standard” digital computer—for example, by having a “clean separation” between software and hardware, or being able to execute stored programs. (Those things might be true, or true to a limited extent, but they’re not in any way necessary for the CT Thesis to hold for the brain.)
Comment #57 October 5th, 2014 at 11:02 am
@ Scott #56: Agreed, but some psychologists, among which C R Gallistel at Rutgers, argue that there are some thing the brain does which manifestly require more than an finite-state automaton. Out of my depth here, just relaying information which agrees with my own personal bias/hunch that there is a basic ingredient missing in current neuroscience.
Comment #58 October 5th, 2014 at 11:17 am
Rahul #50:
I get the feeling that a lot of interesting discussion was from people or about people grossly beyond the simple parallelism misconception? On topics or disagreements deeper than that?
Like take the DWave saga. Is that also under the parallelism rubric?
That’s actually a very interesting question. Obviously, D-Wave’s scientists don’t suffer from the trivial parallelism misconception about QC. And of course, I have colleagues who cautiously support what D-Wave is doing, or at least are agnostic about it, despite understanding the wrongness of the parallelism misconception as well as I do. They’re simply hoping that quantum annealing at finite temperature will be able to exploit tunneling effects to get a speedup compared to classical simulated annealing—even if not in general, and even if not a huge speedup, often enough and large enough to make it interesting. And while we don’t have good theoretical evidence that that’s what’s going to happen, neither can we rule the possibility out. I’ve often said myself that it’s an experiment well worth trying.
At the same time, one wonders whether D-Wave could’ve gotten nearly the attention, funding, and hype that it did, were it not able to operate under the “penumbra” of the parallelism misconception. The majority of popular articles about D-Wave make the mistake in one form or another, and when talking to laypeople or journalists, I’m constantly floored by how often this mistake arises. People genuinely believe that, if D-Wave’s devices were “true quantum computers,” then they’d be guaranteed to get exponential speedups for all sorts of machine learning, pattern recognition, and Big Data problems of interest to companies like Google. And therefore, they think, the only remaining question is whether they’re “true” QCs or not. The idea that you would build a QC, it would work exactly as theory predicts, and yet it still wouldn’t give you a speedup for most such problems, is never even entertained.
So maybe it’s a little like religion: yes, most religious people don’t literally believe that if they say their prayers in exactly the right way each night, God will make them fabulously wealthy and popular, while covering their enemies with leprosy and boils. They believe something much subtler and less childish than that. But still, one can ask (and people like Richard Dawkins do ask) whether the sophisticated versions of religion would even have gained a toehold, had the childish versions not paved the way for them.
So, in summary: I certainly hope this blog has covered things a helluva lot deeper than the parallelism misconception! Yet, if one had to pick a single theme to tie together as much of this blog’s writing about QC as possible, it seems to me that one could do worse.
Comment #59 October 5th, 2014 at 11:44 am
Scott #57:
All good points. I just thought the “parallelism” title was underselling a lot of the deep, fascinating discussions I’ve seen on the blog & in the comments.
Titles are always a matter of taste & opinion, of course.
Comment #60 October 5th, 2014 at 12:12 pm
Maybe just title it “Quantum Computing is not about Parallelism”? OK, that would probably make it sound like the book is narrowly focused on that one thing.
Perhaps the snappier “It’s not about Parallelism” (together with a subtitle) — then when the book isn’t focused on the parallelism issue, you can point out that it says right on the cover that it’s not about parallelism! 🙂
Comment #61 October 5th, 2014 at 12:21 pm
Maybe you can compromise a little bit, by being more explicit. Something like: “Speaking the truth to quantum parallelism proponents” (you can change “proponents” to a dozen other things, like: dogmatists or advocates or apologists or believers or fanatics or lunatics or whatever)
Comment #62 October 5th, 2014 at 3:12 pm
Bro you have some sick quantum computing popularization game everyone knows that, but your book title is so bad that not only would I not pick it up off the shelf even though I read your blog, it is so bad that it somehow contaminates your other work by association so I would be less likely to read that too.
Comment #63 October 5th, 2014 at 4:58 pm
I completely agree with the preceding comments that “Speaking Truth To Parallelism” is a horrible title. I have a background in quantum computing and know the phrase “speaking truth to power”, and still the title is mistifying to me (if I hadn’t been reading this blog regularly, I’d have no idea what the book is supposed to be about). Now I expect that the average reader will be completely puzzled…
Comment #64 October 5th, 2014 at 5:55 pm
People genuinely believe that, if D-Wave’s devices were “true quantum computers,” then they’d be guaranteed to get exponential speedups for all sorts of machine learning, pattern recognition, and Big Data problems of interest to companies like Google.
Surely you must have watched some old Star Trek episodes that featured computers? They always were portrayed as omnipotent machines with impeccable logic. This mystification has now simply transferred to quantum computers.
Once people get to experience them first hand these expectations will be deflated quite rapidly, but I doubt any amount of pop-science books, no matter how well written can accomplish this.
Until then these myths will be skillfully employed by marketing pros, just like UNIVAC back in the day tirelessly referred to their early computers as ‘electronic brains’ to feed into the expectation that their versatility was limitless.
At any rate once people have a realistic understanding of QC the mystification will latch onto something new. Seems to be human nature, in that sense the comparison to religion is quite apt.
Comment #65 October 5th, 2014 at 6:01 pm
As in comment #45, I find the “Speaking truth to parallelism” title bothersome for very prosaic reasons. I work in the very literally named field of parallel computing, of the sort with hardware and software peddled by Intel, Nvidia, Cray, IBM, etc. The ‘parallelism’ your title concerns itself with is, as you note, a misconception. ‘Parallelism’ as understood by anyone with an otherwise contemporary knowledge of computing is the practical, classical kind practiced for decades.
Comment #66 October 5th, 2014 at 9:47 pm
Phil Miller #65: I agree; in fact, I was at first confused by the proposed title, because I assumed it referred to the standard topics of parallel algorithms and hardware (which I have also worked in).
Also, in teaching, it’s well-known that students aren’t blank slates. They have ideas about how things work. If you want to teach them that things work like A, but they come in believing that things really work like B, then you absolutely have to start out by explaining, or at least stating explicitly — right at the beginning, before you do anything else — why it is that things *don’t* work like B. Otherwise, they’re just not going to hear what you’re trying to say. That was the motivation for my suggested title in #43.
Comment #67 October 6th, 2014 at 7:01 am
Modest amendments suffice to preserve the sense and cadence — which I greatly admire! — of Scott’s title Speaking Truth to Parallelism, while at the same time respecting the various comments offered.
That middle road might look like something like this (here the language outside of brackets is directly from Scott’s comment #47):
Here the crucial rhetorical amendment is \(\mathsf{\text{Speaking}} \Rightarrow\mathsf{\text{Seeking}} \). Why is this amendment crucial?
From \(\mathsf{\text{Speaking}} \Rightarrow\mathsf{\text{Seeking}} \) in quantum discourse Ongoing discourse regarding both the fundamental feasibility and the practical applications of quantum computing can benefit — as it seems to me — from lessons-learned in the the climate-change debate.
In particular, physicist John Butterworth’s recent essay “Belief, bias and Bayes“ (2014) provides a template for STEAM discourse that is friendly, rational, and science-respecting … yet maximally sympathetic to diverse points-of-view.
When transposed to the quantum domain, Butterworth’s threefold discourse-template becomes a sympathetic framing of quantum discourse, as follows (the language outside of brackets is Butterworth’s):
Conclusion Obviously it is neither necessary, nor feasible, nor even desirable that everyone embrace Butterworth-style triangulations of STEAM debates. Yet surely it would be regrettable if no-one — among students especially! — embraced these framings. And it would be most regrettable of all, if quantum STEAM discourse evolved to resemble the rancorous wrangling of climate-change discourse.
Acknowledgements Butterworth’s wryly titled, diversity-celebrating, gentle-spirited book Smashing Physics (2014) is whole-heartedly commended to Shtetl Optimized readers of all quantum persuasions.
Comment #68 October 6th, 2014 at 7:27 am
A title suggestion dedicated to Richard Farina, (a Cornell alumnus), I mention it here even though its probably not appropriate for your book:
Been Split so Much It All Looks Whole to Me
well, maybe it still needs some work.
Comment #69 October 6th, 2014 at 11:47 am
Off topic comment to Scott:
What’s the latest about Boson Sampling from the experimental front? Has scaling proceeded to larger n?
How about the scattershot boson sampling? Any chance of a follow up post?
Comment #70 October 6th, 2014 at 11:54 am
“going up to Richard Dawkins and thanking him for having taught them that evolution works for the good of the entire species, just as its wise Designer intended.”
Well, this viewpoint is not too uncommon: http://en.wikipedia.org/wiki/Theistic_evolution. IMO for people with very strong religious beliefs aspousing theistic evolution is a huge progress over blatant denying the existence of evolution.
Comment #71 October 6th, 2014 at 12:01 pm
Michael #70: I don’t deny that! In much the same way, one could argue that believing quantum computers will offer exponential speedups for NP-complete problems is an “improvement” over denying quantum mechanics entirely.
Still, Richard Dawkins has devoted his career to trying to show people not merely that evolution happened, but that greedy local optimization seems to suffice to explain its success. I.e., not only do you not need an intelligent designer guiding the process, you don’t need any teleological notions, like “progress” or “the good of the species.” So it would indeed be strange to walk up to him and thank him for teaching you the opposite.
Comment #72 October 6th, 2014 at 12:07 pm
Rahul #69:
What’s the latest about Boson Sampling from the experimental front? Has scaling proceeded to larger n?
How about the scattershot boson sampling? Any chance of a follow up post?
I apologize that science doesn’t happen at blog speed! 🙂 There have been new theory papers related to BosonSampling on the arXiv almost every week, many of them studying what the output amplitudes look like in “noisier” situations than the ones Arkhipov and I considered (typically with only heuristic complexity analysis). But I’m not aware of any dramatic experimental progress within the last year or two. If I hear of any, I’ll let you know!
Comment #73 October 6th, 2014 at 12:38 pm
Hm, I was about to post this article I saw on Reddit not too long ago, but looking at the paper’s abstract, it looks like it’s just one of the ones with only heuristic complexity analysis that Scott talks about. So much for that…
Comment #74 October 6th, 2014 at 12:45 pm
Scott #71: Ok, agreed, Dawkings would be shocked. 🙂
How about another imaginary conversation: Einstein thanking Michelson for his contribution to special relativity. Isn’t it ironic: after Michelson proves that aether doesn’t slip much by Earth, and because Earth drags aether along its orbit the speed of light is the same in all direction, somebody comes to him thanking for proving that aether does not exist! Wasn’t he listening? 🙂
Comment #75 October 6th, 2014 at 12:57 pm
This whole evolution-vs-creation debate is a straw man red herring. In any case, one could easily say God created the process of evolution, along with the logical constraints on our universe that made it work.
Or just say God just invented mathematics and logic itself, and therefore anything that you can prove logically just gives more evidence to the existence of God.
If you are going to believe in God, you start by believing in God, and then all other learning is developing a better model of what it is exactly you believe in. (This is possible because belief here does not have an intellectual meaning, think “believe in me” versus “I believe you wore that same shirt 4 days in a row”.)
Comment #76 October 6th, 2014 at 4:20 pm
Title proposal: Quantum computing — less powerful then you think, more interesting than you can imagine.
Comment #77 October 6th, 2014 at 5:20 pm
Dave R #75:
“God created the process of evolution” is more or less the gist of Theistic Evolution (a.k.a. Evolutionary Creationism).
The purpose, I think, is to alleviate the cognitive dissonance of those who intellectually cannot deny science, emotionally cannot give up religion, and have enough integrity not to descend into outright doublethink.
Comment #78 October 6th, 2014 at 6:17 pm
Scott, maybe a dumb question, but Shor’s algorithm was a surprise discovery, so what are the basic arguments that a better exponential speedup can’t be obtained from Nature, especially if Many-Worlds interpretation of Quantum mechanics is correct?
(feel free to link a talk/paper/suggest I read the book)
Comment #79 October 6th, 2014 at 7:27 pm
The link to the Cornell event doesn’t work; it is accessible only to internal Cornell people I believe.
Are there any other links to this interesting event?
Comment #80 October 6th, 2014 at 8:00 pm
James #78: Formally, no one can rule out the possibility of a fast quantum algorithm to solve NP-complete problems (or even PSPACE-complete problems, for that matter), any more than they can rule out the possibility of a fast classical algorithm for those problems (that’s the P vs. NP question). In some sense, we can’t even hope to prove such results given the current state of knowledge in complexity theory.
What we can say for sure is that
(a) after 20 years of relevant research, no polynomial (or even subexponential) quantum algorithm has been found for NP-complete problems (or even for “easier” problems, like inverting various one-way functions), any more than classical algorithms have been found for these problems.
(b) if a quantum algorithm existed, it would have to look totally different from Shor’s algorithm, or any of the other quantum algorithms we know. (In particular, for known quantum algorithms, such as the adiabatic algorithm with linear interpolation, there are known cases of NP-complete problems for which they provably require exponential time.)
(c) crucially, any fast quantum algorithm for NP-complete problems could not work by “simply trying all the possible solutions in parallel”—that sort of approach, when taken to its logical conclusion, can give you the quadratic speedup of Grover’s algorithm, but provably no more than that. Instead, such an algorithm would have to exploit the structure of NP-complete problems in an extremely nontrivial way, much as a fast classical algorithm would have to.
If people understand all the above, but still want to hunt for a fast quantum algorithm for NP-complete problems (or speculate about its existence), I really have no quarrel with that. My beef is simply that almost all the popular articles don’t explain the universally-accepted points above. Instead, they make it sound like exponential quantum speedups for NP-complete problems are a sure thing, and that such speedups would be as straightforward as trying all the solutions in different branches of the wavefunction—which, again, is known to be false.
Incidentally, what you believe about the Many-Worlds Interpretation has no bearing whatsoever on this question. All that matters is whether the equations of quantum mechanics are exactly correct. If they are, then the question of whether there’s a fast quantum algorithm for NP-complete problems boils down to the mathematical question of whether NP⊆BQP (i.e., the quantum analog of the P vs. NP question).
For more, check out my Scientific American article, or NP-complete Problems and Physical Reality, or pretty much any of my talks on YouTube.
Comment #81 October 6th, 2014 at 8:29 pm
Thanks, the fact you are willing to answer such questions from a layman in such detail is beautiful.
Comment #82 October 6th, 2014 at 8:32 pm
Appreciation is all the thanks I need. 😀
Comment #83 October 6th, 2014 at 10:15 pm
/Incidentally, what you believe about the Many-Worlds Interpretation has no bearing whatsoever on this question./
Maybe it has some bearing on how the question is intuitively understood. If we take many worlds for granted, it’s hard to argue that a QC is not “trying all the possible solutions in parallel”. Main point against this view is equations show a quadratic speedup and no more. Isn’t that better than saying there are many worlds that we can’t interact with? We can’t test non-interacting worlds; we could imagine testing the quadratic speedup.
I like your parallel with Bell inequality. The fact that you can do this thing (try all the possible solution in parallel) that all your prior intuition tells you would logically imply (exponential speedup), yet you still can’t (do better than quadratic speedup for unstructured search), is even more incredible than if you could (have exponential speedup).
Comment #84 October 6th, 2014 at 11:09 pm
re #82: I appreciate SO, not least because of how much work it takes to do something like this.
Comment #85 October 7th, 2014 at 2:10 am
The link to the talk now requires a login. Is there a way to access the talk without a Cornell connection?
Comment #86 October 7th, 2014 at 4:35 am
Don #79, Russ #85: Sorry about that! I don’t know.
Comment #87 October 7th, 2014 at 4:38 am
Jay #83: Yes, that’s true. Someone who accepts Many-Worlds will (almost by definition) use different words to describe what a quantum computer does than someone who rejects it. On the other hand, if we just want to know whether there exists a polynomial-time quantum algorithm to solve NP-complete problems, then the answer (whatever it is) is independent of which words we use to describe it.
Comment #88 October 7th, 2014 at 4:54 am
Scott #58 & #80
I wonder whether a part of this confusion arises due to a fundamental mismatch between the sort of question that comes naturally to most lay-people’s minds versus the questions that the formal TCS field tries to answer. i.e. Raw Speed is what people think about perhaps in some sort of simplistic way. How fast can I solve a problem or how much faster will a certain development allow me to solve problems of interest.
The various families of complexity and limiting behavior is an alien concept so no wonder people make mistakes about the ability of a QC. The constant factors or multiplying factors matter more to people than the large-n behavior.
It is reminiscent of the situation with p values in statistics. There’s nothing inherently evil about them other than that they answer a question that no-one’s really asking and hence people conveniently believe that it answers the question they are asking.
Comment #89 October 7th, 2014 at 5:04 am
Rahul #88: The problem with that view is that, if a quantum computer isn’t giving you an asymptotic speedup, then there’s usually no reason to think it will give you any speedup. (Or rather: whatever speedup you got, would then have nothing directly to do with your device’s being a quantum computer.)
In other words, if people want me to rephrase in terms of constants, I’m happy to oblige: there is no compelling theoretical evidence, at present, that QCs will give any practically-important speedup at all compared to simulated annealing or other classical algorithms, for NP-complete problem instances of size one million (though there might well be a modest speedup, e.g. with the adiabatic algorithm; whether there is or isn’t is a very interesting question).
Comment #90 October 7th, 2014 at 7:20 am
Dave R #75:
This whole evolution-vs-creation debate is a straw man red herring. In any case, one could easily say God created the process of evolution, along with the logical constraints on our universe that made it work.
Or just say God just invented mathematics and logic itself, and therefore anything that you can prove logically just gives more evidence to the existence of God.
I’m not sure how serious you were, but: a God whose only role was to enact the laws of math and logic, or (a bit more comprehensibly…) those of physics, is not a God that could plausibly answer prayers, or forgive sins, or more generally, place any of the concrete demands on human behavior that have long been most of the substance of religion—besides of course those demands that can be defended logically (but in that case, why did we need to refer to God?). That’s the reason why these questions have been disputed.
Comment #91 October 7th, 2014 at 7:54 am
Scott 90: Not sure I follow… Just cause God happened to make laws of Physics that logically led to human beings, why can he not forgive sins? Or do anything else he wanted for that matter?
Anything wrong with religion shows an error in the model we use to understand God; it doesn’t show there is no God.
Thus, logic and reason can be used to debate different models of God for internal consistency (and consistency with things one purports to believe), but not to prove or disprove God’s existence…
Comment #92 October 7th, 2014 at 8:30 am
I think the reasons for misperceptions about quantum computing are largely due to the fact that quantum phenomena is deeply counterintuitive because it is so different from our daily experiences.
Taking a page from Dawkins, what you need is a good meme that correctly frames quantum computing. Good luck! Maybe you should issue that challenge to your readership.
PS. All the unsolicited book title opinions you are receiving remind me of the unsolicited opinions I got about the name of my first child before she was born.
Comment #93 October 7th, 2014 at 8:33 am
Scott, please excuse your readers’ unceasing — yet entirely reasonable natural — desire for clarity about the nature of Shtetl Optimize’s extraordinary claims.
Question Don’t even the most elementary geometric and dimensional considerations provide ample reasons to foresee transformational speedups from D-Wave-type annealing dynamics?
Suppose (for example) that in regard to a class of \(n\)-bit optimization problems (for example, a class of SAT-solving problems) the computational power of an annealing algorithm scales linearly with \(\ln d\), where \(d\) is the dimensionality of the annealing state-space.
For a classical product state-space of (Bloch) qubits we have \(d\sim2^n\). In contrast, for the varietal joins that are the effective state-space of noisy quantum dynamical systems, \(d\sim c^n\), where in practice \(c\simeq 20\) is typical.
Then for this hypothetical-yet-plausible class of problems, the relative computational power of D-Wave-type varietal versus classical annealing is \(n\ln (c/2)\sim \mathcal{O}(n)\). Good on `yah, D-Wave!
From a commercial and/or strategic point-of-view, an \(\mathcal{O}(n)\) speedup is of course utterly transformational … yet to the gatekeepers of the Complexity Zoo, it is “only a polynomial speedup”… hence scarcely interesting.
Both viewpoints are of course reasonable, and needless rhetorical imprecision in this regard can serve only to impair student appreciation of fine works like Anne Greenbaum’s Iterative Methods for Solving Linear Systems (1998) and its successor volume (with Tim Chartier) Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms (2012).
It is desirable too for students to appreciate too, that a considerable proportion of transformational-yet-polynomial algorithmic speedups are held as trade secrets and/or state secrets … much to the impairment of the clarity and naturality of the mathematical literature, and much to the diminishment of the collegiality that sustains the vigor and integrity of fundamental research and teaching.
Summary To great benefit, the STEAM community can work to — in Scott’s well-framed phrase — “combine an openness to extraordinary claims with an unceasing demands for clarity about the nature of those claims”. Two concrete steps are (1) rhetorically respect the transformational implications of “mere” polynomial speedups, and (2) appreciate and preserve the relative freedom that boson-sampling enjoys from the fetters of trade-secrecy and state-secrecy.
Comment #94 October 7th, 2014 at 9:15 am
Whoops! Suddenly my MathJax preview started working, and I can see that the middle paragraphs (of #91) should have read:
The key point is unchanged: “mere” polynomial speedups associated to more-than-classical yet less-than-Hilbert state-spaces are both mathematically plausible and socially transformational.
Exercises (1) chart the constant-dollar stock-price of the (classical) simulation company ANSYS for the past 20 years, and (2) reflect upon year-by-year advances in computer chess strength; how are these advances achieved?
Comment #95 October 7th, 2014 at 9:34 am
Scott #89:
That is a lovely, accurate, pithy summary of the factual situation (I think).
And this is where the “careless or unscrupulous parties”, as you put it, step in to couch that core fact into layers of fluff so that the heart of the matter becomes unrecognizable fuddled up for the lay reader. No wonder people are expecting massive parallelism and other miraculous speedups.
Of course, the media is only one portion of the guilty parties.
Comment #96 October 7th, 2014 at 10:53 am
The link to the streaming video seems to be behind a login wall. One seems to need a Cornell NetID to watch the video.
Comment #97 October 7th, 2014 at 2:18 pm
“Obama has nuclear weapons, but then again, he also has Congress”
I wonder in what universe Obama has Congress?
Comment #98 October 7th, 2014 at 2:34 pm
Scott. Out of interest, can you give a short, memorable and accurate summary of what extra power quantum computing *is* likely to give over classical computing and why? Something at a level that a CS or Physics major who has taken no quantum computing classes could understand. I think it would be helpful if such a short and memorable explanation existed as then it could replace the inaccurate versions that are so prevalent.
The idea of trying all different possibilities at once is easy to understand and remember, even if wrong. It sticks in people’s minds, I would suggest, mostly for want of any other memorable explanation for why people are excited about potential speed ups from quantum computing.
Comment #99 October 7th, 2014 at 2:42 pm
John Sidles #93:
Which ones, for example? Or is that a stupid question? Even if we don’t know the exact algorithms do we know what they do and that they exist?
Comment #100 October 7th, 2014 at 2:58 pm
John Sidles #93, #94: I’ve already explained to you several times that we don’t know any examples of large constant-factor speedups from quantum algorithms. We have exponential and polynomial speedups, and a few factor-of-2 speedups, e.g. for PARITY (which, however, should be seen as model-dependent artifacts). Obviously, if such constant-factor speedups existed, they could be of considerable practical interest, even supposing that asymptotic speedups were unachievable for some reason.
But you don’t get to “suppose” large constant-factor speedups exist, and then pontificate about my narrow-mindedness on the assumption that they do.
Conversations are supposed to make forward progress: I tell you that no examples are known, then you respond by giving me an example—or at any rate, doing something other than simply repeating your original contention that I disregarded the (nonexistent?) examples of what you’re talking about.
Alas, in all your years and thousands of comments on this blog, I can’t recall a single case where you changed the content of anything you said in response to anything anyone else told you. (At most, you acknowledged that the other person’s view was a “Great Truth,” while your original, refuted view was “also a Great Truth.”) Your monologues do slowly evolve over time (e.g., STEM turned into STEAM for some reason), but they’re monologues—quoting and repeating other people’s comments in a chatbot-like fashion, but never learning anything from them. That’s the infuriating characteristic that’s already led to two blog bans and might lead to a third.
Comment #101 October 7th, 2014 at 3:07 pm
#97 Maybe it was Gates who has Congress….
Comment #102 October 7th, 2014 at 3:12 pm
Scott #100: In John Sidle’s defence, he only assumes that acquiring a few random bits of incoming information is just as good as processing all of it, per PCP[poly(n),O(1)] = PCP[0, poly(n)].
Comment #103 October 7th, 2014 at 3:17 pm
Dave R #91:
Not sure I follow… Just cause God happened to make laws of Physics that logically led to human beings, why can he not forgive sins? Or do anything else he wanted for that matter?
Well, of course it’s a logical possibility! What the theory of natural selection did wasn’t to disprove the existence of a God deeply concerned with human affairs (I completely agree that can’t be done), but “merely” to undermine the reasons why most thoughtful people throughout history believed that such a God was warranted by the evidence. I.e., people thought that the apparent design of the living world required a designer, and if there were a designer, then it probably had some reason to design the living world the way it did—something it wanted from all the plants, animals, and humans it created. Natural selection undermined that particular positive case for religion, causing many believers to fall back on arguments of the form “well, you can’t prove that it’s not so.” (Of course, this is all extremely well-trodden ground.)
Comment #104 October 7th, 2014 at 3:19 pm
Wiggy #98:
Out of interest, can you give a short, memorable and accurate summary of what extra power quantum computing *is* likely to give over classical computing and why?
Sure The power of interference. 🙂
(For a longer answer, I’ll be giving a talk on exactly this question at Yale this coming Friday, and will post my slides online.)
Comment #105 October 7th, 2014 at 3:29 pm
What can I tell you Scott – new freshmen every year 🙂
Believe me, my biggest gripe is not with atheists or whatever, but rather with religious people trying to “prove” God exists by the fact that we (humanity) can’t explain something. It inevitably leads to, after someone has explained it, others going “see, I told you God doesn’t exist”.
My point is that belief in God should be excluded from scientific discussion, because it only ends up serving to obfuscate the waters and misrepresent the meaning of faith.
Comment #106 October 7th, 2014 at 3:31 pm
Dave #105:
What can I tell you Scott – new freshmen every year
LOL! In any case, it sounds like our views on this aren’t nearly as far as I’d thought.
Comment #107 October 7th, 2014 at 3:46 pm
“Speaking Truth to Speedup”
Oops, won’t want to use that now that I thought of it first I imagine ;]
Comment #108 October 7th, 2014 at 3:59 pm
#80
Question evoked by this technical answer. We know that, relative to some oracle that can ‘hide the answer at random’, P=!NP. Couldn’t we use BQP as a ‘source of randomness’ to prove that P=!BQP, from which P=!PSPACE would follow?
Comment #109 October 7th, 2014 at 4:17 pm
Jay #108: I confess I don’t quite understand the question. Yes, we know an oracle separation between P and BQP, just like we know an oracle separation between P and NP. But alas, these oracle separations don’t imply any complexity class separations in the “real” (unrelativized) world.
And yes, of course a quantum computer can always generate random numbers, which is one thing that a deterministic Turing machine can’t do (by definition). But that fact doesn’t imply that quantum computers can efficiently decide any language that classical computers can’t also efficiently decide. (After all, we believe today that P=BPP, even though classical randomized computers can generate random numbers, which classical deterministic computers can’t. The conjecture is that randomness improves your language-deciding speed by at most a polynomial factor.)
In any case, in some sense the “right” question to ask is BPP vs. BQP, rather than P vs. BQP—in which case the whole point is moot.
Comment #110 October 7th, 2014 at 4:45 pm
Sorry for the bad question (still your answer helped!).
We have an oracle R so that P^R =! NP^R. Naively, it seems that R is such that (1) P^R == BPP ; (2) NP^R == BQP ; and from that it seems we could conclude (3) BPP =! BQP.
But it’s both too trivial to got unnoticed and too interesting you’d have talk about it. So it’s wrong. My question is, why is it wrong (and moot)?
Comment #111 October 7th, 2014 at 5:32 pm
Jay #110: Sorry dude, but both steps of your argument are nonsense! 🙂
If you choose a random oracle R, then with probability 1 you’ll have PR≠NPR, and also BPP⊂PR. But you will not have PR⊆BPP. Indeed, with probability 1, PR will contain uncomputable problems, like the problem of guessing the bits of the specific random sequence R! (You can choose an oracle randomly, but once you do, it’s just a fixed thing.)
On the other side, the situation is even worse: BQP would not contain NPR (again, NPR has uncomputable problems), but furthermore, we have no reason to believe, at present, that NPR would contain BQP. Quantum interference is just a fundamentally different kind of ability than the nondeterminism of NP, which helps explain why, at present, we can’t prove either of the containments NP⊆BQP or BQP⊆NP (and indeed, both of them might well be false).
Comment #112 October 7th, 2014 at 6:01 pm
“Everything You Always Wanted to Know About Quantum Computing* ”
(*But Were Afraid to Ask)
Comment #113 October 7th, 2014 at 6:38 pm
The link to the video sends me to a page asking for a Cornell login (which I do not have). Is there another source? Thanks!
Comment #114 October 7th, 2014 at 8:27 pm
/P^R will contain uncomputable problems, like the problem of guessing the bits of the specific random sequence R!
This is valid decision problem, really? Ok, but that seems not too difficult to fix. Let call P^R’ the class of *computable* problems that… we would then have BPP=P^R’ and P^R’⊂NP^R’, wouldn’t we?
/we have no reason to believe, at present, that NP^R would contain BQP
Ok, this one kills the nonsensical moot idea. Moreover, dude reads the inclusion would be strict even if NP^R would contain BQP, and that’s kill the idea too. (dude still interested by the technical questions above)
http://arxiv.org/pdf/quant-ph/9701001v1.pdf
Comment #115 October 7th, 2014 at 9:11 pm
Wiggy #98
This is a good reference as well:
http://math.nist.gov/quantum/zoo/
Comment #116 October 7th, 2014 at 9:44 pm
Scott, fortunately I watched your talk before the video became password-protected. I think you said (but I cannot re-watch to verify) that when you were an undergraduate at Cornell, Hopcroft unsuccessfully tried to talk you out of theory, contending that essentially all theory questions were solved.
That person being Hopcroft, I would really like to understand what he meant—what his view of theory was at the time. Can you comment?
Comment #117 October 7th, 2014 at 9:49 pm
Scott, it’s anon 114 again. I think at the end of the talk you say something like you find no reason for a quantum-gravity-computer-brain to have evolved, as neither factoring nor simulating quantum physics have anything to do with surviving the African savannah. This sounds flawed to me–just because we found no use for a quantum-brain other than factoring does not mean that is the only thing such a brain is good for.
Comment #118 October 8th, 2014 at 12:43 am
rrtucci #19. is Scott Dan Brown? Or will he partner with DB?
Carl Offner #43. What about this small modification? Say like “Quantum Computing: Why it does not try every solution in parallel?”
Blake Stacey #38. What about this modification? “The Myths, Mysteries and Magic of Quantum Computers and Parallelism.”
Surely Scott, the book with that title of yours will only be bought and be read by SO fans and almost no-one else. You got create a catchy name like what JS refers to in #27. That title surely knocks home of lots of souls. Besides, that “speaking truth to power” is a difficult concept to grasp especially for people not interested in US politicos (I am one of them).
You said you admire Bill Gates, then try to emulate his speaking/writing/answering style at least.
However, I will surely buy that book whatever title it will have because I have been baptized by SO and at least I can get a whiff of what’s cooking.
Comment #119 October 8th, 2014 at 3:29 am
Wavefunction #97:
I wonder in what universe Obama has Congress?
Obviously, I meant “has” in a negative sense. I.e., he’s had Congress to block almost every single useful thing he’s wanted to do—in some cases, things most Congresspeople would actually support if they came from anyone other than him.
Comment #120 October 8th, 2014 at 3:33 am
Everyone: OK, I emailed the organizers of the Cornell 50th anniversary celebration to ask why the videos are now password-protected, and whether there are plans to make them publicly accessible again. I’m sorry for the inconvenience.
Comment #121 October 8th, 2014 at 3:39 am
Jay #114: You ask an extremely interesting question! Namely: with probability 1 over a random oracle R, is the set of computable languages in PR equal to BPP? I conjecture that this is the case, but I don’t see a proof right now. Does anyone else? If not, I’ll ask about it on CS Theory StackExchange.
(Presumably the proof would go roughly as follows: if our language is not in BPP, then it must have an infinite amount of algorithmic mutual information with R, in which case it isn’t computable.)
But yes, if you don’t impose a computability constraint, then “output the ith bit of R” is a perfectly legit example of a problem in PR.
Comment #122 October 8th, 2014 at 3:55 am
anon #116:
That person being Hopcroft, I would really like to understand what he meant—what his view of theory was at the time. Can you comment?
I’ve met several other people who Hopcroft tried to talk out of doing theory, so it’s not an isolated case. I’m hesitant to speak for him, but I suspect what he had in mind is that the kind of theory that was popular in the 60s and 70s—regular languages, finite and pushdown automata, computability, basic graph algorithms and data structures, NP-completeness proofs—has been very heavily mined, so that even if there are still open problems left, an ambitious young person might do better to pick a different area. And I would agree with him about that, but also say that TCS has responded by simply moving into new areas: to give just a few examples, inapproximability, derandomization, locally decodable codes, fully homomorphic encryption, learning theory, combinatorial auctions, phylogenetic trees, streaming and sketching algorithms, compressed sensing, quantum computing. In a panel discussion at the CU50 event, Hopcroft expressed the view that CS is undergoing a fundamental transformation, from an “inwardly-focused” discipline (about compilers, operating systems, etc.) to an “outwardly-focused” one (about connections to biology, economics, statistics, and other fields). So, while I didn’t talk to him about this, I hope he’d take a rosier view of the kind of theory that many of us do today, which (I’d submit) is outwardly-focused in precisely the way he was talking about.
Comment #123 October 8th, 2014 at 4:04 am
anon #117:
I think at the end of the talk you say something like you find no reason for a quantum-gravity-computer-brain to have evolved, as neither factoring nor simulating quantum physics have anything to do with surviving the African savannah. This sounds flawed to me–just because we found no use for a quantum-brain other than factoring does not mean that is the only thing such a brain is good for.
Well, sure. But I’d say that the ball is now firmly in the court of the quantum brain proponents, to explain what they think a quantum brain would be good for—so that it could have evolved despite what looks like the extreme difficulty of maintaining long-range entanglement in the hot, wet environment of the brain (and the lack of evidence from neuroscience that any such thing is happening). My point was just that you don’t get to blithely assume—as many people writing about this subject do—that, if the brain were a quantum computer, then it could achieve super-duper-creativity by exploring all the possible answers in parallel. It’s worthwhile for people to understand that that’s not a good description of how any known quantum algorithm actually works.
Comment #124 October 8th, 2014 at 6:55 am
#115
Thanks for the link but I think we have misunderstood each other. The challenge is not to list all the results we can think of in quantum algorithms. It is rather to give a short, memorable and accurate summary of why we are excited by quantum computing for those not working in the area. People can and do easily remember and understand the inaccurate sentence “You can try all different possibilities simultaneously and hence solve problems exponentially faster. ”
So let me creep around the topic a little. People can understand “Standard computing is based on classical mechanics but quantum computing is based on quantum mechanics and if we can get this to work, which will involve considerable engineering challenges we haven’t fuilly resolved yet, we could achieve spectacular speed-ups”. But then we need to be able to say *why*. Now Scott would answer “interference” but that is a little short. I suggest we just need two or more clear sentences to follow.
Comment #125 October 8th, 2014 at 7:34 am
/ PR equal to BPP? (…) I’ll ask about it on CS Theory StackExchange. (…) “output the ith bit of R” is a perfectly legit example of a problem in PR.
Thanks! Very bad at guessing what is obvious and what is not. Can we take P^R’⊂NP^R’ as obvious or restricting to computable problems may break variations on Baker et al.’s strategy?
Comment #126 October 8th, 2014 at 8:46 am
Jay #125: First of all, if you just want an oracle separation between P and NP, you don’t need a random oracle. An explicit, computable oracle A, constructed via diagonalization, also works (in fact that was what Baker-Gill-Solovay did originally—random oracles were introduced later, by Bennett and Gill). In which case, all languages in PA and NPA will clearly be computable.
Having said that, if you do use a random oracle R, then I believe you’re right that the only languages in NPR but not in PR, which can be proved to be such with current techniques, are going to be uncomputable languages! (For example, the language {0n : the first 2n bits of R contain a string of n consecutive 1’s}.)
Of course, “really” P≠NP :-), and therefore any NP-complete language should give an example of something in NPR but not in PR. However, related to the previous conjecture, let me now conjecture the following: if P=NP, then with probability 1 over a random oracle R, the only languages in NPR but not in PR are uncomputable. (Indeed, this would follow from a direct analogue of the other conjecture for NP: that for a random oracle R, the only languages in NPR but not in AM, the probabilistic version of NP, are uncomputable languages.)
Comment #127 October 8th, 2014 at 8:48 am
Scott #22:
Out of curiosity, Hopcraft back then was dissuading you and others from doing theory, so was there something else specifically that he wanted people to work on?
Like you for instance. In other words, what are typical non-theory jumps for a guy like you in an alternative universe. I’m assuming Hopcraft wasn’t exactly saying go design planes or something.
Programming? Or stuff like chip design? UI design? Like what was possibly the alternative pathways someone like Hopcraft had in mind looking at the state of TCS back then.
Again, just curious.
Comment #128 October 8th, 2014 at 8:57 am
Rahul #127: I believe he did mention other parts of CS that I should consider instead, but to be perfectly honest, I don’t remember which they were, and I don’t want to put words in his mouth. The conversation was 17 years ago.
(Incidentally, trying to dissuade people from doing theory could just be a standard ritual, justified in some such way as: “if this person is truly meant to do theory, then he or she will ignore my advice; the only ones on whom the advice will work are those for whom it’s good advice.” Like the early scenes of a karate movie, where the master tries to talk the apprentice out of his or her quest. 😉 )
Comment #129 October 8th, 2014 at 9:14 am
Wiggy #124:
Now Scott would answer “interference” but that is a little short. I suggest we just need two or more clear sentences to follow.
Reminds me of when a reporter asked Feynman to explain in a couple sentences what he had won the Nobel Prize for, and he answered that if he could do that, it wouldn’t have been worth a Nobel Prize. 🙂
OK, OK, how about: “Quantum algorithms achieve speedups by exploiting the central phenomenon of quantum mechanics, which is interference between paths with different amplitudes. The quantum algorithm designer carefully choreographs things so that the paths leading to each wrong answer interfere destructively and cancel each other out, while the paths leading to the right answer—or at any rate, to some answer that tells you something about your original problem—reinforce.”
Comment #130 October 8th, 2014 at 9:19 am
Everyone: I heard back from the people at Cornell; they say they’re doing a light edit pass on the videos, but in the meantime, the old URLs should have continued to work; they’ll look into the matter and get back to me in a few days.
Comment #131 October 8th, 2014 at 9:51 am
#126
Very interesting, thanks!
Comment #132 October 8th, 2014 at 11:13 am
#129 Scott, that’s very nice.
To follow it up, can I suggest that a Lakatos style dialogue (see https://en.wikipedia.org/wiki/Proofs_and_Refutations ) with imaginary inquisitors on the topic of quantum computing could be a) a huge amount of fun and b) immensely useful.
Comment #133 October 8th, 2014 at 11:14 am
Jay #131: OK, I posted your question on CS StackExchange! Thanks again for the interesting question; hopefully someone will answer it soon.
Comment #134 October 8th, 2014 at 3:20 pm
I got some basic questions.
1) Is the hidden subgroup problem for all groups in BQP? (I know it is for some non-abelian groups, like generalized quaternion groups)
2) What’s the relationship between BQP and NP-intermediate?
3) Is circuit minimization in BQP?
4) How can quantum algorithms be leveraged for first order theorem proving? Is search sufficient? 3 SAT seems pretty easy in comparison. I mean technically there’s a quadratic speedup for 3-sat, and you can reduce a SMT question to SAT, but what about for undecidable theories with infinite models? It’s not obvious to me how to implement resolution with a set of support with quantum search.
Comment #135 October 8th, 2014 at 4:21 pm
While you’re on the subject of the random oracles, what do you think about the random oracle hypothesis? The IP theorem gives a counterexample. Is there some substitute with algebraic oracles?
Comment #136 October 8th, 2014 at 4:21 pm
So, if I understand the responses so far, we indeed have BPP=P^R’ and AM=NP^R’, through appeal to 1-0 law and known equivalences BPP=Almost-P and AM=Almost-NP (was bluffed by the appeal to 1-0 law!).
This result, in addition to P^R⊂NP^R, confirm your conjecture that finding a computable problem separating P^R and NP^R (would lead to BPP⊂AM)/(is as hard to prove as BPP⊂AM).
Thanks Scott for providing&posting a clean question, and thanks Grochow&Jeřábek for the answer!
Comment #137 October 8th, 2014 at 6:40 pm
Douglas #135: Don’t believe the Random Oracle Hypothesis, never did. On the other hand, I dislike when people get dogmatic about these things. Even if ROH fails, it can still be extremely interesting to know whether two complexity classes can or can’t be separated by a random oracle—basically, you’re asking whether there’s a “highly unstructured problem” (or better: problem with extremely weak promise) that one model of computation can solve and the other can’t.
(For example, would you have guessed that P and NP can be separated by a random oracle, but that P and NP∩coNP can’t be—at least not without separating complexity classes in the unrelativized world?)
Comment #138 October 8th, 2014 at 7:52 pm
Dez #134:
(1) Ettinger, Hoyer, and Knill showed that HSP can always be solved using a polynomial number of quantum queries to the group oracle. Unfortunately, for most nonabelian groups (Sn, D2n, etc.), we don’t actually know how to implement the measurement on the coset states in BQP—we only know that a measurement exists (possibly requiring exponential time)! So, unknown.
(2) There exist (probably) NP-intermediate problems, like circuit minimization, the turnpike problem, etc., that no one has had any good ideas for how to put in BQP. In the other direction, we don’t know whether BQP is contained in NP. So, I guess I’ll go with incomparable as far as anyone knows?
(On the other hand, here’s an interesting question that just occurred to me. Can one show that, if NP⊄BQP, then there must exist NP-intermediate problems that aren’t in BQP? I conjecture that one could, using a variant of Ladner’s construction. Of course, the NP-intermediate problem constructed this way will be extremely artificial.)
(3) As I said, I’ve never seen any half-promising idea for how to put circuit minimization in BQP, though (I hope you’re sitting down for this…) we can’t rule it out either.
(4) The question of what polynomial speedups one could expect for various specific NP-complete problems is an extremely messy and complicated one. For one has to compare the best classical algorithm out there against the best quantum algorithm—and both might be extremely hard to determine on their own! And the answers might be problem-dependent.
So, to answer your question: I can’t think right now of anything better to do for first-order theorem-proving with a quantum computer, than
(a) taking a standard backtrack search algorithm and Groverizing it, or
(b) converting to 3SAT and then running the adiabatic algorithm.
Comment #139 October 8th, 2014 at 11:37 pm
Scott #128:
Perhaps CS needs harder, colder, more persuasive karate masters? 🙂
Comment #140 October 9th, 2014 at 9:16 am
Scott – can you comment on the response to Jay’s question over at StackExchange? It is a little confusing to me because
a) Josh uses this AlmostP class when you explicitly say not to.
b) Emil points out that the only property of computable languages that is used in the proof is that they are countable. But if we union in your “problem of guessing the bits of the specific random sequence R”, the language is still countable but not computable, right?
Comment #141 October 9th, 2014 at 10:58 am
Sleepy #140: Josh’s solution is correct, and nice (I don’t know why I didn’t think of using the zero-one law).
a) While Jay’s model was different from AlmostP (because of the order of quantifiers), Josh PROVES that it ends up equaling AlmostP.
b) In place of the computable languages, we could use any countable set of languages that’s SPECIFIED IN ADVANCE (i.e., any set not depending on R).
Comment #142 October 9th, 2014 at 12:21 pm
In fields of computer science other than quantum computing, such as machine learning, for example, there are algorithms that seem to solve real-world instances of NP-complete problems efficiently. Why they do is, according to some talks I’ve heard, not well-understood mathematically. So is it crazy to think that a quantum computer might do something strange and new that lets it solve real-world instances of difficult problems efficiently? It’s a hard question to answer because we can’t directly do much experimentation yet, but my point is that sometimes we can make practical progress without understanding the theory, right?
Comment #143 October 9th, 2014 at 1:39 pm
Dear Scott,
Just about getting a sense of the current happenings around here, but, seriously:
When was the last time you ran the risk of an “Ask Me about Anything” edition of your blog-posts? (The quoted words may not be exact.)
*Before* you got your tenure?
–Ajit
[E&OE]
Comment #144 October 9th, 2014 at 3:04 pm
Scott #138:
Thanks, I appreciate it. It’s exciting that so much is unknown and so much to learn, but also a bit distressing that we don’t know anything.
I’m trying to imagine what sort of problems are outside NP but inside BQP. Are there any candidates? Can we prove that there are BQP problems that exist outside of NP if we make assumptions about other complexity classes?
Circuit minimization, if it’s in BQP, struck me as an actually useful application of quantum computers. Maybe it’s too much to hope for it to be in BQP.
As for quantum algorithms that attempt to answer first order validity, it would be nice to know there’s some polynomial speedup faster than Groverizing (what an amusing term) but I also suspect there isn’t. It’s not obvious to me even how to apply Grover’s algorithm to first order resolution for undecidable theories either. I guess that shouldn’t be too surprising, given how much work is still left to do improving the question of answering first order validity with classical algorithms.
Comment #145 October 9th, 2014 at 5:36 pm
Sam Hopkins #142
Can you provide some references of these particular algorithms and on how they were tested?
Comment #146 October 9th, 2014 at 10:18 pm
If you really do want to continue with the ineffective protest slogans of people who shouldn’t write until they get a job shtick, Scott, you could call your new book “Rage Against the Bad Meme: Speaking Truth to Quantum Magic” and also cover things like long-distance entanglement ≠ faster than light communication, rather than just “it’s not parallelism, stupid”. Maybe call The Great Randi and ask for his suggestions; he is one of the best debunkers of our time.
Comment #147 October 9th, 2014 at 10:33 pm
Ajit #143: My last Ask Me Anything was less than a year and a half ago, after I got tenure (indeed, it was subtitled “Tenure Edition”). I’ll do another one soon—sooner if enough people request it. I assure you that the reason for the delay is not fear of what people might ask me, but lack of time (especially large contiguous chunks of it). These days, every minute I spend blogging is a minute I’m likely getting yelled at for not changing a diaper.
Comment #148 October 9th, 2014 at 10:43 pm
Dez #144:
I’m trying to imagine what sort of problems are outside NP but inside BQP. Are there any candidates? Can we prove that there are BQP problems that exist outside of NP if we make assumptions about other complexity classes?
If you’re willing to broaden ever-so-slightly what you mean by “BQP”—to include sampling tasks performable in quantum polynomial time (rather than just language decision problems)—then the answers to your questions are “yes” and “yes.” This follows from my work with Arkhipov, and the independent work by Bremner, Jozsa, and Shepherd. The candidate problems are things like BosonSampling. One can prove that, if these quantum sampling tasks could be simulated exactly in classical probabilistic polynomial time with an NP oracle (i.e., in BPPNP), then the polynomial hierarchy would collapse to the fourth level.
If, on the other hand, you insist on talking about promise problems, then the best candidates we can currently give, for problems in PromiseBQP but not in PromiseNP, are things like, “the problem of simulating a given quantum circuit, to see whether it accepts with probability at least 2/3 or at most 1/3, promised that one of those is the case.” (Or other things known to be equivalent to that, like “the problem of estimating the Jones polynomial of a given knot.”) We don’t know of any bad consequences if these problems were in PromiseNP; it just seems unlikely.
And if you insist on talking about BQP and NP themselves—i.e., the “traditional” classes of language decision problems, with no promise—then we don’t currently have any candidate for something in BQP but not in NP (but nor can we give evidence against it).
Comment #149 October 9th, 2014 at 11:00 pm
Sam #142:
So is it crazy to think that a quantum computer might do something strange and new that lets it solve real-world instances of difficult problems efficiently?
No, it’s not crazy at all. It’s a fascinating question fully worthy of all the effort it’s received from researchers of the caliber of Farhi, Goldstone, Gutmann, et al. And you’re completely right that, at this point, it seems likely that it will only be settled by experiments with real quantum computers, when and if they’re built. (Though it’s also possible that people will still debate the question, even after universal QCs are a reality: “I got a speedup using my QC!” “Nuh-uh! I can get the same performance using a tuned-up version of simulated annealing!” “Oh yeah? Bet your classical code can’t solve these instances!” “Maybe not, but I have a new classical code that can!” etc.)
As I’ve said before, as long as people understand
(a) the lack of current evidence that QCs will give a huge performance advantage for NP-complete problems, and
(b) the need for extreme standards of care and honesty when reporting experimental results about this question (given the difficulty of figuring out asymptotic growth rates from data for small n, the incentive “not to look too hard” for a classical algorithm that matches the performance of your quantum algorithm, etc.),
I have no further quarrel with speculations like the one you ask about.
Comment #150 October 9th, 2014 at 11:08 pm
Scott #147:
Cool. So tenure doesn’t affect the blog. Fine. Just wanted to ask a question. Guess any time is good enough. So, here I go:
The implications of success in building a QC, or even otherwise getting NP problems to accelerate are obvious: such huge amount of our infrastructure is based on public key cryptography. Not only Internet commerce and financial institutions but also defence installations.
Do you think that the amount of investment in this public key cryptography technology might be resulting in discouragement of research in this direction? Discouragement, including in the sense that there might be some deliberate spin going on to make it look as if these problems are more difficult than they actually are?
In particular, suppose someone finds a way to solve one of the NP problems in a significantly faster way. Not necessarily quantum; it might even be some classical way. … Apart from the usual “skepticism” from other researchers, would he also face some “trouble” (including that from government)?
What is your take on this scenario? Also, of your readers’? What would you (and they) suggest him? Should he go to a corporation and file for a patent (keep a relatively insignificant amount of money) and let the corporates handle all the headaches? Or should he go to arXiv, upload a paper, and thus hand it all for free to any one, including the stealers who want to hack into your bank right tomorrow if that is possible?
Finally, since the public key cryptography isn’t going to hold its fort forever, what other competing security technologies or means could possibly replace it? Would the existence of such alternative technologies lend a helping hand to the inventor?
These were the issues I wanted to raise somewhere. Perhaps you could discuss it sometime.
Best,
–Ajit
[E&OE]
Comment #151 October 10th, 2014 at 7:49 am
Ajit #150: The answer is no—in my 16 years in theoretical computer science, I’ve never seen an indication that anyone, in or out of the US government, has ever discouraged research in algorithms in order to protect the existing public-key cryptosystems.
The first thing you need to understand about that idea is that it would be spectacularly ineffective. If you prevent mathematical weaknesses in your cryptosystem from being publicly researched or discussed, the weaknesses still exist, and will probably be found eventually—maybe by hackers, or the intelligence agencies of unfriendly countries, etc. Far better (on the modern view) for everything to come out in public, so you can patch the weakness and move on.
(Weaknesses that you yourself deliberately inserted—i.e., backdoors—are of course a different matter, but one not directly relevant to your question.)
The second relevant point is that the academic CS community would react apoplectically if (say) the NSA even tried anything like what you suggest. Maybe academic scientists and mathematicians haven’t always paid as much attention as they should to whether the NSA was violating ordinary people’s privacy—but tell scientists they’re not allowed to publish their research papers, and then watch the shit hit the fan. 😉
Thirdly, there already have been many algorithmic discoveries that have potentially threatened public-key infrastructure, such as the Quadratic Field Sieve and the Number Field Sieve (the classical subexponential-time factoring algorithms), Shor’s quantum factoring algorithm, and Joux’s recent work on discrete logs in GF(2n). But the NSA didn’t try to stifle any of these discoveries: they just reacted to them, the same way everyone else did.
Fourthly, your question conflates “NP problems” in general with the specific NP problems—like factoring and discrete log—that are actually relevant to existing public-key cryptosystems. Historically, improvements in (say) heuristic algorithms for NP-complete optimization problems have had no implications whatsoever for factoring, and conversely, improvements in factoring algorithms have had no implications whatsoever for solving NP-complete problems, because the methods one wants to use for factoring are so specialized and number-theoretic.
And for factoring, someone who discovered a fast algorithm would have no burden of skepticism to overcome. When people email me to say they’ve discovered a fast classical factoring algorithm, my response is always: “great! code up your algorithm, then use it to factor the RSA challenge numbers, and send me the factors!” Ron Rivest tells me he does the same thing. Neither of us ever hears back. 🙂
OK, so suppose you do discover a fast classical factoring algorithm. What’s the ethical thing to do? Well, there’s already a well-established protocol for academics to disclose computer security weaknesses (which, in practice, usually means bugs in implementation, though it could also be more mathematical). The protocol is that you first contact the companies that produce or use the flawed system, to give them a month or so to get a patch ready. Then you disclose the weakness to the world. For a fast factoring algorithm, I imagine the same ethical principles would apply, except that the scale (i.e., what needed to be fixed) would be massively larger.
Which brings me to your last question: if and when RSA, Diffie-Hellman, and elliptic curve cryptography all fall, we’ll still have several options, including
(a) lattice-based or error-correcting-code-based cryptography—currently less efficient than RSA for comparable security, but people are working on improving it,
(b) going back to private-key crypto, which when properly implemented, seems much harder to break (even if you don’t use one-time-pads), or
(c) switching, ironically, to quantum key distribution. (“Quantum giveth, and quantum taketh away.”)
Comment #152 October 10th, 2014 at 8:11 am
Scott, on #151, what if someone instead claims that they have discovered a fast classical algorithm for computing discrete logarithms modulo a prime? Are there standard challenges like the RSA challenge for that too?
Comment #153 October 10th, 2014 at 8:27 am
jonas #152: I think there are, but if not, you could easily generate some yourself. (Just pick a large random prime, and 2 other random numbers modulo it! Or, if you want to generate the instance while also knowing the answer, that’s easily done as well.)
Comment #154 October 10th, 2014 at 9:37 am
Scott: re #153, ok. Public instances posed by trusted third parties like those in the RSA challenge are important because they help convince everyone, not just you if you give numbers in the challenge, while at the same time working like a zero knowledge proof, not letting you to choose numbers that help you break particular cryptographic messages of your choice.
Comment #155 October 10th, 2014 at 12:29 pm
Scott, what is your understanding of the history of DES? Did NSA have differential cryptanalysis before? Did IBM invent it, and were convinced to keep it secret? Both?
But some say that the DES changes did cause academics to freak out, creating academic cryptography, and the development of differential cryptanalysis a decade and a half later. But that is a pretty big head start.
I think that there are other examples of NSA convincing people to keep their discoveries secret, but I don’t know them off the top of my head.
Comment #156 October 10th, 2014 at 2:12 pm
Douglas #155: I don’t know the history well enough to say. But
(a) Even if the NSA were able to get away with such things in the 1970s, academic cryptographers have become so super-duper-sensitive about these issues that it seems doubtful they can do so today.
(b) There’s a difference between discovering a detailed vulnerability in some particular system like DES (something of no broader intellectual interest), and discovering a fast factoring algorithm, which is what Ajit was asking about. Much much harder to suppress the latter.
Comment #157 October 10th, 2014 at 3:01 pm
Differential cryptanalysis was not specific to DES. It broke most contemporary private-key cryptosystems. It is the foundation of the modern field.
Which is not to say that it is of as broad interest as factoring, which solves a problem everyone knows about, and stands for the difference between quantum and classical computation.
Comment #158 October 10th, 2014 at 3:35 pm
Douglas #157: Yes, thanks, you’re right. Having read some more about DES and differential cryptanalysis, it does indeed sound like the best historical example of what Ajit was asking for. Something of some intellectual interest (albeit not nearly as much interest as a fast factoring algorithm) was, in fact, kept secret at the urging of the NSA (albeit by IBM researchers rather than academics). Of course it was eventually rediscovered, illustrating one of the points in my comment.
Note, also, that this wasn’t a matter of the NSA suppressing a whole research area for fear of what might be discovered there—or of its suppressing knowledge of a general weakness in a cryptographic standard it had adopted, even though that weakness would remain to be rediscovered by someone else. (That, as I said, would be stupid of them.) Rather, they suppressed the fact that DES was designed to evade differential cryptanalysis, since they couldn’t explain that without revealing differential cryptanalysis itself.
Even then, I’m a bit skeptical that anything similar would happen today—especially now that, post-Snowden, whatever trust once existed between NSA and the broader community of crypto experts has dwindled to where it seems funny even to use the word “trust.”
Comment #159 October 10th, 2014 at 4:49 pm
Jonas, it’s easy to create a credible problem instances using hash functions. Choose a prime and compute the discrete logarithm of SHA256(0). There are standard primes. There’s probably a DSA standard that specifies some. Or you can concatenate a bunch of hashes to get a big enough number and then take the next biggest prime.
Comment #160 October 11th, 2014 at 12:21 pm
My previous comment contains many errors. First, it does not contain a problem instance, because it does not specify a generator for the group.
Second, random instances are not cryptographically meaningful instances. The problem is that people do not work with the full group of units mod p, but with a pretty small subgroup of controlled size. I suppose that if you had a standard set of domain parameters you could raise a random number to a particular value to get into the standard group and then have a credible random instance.
A cursory search does not bring me a standard set of domain parameters. Creating your own is more involved than just choosing a prime and might be subject to suspicion. But this must be implemented in crypto libraries, so you can just set the random seed to 0 or SHA(0) or something to generate a credible set of domain parameters of known provenance.
Comment #161 October 11th, 2014 at 9:16 pm
now we need to clear on major misconception , dwave claims adiabatic quantum computation achieves exponential speed up via quantum tunneling for optimization problems what does complexity theory math models say about it?
Comment #162 October 12th, 2014 at 7:21 am
upen #161: See here.
Comment #163 October 12th, 2014 at 10:20 am
Re: Discrete log challenges.
As Scott already said, there are no published challenges but it easy to generate one yourself.
But I wanted to point out that, for the similar question of elliptic curve discrete log challenges, there many many well-funded challenges in the form of Bitcoin. If you can break elliptic curve discrete logs for the curve secp256k1, you can abscond with millions of dollars in Bitcoin. Of course, if you are too greedy, you’ll crash the price.
Comment #164 October 12th, 2014 at 12:36 pm
yesterday i was reading through geometric complexity and i was thinking on these lines assume i have a hypothetical algorithm
that relies on some coefficients to solve np problems and by trial and error we find these coefficients for several n but finding
these coefficients is again a np hard problem or might be even worse or may be bounded in a polynomial search space ….
how do we reconcile this now there are no geometric obstruction certificates for part of the problem set?
or the problem set does not contain the values of n we for which
np hard problems have become simple
Comment #165 October 13th, 2014 at 9:48 am
I have taught Calculus 2 several times, and it often happens that, after a whole semester of talking about improper integrals and convergence of series, someone remarks that the harmonic series must converge, since you are adding smaller and smaller terms, or else that the series $\sum n^{-2}$ must diverge, since you keep adding more and more.
Scott, you are fighting a hopeless battle…
Comment #166 October 14th, 2014 at 8:55 am
Scott, your analysis of what might happen if the NSA found out that someone had invented a fast non-quantum factoring algorithm before it was published seems surprisingly naive.
In fact it’s a fun game to speculate what they would do. I suspect they would forcibly bring the person in for a gentle chat. Then sit around in panic meetings trying to work out what to do while you waited for hours if not days. Then they might offer you a highly paid classified job and appeal to your patrotism (assuming you of a nationality they approved of) and if you seemed unkeen they could quietly point out that you would be sent to jail for life if you leaked the factoring algorithm.
What do you think they would do?
Comment #167 October 14th, 2014 at 9:53 am
Scott, would you mind to comment on Grochow’s last clarification (following on Jeřábek’s comment about countability vs computability)?
First he explicits the result: for any countable (computable or not) C⊇AM, if P=NP, the “only” languages that witness the oracle separation P^R≠NP^R are outside of C.
Second he noticed that it sounds like, for any L0 we could consider C=AM∪{L0}, and thereby “show” that no L0 realizes NP^R≠P^R, contradicting the well-known theorem. Is it Bennet and Gill he had in mind?
Third, could we reexpressed this result as “if a language does not witness P≠NP, then it does not witness BPP≠AM”? Isn’t that an immediate proof that AM=NP?
Comment #168 October 14th, 2014 at 12:19 pm
Jay #167: Yes, Josh’s update is correct. And no, I don’t see any proof of AM=NP in anything he wrote—for one thing, I have no idea how you got that “reexpression” of what he wrote.
Yes, Josh was talking about Bennett and Gill’s result. As Josh pointed out himself, the reason there’s no contradiction is that “probability 1” is not the same as “all.” If P=NP, and you fix L in advance, then with probability 1 over R, your L will not witness PR≠NPR. On the other hand, with probability 1 over R, there is some L that witnesses PR≠NPR. These statements are perfectly consistent.
Comment #169 October 14th, 2014 at 12:32 pm
Wiggy #166: If you just wrote a paper about factoring being in classical polynomial time, without (let’s say) explicitly pointing out any implications for breaking any particular cryptosystem, then I don’t see how the NSA would have any ground to prevent you from publishing the paper that could hold up in court. They might plead with you to delay publication by a few weeks or months, while they scrambled to upgrade the nation’s cybersecurity infrastructure. And they’d probably be right that delaying publication would be an ethical thing to do. They might also offer you vast sums of money if you gave them secret, exclusive access to the algorithm, even just for a few years. But throwing you in jail for publishing a pure math paper? I’d love to see that one adjudicated in court. If you’re right about what would happen, I’d then agree that our system had been shown to be fundamentally no different than the USSR’s.
Comment #170 October 14th, 2014 at 1:32 pm
#169
Thx again. Now it’s time I stop bothering you. One last thing 🙂 Was L a typo in “if you fix *R* in advance”?
Comment #171 October 14th, 2014 at 2:21 pm
#170 Scott. The situation may be different if they found out pre or post publication, I really can’t guess. But in general, there are catch-all “endangering national security” laws and they could argue that releasing a math paper that you knew would endanger the safety of the US is no better than releasing the passwords to a top secret military computer system. You could after all get arrested for a number of years for publishing DeCSS code.
Arguably, watching a region 1 DVD of the Matrix in France is less of a risk to national security than being to decrypt military communication.
Of course I agree with you that in some (thankfully not all) disturbing ways the US is fundamentally no different than the USSR.
(I would be very interested to hear what other, perhaps more knowledgeable, people think the NSA would do.)
Comment #172 October 14th, 2014 at 3:57 pm
Wiggy, as Scott pointed out above, this has happened, twice. Not polynomial time algorithms, but algorithms fast enough to break the existing RSA infrastructure.
Comment #173 October 15th, 2014 at 4:17 am
#173 Douglas Knight. I may be historically inaccurate but I don’t feel anything similar to the NSA discovering pre-publication that there is a technique that will fundamentally undermine a large section of the security infrastructure of the nation has happened. Or at least we haven’t been told about it if it has.
Let me take the examples already given. I should say I have no idea if the NSA knew about them pre-publication or not.
Shor’s algorithm. Surely the NSA would have taken the view that this posed no immediate threat. 20 years later there are still respectable academics who seem convinced that it will never pose a serious threat.
Quadratic sieve (1981 according to wikipedia). RSA-129 was cracked in 1994 using QS.
The number field sieve (1990). Another speed up, and it has been improved after years of refinement. RSA-768 was cracked in 2009.
I don’t think it is fair to say these techniques broke the RSA infrastructure.
I also don’t know what key sizes the US government used in 81 or 90 or what they predicted the abilities of these methods would be. Maybe someone here does.
However, we do know that if an algorithm were published that allowed you to crack RSA-4096, say, on a home desktop, this would fundamentally break the computer security of the US.
Comment #174 May 19th, 2016 at 1:25 pm
[…] Aronson has complained about similar simplification of quantum computing by the media lead to the popular impression that “quantum computing = […]