Archive for the ‘Nerd Interest’ Category

Quanta of Solace

Thursday, June 20th, 2019

In Quanta magazine, Kevin Hartnett has a recent article entitled A New Law to Describe Quantum Computing’s Rise? The article discusses “Neven’s Law”—a conjecture, by Hartmut Neven (head of Google’s quantum computing effort), that the number of integrated qubits is now increasing exponentially with time, so that the difficulty of simulating a state-of-the-art QC on a fixed classical computer is increasing doubly exponentially with time. (Jonathan Dowling tells me that he expressed the same thought years ago.)

Near the end, the Quanta piece quotes some UT Austin professor whose surname starts with a bunch of A’s as follows:

“I think the undeniable reality of this progress puts the ball firmly in the court of those who believe scalable quantum computing can’t work. They’re the ones who need to articulate where and why the progress will stop.”

The quote is perfectly accurate, but in context, it might give the impression that I’m endorsing Neven’s Law. In reality, I’m reluctant to fit a polynomial or an exponential or any other curve through a set of numbers that so far hasn’t exceeded about 50. I say only that, regardless of what anyone believes is the ultimate rate of progress in QC, what’s already happened today puts the ball firmly in the skeptics’ court.

Also in Quanta, Anil Ananthaswamy has a new article out on How to Turn a Quantum Computer Into the Ultimate Randomness Generator. This piece covers two schemes for using a quantum computer to generate “certified random bits”—that is, bits you can prove are random to a faraway skeptic. one due to me, the other due to Brakerski et al. The article cites my paper with Lijie Chen, which shows that under suitable computational assumptions, the outputs in my protocol are hard to spoof using a classical computer. The randomness aspect will be addressed in a paper that I’m currently writing; for now, see these slides.

As long as I’m linking to interesting recent Quanta articles, Erica Klarreich has A 53-Year-Old Network Coloring Conjecture is Disproved. Briefly, Hedetniemi’s Conjecture stated that, given any two finite, undirected graphs G and H, the chromatic number of the tensor product G⊗H is just the minimum of the chromatic numbers of G and H themselves. This reasonable-sounding conjecture has now been falsified by Yaroslav Shitov. For more, see also this post by Gil Kalai—who appears here not in his capacity as a quantum computing skeptic.

In interesting math news beyond Quanta magazine, the Berkeley alumni magazine has a piece about the crucial, neglected topic of mathematicians’ love for Hagoromo-brand chalk (hat tip: Peter Woit). I can personally vouch for this. When I moved to UT Austin three years ago, most offices in CS had whiteboards, but I deliberately chose one with a blackboard. I figured that chalk has its problems—it breaks, the dust gets all over—but I could live with them, much more than I could live with the Fundamental Whiteboard Difficulty, of all the available markers always being dry whenever you want to explain anything. With the Hagoromo brand, though, you pretty much get all the benefits of chalk with none of the downsides, so it just strictly dominates whiteboards.

Jan Kulveit asked me to advertise the European Summer Program on Rationality (ESPR), which will take place this August 13-23, and which is aimed at students ages 16-19. I’ve lectured both at ESPR and at a similar summer program that ESPR was modeled after (called SPARC)—and while I was never there as a student, it looked to me like a phenomenal experience. So if you’re a 16-to-19-year-old who reads this blog, please consider applying!

I’m now at the end of my annual family trip to Tel Aviv, returning to the Eastern US tonight, and then on to STOC’2019 at the ACM Federated Computing Research Conference in Phoenix (which I can blog about if anyone wants me to). It was a good trip, although marred by my two-year-old son Daniel falling onto sun-heated metal and suffering a second-degree burn on his leg, and then by the doctor botching the treatment. Fortunately Daniel’s now healing nicely. For future reference, whenever bandaging a burn wound, be sure to apply lots of Vaseline to prevent the bandage from drying out, and also to change the bandage daily. Accept no fancy-sounding substitute.

On the scientific accuracy of “Avengers: Endgame”

Friday, May 3rd, 2019


Today Ben Lindbergh, a writer for The Ringer, put out an article about the scientific plausibility (!) of the time-travel sequences in the new “Avengers” movie. The article relied on two interviewees:

(1) David Deutsch, who confirmed that he has no idea what the “Deutsch proposition” mentioned by Tony Stark refers to but declined to comment further, and

(2) some quantum computing dude from UT Austin who had no similar scruples about spouting off on the movie.

To be clear, the UT Austin dude hadn’t even seen the movie, or any of the previous “Avengers” movies for that matter! He just watched the clips dealing with time travel. Yet Lindbergh still saw fit to introduce him as “a real-life [Tony] Stark without the vast fortune and fancy suit.” Hey, I’ll take it.

Anyway, if you’ve seen the movie, and/or you know Deutsch’s causal consistency proposal for quantum closed timelike curves, and you can do better than I did at trying to reconcile the two, feel free to take a stab in the comments.

Death of proof greatly exaggerated

Thursday, March 7th, 2019

In 1993, the science writer John Horgan—who’s best known for his book The End of Science, and (of course) for interviewing me in 2016—wrote a now-(in)famous cover article for Scientific American entitled “The Death of Proof.” Mashing together a large number of (what I’d consider) basically separate trends and ideas, Horgan argued that math was undergoing a fundamental change, with traditional deductive proofs being replaced by a combination of non-rigorous numerical simulations, machine-generated proofs, probabilistic and probabilistically-checkable proofs, and proofs using graphics and video. Horgan also suggested that Andrew Wiles’s then-brand-new proof of Fermat’s Last Theorem—which might have looked, at first glance, like a spectacular counterexample to the “death of proof” thesis—could be the “last gasp of a dying culture” and a “splendid anachronism.” Apparently, “The Death of Proof” garnered one of the largest volumes of angry mail in Scientific American‘s history, with mathematician after mathematician arguing that Horgan had strung together half-digested quotes and vignettes to manufacture a non-story.

Now Horgan—who you could variously describe as a wonderful sport, or a ham, or a sucker for punishment—has written a 26-year retrospective on his “death of proof” article. The prompt for this was Horgan’s recent discovery that, back in the 90s, David Hoffman and Hermann Karcher, two mathematicians annoyed by the “death of proof” article, had named a nonexistent mathematical object after its author. The so-called Horgan surface is a minimal surface that numerical computations strongly suggested should exist, but that can be rigorously proven not to exist after all. “The term was intended as an insult, but I’m honored anyway,” Horgan writes.

As a followup to his blog post, Horgan then decided to solicit commentary from various people he knew, including yours truly, about “how proofs are faring in an era of increasing computerization.” He wrote, “I’d love to get a paragraph or two from you.” Alas, I didn’t have the time to do as requested, but only to write eight paragraphs. So Horgan suggested that I make the result into a post on my own blog, which he’d then link to. Without further ado, then:

John, I like you so I hate to say it, but the last quarter century has not been kind to your thesis about “the death of proof”!  Those mathematicians sending you the irate letters had a point: there’s been no fundamental change to mathematics that deserves such a dramatic title.  Proof-based math remains quite healthy, with (e.g.) a solution to the Poincaré conjecture since your article came out, as well as to the Erdős discrepancy problem, the Kadison-Singer conjecture, Catalan’s conjecture, bounded gaps in primes, testing primality in deterministic polynomial time, etc. — just to pick a few examples from the tiny subset of areas that I know anything about.

