Five announcements
1. Sanjeev Arora sent me a heads-up that there’s a discussion about the future of the STOC conference at the Windows on Theory blog—in particular, about the idea of turning STOC into a longer “CS theory festival.” If you have opinions about this, don’t miss the chance to make your voice heard.
2. Back in January, I blogged about a new quantum optimization algorithm by Farhi, Goldstone, and Gutmann, which was notable for being, as far as anyone could tell, the first quantum algorithm to achieve a provably better approximation ratio than the best-known classical algorithm for an NP-hard optimization problem. Today, I report that a fearsome list of authors—Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright—has put out an eagerly-awaited paper that gives a classical algorithm for the same problem, with better performance than the quantum algorithm’s. (They write that this “improves both qualitatively and quantitatively” on Farhi et al.’s work; I assume “qualitatively” refers to the fact that the new algorithm is classical.) What happened, apparently, is that after I blogged (with enthusiasm) about the Farhi et al. result, a bunch of classical complexity theorists read my post and decided independently that they could match or beat the quantum algorithm’s performance classically; then they found out about each other and decided to merge their efforts. I’m proud to say that this isn’t the first example of this blog catalyzing actual research progress, though it’s probably the best example so far. [Update: Luca Trevisan now has a great post explaining what happened in much more detail, entitled “How Many Theoreticians Does It Take to Approximate Max 3Lin?”]
Another update: Farhi et al. have posted a new version of their paper, in which they can almost match the performance of the classical algorithm using their quantum algorithm.
3. Jennifer Ouellette has a wonderful article in Quanta magazine about recent progress in AdS/MERA (i.e., “the emergence of spacetime from entanglement”), centered around the ideas of Brian Swingle. This is one of the main things that I’d love to understand better right now—if I succeed even partially, you’ll know because I’ll write a blog post trying to explain it to others. See also this blog post by Sean Carroll (about this paper by Ning Bao et al.), and this paper by Pastawski, Yoshida, Harlow, and Preskill, which explicitly mines the AdS/CFT correspondence for examples of quantum error-correcting codes.
4. Celebrity rationalist Julia Galef, who I had the great honor of meeting recently, has a podcast interview with Sean Carroll about why Carroll accepts the many-worlds interpretation. (Or if, like me, you prefer the written word to the spoken one, click here for a full transcript.) Unfortunately, Sean is given the opportunity at the end of the interview to recommend one science book to his listeners—just one!—but he squanders it by plugging some weird, self-indulgent thing called Quantum Computing Since Democritus. Julia also has a YouTube video about what she learned from the interview, but I haven’t yet watched it (is there a transcript?).
5. I came across an insightful if meandering essay about nerd culture by Meredith L. Patterson. In particular, noticing how the term “nerd” has been co-opted by normal, socially-skilled people, who’ve quickly set about remaking nerd social norms to make them identical to the rest of the world’s norms, Patterson coins the term “weird-nerd” to describe people like herself, who are still nerds in the original sense and who don’t see nerd culture as something horribly, irreparably broken. As she writes: “We’ll start to feel less defensive when we get some indication — any indication — that our critics understand what parts of our culture we don’t want to lose and why we don’t want to lose them.” (But is this the start of a linguistic treadmill? Will we eventually need to talk about weird-weird-nerds, etc.?)
Follow
Comment #1 May 17th, 2015 at 5:36 am
Oh, man, I have a bunch to say about the notion of “nerd”! This is an inconvenient time, but maybe I can cobble together something quickly from previous writings… (I wish I had something to say about the mathematics or physics in this post, but, I don’t!) So as a result this will not be responding very much to the actual link, sorry; my apologies if I’m saying something already addressed in there.
Basically, I agree that there is a useful notion of “nerd” that seems to have gotten buried beneath the whole “geek culture” avalanche (comic book movies are pretty damn mainstream now, remember!), and it seems to line up well with how you use the word “nerd”. I agree it might be a good idea to use a term other than “nerd”, though as to what it might be I don’t know (I’d considered “knerd” or “pnerd”, but, those are kind of throwaway terms, not really fit for general use); the reason being, anytime anyone wants to talk about nerds in the useful sense (and, say, their relation to feminism), someone always takes it as nerds in the “geek culture” sense, and then the whole discussion gets derailed and the point gets entirely lost. (And as for Hanson’s “smart sincere syndrome”, well, we tend to be self-congratulatory enough already. 😛 )
But it’s not just about being merely “weird”! So what is this useful sense? Well, OK, there’s a few different ones, though they’re related. You’ve got the ordinary sense of, like, people with technical interests or who like comic books or anime and such, or who are socially awkward, aren’t well-groomed, etc; this is maybe useful, but it’s not that useful, and it’s mixed together with a bunch of the “geek culture” stuff I want to ignore, so I’m mostly going to ignore this. We’ll call these sense-1 nerds.
The first more useful sense is how Robin Hanson, Michael Vassar, Razib Khan, etc., all use the word “nerd”. OK, I’m not sure they’re all on exactly the same page, but they seem to be getting at something in common — people with a focus on explicit beliefs and reduced compartmentalization, people who bite bullets, and who also are frequently drawn to simple principles. We’ll call these sense-2 nerds. Sense-2 nerds tend — at least, like, in environments I’m familiar with — to be sense-1 nerds, but the reverse is less true.
We can then break down sense 2 even further. (We can also break down sense 1 further, but I’m not interested in doing so here.) First off, we’ve got 2a, which is the more general form of sense 2 — nerdism in general, including Hindu fundamentalists and whoever.
(We might want to be even more general, call this, uh, 2a’ — if you read Sark Julian or N. N. Taleb, they seem to use the word “nerd” in a much broader sense, so broad that you should not be looking at who is or is not a nerd, but rather noticing the nerdy aspects and non-nerdy aspects of all things.)
Then you have sense 2b, which, as best I can tell, seems to be how you use the word “nerd”; sense 2b is the realization of 2a that I’m most familiar with. It includes e.g. a focus on truth and a belief in extreme honesty (and also bluntness); not a mere disregard for social niceties, but often an active disdain for them as being somehow wrong. To my mind this archetype of Nerd is largely defined by its contrast with the opposing archetype of Suit. (Some people would use the opposition Nerd/Jock, but I find the Nerd/Suit contrast to be more illuminating.)
(Ozy has this notion that they refer to as the “not-geek not-autism thing”, which sounds at first like it might be nerdism, in either sense 2a or 2b, but from their descriptions of it doesn’t seem to be. I don’t know what’s up with that.)
So, in summary, I’m claiming that there is a useful core notion of “nerd”, it’s a particular thing, not just weirdness and not just “geek culture”, I think you recognize what it is, but we need to do a better job being clear about this when we talk about nerds, because the point keeps getting lost, but I don’t know how.
Comment #2 May 17th, 2015 at 6:25 am
I’d like to point out Brian Koberlein’s podcast, where he interviews Edwin Hach about quantum computing. (It seems he studies fundamentals and not QI or QC, so there are some errors in the presentation)
https://briankoberlein.com/2015/05/16/quantum-computersphysical-constants/
Comment #3 May 17th, 2015 at 7:43 am
AdS/MERA and the error-correcting codes seems interesting. There’s been talk about spacetime having to be emergent for a long time.
A couple of things come intuitively to mind:
– Error-correcting codes could give properties that otherwise look like fine-tuning.
– Lack of entanglement tearing spacetime apart sounds similar to a planckian cosmological constant creating Planck-sized Hubble volumes
It would be neat if these were connected.
Comment #4 May 17th, 2015 at 7:50 am
First comment! Woohoo!
On a more serious note, what do you think about conferences and efficiency. It’s no secret that we academics live on a tight budget, many are trapped in the post-doc cycle and many don’t become post-docs in the first place for shortage of places. Do you think we should be stingy with conferences? I mean a collective planning by members of a field of how many conferences we should have per year and cutting down on unnecessary (and perhaps distracting) activities like tours of the city where the conference is held or expensive dinners. Ultimately such activities are usually funded by research schools, and the money
Comment #5 May 17th, 2015 at 7:52 am
cont. could be devoted to getting more post-docs or for genuine research.
Edit: Apparently I didn’t type fast enough and I’m 3rd commenter not 1st..damn
Comment #6 May 17th, 2015 at 12:23 pm
Pat #4: I do think, in general, that there are too many conferences, at least in the fields I know. I don’t know what to do about this, except to say:
– If you’re thinking of planning a conference, think hard about whether your field really needs another (in addition to how much work it will be for you!). I’ve managed to get through my entire career so far, I’m happy to say, without adding a single new conference or workshop of any kind (fingers crossed) 😉
– If you’re invited to a conference, think hard about how much value it has. See if you can limit your conference attendance to 5 or 6 per year (yes, for most of the academics I know, at least the ones without kids, that would be a significant limit!).
Having said that, I also think whatever conferences we do have should be fine affairs, and should provide opportunities for grad students, postdocs, etc. to socialize and meet each other. So I’m not at all averse to holding them in interesting locations, having good food, and offering time off for tourism (though it’s fine if the participants have to pay for much of that themselves).
You put conference spending up against the hiring of more grad students and postdocs, and there are indeed legitimate questions there (the amount I spend on travel each year is, I dunno, maybe half the cost of one PhD student?). But then there’s also the question of the value of increasing the number of grad students and postdocs, if there aren’t also going to be more tenure-track faculty lines. How much does it help to widen the first part of the hose if the rest of it remains as narrow as before?
Comment #7 May 17th, 2015 at 3:21 pm
It would be awesome if some of those fancy space/time, quantum/gravitation math constructions could lead to unique “macro” predictions that don’t require a particle accelerator the size of the solar system or poking an actual black hole with a stick.
Comment #8 May 17th, 2015 at 5:18 pm
If there is another printing of your book, then that Sean Carroll quote had better be on the cover.
Comment #9 May 17th, 2015 at 6:37 pm
That was a quick response from the Polynomial Alliance. 🙂
Research in Quantum Computing & NP-hard optimization problems seems to be very active.
Do you expect that sooner or a later a proof of a quantum speedup for NP-Hard optimization problems will hold?
D-Wave and Google seem to be counting on it. I’ve not seen any really compelling evidence for that. A Grover type of speedup seems plausible, but i imagine even then it would only apply to a subset of inputs and be just another heuristic.
Comment #10 May 17th, 2015 at 7:08 pm
I can’t think of a single idea of Sean Carroll’s that I agree with. The epistemic version of the Copenhagen interpretation is the original version, it’s not some modern innovation. Many Worlds has no sensible account of what a world is or where the Born rule comes from – the wonderland logic of his paper with Sebens certainly doesn’t count. He has some recent papers trying to eliminate Boltzmann brains by denying that vacuum fluctuations in de Sitter space are real, or by saying that the Boltzmann brain needs to be externally observed to be real… I struggle to think of another celebrity physicist like this.
Comment #11 May 17th, 2015 at 7:13 pm
Job #9:
Do you expect that sooner or a later a proof of a quantum speedup for NP-Hard optimization problems will hold?
Even if it’s true that there are quantum speedups for NP-hard optimization problems, I don’t expect such a speedup to be proved anytime soon, simply because a proof would require ruling out any possible classical algorithm with comparable performance. One could, of course, hope for a speedup under reasonable assumptions: for example, if someone discovered a quantum algorithm that provably, always solved 3SAT in 2√n time, then that would be a quantum speedup under the widely-believed Exponential Time Hypothesis (that 3SAT requires 2Ω(n) time classically). Unfortunately, such an algorithm seems like a long shot.
So maybe the more likely scenario is that we continue to design and explore quantum algorithms for NP-hard problems (like the adiabatic algorithm and Farhi et al.’s new algorithm), and it continues to be really hard to figure out how much speedup they’re giving you over classical. E.g., sometimes the quantum algorithms outperform any classical algorithm that anyone can think of, but then someone else does think of a quantum algorithm (as happened here), but then new cases are found where the quantum algorithm again does better, etc. On this view, a quantum algorithm for optimization problems would indeed be “just another heuristic” (as you put it), although it might well be the best heuristic available at a given time and for a given application (assuming, of course, a hypothetical world with scalable QCs).
One last remark: while Farhi et al.’s algorithm attacks a problem (Max3Lin) that’s known to be NP-hard to approximate beyond a certain ratio, the approximation ratio that they achieve is below the critical value! Indeed, it’s only because we’re talking about a “non-NP-hard region” of the NP-hard problem, that a polynomial-time quantum algorithm with provable performance guarantee was a reasonable thing to hope for. (Of course, there turned out to be a fast classical algorithm for this region as well! But it was clear even before that that this region wasn’t NP-hard—for one thing, because solutions always existed there, putting the problem in NP∩coNP.)
Comment #12 May 17th, 2015 at 7:43 pm
By approximation ratio are you referring to the number of instances that the heuristic is able to solve versus the total number of possible instances of size n, for some fixed n?
I’ve wondered whether the success ratio for these NP-Hard heuristics approaches zero as n increases – in fact i’ve always assumed that’s the case.
If that’s true, and these algorithms do solve 0% of all instances, then why wouldn’t a classical heuristic always be able to match a quantum heuristic?
Comment #13 May 17th, 2015 at 8:14 pm
Job #12: No, that’s not what it means. These are not average-case algorithms; they’re supposed to work for every instance that satisfies the stated conditions. But they’re approximation algorithms, so they may not satisfy all the constraints. The approximation ratio is the number of constraints that the algorithm guarantees it will satisfy, divided by the number of constraints that are satisfied by the optimal assignment. In the case at hand, the ratio looks like 1/2+c/√D, where c is a constant and D is a parameter (the number of constraints that each variable appears in).
Comment #14 May 18th, 2015 at 12:32 am
Scott,
What is a nerd “in the original sense”?
I first heard the word in 1961, in 7-th grade homeroom. I used the word “nard” (an insult my brother and his pals had made up), and my homeroom teacher (just out of college, and sporting the first multi colored hair I had ever seen) said “Don’t you mean nerd?”. Unfortunately, she did not say what she thought nerd meant.
Comment #15 May 18th, 2015 at 1:06 am
…OK, having actually read the Patterson article now, I see that I was largely repeating what was already in it…
(I don’t really understand the bit about “constructivism” though. Seems to me nerds are plenty willing to follow lines of logic to their conclusion and bite the bullet without any constructive requirement; I’d call that one of their distinguishing features…)
Comment #16 May 18th, 2015 at 2:16 am
#2 Am I allowed to gloat & be all annoying & say I-told-you-so. 🙂
OK, to be fair, Scott did admit this was a plausible bet. 🙂
At this point is it reasonable to accept the following statement as a working hypothesis (or maybe a challenge?)
“No quantum algorithm can provably achieve a better approximation ratio for a natural NP-hard optimization problem than the corresponding best known classical algorithm.”
Comment #17 May 18th, 2015 at 8:03 am
Rahul #16: Yeah, that’s the obvious challenge now (or, working hypothesis to be refuted)! I can tell you that Farhi et al. are looking hard for other examples where “Quinoa”-type algorithms might get an advantage. Very far from obvious that they’ll succeed; definitely worth looking.
Comment #18 May 18th, 2015 at 9:39 am
Scott #17:
Good to know about people continuing to look.
My impression is that nobody looks real hard for a very optimal classical algorithm for some of these rather abstruse problems………….until a situation arises when a quantum algo does better than the best known classical algo.
And then, of course, a lot of very smart people start looking for a classical winner. And they seem to find it.
Comment #19 May 18th, 2015 at 9:48 am
Rahul #18: Well, yes, that’s clearly what happened in this one case. If it happens two or three more times, then we can start claiming a pattern! 🙂 (But keep in mind: Simon, in 1994, was motivated by what then looked like a pattern that if you had a quantum algorithm for an interesting problem—e.g., Deutsch-Jozsa for parity—there would then also be a classical algorithm with similar performance. He discovered his algorithm, which less than a year later led to Shor’s algorithm, while looking for counterexamples to that pattern.)
Comment #20 May 18th, 2015 at 11:27 am
Scott #19:
Is there still an off chance that some inspired genius comes up with a classical algo that beats Shor? Just wondering.
Or is that possibility excluded by some lower bounds proof?
I do admit that 20 years is a long time and lots of very smart people must have tried, but hey then again it took a 100+ years to crack FLT.
Comment #21 May 18th, 2015 at 11:52 am
The more you know…
Comment #22 May 18th, 2015 at 12:01 pm
Raoul #14:
What is a nerd “in the original sense”?
If you missed it, we had pretty extensive discussions of such things on this blog a few months ago, 🙂 but briefly, I think of a “nerd” as anyone who places an abnormal, socially-crippling amount of value on science, rationality, clarity, and truth, as opposed to the winning of social status games.
Some nerds, the more extroverted ones, will just blurt out whatever they think is true, regardless of the social consequences. Other nerds, probably the majority, will realize that their abnormal truth-orientation often makes them social pariahs, and respond by becoming introverts.
Other stereotypical nerd qualities—poor fashion sense and athletic skill, fascination with math and programming, etc.—I view as consequences of the abnormal truth-orientation, rather than as defining qualities of nerdiness. Intelligence is certainly a risk factor for the truth-orientation, but I wouldn’t regard it as a defining quality either.
There’s also this enormous cluster of other attributes—fascination with Star Wars, comic books, anime, Monty Python, etc.—that seems to define “nerdiness” for much of the world, but for which I’d prefer to reserve a different word (geekiness?). These fandoms might be slightly correlated with the sort of truth-orientation I’m talking about (or not—I don’t know!), but they don’t really have anything to do with it.
Comment #23 May 18th, 2015 at 12:11 pm
Rahul #20: Yes, of course it’s possible that someone will find a fast classical factoring algorithm! You couldn’t possibly rule that out without first proving P≠NP (and even then, the classical hardness of factoring is a much stronger statement, and one that not all reasonable people even believe).
On the other hand, such an algorithm would be universally seen as a revolution in math and cryptography. Unlike with what we’re talking about here, it certainly wouldn’t be a case of no one knowing why the problem was all that important until a quantum algorithm for it was found.
Comment #24 May 18th, 2015 at 12:26 pm
The Meredith Patterson article came up on the other Scott A’s blog a while back, at least in the comments – alas my Google skills aren’t up to finding it. I think my comment was something along the lines that it was interesting to read an article complaining of the author’s existence implicitly being erased, while finding that the article was implicitly erasing my own existence. (Grr, I hate those terms. But those are the ones the article used.)
In short – I quite liked the opening parts, but when she rolled onto define what she thought a weird nerd was, that didn’t seem to be me. Although, re-reading, perhaps there’s an ambiguity: ‘I prefer this term to “weird nerds,” and so I’ll use it here: hackers.’ When I read it first time, I thought she was saying ‘”hackers” is a synonym for “weird nerds”‘ whereas now, maybe she’s saying ‘hackers are a subtype of weird nerds’. Maybe I’m being too charitable. Anyway, I identified with the weird nerd bit but not with the hacker bit.
Comment #25 May 18th, 2015 at 1:00 pm
Graeme #21: Haha, that’s clearly related to what Patterson was talking about, but like almost every popular representation of nerdiness—The Big Bang Theory being a partial exception—it focuses on the external and superficial (glasses, wardrobe, Star Trek), without getting to the heart of the matter (truth-orientation), except very indirectly, through the example of the narrator’s speech itself. Also, I had to look up what “eventing” was. Most importantly, of course, I cringed when the narrator explained that “a real nerd is ashamed to be called a nerd.” Even among the most introverted nerds, I don’t think I’ve ever seen shame that was unmixed with defiant pride.
Comment #26 May 18th, 2015 at 2:15 pm
This definition is a close fit to a large, growing, active, inclusive, diverse (and outstandingly friendly) community of self-identified nerds: the Mennonerds.
On Hollywood’s radar screen, this community scarcely exists — it would be quite surprising were The Big Bang Theory to spawn a sequel titled Mennonerds.
And yet a sufficiently imaginative team of writers might discern within the Mennonerd community abundant themes of nerdly humor, passion, struggle, and even triumph. Hollywood, take notice!
Resolved for purposes of debate Kurt Gödel’s philosophical viewpoint — as surveyed in the Gödel’s Lost Letter essay “Reconstructing Gödel” (of Nov. 1, 2014), for example — is a markedly better match to Mennonerds than to The Big Bang Theory. Similarly for nerdly luminaries like Ludwig Wittgenstein (an ardent Tolstoy admirer) and John von Neumann (per his brother Nicholas’ marvelously interesting biography John von Neumann as Seen by His Brother).
Summary The early Enlightenment of the 17th century was born largely of friendly ferment exchanged among three arch-nerd communities: the Anabaptists, the Collegients, and the Spinozists …… and it was crucial to the viability of the early Enlightenment that this ferment was shared warmly and vigorously among that century’s nerd-communities.
Conclusion Now in the 21st century, again a nerdly Enlightenment is fermenting among communities like the Mennonerds (the heirs of Anabaptism), the Big Bang Theorists (the heirs of the Collegiants), and the Univalent Foundationists (the heirs of the Spinozists). And in our 21st century as in the 17th century, it were best if our century’s nerdly communities did not isolate themselves, but rather shared their transgressively nerdly visions — which are naturally compatible (as it seems to me) — in sustained friendly discourse.
Comment #27 May 18th, 2015 at 4:11 pm
Re #22,
By “original meaning of nerd”, I thought maybe some documentation on early usage had been uncovered, as opposed to what the word means now.
I am a little uncomfortable that children associate being smart and the STEM world with being pleasantly goofy. A century ago, many of the greatest physicists and mathematicians went to the mountains often, either trekking or actual climbing. I recommend this for everyone. A brisk climb in thin air will make you glad you don’t have a Star Wars costume in your pack.
Comment #28 May 18th, 2015 at 5:21 pm
Raoul #27: In recent years, we’ve lost a tragic number of truly brilliant mathematicians and computer scientists in mountain-climbing, rafting, and boating accidents (e.g., Oded Schramm, Misha Alekhnovich, Jim Gray, several others who I’m forgetting). And according to a biography I read, Einstein came very close to dying as a teenager when he lost his footing on a mountain-climbing trip. So my personal advice is that nerds choose more nerd-appropriate leisure activities—like, let’s say, a stroll through the grasslands of Princeton, NJ, or from the parking lot to the office. 🙂
Comment #29 May 18th, 2015 at 6:06 pm
Scott #28: Maybe it’s not a coincidence that those bold thinkers didn’t restrict themselves to such pathetically tepid activities.
Comment #30 May 18th, 2015 at 6:38 pm
Huck #29: So then, the advice to nerds would be to go on dangerous mountain-climbing trips, in order to cause themselves retroactively to have been the sort of personalities that go on dangerous mountain-climbing trips and that also think bold thoughts? The causal pretzel here reminds me of the guy who always carries a bomb with him on the plane, because what are the chances that there would be two bombs on the same plane? 🙂
Comment #31 May 18th, 2015 at 7:21 pm
Scott #30: I don’t think Huck’s comment was intended to be advice, but rather as an attempted explanation. Still, this does provide a nice real-world example of the smoking lesion problem* assuming it holds up (to which I don’t assign that much credence).
* I can’t find a Wikipedia article on this.
Comment #32 May 18th, 2015 at 7:36 pm
Scott #6: “But then there’s also the question of the value of increasing the number of grad students and postdocs, if there aren’t also going to be more tenure-track faculty lines. How much does it help to widen the first part of the hose if the rest of it remains as narrow as before?”
Thank you for saying this. I find that this doesn’t get said enough. And a related question, that also does not get discussed enough, is this: are we educating grad students about the shortage of tenure-track positions and the consequences to their (imagined) careers sufficiently early in their PhD programs, so that they have the time to figure out alternative rewarding careers while still in school? In my more cynical moments I argue that the complete lack of this conversation constitutes an unacceptable abdication of responsibility on the part of universities and professors, but that’s another topic for another day. (And yes, I buy that grad students are adults, and need to take responsibility for their own careers, but even so, the lack of this discussion makes no sense to me.)
Comment #33 May 18th, 2015 at 7:45 pm
Scott #30,
This sounds suspiciously close to the smoking lesion problem http://wiki.lesswrong.com/wiki/Smoking_lesion
I suspect what is going on here is the availability heuristic. I’d expect that if one took a genuinely representative sample one wouldn’t find more people in such fields dying than in the general population. But I’m guessing from the smiley you ended comments 28 and 30 with that you already have that conclusion.
Comment #34 May 18th, 2015 at 8:08 pm
Perhaps you can post separate blog posts instead of five-in-ones? It’s impossible to keep up with five intermixed comment streams.
Comment #35 May 18th, 2015 at 8:15 pm
Scott #30: That’s dizzying. I’m not sure where you got the “retroactively” or bomb analogy from.
My point was that many who climb intellectual mountains draw inspiration from climbing physical ones. The two activities are not as far off as you might think, as evidenced by your list of examples and many others.
Comment #36 May 18th, 2015 at 10:13 pm
Scott #6:
Indeed!
Also, might the same apply to Journals too? Not sure if this applies to QC / CS but in the fields I’m familiar with there is a proliferation of micro Journals. A lot of these tend to be of questionable quality & impact.
Shouldn’t we be prioritizing quality over quantity?
Comment #37 May 18th, 2015 at 10:22 pm
Rahul #36:
Also, might the same apply to Journals too?
Yes.
Shouldn’t we be prioritizing quality over quantity?
Yes.
However, a big difference between conferences and journals is that conferences more directly eat up people’s time: it’s not obvious that starting a new journal leads to any more papers being reviewed and published, rather than just more competition between journals for the same papers (with the number of papers largely determined just by how many people are in the field). Whereas starting a new conference really is a decision to have a research community spend a week schmoozing with each other when they could’ve been doing something else. Sometimes that’s the right decision, but one should consider it carefully.
Comment #38 May 19th, 2015 at 12:36 am
Scott #37:
Interesting. One metric to compare might be whether people today are publishing more papers (peer reviewed papers) per year than, say, 50 years ago in a field like Physics or Chemistry that has a reasonably long data set available.
My bet is that they are. But I’d love to know.
The other way to look at this is that perhaps there are more people in the field *because* there are more Journals. i.e. Even if the publications per person remained constant, back in the day only the highest quality people or papers might have had a chance to see the light of day just because there were fewer avenues to get published at.
We do know that funding or tenure, or PhDs etc. are tied to getting publications. Therefore perhaps the ease of publication is driving more people into the field?
Comment #39 May 19th, 2015 at 5:14 am
Rahul #38: From my experience, journals seem like an epiphenomenon—i.e., just not an important causal factor in how many people are working in a given subarea, a consequence rather than a cause. What really controls how many people can work in a given area is how many postdoc positions, tenure-track faculty lines, and other research positions (e.g. in industry) are available. That, in turn, depends on how excited people are about the area: other faculty in the department, sure, but also the students. If zillions of prospective grad students want a given area—whether it’s quantum computing or machine learning or biomedical computing—faculty will get the message that they should hire in that area if they want to stay competitive. And at a different level of granularity, if undergrads are flocking to a given department—as happened to CS departments during the dotcom bubble, and is happening again now—deans will get the message that that department needs more faculty slots.
Comment #40 May 19th, 2015 at 1:54 pm
Scott #39:
What happened after the dot com bubble burst? Did the undergrads stop flocking? What did the deans do to the excess faculty hires when (if?) student interest waned?
Should departments reinforce hype? Should deans rush to cater to the flavor of the month?
Comment #41 May 19th, 2015 at 5:57 pm
@ Mr. Bennett #35:
The great engineer Seymour Cray used to dig tunnels by hand on his property to gain inspiration when he was facing a tough technological hurdle.
Comment #42 May 19th, 2015 at 10:48 pm
1) A quantum algorithm does bettter than any known classical algorithm on some problem.
2) Then better classical algorithms are found so point (1) is no longer the case.
Question: Is this good news or bad news? Of course its good news in that we know more than we used to, and the quantum algorithm was still good to have as an inspiration.
But as a thought experiment- if six months after Shor’s alg for factoring a classical algorithm for factoring was found, then would quantum complexity and quantum algorithms have become popular (no matter how you measure it) fields? I think prob not. And that would be a loss.
Comment #43 May 20th, 2015 at 2:18 am
Re nerdiness: I wonder if you can relate to Jonah Sinick’s story: http://lesswrong.com/r/lesswrong/lw/m6e/how_my_social_skills_went_from_horrible_to/
Comment #44 May 20th, 2015 at 3:12 am
You know, walking is good too.
Comment #45 May 20th, 2015 at 7:14 am
GASARCH #42: You mean, when you became an academic, you didn’t sign the pact that says that learning the truth is always good news, whichever way it goes? Even Farhi, if you asked him, would enthusiastically agree that the classical algorithm for Max 3Lin is wonderful news—fantastic, couldn’t be better. 😉
Comment #46 May 20th, 2015 at 7:21 am
Shmi #43: Jonah is a very good friend, and yes, I can relate to many parts of his story (though he’s probably one of the rare people who spends even more time “metacogitating” than I do, or used to). 🙂
Comment #47 May 20th, 2015 at 7:54 am
Huck #35, William #41, Job #44: To clarify, I love nature outings myself (relatively safe ones), and would never claim another math/science person is “not a true nerd” if they like climbing 3-mile-high avalanche-prone mountains with their bare hands. I just want them to be careful, is all.
Digging tunnels by hand on your own property sounds pretty safe to me, though not the most “inspiring” activity I can think of. To each his own, I guess.
Comment #48 May 20th, 2015 at 10:40 am
Many “nerds” are interested in physical activity as a way to relax their mind/get away from things/focus on their own (neglected) body as a system.
It doesn’t have to involve much risk, e.g. running/jogging (Turing was into it apparently).
I personally started running 3 years ago, and it has changed my life.
And with the advent of VR, even the most physically challenged nerds will soon be able to experience “extreme” situations in a pretty safe way 🙂
Comment #49 May 20th, 2015 at 10:57 am
@GSARCH #42:
Why would it have been a loss? If QC wouldn’t have been as popular maybe that fan following would have gone somewhere else?
Perhaps to that hypothetical algo. that turned out better than Shor.
Comment #50 May 20th, 2015 at 2:54 pm
Rahul #40:
What happened after the dot com bubble burst? Did the undergrads stop flocking? What did the deans do to the excess faculty hires when (if?) student interest waned?
Should departments reinforce hype? Should deans rush to cater to the flavor of the month?
Academics are always asking questions like, “is X just a flavor of the month, or is it here to stay? should we try to hire in this area, or should we wait and see?”
Keep in mind that, when it comes to CS as a whole, the academics who were dramatically, egregiously wrong were the ones who bet on its being just a passing fad. The ones who, in the 60s and 70s, said “we need to hire in this now” were completely and totally vindicated by history. More recently, and within CS, one could make similar comments about bioinformatics, machine learning, network and computer security, etc. So these are not such easy questions.
Also keep in mind that, if any CS department “mistakenly” hired too many permanent faculty during the dotcom boom in the late 90s, then at any rate, those faculty are sorely needed again right now, when CS enrollments are exploding all over the country (like, 30% growth per year) and departments are straining for enough faculty to teach all their courses! 🙂
Comment #51 May 20th, 2015 at 4:14 pm
@Scott #47:
Scott, digging dirt did wonders for Mr. Cray, his innovations in supercomputer design are nothing less than awe inspiring, if you start digging now, maybe you are “only a mile or two away” from proving P!=NP 😉
Comment #52 May 20th, 2015 at 9:24 pm
Heh, recommending your book is about the only rational thing I heard in that Rationally Speaking podcast.
Comment #53 May 22nd, 2015 at 9:15 am
Maybe I’m missing something fundamental, but how come it seems so difficult to come up with hard problems that quantum algorithms can solve way more efficiently than classical ones?
The obvious situation where QC outclass classic machines is for simulating quantum systems, right? Like Boson sampling?
The only currently known similarity between NP-hard problems and quantum systems is that they both feature an exponential explosion (number of potential solution vs state space size), but that’s about it?
Comment #54 May 22nd, 2015 at 9:37 am
Regarding #3, well these theories are all interesting, but so far all attempts to quantize space-time have failed. There was a very telling comment on Sean blog I thought, I quote:
“With the thousands of PhDs, Post docs and careers piled in the general direction of quantizing gravity, and zero hard results, its a fairly obvious dead end.”
Yes, I know quantum-gravity theorists nearly all make the strong assumption that space and time should be quantized, but at this point, in light of the above (repeated failure over decades by thousands of the worlds best and brightest), we really have to question the underlying assumption.
I put it to readers that space-time is NOT in fact quantized, its continuous, and that space-time is NOT in fact emergent, but fundamental.
That is to say, what if quantum effects are merely side-effects of the geometry of space-time, and the continuous geometry of space-time in fact remains rock-solid, and never breaks down at any scale?
Comment #55 May 22nd, 2015 at 12:43 pm
fred #53: We do have other examples of problems that we think quantum computers can solve way more efficiently than classical ones—factoring, discrete log, elliptic curve problems, solving Pell’s equation, finding the unit group and class group of a number field, etc. If you’re willing to include black-box problems, then there are far more examples still. It’s just that we don’t count these, because they’re already understood! If your goal is to go beyond the quantum algorithms that hundreds of smart people have thought of in two decades of working on this … well, yeah, that’s not impossible but is probably hard, no great surprise there. 🙂
Comment #56 May 22nd, 2015 at 4:38 pm
mjgeddes #54:
what if quantum effects are merely side-effects of the geometry of space-time, and the continuous geometry of space-time in fact remains rock-solid, and never breaks down at any scale?
Well, you can conjecture that; like with anything else, the question is what you do with it. So for example, how on earth would you explain Bell inequality violation, or a quantum computation that factored a 10,000-digit number, as “merely side-effects of the geometry of space-time”? Or do you deny that quantum computation is possible? What about Bell violations?
You should also realize that AdS/CFT and the MERA stuff I was talking about are extremely different from, and in some ways diametrically opposed to, the “traditional” ideas about how to quantize spacetime, like loop quantum gravity and spin foams. You don’t put a lattice on spacetime; instead you map a gravity state, via a nonlocal mapping, to a collection of qubits that lives in a different number of spacetime dimensions. It’s true that AdS/CFT and LQG agree about something special happening at the Planck scale of 10-33 cm or 10-43 seconds—our ordinary ideas about distances and times breaking down there—but that’s because that looks like a pretty robust prediction of known physics (in particular, the fact that attempted probes at that scale would just create black holes instead).
Comment #57 May 22nd, 2015 at 5:41 pm
Scott #55
“We do have other examples of problems that we think quantum computers can solve way more efficiently than classical ones […] we don’t count these, because they’re already understood!”
You say “we think” and “they’re understood”, so I’m still not clear whether we have any rigorous proof for any type of problem that QC is definitely better.
If there is no rigorous proof yet, is it for the same reasons that it’s hard to prove that NP!=P?
Comment #58 May 22nd, 2015 at 8:52 pm
fred #57: For many black-box problems, like Simon’s problem and period-finding and searching glued trees and forrelation, there are rigorous proofs that quantum algorithms are exponentially faster than classical randomized ones.
For non-black-box problems, like factoring and discrete log, we indeed can’t hope for rigorous proofs that quantum is exponentially faster in the current state of knowledge, for basically the same reasons why it’s hard to prove P≠NP. (Indeed, if factoring or discrete log are hard classically, then P≠NP.) The best one can say is that a fast classical algorithm for these problems would be a world-changing revolution in classical algorithms.
Comment #59 May 22nd, 2015 at 9:19 pm
Scott #57:
For many black-box problems, like Simon’s problem and period-finding and searching glued trees and forrelation, there are rigorous proofs that quantum algorithms are exponentially faster than classical randomized ones.
Are you referring to the oracle separations?
From your statement it sounds like classical machines can’t possibly solve black-box problems (e.g. Simon’s), but in a hypothetical scenario that BQP=BPP, then wouldn’t classical machines also be able to solve those black-box problems?
I find this very confusing because on one hand oracle separations don’t prove BQP!=BPP and yet they’re often presented as evidence of an exponential quantum speedup.
Were you not referring to the oracle separation for Simon’s problem when you referred to rigorous proofs that quantum algorithms are exponentially faster? If not, which definitive proof that classical machines can’t solve black-box problems were you thinking of?
Comment #60 May 22nd, 2015 at 10:26 pm
Job #59: Yes, “black-box separations” and “oracle separations” refer to the same thing. And yes, the black-box setting is one where we have rigorous proof than quantum computing can give you exponential speedup. In the more practically-relevant setting of gate complexity—i.e., of the unrelativized BPP vs. BQP problem—we have no such rigorous proof, and no hope of one without proving P≠PSPACE. Two different settings, two different situations. For more, see (e.g.) my 6.845 lecture notes.
Comment #61 May 23rd, 2015 at 3:15 am
Scott #56
“Well, you can conjecture that; like with anything else, the question is what you do with it. So for example, how on earth would you explain Bell inequality violation, or a quantum computation that factored a 10,000-digit number, as “merely side-effects of the geometry of space-time”? Or do you deny that quantum computation is possible? What about Bell violations?”
Oh, there’s no doubt that quantum mechanics is a successful theory in the sense of being a fantastic ‘calculational black-box’ that makes correct predictions – so there’s no doubt that things like quantum computational and bell violations are very real.
But as all the philosophical arguments over the correct interpretation of QM show (i.e MWI versus Copenhagen etc.) there remains confusion about QM actually says about reality…there is a missing picture here.
So if we take the geometry of space-time as fundamental, there may be some way to explain QM in terms of a conventional (classical) space-time picture.
“You should also realize that AdS/CFT and the MERA stuff I was talking about are extremely different from, and in some ways diametrically opposed to, the “traditional” ideas about how to quantize spacetime, like loop quantum gravity and spin foams.”
Well I read the Jennifer Ouellette article in Quanta, but I had a hard time making sense of it, there were a lot of complex ideas being thrown in a popular article, hard to understand. As I understand it, Sean Carroll favours a discrete model where space-time somehow emerges from quantum-information.
I know ‘the universe is a computer’ is a popular metaphor these days, but it can’t literally be true, because information always has be instantiated on an underlying physical hardware located in a space-time that can only ever be consistently described using a number-line of natural numbers (that is to say, based on calculus – *continuous* geometry).
“It’s true that AdS/CFT and LQG agree about something special happening at the Planck scale of 10-33 cm or 10-43 seconds—our ordinary ideas about distances and times breaking down there”
Quantum gravity theorists talk about the ‘Plank scale’ and the numbers ’10-33cm and 10-43 seconds’ are thrown about like ‘magic numbers’, but there’s no sound theory for thinking that ‘ordinary ideas about distances and times’ are breaking down there. At least, I’m not convinced.
Comment #62 May 23rd, 2015 at 2:22 pm
mjgeddes #61
Bell violations merely point out that classical field theory would have to be a nonlocal theory to explain those violations.
IOW, quantum theory is a correct theory.
There is no missing picture. There are only ‘philosophers’ who can’t accept that world doesn’t follow their preconceived and preferred notions.
There is are no magic numbers thrown about the Planck scale. Planck constant is a physical, measurable constant and it is well known that physical effects commensurable with the Planck constant follow quantum, as opposed to the classical laws of mechanics.
Comment #63 May 25th, 2015 at 3:34 am
Tony #62
>>”IOW, quantum theory is a correct theory.
There is no missing picture.”
There *is* a missing picture, namely how quantum mechanics is related to space-time geometry. Because there is no such consistent picture, general relativity and quantum mechanics actually contradict one another.
One idea that shows promise is ER = EPR (the conjecture is by Susskind and Maldacena, and suggests that Einstein-Rosen (ER) bridges ( wormholes) are in fact equivalent to quantum entanglement (EPR – Einstein-Podolsky-Rosen).
I’m not saying that this specific idea is correct, but it shows you how quantum effects *could* be given an interpretation in terms of classical space-time geometry.
>>”There is are no magic numbers thrown about the Planck scale. Planck constant is a physical, measurable constant and it is well known that physical effects commensurable with the Planck constant follow quantum, as opposed to the classical laws of mechanics.”
I was specifically referring to claims that space-time is discrete – the claims that there are minimum units of space and time. This is not proven at all. For instance, this is matter of on-going by physics experts at sites such as Physics Stack Exchange.
The fact that Plank units can be derived by arranging physics constants fails to prove that space and time are discrete, a claim many quantum-gravity theorists have tried to make.
Comment #64 May 25th, 2015 at 8:53 am
mjgeddes #63: As a point of information, Susskind and Maldacena, who proposed ER=EPR, say they only expect a geometric picture to work for simple quantum states, such as a large collection of EPR pairs. For more complicated quantum states—like, say, the intermediate states of Shor’s factoring algorithm—they don’t expect any interpretation in terms of spacetime geometry (indeed, if there were such an interpretation, then why couldn’t we use it to efficiently simulate Shor’s algorithm on a classical computer?).
The other thing is that, if you buy into ER=EPR at all, then you’ve bought into a set of ideas about quantum gravity that do treat the Planck scale as fundamental, not just some arbitrary combination of constants.
Comment #65 May 25th, 2015 at 3:09 pm
#63
You are changing the meaning of your statements. Of course, until we know everything about everything, there will always be some “missing picture”.
That’s quite different from tying the missing picture to “philosophical arguments over the correct interpretation of QM show (i.e MWI versus Copenhagen etc.)”
If we could find the ‘missing picture’ via philosophical arguments we would already know everything that is to know, if you subscribe to the ‘right’ kind of philosophy, that is.
If somebody is talking about the ‘Planck scale’ it doesn’t mean that he is claiming that spacetime is discrete. Read about Planck scale at Wiki and search for ‘discrete’. You won’t find it.
Comment #66 May 25th, 2015 at 5:13 pm
I’ve always wondered – if QM indeed allows for way more efficient computations than the classical mode, why is nature (at the biological level) apparently so rooted in the classical realm?
(probably a silly question since humans are part of nature, and by extension so is any quantum computer).
Comment #67 May 25th, 2015 at 7:29 pm
#66 Fred
You mean how come that The Brotherhood of Quantum-computing Neutrinos hasn’t taken over the world yet?
That’s because they don’t see us at all. Roughly 300 trillion of them pass through you every second. 🙂
Comment #68 May 29th, 2015 at 3:37 pm
Hey Scott,
The quantum gravity claim that space-time is a ‘foam’ at the Planck scale is in big trouble!
“A new study combining data from NASA’s Chandra X-ray Observatory and Fermi Gamma-ray Telescope, and the Very Energetic Radiation Imaging Telescope Array (VERITAS) in Arizona is helping scientists set limits on the quantum nature of space-time on extremely tiny scales. Certain aspects of quantum mechanics predict that space-time – the three dimensions of space plus time — would not be smooth on the scale of about ten times a billionth of a trillionth of the diameter of a hydrogen atom’s nucleus. They refer to the structure that may exist at this extremely small size as “space-time foam.”
“Because space-time foam is so small, it is impossible to observe it directly. However, depending on what model of space-time is used, light that has traveled over great cosmic distances may be affected by the unseen foam in ways that scientists can analyze. More specifically, some models predict that the accumulation of distance uncertainties for light traveling across billions of light years would cause the image quality to degrade so much that the objects would become undetectable. The wavelength where the image disappears should depend on the model of space-time foam used.”
NO SUCH EFFECTS ARE PRESENT! In fact:
“Space-time appears to be smooth, at least on scales of 10-16 cm, a thousand times smaller than an atomic nucleus, and space-time must be much less foamy than most models predict.”
http://www.dailygalaxy.com/my_weblog/2015/05/our-invisible-universe-the-foamy-structure-of-spacetime.html
Comment #69 May 29th, 2015 at 10:04 pm
mjgeddes #68: The thing about cosmic rays changing their speed is a prediction of one particular, speculative set of ideas about spacetime discreteness, one that very few serious physicists ever spent time on. (Having said that, being falsified by observation is an honorable fate for a physical theory, much more honorable than never saying anything definite at all.)
The broader idea that our usual notions of space and time have to break down at the Planck scale—something that almost all high-energy physicists believe, because of general arguments about GR and quantum mechanics that seem impossible to avoid—isn’t affected in the slightest by this.
Comment #70 June 26th, 2015 at 3:59 pm
[…] AdS/MERA correspondence has been making the rounds of the blogosphere with nice posts by Scott Aaronson and Sean Carroll, so let’s take a look at the topic here at Quantum […]
Comment #71 March 6th, 2016 at 2:30 pm
[…] turns out not to beat the best classical algorithms on the Max E3LIN2 problem (see here and here)—still, whatever the algorithm does do, at least there’s no polynomial-time classical […]