There are evolutionary changes to mathematical practice, as there always have been.  Since 2009, the website MathOverflow has let mathematicians query the global hive-mind about an obscure reference or a recalcitrant step in a proof, and get near-instant answers.  Meanwhile “polymath” projects have, with moderate success, tried to harness blogs and other social media to make advances on long-standing open math problems using massive collaborations.

While humans remain in the driver’s seat, there are persistent efforts to increase the role of computers, with some notable successes.  These include Thomas Hales’s 1998 computer-assisted proof of the Kepler Conjecture (about the densest possible way to pack oranges) — now fully machine-verified from start to finish, after the Annals of Mathematics refused to publish a mixture of traditional mathematics and computer code (seems this is not exactly what happened; see the comment section for more).  It also includes William McCune’s 1996 solution to the Robbins Conjecture in algebra (the computer-generated proof was only half a page, but involved substitutions so strange that for 60 years no human had found them); and at the “opposite extreme,” the 2016 solution to the Pythagorean triples problem by Marijn Heule and collaborators, which weighed in at 200 terabytes (at that time, “the longest proof in the history of mathematics”).

It’s conceivable that someday, computers will replace humans at all aspects of mathematical research — but it’s also conceivable that, by the time they can do that, they’ll be able to replace humans at music and science journalism and everything else!

New notions of proof — including probabilistic, interactive, zero-knowledge, and even quantum proofs — have seen further development by theoretical computer scientists since 1993.  So far, though, these new types of proof remain either entirely theoretical (as with quantum proofs), or else they’re used for cryptographic protocols but not for mathematical research.  (For example, zero-knowledge proofs now play a major role in certain cryptocurrencies, such as Zcash.)

In many areas of math (including my own, theoretical computer science), proofs have continued to get longer and harder for any one person to absorb.  This has led some to advocate a split approach, wherein human mathematicians would talk to each other only about the handwavy intuitions and high-level concepts, while the tedious verification of details would be left to computers.  So far, though, the huge investment of time needed to write proofs in machine-checkable format — for almost no return in new insight — has prevented this approach’s wide adoption.

Yes, there are non-rigorous approaches to math, which continue to be widely used in physics and engineering and other fields, as they always have been.  But none of these approaches have displaced proof as the gold standard whenever it’s available.  If I had to speculate about why, I’d say: if you use non-rigorous approaches, then even if it’s clear to you under what conditions your results can be trusted, it’s probably much less clear to others.  Also, even if only one segment of a research community cares about rigor, whatever earlier work that segment builds on will need to be rigorous as well — thereby exerting constant pressure in that direction.  Thus, the more collaborative a given research area becomes, the more important is rigor.

For my money, the elucidation of the foundations of mathematics a century ago, by Cantor, Frege, Peano, Hilbert, Russell, Zermelo, Gödel, Turing, and others, still stands as one of the greatest triumphs of human thought, up there with evolution or quantum mechanics or anything else.  It’s true that the ideal set by these luminaries remains mostly aspirational.  When mathematicians say that a theorem has been “proved,” they still mean, as they always have, something more like: “we’ve reached a social consensus that all the ideas are now in place for a strictly formal proof that could be verified by a machine … with the only task remaining being massive rote coding work that none of us has any intention of ever doing!”  It’s also true that mathematicians, being human, are subject to the full panoply of foibles you might expect: claiming to have proved things they haven’t, squabbling over who proved what, accusing others of lack of rigor while hypocritically taking liberties themselves.  But just like love and honesty remain fine ideals no matter how often they’re flouted, so too does mathematical rigor.

Update: Here’s Horgan’s new post (entitled “Okay, Maybe Proofs Aren’t Dying After All”), which also includes a contribution from Peter Woit.

De-sneering my life

Wednesday, February 27th, 2019

If I’m being honest, the most exciting recent development in my life is this: a little over a month ago, I stopped checking “SneerClub” (a place I’d previously resolved not even to name here, but I think an exception is warranted now). Permanently, cold turkey. I won’t even visit to read their sneers about this post. I’ve made progress cutting down on other self-destructive social media fixations as well. Many friends suggested this course to me, and I thank them all, though I ultimately had to follow my own path to the obvious.

Ironically, the SneerClubbers themselves begged me to stop reading them (!), so presumably for once they’ll be okay with something I did (but if not, I don’t care). If any of them still have something to say to me, they can come to this blog, or email me, or if they pass through Austin, set up a time to hash it out over chips and queso (my treat). What I’ll no longer do is spend hours every week binge-reading a forum of people who’ve adopted nastiness and bad faith as their explicit principles. I’ll no longer toss and turn at night wondering how it came about that two thousand Redditors hate Scott Aaronson so much, and what I could say or do (short of total self-abnegation) that would make them hate me less. I plan to spend the freed-up time being Scott Aaronson.

Resolving to ignore one particular online hate pit—and then sticking to the resolution, as so far I have—has been a pure, unmitigated improvement to my quality of life. If you don’t believe me, ask my wife and kids. I recommend this course to anyone.

You could sensibly ask: why did I ever spend time worrying about an anti-nerds-like-me forum that’s so poisonous for its targets and participants alike? After long introspection, I think the answer is: there’s a part of me, perhaps a gift from the childhood bullies, that’s so obsessed with “society’s hatred of STEM nerds,” that it constantly seeks out evidence to confirm that its fears are justified—evidence that it can then wave in front of the rest of my brain to say “you see?? what did I always tell you?” And alas, whenever that part of my brain seeks such evidence, the world dutifully supplies mountains of it. It’s never once disappointed.

Now the SneerClubbers—who are perceptive and talented in their cruelty, if in nothing else—notice this about me, and gleefully ridicule me for it. But they’re oblivious to the central irony: that unlike the vast majority of humankind, or even the vast majority of social justice activists, they (the SneerClubbers) really do hate everyone like me. They’re precisely what the paranoid part of my brain wrongly fears that everyone else I meet is secretly like. They’re like someone who lectures you about your hilariously overblown fear of muggers, while simultaneously mugging you.

But at least they’re not the contented and self-confident bullies of my childhood nightmares, kicking dirt down at nerds from atop their pinnacle of wokeness and social adeptness. If you spend enough time studying them, they themselves come across as angry, depressed, pathetic. So for example: here’s one of my most persistent attackers, popping up on a math thread commemorating Michael Atiyah (one of the great mathematicians of the 20th century), just to insult Atiyah—randomly, gratuitously, and a few days after Atiyah had died. Almost everything posted all over Reddit by this individual—who uses the accurate tagline “unpleasantly radical”—has the same flavor. Somehow seeing this made it click for me: wait a second, these are the folks are lecturing me about my self-centeredness and arrogance and terrible social skills? Like, at least I try to be nice.

Scott Alexander, who writes the world’s best blog and is a more central target of SneerClub than I’ve been, recently announced that he asked the moderators of r/ssc to close its notorious “Culture War” thread, and they’ve done so—moving the thread to a new home on Reddit called “TheMotte.”

For those who don’t know: r/ssc is the place on Reddit to discuss Scott’s SlateStarCodex blog, though Scott himself was never too involved as more than a figurehead.  The Culture War thread was the place within r/ssc to discuss race, gender, immigration, and other hot-button topics.  The thread, which filled up with a bewildering thousands of comments per week (!), attracted the, err … full range of political views, including leftists, libertarians, and moderates but also alt-righters, neoreactionaries, and white nationalists. Predictably, SneerClub treated the thread as a gift from heaven: a constant source of inflammatory material that they could use to smear Scott personally (even if most of the time, Scott hadn’t even seen the offending content, let alone endorsing it).

Four months ago, I was one of the apparently many friends who told Scott that I felt he should dissociate the Culture War thread from his brand. So I congratulate him on his decision, which (despite his eloquently-expressed misgivings) I feel confident was the right one. Think about it this way: nobody’s freedom of speech has been curtailed—the thread continues full steam at TheMotte, for anyone who enjoys it—but meanwhile, the sneerers have been deprived of a golden weapon with which to slime Scott. Meanwhile, while the sneerers themselves might never change their minds about anything, Scott has demonstrated to third parties that he’s open and reasonable and ready to compromise, like the debater who happily switches to his opponent’s terminology. What’s not to like?

A couple weeks ago, while in Albuquerque for the SQuInT conference, I visited the excellent National Museum of Nuclear Science and History.  It was depressing, as it should have been, to tour the detailed exhibits about the murderous events surrounding the birth of the nuclear era: the Holocaust, the Rape of Nanking, the bombings of Hiroshima and Nagasaki. It was depressing in a different way to tour the exhibits about the early Atomic Age, and see the boundless optimism that ‘unleashing the power of the atom’ would finally usher in a near-utopia of space travel and clean energy—and then to compare that vision to where we are now, with climate change ravaging the planet and (in a world-historic irony) the people who care most about the environment having denounced and marginalized the most reliable source of carbon-free energy, the one that probably had the best chance to avert our planet’s terrifying future.

But on the bright side: how wonderful to have born into a time and place when, for the most part, those who hate you have only the power to destroy your life that you yourself grant them. How wonderful when one can blunt their knives by simply refusing to open a browser tab.

The Winding Road to Quantum Supremacy

Tuesday, January 15th, 2019

Greetings from QIP’2019 in Boulder, Colorado! Obvious highlights of the conference include Urmila Mahadev’s opening plenary talk on her verification protocol for quantum computation (which I blogged about here), and Avishay Tal’s upcoming plenary on his and Ran Raz’s oracle separation between BQP and PH (which I blogged about here). If you care, here are the slides for the talk I just gave, on the paper “Online Learning of Quantum States” by me, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Feel free to ask in the comments about what else is going on.

I returned a few days ago from my whirlwind Australia tour, which included Melbourne and Sydney; a Persian wedding that happened to be held next to a pirate ship (the Steve Irwin, used to harass whalers and adorned with a huge Jolly Roger); meetings and lectures graciously arranged by friends at UTS; a quantum computing lab tour personally conducted by 2018 “Australian of the Year” Michelle Simmons; three meetups with readers of this blog (or more often, readers of the other Scott A’s blog who graciously settled for the discount Scott A); and an excursion to Grampians National Park to see wild kangaroos, wallabies, koalas, and emus.

But the thing that happened in Australia that provided the actual occassion for this post is this: I was interviewed by Adam Ford in Carlton Gardens in Melbourne, about quantum supremacy, AI risk, Integrated Information Theory, whether the universe is discrete or continuous, and to be honest I don’t remember what else. You can watch the first segment, the one about the prospects for quantum supremacy, here on YouTube. My only complaint is that Adam’s video camera somehow made me look like an out-of-shape slob who needs to hit the gym or something.

Update (Jan. 16): Adam has now posted a second video on YouTube, wherein I talk about my “Ghost in the Quantum Turing Machine” paper, my critique of Integrated Information Theory, and more.

And now Adam has posted yet a third segment, in which I talk about small, lighthearted things like existential threats to civilization and the prospects for superintelligent AI.

And a fourth, in which I talk about whether reality is discrete or continuous.

Related to the “free will / consciousness” segment of the interview: the biologist Jerry Coyne, whose blog “Why Evolution Is True” I’ve intermittently enjoyed over the years, yesterday announced my existence to his readers, with a post that mostly criticizes my views about free will and predictability, as I expressed them years ago in a clip that’s on YouTube (at the time, Coyne hadn’t seen GIQTM or my other writings on the subject). Coyne also took the opportunity to poke fun at this weird character he just came across whose “life is devoted to computing” and who even mistakes tips for change at airport smoothie stands. Some friends here at QIP had a good laugh over the fact that, for the world beyond theoretical computer science and quantum information, this is what 23 years of research, teaching, and writing apparently boil down to: an 8.5-minute video clip where I spouted about free will, and also my having been arrested once in a comic mix-up at Philadelphia airport. Anyway, since then I had a very pleasant email exchange with Coyne—someone with whom I find myself in agreement much more often than not, and who I’d love to have an extended conversation with sometime despite the odd way our interaction started.

Incompleteness ex machina

Sunday, December 30th, 2018

I have a treat with which to impress your friends at New Year’s Eve parties tomorrow night: a rollicking essay graciously contributed by a reader named Sebastian Oberhoff, about a unified and simplified way to prove all of Gödel’s Incompleteness Theorems, as well as Rosser’s Theorem, directly in terms of computer programs. In particular, this improves over my treatments in Quantum Computing Since Democritus and my Rosser’s Theorem via Turing machines post. While there won’t be anything new here for the experts, I loved the style—indeed, it brings back wistful memories of how I used to write, before I accumulated too many imaginary (and non-imaginary) readers tut-tutting at crass jokes over my shoulder. May 2019 bring us all the time and the courage to express ourselves authentically, even in ways that might be sneered at as incomplete, inconsistent, or unsound.

The NP genie

Tuesday, December 11th, 2018

Hi from the Q2B conference!

Every nerd has surely considered the scenario where an all-knowing genie—or an enlightened guru, or a superintelligent AI, or God—appears and offers to answer any question of your choice.  (Possibly subject to restrictions on the length or complexity of the question, to prevent glomming together every imaginable question.)  What do you ask?

(Standard joke: “What question should I ask, oh wise master, and what is its answer?”  “The question you should ask me is the one you just asked, and its answer is the one I am giving.”)

The other day, it occurred to me that theoretical computer science offers a systematic way to generate interesting variations on the genie scenario, which have been contemplated less—variations where the genie is no longer omniscient, but “merely” more scient than any entity that humankind has ever seen.  One simple example, which I gather is often discussed in the AI-risk and rationality communities, is an oracle for the halting problem: what computer program can you write, such that knowing whether it halts would provide the most useful information to civilization?  Can you solve global warming with such an oracle?  Cure cancer?

But there are many other examples.  Here’s one: suppose what pops out of your lamp is a genie for NP questions.  Here I don’t mean NP in the technical sense (that would just be a pared-down version of the halting genie discussed above), but in the human sense.  The genie can only answer questions by pointing you to ordinary evidence that, once you know where to find it, makes the answer to the question clear to every competent person who examines the evidence, with no further need to trust the genie.  Or, of course, the genie could fail to provide such evidence, which itself provides the valuable information that there’s no such evidence out there.

More-or-less equivalently (because of binary search), the genie could do what my parents used to do when my brother and I searched the house for Hanukkah presents, and give us “hotter” or “colder” hints as we searched for the evidence ourselves.

To make things concrete, let’s assume that the NP genie will only provide answers of 1000 characters or fewer, in plain English text with no fancy encodings.  Here are the candidates for NP questions that I came up with after about 20 seconds of contemplation:

  • Which pieces of physics beyond the Standard Model and general relativity can be experimentally confirmed with the technology of 2018? What are the experiments we need to do?
  • What’s the current location of the Ark of the Covenant, or its remains, if any still exist?  (Similar: where can we dig to find physical records, if any exist, pertaining to the Exodus from Egypt, or to Jesus of Nazareth?)
  • What’s a sketch of a resolution of P vs. NP, from which experts would stand a good chance of filling in the details?  (Similar for other any famous unsolved math problem.)
  • Where, if anywhere, can we point radio telescopes to get irrefutable evidence for the existence of extraterrestrial life?
  • What happened to Malaysia Flight 370, and where are the remains by which it could be verified?  (Similar for Amelia Earhart.)
  • Where, if anywhere, can we find intact DNA of non-avian dinosaurs?

Which NP questions would you ask the genie?  And what other complexity-theoretic genies would be interesting to consider?  (I thought briefly about a ⊕P genie, but I’m guessing that the yearning to know whether the number of sand grains in the Sahara is even or odd is limited.)

Update: I just read Lenny Susskind’s Y Combinator interview, and found it delightful—pure Lenny, and covering tons of ground that should interest anyone who reads this blog.

Teaching quantum in junior high: special Thanksgiving guest post by Terry Rudolph

Thursday, November 22nd, 2018

Happy Thanksgiving!

People have sometimes asked me: “how do you do it?  how do you do your research, write papers, teach classes, mentor grad students, build up the quantum center at UT, travel and give talks every week or two, serve on program committees, raise two rambunctious young kids, and also blog and also participate in the comments and also get depressed about people saying mean things on social media?”  The answer is that increasingly I don’t.  Something has to give, and this semester, alas, that something has often been blogging.

And that’s why, today, I’m delighted to have a special guest post by my good friend Terry Rudolph.  Terry, who happens to be Erwin Schrödinger’s grandson, has done lots of fascinating work over the years in quantum computing and the foundations of quantum mechanics, and previously came up on this blog in the context of the PBR (Pusey-Barrett-Rudolph) Theorem.  Today, he’s a cofounder and chief architect at PsiQuantum, a startup in Palo Alto that’s trying to build silicon-photonic quantum computers.

Terry’s guest post is about the prospects for teaching quantum theory at the junior high school level—something he thought about a lot in the context of writing his interesting recent book Q is for Quantum.  I should stress that the opinions in this post are Terry’s, and don’t necessarily reflect the official editorial positions of Shtetl-Optimized.  Personally, I have taught the basics of quantum information to sharp junior high and high school students, so I certainly know that it’s possible.  (By undergrad, it’s not only possible, but maybe should become standard for both physics and CS majors.)  But I would also say that, given the current state of junior high and high school education in the US, it would be a huge step up if most students graduated fully understanding what’s a probability, what’s a classical bit, what’s a complex number, and any of dozens of other topics that feed into quantum information—so why not start by teaching the simpler stuff well?  And also, if students don’t learn the rules of classical probability first, then how will they be properly shocked when they come to quantum? 🙂

But without further ado, here’s Terry—who’s also graciously agreed to stick around and answer some comments.

Can we/should we teach Quantum Theory in Junior High?

by Terry Rudolph

Should we?

Reasons which suggest the answer is “yes” include:

Economic: We are apparently into a labor market shortage in quantum engineers.  We should not, however, need the recent hype around quantum computing to make the economic case – the frontier of many disparate regions of the modern science and technology landscape is quantum.  Surely if students do decide to drop out of school at 16 they should at least be equipped to get an entry-level job as a quantum physicist?

Educational: If young peoples’ first exposures to science are counterintuitive and “cutting edge,” it could help excite them into STEM.  The strong modern quantum information theoretic connections between quantum physics, computer science and math can help all three subjects constructively generate common interest.

Pseudo-Philosophical: Perhaps our issues with understanding/accepting quantum theory are because we come to it late and have lost the mental plasticity for a “quantum reset” of our brain when we eventually require it late in an undergraduate degree.  It may be easier to achieve fluency in the “language of quantum” with early exposure.

Can we?

There are two distinct aspects to this question: Firstly, is it possible at the level of “fitting it in” – training teachers, adjusting curricula and so on?  Secondly, can a nontrivial, worthwhile fraction of quantum theory even be taught at all to pre-calculus students?

With regards to the first question, as the child of two schoolteachers I am very aware that an academic advocating for such disruption will not be viewed kindly by all.  As I don’t have relevant experience to say anything useful about this aspect, I have to leave it for others to consider.

Let me focus for the remainder of this post on the second aspect, namely whether it is even possible to appropriately simplify the content of the theory.  This month it is exactly 20 years since I lectured the first of many varied quantum courses I have taught at multiple universities. For most of that period I would have said it simply wasn’t possible to teach any but the most precocious of high school students nontrivial technical content of quantum theory – despite some brave attempts like Feynman’s use of arrows in QED: The Strange Theory of Light and Matter (a technique that cannot easily get at the mysteries of two-particle quantum theory, which is where the fun really starts).  I now believe, however, that it is actually possible.

A pedagogical method covering nontrivial quantum theory using only basic arithmetic

My experience talking about quantum theory to 12-15 year olds has only been in the idealized setting of spending a few hours with them at science fairs, camps and similar.  In fact it was on the way to a math camp for very young students, desperately trying to plan something non-trivial to engage them with, that I came up with a pedagogical method which I (and a few colleagues) have found does work.

I eventually wrote the method into a short book Q is for Quantum, but if you don’t want to purchase the book then here is a pdf of Part I,, which takes a student knowing only the rules of basic arithmetic through to learning enough quantum computing they can understand the Deutsch–Jozsa algorithm.  In fact not only can they do a calculation to see how it works in detail, they can appreciate conceptual nuances often under-appreciated in popular expositions, such as why gate speed doesn’t matter – it’s all about the number of steps, why classical computing also can have exponential growth in “possible states” so interference is critical, why quantum computers do not compute the uncomputable and so on.

Before pointing out a few features of the approach, here are some rules I set myself while writing the book:

  • No analogies, no jargon – if it can’t be explained quantitatively then leave it out.
  • No math more than basic arithmetic and distribution across brackets.
  • Keep clear the distinction between mathematical objects and the observed physical events they are describing.
  • Be interpretationally neutral.
  • No soap opera: Motivate by intriguing with science, not by regurgitating quasi-mythological stories about the founders of the theory.
  • No using the word “quantum” in the main text! This was partly to amuse myself, but I also thought if I was succeeding in the other points then I should be able to avoid a word almost synonymous with “hard and mysterious.”

One of the main issues to confront is how to represent and explain superposition.  It is typical in popular expositions to draw analogies between a superposition of, say, a cat which is dead and a cat which is alive by saying it is dead “and” alive.  But if superposition was equivalent to logical “and”, or, for that matter, logical “or”, then quantum computing wouldn’t be interesting, and in this and other ways the analogy is ultimately misleading.  The approach I use is closer to the latter – an unordered list of possible states for a system (which is most like an “or”) can be used to represent a superposition. Using a list has some advantages – it is natural to apply a transformation to all elements of a list, for instance doubling the list of ingredients in a recipe.  More critically, given two independent lists of possibilities the new joint list of combined possibilities is a natural concept.  This makes teaching the equivalent of the Kronecker (tensor) product for multiple systems easy, something often a bit tricky even for undergrads to become comfortable with.

Conceptually the weirdest part of the whole construction, particularly for someone biased by the standard formalism, is that I use a standard mathematical object (a negative or minus sign) applied to a diagram of a physical object (a black or white ball).  Moreover, positive and negative balls in a diagram can cancel out (interfere).  This greatly simplifies the exposition, by removing a whole level of abstraction in the standard theory (we do not need to use a vector containing entries whose specific ordering must be remembered in order to equate them to the physical objects).  While it initially seemed odd to me personally to do this, I have yet to have any young person think of it as any more weird than using the negative sign on a number.  And if it is always kept clear that drawing and manipulating the whole diagram is an abstract thing we do, which may or may not have any correspondence to what is “really going on” in the physical setups we are describing, then there really is no difference.

There are some subtleties about the whole approach – while the formalism is universal for quantum computing, it can only make use of unitary evolution which is proportional to a matrix with integer entries.  Thus the Hadamard gate (PETE box) is ok, the Controlled-NOT and Toffoli likewise, but a seemingly innocuous gate like the controlled-Hadamard is not capable of being incorporated (without adding a whole bunch of unintuitive and unjustified rules).  The fact the approach covers a universal gate set means some amazing things can be explained in this simple diagrammatic language.  For example, the recent paper Quantum theory cannot consistently describe the use of itself, which led to considerable discussion on this blog, can be fully reproduced.  That is, a high school student can in principle understand the technical details of a contemporary argument between professional physicists.  I find this amazing.

Based on communication with readers I have come to realize the people at most risk of being confused by the book are actually those already with a little knowledge – someone who has done a year or two’s worth of undergraduate quantum courses, or someone who has taken things they read in pop-sci books too literally.  Initially, as I was developing the method, I thought it would be easy to keep “touching base” with the standard vector space formalism.  But in fact it becomes very messy to do so (and irrelevant for someone learning quantum theory for the first time).  In the end I dropped that goal, but now realize I need to develop some supplementary notes to help someone in that situation.

Q is for Quantum is certainly not designed to be used as a classroom text – if nothing else my particular style and choice of topics will not be to others’ tastes, and I haven’t included all the many, many simple examples and exercises I have students doing along with me in class when I actually teach this stuff.  It should be thought of as more a “proof of principle,” that the expository challenge can be met.  Several colleagues have used parts of these ideas already for teaching, and they have given me some great feedback.  As such I am planning on doing a revised and slightly expanded version at some point, so if you read it and have thoughts for improvement please send me them.

Review of Bryan Caplan’s The Case Against Education

Thursday, April 26th, 2018

If ever a book existed that I’d judge harshly by its cover—and for which nothing inside could possibly make me reverse my harsh judgment—Bryan Caplan’s The Case Against Education would seem like it.  The title is not a gimmick; the book’s argument is exactly what it says on the tin.  Caplan—an economist at George Mason University, home of perhaps the most notoriously libertarian economics department on the planet—holds that most of the benefit of education to students (he estimates around 80%, but certainly more than half) is about signalling the students’ preexisting abilities, rather than teaching or improving the students in any way.  He includes the entire educational spectrum in his indictment, from elementary school all the way through college and graduate programs.  He does have a soft spot for education that can be shown empirically to improve worker productivity, such as technical and vocational training and apprenticeships.  In other words, precisely the kind of education that many readers of this blog may have spent their lives trying to avoid.

I’ve spent almost my whole conscious existence in academia, as a student and postdoc and then as a computer science professor.  CS is spared the full wrath that Caplan unleashes on majors like English and history: it does, after all, impart some undeniable real-world skills.  Alas, I’m not one of the CS professors who teaches anything obviously useful, like how to code or manage a project.  When I teach undergrads headed for industry, my only role is to help them understand concepts that they probably won’t need in their day jobs, such as which problems are impossible or intractable for today’s computers; among those, which might be efficiently solved by quantum computers decades in the future; and which parts of our understanding of all this can be mathematically proven.

Granted, my teaching evaluations have been [clears throat] consistently excellent.  And the courses I teach aren’t major requirements, so the students come—presumably?—because they actually want to know the stuff.  And my former students who went into industry have emailed me, or cornered me, to tell me how much my courses helped them with their careers.  OK, but how?  Often, it’s something about my class having helped them land their dream job, by impressing the recruiters with their depth of theoretical understanding.  As we’ll see, this is an “application” that would make Caplan smile knowingly.

If Caplan were to get his way, the world I love would be decimated.  Indeed, Caplan muses toward the end of the book that the world he loves would be decimated too: in a world where educational investment no longer exceeded what was economically rational, he might no longer get to sit around with other economics professors discussing what he finds interesting.  But he consoles himself with the thought that decisionmakers won’t listen to him anyway, so it won’t happen.

It’s tempting to reply to Caplan: “now now, your pessimism about anybody heeding your message seems unwarranted.  Have anti-intellectual zealots not just taken control of the United States, with an explicit platform of sticking it to the educated elites, and restoring the primacy of lower-education jobs like coal mining, no matter the long-term costs to the economy or the planet?  So cheer up, they might listen to you!”

Indeed, given the current stakes, one might simply say: Caplan has set himself against the values that are the incredibly fragile preconditions for all academic debate—even, ironically, debate about the value of academia, like the one we’re now having.  So if we want such debate to continue, then we have no choice but to treat Caplan as an enemy, and frame the discussion around how best to frustrate his goals.

In response to an excerpt of Caplan’s book in The Atlantic, my friend Sean Carroll tweeted:

It makes me deeply sad that a tenured university professor could write something like this about higher education.  There is more to learning than the labor market.

Why should anyone with my basic values, or Sean’s, give Caplan’s thesis any further consideration?  As far as I can tell, there are only two reasons: (1) common sense, and (2) the data.

In his book, Caplan presents dozens of tables and graphs, but he also repeatedly asks his readers to consult their own memories—exploiting the fact that we all have firsthand experience of school.  He asks: if education is about improving students’ “human capital,” then why are students so thrilled when class gets cancelled for a snowstorm?  Why aren’t students upset to be cheated out of some of the career-enhancing training that they, or their parents, are paying so much for?  Why, more generally, do most students do everything in their power—in some cases, outright cheating—to minimize the work they put in for the grade they receive?  Is there any product besides higher education, Caplan asks, that people pay hundreds of thousands of dollars for, and then try to consume as little of as they can get away with?  Also, why don’t more students save hundreds of thousands of dollars by simply showing up at a university and sitting in on classes without paying—something that universities make zero effort to stop?  (Many professors would be flattered, and would even add you to the course email list, entertain your questions, and give you access to the assignments—though they wouldn’t grade your assignments.)

And: if the value of education comes from what it teaches you, how do we explain the fact that students forget almost everything so soon after the final exam, as attested by both experience and the data?  Why are employers satisfied with a years-ago degree; why don’t they test applicants to see how much understanding they’ve retained?

Or if education isn’t about any of the specific facts being imparted, but about “learning how to learn” or “learning how to think creatively”—then how is it that studies find academic coursework has so little effect on students’ general learning and reasoning abilities either?  That, when there is an improvement in reasoning ability, it’s tightly concentrated on the subject matter of the course, and even then it quickly fades away after the course is over?

More broadly, if the value of mass education derives from making people more educated, how do we explain the fact that high-school and college graduates, most of them, remain so abysmally ignorant?  After 12-16 years in something called “school,” large percentages of Americans still don’t know that the earth orbits the sun; believe that heavier objects fall faster than lighter ones and that only genetically modified organisms contain genes; and can’t locate the US or China on a map.  Are we really to believe, asks Caplan, that these apparent dunces have nevertheless become “deeper thinkers” by virtue of their schooling, in some holistic, impossible-to-measure way?  Or that they would’ve been even more ignorant without school?  But how much more ignorant can you be?  They could be illiterate, yes: Caplan grants the utility of teaching reading, writing, and arithmetic.  But how much beyond the three R’s (if those) do typical students retain, let alone use?

Caplan also poses the usual questions: if you’re not a scientist, engineer, or academic (or even if you are), how much of your undergraduate education do you use in your day job?  How well did the course content match what, in retrospect, you feel someone starting your job really needs to know?  Could your professors do your job?  If not, then how were they able to teach you to do it better?

Caplan acknowledges the existence of inspiring teachers who transform their students’ lives, in ways that need not be reflected in their paychecks: he mentions Robin Williams’ character in The Dead Poets’ Society.  But he asks: how many such teachers did you have?  If the Robin Williamses are vastly outnumbered by the drudges, then wouldn’t it make more sense for students to stream the former directly into their homes via the Internet—as they can now do for free?

OK, but if school teaches so little, then how do we explain the fact that, at least for those students who are actually able to complete good degrees, research confirms that (on average) having gone to school really does pay, exactly as advertised?  Employers do pay more for a college graduate—yes, even an English or art history major—than for a dropout.  More generally, starting salary rises monotonically with level of education completed.  Employers aren’t known for a self-sacrificing eagerness to overpay.  Are they systematically mistaken about the value of school?

Synthesizing decades of work by other economists, Caplan defends the view that the main economic function of school is to give students a way to signal their preexisting qualities, ones that correlate with being competent workers in a modern economy.  I.e., that school is tacitly a huge system for winnowing and certifying young people, which also fulfills various subsidiary functions, like keeping said young people off the street, socializing them, maybe occasionally even teaching them something.  Caplan holds that, judged as a certification system, school actually works—well enough to justify graduates’ higher starting salaries, without needing to postulate any altruistic conspiracy on the part of employers.

For Caplan, a smoking gun for the signaling theory is the huge salary premium of an actual degree, compared to the relatively tiny premium for each additional year of schooling other than the degree year—even when we hold everything else constant, like the students’ academic performance.  In Caplan’s view, this “sheepskin effect” even lets us quantitatively estimate how much of the salary premium on education reflects actual student learning, as opposed to the students signaling their suitability to be hired in a socially approved way (namely, with a diploma or “sheepskin”).

Caplan knows that the signaling story raises an immediate problem: namely, if employers just want the most capable workers, then knowing everything above, why don’t they eagerly recruit teenagers who score highly on the SAT or IQ tests?  (Or why don’t they make job offers to high-school seniors with Harvard acceptance letters, skipping the part where the seniors have to actually go to Harvard?)

Some people think the answer is that employers fear getting sued: in the 1971 Griggs vs. Duke Power case, the US Supreme Court placed restrictions on the use of intelligence tests in hiring, because of disparate impact on minorities.  Caplan, however, rejects this explanation, pointing out that it would be child’s-play for employers to design interview processes that functioned as proxy IQ tests, were that what the employers wanted.

Caplan’s theory is instead that employers don’t value only intelligence.  Instead, they care about the conjunction of intelligence with two other traits: conscientiousness and conformity.  They want smart workers who will also show up on time, reliably turn in the work they’re supposed to, and jump through whatever hoops authorities put in front of them.  The main purpose of school, over and above certifying intelligence, is to serve as a hugely costly and time-consuming—and therefore reliable—signal that the graduates are indeed conscientious conformists.  The sheer game-theoretic wastefulness of the whole enterprise rivals the peacock’s tail or the bowerbird’s ornate bower.

But if true, this raises yet another question.  In the signaling story, graduating students (and their parents) are happy that the students’ degrees land them good jobs.  Employers are happy that the education system supplies them with valuable workers, pre-screened for intelligence, conscientiousness, and conformity.  Even professors are happy that they get paid to do research and teach about topics that interest them, however irrelevant those topics might be to the workplace.  So if so many people are happy, who cares if, from an economic standpoint, it’s all a big signaling charade, with very little learning taking place?

For Caplan, the problem is this: because we’ve all labored under the mistaken theory that education imparts vital skills for a modern economy, there are trillions of dollars of government funding for every level of education—and that, in turn, removes the only obstacle to a credentialing arms race.  The equilbrium keeps moving over the decades, with more and more years of mostly-pointless schooling required to prove the same level of conscientiousness and conformity as before.  Jobs that used to require only a high-school diploma now require a bachelors; jobs that used to require only a bachelors now require a masters, and so on—despite the fact that the jobs themselves don’t seem to have changed appreciably.

For Caplan, a thoroughgoing libertarian, the solution is as obvious as it is radical: abolish government funding for education.  (Yes, he explicitly advocates a complete “separation of school and state.”)  Or if some state role in education must be retained, then let it concentrate on the three R’s and on practical job skills.  But what should teenagers do, if we’re no longer urging them to finish high school?  Apparently worried that he hasn’t yet outraged liberals enough, Caplan helpfully suggests that we relax the laws around child labor.  After all, he says, if we’ve decided anyway that teenagers who aren’t academically inclined should suffer through years of drudgery, then instead of warming a classroom seat, why shouldn’t they apprentice themselves to a carpenter or a roofer?  That way they could contribute to the economy, and gain the independence from their parents that most of them covet, and learn skills that they’d be much more likely to remember and use than the dissection of owl pellets.  Even if working a real job involved drudgery, at least it wouldn’t be as pointless as the drudgery of school.

Given his conclusions, and the way he arrives at them, Caplan realizes that he’ll come across to many as a cartoon stereotype of a narrow-minded economist, who “knows the price of everything but the value of nothing.”  So he includes some final chapters in which, setting aside the charts and graphs, he explains how he really feels about education.  This is the context for what I found to be the most striking passages in the book:

I am an economist and a cynic, but I’m not a typical cynical economist.  I’m a cynical idealist.  I embrace the ideal of transformative education.  I believe wholeheardedly in the life of the mind.  What I’m cynical about is people … I don’t hate education.  Rather I love education too much to accept our Orwellian substitute.  What’s Orwellian about the status quo?  Most fundamentally, the idea of compulsory enlightenment … Many idealists object that the Internet provides enlightenment only for those who seek it.  They’re right, but petulant to ask for more.  Enlightenment is a state of mind, not a skill—and state of mind, unlike skill, is easily faked.  When schools require enlightenment, students predictably respond by feigning interest in ideas and culture, giving educators a false sense of accomplishment. (p. 259-261)

OK, but if one embraces the ideal, then rather than dynamiting the education system, why not work to improve it?  According to Caplan, the answer is that we don’t know whether it’s even possible to build a mass education system that actually works (by his lights).  He says that, if we discover that we’re wasting trillions of dollars on some sector, the first order of business is simply to stop the waste.  Only later should we entertain arguments about whether we should restart the spending in some new, better way, and we shouldn’t presuppose that the sector in question will win out over others.

Above, I took pains to set out Caplan’s argument as faithfully as I could, before trying to pass judgment on it.  At some point in a review, though, the hour of judgment arrives.

I think Caplan gets many things right—even unpopular things that are difficult for academics to admit.  It’s true that a large fraction of what passes for education doesn’t deserve the name—even if, as a practical matter, it’s far from obvious how to cut that fraction without also destroying what’s precious and irreplaceable.  He’s right that there’s no sense in badgering weak students to go to college if those students are just going to struggle and drop out and then be saddled with debt.  He’s right that we should support vocational education and other non-traditional options to serve the needs of all students.  Nor am I scandalized by the thought of teenagers apprenticing themselves to craftspeople, learning skills that they’ll actually value while gaining independence and starting to contribute to society.  This, it seems to me, is a system that worked for most of human history, and it would have to fail pretty badly in order to do worse than, let’s say, the average American high school.  And in the wake of the disastrous political upheavals of the last few years, I guess the entire world now knows that, when people complain that the economy isn’t working well enough for non-college-graduates, we “technocratic elites” had better have a better answer ready than “well then go to college, like we did.”

Yes, probably the state has a compelling interest in trying to make sure nearly everyone is literate, and probably most 8-year-olds have no clue what’s best for themselves.  But at least from adolescence onward, I think that enormous deference ought to be given to students’ choices.  The idea that “free will” (in the practical rather than metaphysical sense) descends on us like a halo on our 18th birthdays, having been absent beforehand, is an obvious fiction.  And we all know it’s fiction—but it strikes me as often a destructive fiction, when law and tradition force us to pretend that we believe it.

Some of Caplan’s ideas dovetail with the thoughts I’ve had myself since childhood on how to make the school experience less horrible—though I never framed my own thoughts as “against education.”  Make middle and high schools more like universities, with freedom of movement and a wide range of offerings for students to choose from.  Abolish hall passes and detentions for lateness: just like in college, the teacher is offering a resource to students, not imprisoning them in a dungeon.  Don’t segregate by age; just offer a course or activity, and let kids of any age who are interested show up.  And let kids learn at their own pace.  Don’t force them to learn things they aren’t ready for: let them love Shakespeare because they came to him out of interest, rather than loathing him because he was forced down their throats.  Never, ever try to prevent kids from learning material they are ready for: instead of telling an 11-year-old teaching herself calculus to go back to long division until she’s the right age (does that happen? ask how I know…), say: “OK hotshot, so you can differentiate a few functions, but can you handle these here books on linear algebra and group theory, like Terry Tao could have when he was your age?”

Caplan mentions preschool as the one part of the educational system that strikes him as least broken.  Not because it has any long-term effects on kids’ mental development (it might not), just because the tots enjoy it at the time.  They get introduced to a wide range of fun activities.  They’re given ample free time, whether for playing with friends or for building or drawing by themselves.  They’re usually happy to be dropped off.  And we could add: no one normally minds if parents drop their kids off late, or pick them up early, or take them out for a few days.  The preschool is just a resource for the kids’ benefit, not a never-ending conformity test.  As a father who’s now seen his daughter in three preschools, this matches my experience.

Having said all this, I’m not sure I want to live in the world of Caplan’s “complete separation of school and state.”  And I’m not using “I’m not sure” only as a euphemism for “I don’t.”  Caplan is proposing a radical change that would take civilization into uncharted territory: as he himself notes, there’s not a single advanced country on earth that’s done what he advocates.  The trend has everywhere been in the opposite direction, to invest more in education as countries get richer and more technology-based.  Where there have been massive cutbacks to education, the causes have usually been things like famine or war.

So I have the same skepticism of Caplan’s project that I’d have (ironically) of Bolshevism or any other revolutionary project.  I say to him: don’t just persuade me, show me.  Show me a case where this has worked.  In the social world, unlike the mathematical world, I put little stock in long chains of reasoning unchecked by experience.

Caplan explicitly invites his readers to test his assertions against their own lives.  When I do so, I come back with a mixed verdict.  Before college, as you may have gathered, I find much to be said for Caplan’s thesis that the majority of school is makework, the main purposes of which are to keep the students out of trouble and on the premises, and to certify their conscientiousness and conformity.  There are inspiring teachers here and there, but they’re usually swimming against the tide.  I still feel lucky that I was able to finagle my way out by age 15, and enter Clarkson University and then Cornell with only a G.E.D.

In undergrad, on the other hand, and later in grad school at Berkeley, my experience was nothing like what Caplan describes.  The professors were actual experts: people who I looked up to or even idolized.  I wanted to learn what they wanted to teach.  (And if that ever wasn’t the case, I could switch to a different class, excepting some major requirements.)  But was it useful?

As I look back, many of my math and CS classes were grueling bootcamps on how to prove theorems, how to design algorithms, how to code.  Most of the learning took place not in the classroom but alone, in my dorm, as I struggled with the assignments—having signed up for the most advanced classes that would allow me in, and thereby left myself no escape except to prove to the professor that I belonged there.  In principle, perhaps, I could have learned the material on my own, but in reality I wouldn’t have.  I don’t still use all of the specific tools I acquired, though I do still use a great many of them, from the Gram-Schmidt procedure to Gaussian integrals to finding my way around a finite group or field.  Even if I didn’t use any of the tools, though, this gauntlet is what upgraded me from another math-competition punk to someone who could actually write research papers with long proofs.  For better or worse, it made me what I am.

Just as useful as the math and CS courses were the writing seminars—places where I had to write, and where my every word got critiqued by the professor and my fellow students, so I had to do a passable job.  Again: intensive forced practice in what I now do every day.  And the fact that it was forced was now fine, because, like some leather-bound masochist, I’d asked to be forced.

On hearing my story, Caplan would be unfazed.  Of course college is immensely useful, he’d say … for those who go on to become professors, like me or him.  He “merely” questions the value of higher education for almost everyone else.

OK, but if professors are at least good at producing more people like themselves, able to teach and do research, isn’t that something, a base we can build on that isn’t all about signaling?  And more pointedly: if this system is how the basic research enterprise perpetuates itself, then shouldn’t we be really damned careful with it, lest we slaughter the golden goose?

Except that Caplan is skeptical of the entire enterprise of basic research.  He writes:

Researchers who specifically test whether education accelerates progress have little to show for their efforts.  One could reply that, given all the flaws of long-run macroeconomic data, we should ignore academic research in favor of common sense.  But what does common sense really say? … True, ivory tower self-indulgence occasionally revolutionizes an industry.  Yet common sense insists the best way to discover useful ideas is to search for useful ideas—not to search for whatever fascinates you and pray it turns out to be useful (p. 175).

I don’t know if common sense insists that, but if it does, then I feel on firm ground to say that common sense is woefully inadequate.  It’s easy to look at most basic research, and say: this will probably never be useful for anything.  But then if you survey the inventions that did change the world over the past century—the transistor, the laser, the Web, Google—you find that almost none would have happened without what Caplan calls “ivory tower self-indulgence.”  What didn’t come directly from universities came from entities (Bell Labs, DARPA, CERN) that wouldn’t have been thinkable without universities, and that themselves were largely freed from short-term market pressures by governments, like universities are.

Caplan’s skepticism of basic research reminded me of a comment in Nick Bostrom’s book Superintelligence:

A colleague of mine likes to point out that a Fields Medal (the highest honor in mathematics) indicates two things about the recipient: that he was capable of accomplishing something important, and that he didn’t.  Though harsh, the remark hints at a truth. (p. 314)

I work in theoretical computer science: a field that doesn’t itself win Fields Medals (at least not yet), but that has occasions to use parts of math that have won Fields Medals.  Of course, the stuff we use cutting-edge math for might itself be dismissed as “ivory tower self-indulgence.”  Except then the cryptographers building the successors to Bitcoin, or the big-data or machine-learning people, turn out to want the stuff we were talking about at conferences 15 years ago—and we discover to our surprise that, just as the mathematicians gave us a higher platform to stand on, so we seem to have built a higher platform for the practitioners.  The long road from Hilbert to Gödel to Turing and von Neumann to Eckert and Mauchly to Gates and Jobs is still open for traffic today.

Yes, there’s plenty of math that strikes even me as boutique scholasticism: a way to signal the brilliance of the people doing it, by solving problems that require years just to understand their statements, and whose “motivations” are about 5,000 steps removed from anything Caplan or Bostrom would recognize as motivation.  But where I part ways is that there’s also math that looked to me like boutique scholasticism, until Greg Kuperberg or Ketan Mulmuley or someone else finally managed to explain it to me, and I said: “ah, so that’s why Mumford or Connes or Witten cared so much about this.  It seems … almost like an ordinary applied engineering question, albeit one from the year 2130 or something, being impatiently studied by people a few moves ahead of everyone else in humanity’s chess game against reality.  It will be pretty sweet once the rest of the world catches up to this.”

I have a more prosaic worry about Caplan’s program.  If the world he advocates were actually brought into being, I suspect the people responsible wouldn’t be nerdy economics professors like himself, who have principled objections to “forced enlightenment” and to signalling charades, yet still maintain warm fuzzies for the ideals of learning.  Rather, the “reformers” would be more on the model of, say, Steve Bannon or Scott Pruitt or Alex Jones: people who’d gleefully take a torch to the universities, fortresses of the despised intellectual elite, not in the conviction that this wouldn’t plunge humanity back into the Dark Ages, but in the hope that it would.

When the US Congress was debating whether to cancel the Superconducting Supercollider, a few condensed-matter physicists famously testified against the project.  They thought that $10-$20 billion for a single experiment was excessive, and that they could provide way more societal value with that kind of money were it reallocated to them.  We all know what happened: the SSC was cancelled, and of the money that was freed up, 0%—absolutely none of it—went to any of the other research favored by the SSC’s opponents.

If Caplan were to get his way, I fear that the story would be similar.  Caplan talks about all the other priorities—from feeding the world’s poor to curing diseases to fixing crumbling infrastructure—that could be funded using the trillions currently wasted on runaway credential signaling.  But in any future I can plausibly imagine where the government actually axes education, the savings go to things like enriching the leaders’ cronies and launching vanity wars.

My preferences for American politics have two tiers.  In the first tier, I simply want the Democrats to vanquish the Republicans, in every office from president down to dogcatcher, in order to prevent further spiraling into nihilistic quasi-fascism, and to restore the baseline non-horribleness that we know is possible for rich liberal democracies.  Then, in the second tier, I want the libertarians and rationalists and nerdy economists and Slate Star Codex readers to be able to experiment—that’s a key word here—with whether they can use futarchy and prediction markets and pricing-in-lieu-of-regulation and other nifty ideas to improve dramatically over the baseline liberal order.  I don’t expect that I’ll ever get what I want; I’ll be extremely lucky even to get the first half of it.  But I find that my desires regarding Caplan’s program fit into the same mold.  First and foremost, save education from those who’d destroy it because they hate the life of the mind.  Then and only then, let people experiment with taking a surgical scalpel to education, removing from it the tumor of forced enlightenment, because they love the life of the mind.

Amazing progress on longstanding open problems

Wednesday, April 11th, 2018

For those who haven’t seen it:

  1. Aubrey de Grey, better known to the world as a radical life extension researcher, on Sunday posted a preprint on the arXiv claiming to prove that the chromatic number of the plane is at least 5—the first significant progress on the Hadwiger-Nelson problem since 1950.  If you’re tuning in from home, the Hadwiger-Nelson problem asks: what’s the minimum number of colors that you need to color the Euclidean plane, in order to ensure that every two points at distance exactly 1 from each other are colored differently?  It’s not hard to show that at least 4 colors are necessary, or that 7 colors suffice: try convincing yourself by staring at the figure below.  Until a few days ago, nothing better was known.
    This is a problem that’s intrigued me ever since I learned about it at a math camp in 1996, and that I spent at least a day of my teenagerhood trying to solve.
    De Grey constructs an explicit graph with unit distances—originally with 1567 vertices, now with 1585 vertices after after a bug was fixed—and then verifies by computer search (which takes a few hours) that 5 colors are needed for it.  Update: My good friend Marijn Heule, at UT Austin, has now apparently found a smaller such graph, with “only” 874 vertices.  See here.
    So, can we be confident that the proof will stand—i.e., that there are no further bugs?  See the comments of Gil Kalai’s post for discussion.  Briefly, though, it’s now been independently verified, using different SAT-solvers, that the chromatic number of de Grey’s corrected graph is indeed 5.  Paul Phillips emailed to tell me that he’s now independently verified that the graph is unit distance as well.  So I think it’s time to declare the result correct.
    Question for experts: is there a general principle by which we can show that, if the chromatic number of the plane is at least 6, or is 7, then there exists a finite subgraph that witnesses it?  (This is closely related to asking, what’s the logical complexity of the Hadwiger-Nelson problem: is it Π1?)  Update: As de Grey and a commenter pointed out to me, this is the de Bruijn-Erdös Theorem from 1951.  But the proofs inherently require the Axiom of Choice.  Assuming AC, this also gives you that Hadwiger-Nslson is a Π1 statement, since the coordinates of the points in any finite counterexample can be assumed to be algebraic. However, this also raises the strange possibility that the chromatic number of the plane could be smaller assuming AC than not assuming it.
  2. Last week, Urmila Mahadev, a student (as was I, oh so many years ago) of Umesh Vazirani at Berkeley, posted a preprint on the arXiv giving a protocol for a quantum computer to prove the results of any computation it performs to a classical skeptic—assuming a relatively standard cryptographic assumption, namely the quantum hardness of the Learning With Errors (LWE) problem, and requiring only classical communication between the skeptic and the QC.  I don’t know how many readers remember, but way back in 2006, inspired by a $25,000 prize offered by Stephen Wolfram, I decided to offer a $25 prize to anyone who could solve the problem of proving the results of an arbitrary quantum computation to a classical skeptic, or who could give oracle evidence that a solution was impossible.  I had first learned this fundamental problem from Daniel Gottesman.
    Just a year or two later, independent work of Aharonov, Ben-Or, and Eban, and of Broadbent, Fitzsimons, and Kashefi made a major advance on the problem, by giving protocols that were information-theoretically secure.  The downside was that, in contrast to Mahadev’s new protocol, these earlier protocols required the verifier to be a little bit quantum: in particular, to exchange individual unentangled qubits with the QC.  Or, as shown by later work, the verifier could be completely classical, but only if it could send challenges to two or more quantum computers that were entangled but unable to communicate with each other.  In light of these achievements, I decided to award both groups their own checks for half the prize amount ($12.50), to be split among themselves however they chose.
    Neither with Broadbent et al.’s or Aharonov et al.’s earlier work, nor with Mahadev’s new work, is it immediately clear whether the protocols relativize (that is, whether they work relative to an arbitrary oracle), but it’s plausible that they don’t.
    Anyway, assuming that her breakthrough result stands, I look forward to awarding Urmila the full $25 prize when I see her at the Simons Institute in Berkeley this June.

Huge congratulations to Aubrey and Urmila for their achievements!

Update (April 12): My friend Virgi Vassilevska Williams asked me to announce a theoretical computer science women event, which will take during the upcoming STOC in LA.

Another Update: Another friend, Holden Karnofsky of the Open Philanthropy Project, asked me to advertise that OpenPhil is looking to hire a Research Analyst and Senior Research Analyst. See also this Medium piece (“Hiring Analytical Thinkers to Help Give Away Billions”) to learn more about what the job would involve.