Shtetl-Optimized

1. Good news, everyone! Following years of requests, this blog finally supports rich HTML and basic TeX in comments. Also, the German spam that used to plague the blog (when JavaScript was disabled) is gone. For all this, I owe deep gratitude to a reader and volunteer named Filip Dimitrovski.
   
2. Filip refused to accept any payment for fixing this blog. Instead, he asked only one favor: namely, that I use my platform to raise public awareness about the plight of the MAOI antidepressant Nardil. Filip tells me that, while tens of thousands of people desperately need Nardil—no other antidepressant ever worked for them—it’s become increasingly unavailable because the pharma companies can no longer make money on it. He points me to a SlateStarCodex post from 2015 that explains the problem in more detail (anyone else miss SlateStarCodex?). More recent links about the worsening crisis here, here, and here.
   
3. Here’s a fantastic interview of Bill Gates by Steven Levy, about the coronavirus debacle in the US. Gates, who’s always been notoriously and strategically nonpartisan, is more explicit than I’ve ever seen him before in explaining how the Trump administration’s world-historic incompetence led to where we are.
   
4. Speaking of which, here’s another excellent article, this one in The American Interest, about the results of “wargames” trying to simulate what happens in the extremely likely event that Trump contests a loss of the November election. Notably, the article sets out six steps that could be taken over the next few months to decrease the chance of a crisis next to which all the previous crises of 2020 will pale.
   
5. A reader asked me to share a link to an algorithm competition, related to cryptographic “proofs of time,” that ends on August 31. Apparently, my having shared a link to a predecessor of this competition—at the request of friend-of-the-blog Bram Cohen—played a big role in attracting good entries.
   
6. Huge congratulations to my former PhD student Shalev Ben-David, as well as Eric Blais, for co-winning the FOCS’2020 Best Paper Award—along with two other papers—for highly unconventional work about a new minimax theorem for randomized algorithms. (Ben-David and Blais also have a second FOCS paper, which applies their award paper to get the first tight composition theorem for randomized query complexity. Here’s the full list of FOCS papers—lots of great stuff, for a conference that of course won’t physically convene!) Anyway, a central idea in Ben-David and Blais’s new work is to use proper scoring rules to measure the performance of randomized algorithms—algorithms that now make statements like “I’m 90% sure that this is a yes-input,” rather than just outputting a 1-bit guess. Notably, Shalev tells me that he learned about proper scoring rules by reading rationalist blogs. So next time you lament your untold hours sacrificed to that pastime, remind yourself of where it once led!
   
7. What have I been up to lately? Besides Busy Beaver, hanging out with my kids, and just trying to survive? Mostly giving a lot of Zoom lectures! For those interested, here’s a Q&A that I recently did on the past and present of quantum computing, hosted by Andris Ambainis in Latvia. It did feel a bit surreal when my “interviewer” asked me to explain how I got into quantum computing research, and my answer was basically: “well, as you know, Andris, a lot of it started when I got hold of your seminal paper back in 1999…”

Update (July 27): I now have a substantially revised and expanded version (now revised and expanded even a second time), which incorporates (among other things) the extensive feedback that I got from this blog post. There are new philosophical remarks, some lovely new open problems, and an even-faster-growing (!) integer sequence. Check it out!

---

A life that was all covid, cancellations, and Trump, all desperate rearguard defense of the beleaguered ideals of the Enlightenment, would hardly be worth living. So it was an exquisite delight, these past two weeks, to forget current events and write an 18-page survey article about the Busy Beaver function: the staggeringly quickly-growing function that probably encodes a huge portion of all interesting mathematical truth in its first hundred values, if only we could know those values or exploit them if we did.

Without further ado, here’s the title, abstract, and link:

The Busy Beaver Frontier
by Scott Aaronson

The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: when does the BB function first exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n+1)>2^BB(n) for large enough n? Given BB(n), how many advice bits are needed to compute BB(n+1)? Do all Busy Beavers halt on all inputs, not just the 0 input? Is it decidable whether BB(n) is even or odd?

The article is slated to appear soon in SIGACT News. I’m grateful to Bill Gasarch for suggesting it—even with everything else going on, this was a commission I felt I couldn’t turn down!

Besides Bill, I’m grateful to the various Busy Beaver experts who answered my inquiries, to Marijn Heule and Andy Drucker for suggesting some of the open problems, to Marijn for creating a figure, and to Lily, my 7-year-old daughter, for raising the question about the first value of n at which the Busy Beaver function exceeds the Ackermann function. (Yes, Lily’s covid homeschooling has included multiple lessons on very large positive integers.)

There are still a few days until I have to deliver the final version. So if you spot anything wrong or in need of improvement, don’t hesitate to leave a comment or send an email. Thanks in advance!

Of course Busy Beaver has been an obsession that I’ve returned to many times in my life: for example, in that Who Can Name the Bigger Number? essay that I wrote way back when I was 18, in Quantum Computing Since Democritus, in my public lecture at Festivaletteratura, and in my 2016 paper with Adam Yedidia that showed that the values of all Busy Beaver numbers beyond the 7910^th are independent of the axioms of set theory (Stefan O’Rear has since shown that independence starts at the 748^th value or sooner). This survey, however, represents the first time I’ve tried to take stock of BusyBeaverology as a research topic—collecting in one place all the lesser-known theorems and empirical observations and open problems that I found the most striking, in the hope of inspiring not just contemplation or wonderment but actual progress.

Within the last few months, the world of deep mathematics that you can actually explain to a child lost two of its greatest giants: John Conway (who died of covid, and who I eulogized here) and Ron Graham. One thing I found poignant, and that I didn’t know before I started writing, is that Conway and Graham both play significant roles in the story of the Busy Beaver function. Conway, because most of the best known candidates for Busy Beaver Turing machines turn out, when you analyze them, to be testing variants of the notorious Collatz Conjecture—and Conway is the one who proved, in 1972, that the set of “Collatz-like questions” is Turing-undecidable. And Graham because of Graham’s number from Ramsey theory—a candidate for the biggest number that’s ever played a role in mathematical research—and because of the discovery, four years ago, that the 18^th Busy Beaver number exceeds Graham’s number.

(“Just how big is Graham’s number? So big that the 17^th Busy Beaver number is not yet known to exceed it!”)

Anyway, I tried to make the survey pretty accessible, while still providing enough technical content to sink one’s two overgrown front teeth into (don’t worry, there are no such puns in the piece itself). I hope you like reading it at least 1/BB(10) as much as I liked writing it.

Update (July 24): Longtime commenter Joshua Zelinsky gently reminded me that one of the main questions discussed in the survey—namely, whether we can prove BB(n+1)>2^BB(n) for all large enough n—was first brought to my attention by him, Joshua, in a 2013 Ask-Me-Anything session on this blog! I apologize to Joshua for the major oversight, which has now been corrected. On the positive side, we just got a powerful demonstration both of the intellectual benefits of blogging, and of the benefits of sharing paper drafts on one’s blog before sending them to the editor!

Longtime friend-of-the-blog Michael Nielsen, formerly a quantum computing theorist and now an independent thinker about science and AI and learning, posted the following exchange with the astounding GPT-3 text generator / chatbot:

Q: Is it possible to use quantum computers to solve NP-complete problems in polynomial time?
A: It is not possible to use quantum computers to solve NP-complete problems in polynomial time.

Q: Why not?
A: Because NP-complete problems are not in BQP.

Q: You’ve just restated your earlier assertion! What I’d like is to understand the underlying reason why not!
A: I’m sorry, but I don’t have time to explain the underlying reason why not.

Q: No offence, but this seems really bogus. I don’t believe you understand the reason why!
A: I’m sorry, but I don’t have time to explain the underlying reason why not.

(And then there are a few more rounds of the AI not having time to “explain the underlying reason why not.”)

This is, like, 80% of the way to replacing Shtetl-Optimized!

For much more discussion of GPT-3 and its implications, and samples of its output, see for example the SSC subreddit. At the moment, as far as I can tell, the closest a person off the street can easily come to experimenting with GPT-3 themselves is using a website called AI Dungeon.

And yes, as many have already remarked, this is clearly the MITS Altair of text-generating AI, an amusing toy that’s also the start of something that will change the world.

Update (July 17): Friend-of-the-blog Karen Morenz points me to a piece by Bonny Brooks, articulating a left-wing case against cancel culture. I read it and found much to agree with. Mostly, though, I was really happy to spend this week doing some actual research (nearly the first since the pandemic started) rather than blogging culture-war stuff! Speaking of which, please get in any last comments within the next day or so; then I’ll close down the thread.

---

If there were ever a time for liberals and progressives to put aside their internal squabbles, you’d think it was now. The President of the United States is a racist gangster, who might not leave if he loses the coming election—all the more reason to ensure he loses in a landslide. Due in part to that gangster’s breathtaking incompetence, 130,000 Americans are now dead, and the economy tanked, from a pandemic that the rest of the world has under much better control. The gangster’s latest “response” to the pandemic has been to disrupt the lives of thousands of foreign scientists—including several of my students—by threatening to cancel their visas. (American universities will, of course, do whatever they legally can to work around this act of pure spite.)

So how is the left responding to this historic moment?

This weekend, 536 people did so by … trying to cancel Steven Pinker, stripping him of “distinguished fellow” and “media expert” status (whatever those are) in the Linguistics Society of America for ideological reasons.

Yes, Steven Pinker: the celebrated linguist and cognitive scientist, author of The Language Instinct and How the Mind Works (which had a massive impact on me as a teenager) and many other books, and academic torch-bearer for the Enlightenment in our time. For years, I’d dreaded the day they’d finally come for Steve, even while friends assured me my fears must be inflated since, after all, they hadn’t come for him yet.

I concede that the cancelers’ logic is impeccable. If they can get Pinker, everyone will quickly realize that there’s no longer any limit to who they can get—including me, including any writer or scientist who crosses them. If you’ve ever taken, or aspire to take, any public stand riskier than “waffles are tasty,” then don’t delude yourself that you’ll be magically spared—certainly not by your own progressive credentials.

I don’t know if the “charges” against Pinker merit a considered response (Pinker writes that some people wondered if they were satire). For those who care, though, here’s a detailed and excellent takedown by the biologist and blogger Jerry Coyne, and here’s another by Barbara Partee.

So, it seems Pinker once used the term “urban crime,” which can be a racist dogwhistle—except that in this case, it literally meant “urban crime.” Pinker once referred to Bernie Goetz, whose 1984 shooting of four robbers in the NYC subway polarized the US at the time, as a “mild-mannered engineer,” in a sentence whose purpose was to contrast that description with the ferocity of Goetz’s act. Pinker “appropriated” the work of a Black scholar, Harvard Dean Lawrence Bobo, which apparently meant approvingly citing him in a tweet. Etc. Ironically, it occurred to me that the would-be Red Guards could’ve built a much stronger case against Pinker had they seriously engaged with his decades of writing—writing that really does take direct aim at their whole worldview, they aren’t wrong about that—rather than superficially collecting a few tweets.

What Coyne calls the “Purity Posse” sleazily gaslights its readers as follows:

We want to note here that we have no desire to judge Dr. Pinker’s actions in moral terms, or claim to know what his aims are. Nor do we seek to “cancel” Dr. Pinker, or to bar him from participating in the linguistics and LSA communities (though many of our signatories may well believe that doing so would be the right course of action).

In other words: many of us “may well believe” that Pinker’s scientific career should be ended entirely. But magnanimously, for now, we’ll settle for a display of our power that leaves the condemned heretic still kicking. So don’t accuse us of wanting to “cancel” anyone!

In that same generous spirit:

Though no doubt related, we set aside questions of Dr. Pinker’s tendency to move in the proximity of what The Guardian called a revival of “scientific racism”, his public support for David Brooks (who has been argued to be a proponent of “gender essentialism”), his expert testimonial in favor of Jeffrey Epstein (which Dr. Pinker now regrets), or his dubious past stances on rape and feminism.

See, even while we make these charges, we disclaim all moral responsibility for making them. (For the record, Alan Dershowitz asked Pinker for a linguist’s opinion of a statute, so Pinker provided it; Pinker didn’t know at the time that the request had anything to do with Epstein.)

Again and again, spineless institutions have responded to these sorts of ultimatums by capitulating to them. So I confess that the news about Pinker depressed me all weekend. The more time passed, though, the more it looked like the Purity Posse might have actually overplayed its hand this time. Steven Pinker is not weak prey.

Let’s start with what’s missing from the petition: Noam Chomsky pointedly refused to sign. How that must’ve stung his comrades! For that matter, virtually all of the world’s well-known linguists refused to sign. Ray Jackendoff and Michel DeGraff were originally on the petition, but their names turned out to have been forged (were others?).

But despite the flimsiness of the petition, suppose the Linguistics Society of America caved. OK, I mused, how many people have even heard of the Linguistics Society of America, compared to the number who’ve heard of Pinker or read his books? If the LSA expelled Pinker, wouldn’t they be forever known to the world only as the organization that had done that?

I’m tired of the believers in the Enlightenment being constantly on the defensive. “No, I’m not a racist or a misogynist … on the contrary, I’ve spent decades advocating for … yes, I did say that, but you completely misunderstood my meaning, which in context was … please, I’m begging you, can’t we sit and discuss this like human beings?”

It’s time for more of us to stand up and say: yes, I am a center-left extremist. Yes, I’m an Enlightenment fanatic, a radical for liberal moderation and reason. If liberalism is the vanilla of worldviews, then I aspire to be the most intense vanilla anyone has ever tasted. I’m not a closeted fascist. I’m not a watered-down leftist. I’m something else. I consider myself ferociously anti-racist and anti-sexist and anti-homophobic and pro-downtrodden, but I don’t cede to any ideological faction the right to dictate what those terms mean. The world is too complicated, too full of ironies and surprises, for me to outsource my conscience in that way.

Enlightenment liberalism at least has the virtue that it’s not some utopian dream: on the contrary, it’s already led to most of the peace and prosperity that this sorry world has ever known, wherever and whenever it’s been allowed to operate. And while “the death of the Enlightenment” gets proclaimed every other day, liberal ideals have by now endured for centuries. They’ve outlasted kings and dictators, the Holocaust and the gulag. They certainly have it within them to outlast some online sneerers.

Yes, sometimes martyrdom (or at least career martyrdom) is the only honorable course, and yes, the childhood bullies did gift me with a sizeable persecution complex—I’ll grant the sneerers that. But on reflection, no, I don’t want to be a martyr for Enlightenment values. I want Enlightenment values to win, and not by vanquishing their opponents but by persuading them. As Pinker writes:

A final comment: I feel sorry for the signatories. Moralistic dudgeon is a shallow and corrosive indulgence, & policing the norms of your peer group a stunting of the intellect. Learning new ideas & rethinking conventional wisdom are deeper pleasures … and ultimately better for the world. Our natural state is ignorance, fallibility, & self-deception. Progress comes only from broaching & evaluating ideas, including those that feel unfamiliar and uncomfortable.

Spend a lot of time on Twitter and Reddit and news sites, and it feels like the believers in the above sentiment are wildly outnumbered by the self-certain ideologues of all sides. But just like the vanilla in a cake can be hard to taste, so there are more Enlightenment liberals than it seems, even in academia—especially if we include all those who never explicitly identified that way, because they were too busy building or fixing or discovering or teaching, and because they mistakenly imagined that if they just left the Purity Posse alone then the Posse would do likewise. If that’s you, then please ask yourself now: what is my personal break-point for speaking up?

Like many academics, I’ve now been regularly “attending” conferences and giving talks via Zoom for four months. Naturally, I’ve learned a lot about how to use this platform—one that, despite numerous quirks and flaws, actually works well enough that it could probably replace at least 2/3 of in-person talks and meetings after the covid crisis is over. But one particular lesson is so important that I thought I’d make a public service announcement of it. So without further ado:

Email the link.

You know, the thing like

https://us02web.zoom.us/jblahblah

that you actually click to get to the actual conversation. Definitely email the link to the speaker (!). But also email it to whomever said they plan to attend. Resend the link between a day and an hour in advance, so that it doesn’t get buried, but turns up right away when people search their inboxes. If possible, put the link in every single email about the meeting or lecture. Even if you already sent the link for previous iterations of the meeting and it hasn’t changed, send it again. Don’t assume people will find the link on the web. Don’t make them click through five other links or open an attached PDF for it. Don’t send ten emails that explain every possible detail of the meeting except how to get to it. Just email the link. That’s all. Thanks!

2020 sucks.

Yesterday I learned that David Poulin, a creative and widely-beloved quantum computing and information theorist, has died at age 43, of an aggressive brain cancer. After studying under many of the field’s legends—Gilles Brassard, Wojciech Zurek, Ray Laflamme, Gerard Milburn, John Preskill—David became a professor at the University of Sherbrooke in Quebec. There he played a leading role in CIFAR (the Canadian Institute For Advanced Research), eventually co-directing its quantum information science program with Aephraim Steinberg. Just this fall (!), David moved to Microsoft Research to start a new phase of his career. He’s survived by a large family.

While I can’t claim any deep knowledge of David’s work—he and I pursued very different problems—it seems appropriate to mention some of his best-known contributions. With David Kribs, Ray Laflamme, and Maia Lesosky, he introduced the formalism of operator quantum error correction, and made many other contributions to the theory of quantum error-correction and fault-tolerance (including the estimation of thresholds). He and coauthors showed in a Nature paper how to do quantum state tomography on 1D matrix product states efficiently. With Pavithran Iyer, he proved that optimal decoding of stabilizer codes is #P-hard.

And if none of that makes a sufficient impression on Shtetl-Optimized readers: well, back in 2013, when D-Wave was claiming to have achieved huge quantum speedups, David Poulin was one of the few experts willing to take a clear skeptical stance in public (including right in my comment section—see here for example).

I vividly remember being officemates with David back in 2003, at the Perimeter Institute in Waterloo—before Perimeter had its sleek black building, when it still operated out of a converted tavern. (My and David’s office was in the basement, reached via a narrow staircase.) David liked to tease me: for example, if I found him in conversation with someone else and asked what it was about, he’d say, “oh, nothing to do with computational efficiency, no reason for you to care.” (And yet, much of David’s work ultimately would have to do with computational efficiency.)

David was taken way too soon and will be missed by everyone who knew him. Feel free to share David stories in the comments.

Update (6/24): For further thoughts and context about this unfolding saga, see this excellent piece by Tom Chivers (author of The AI Does Not Hate You, so far the only book about the rationalist community, one that I reviewed here).

---

This morning, like many others, I woke up to the terrible news that Scott Alexander—the man I call “the greatest Scott A. of the Internet”—has deleted SlateStarCodex in its entirety. The reason, Scott explains, is that the New York Times was planning to run an article about SSC. Even though the article was going to be positive, NYT decided that by policy, it would need to include Scott’s real surname (Alexander is his middle name). Scott felt that revealing his name to the world would endanger himself and his psychiatry patients. Taking down his entire blog was the only recourse that he saw.

The NYT writer, Cade Metz, was someone who I’d previously known and trusted from his reporting on Google’s quantum supremacy experiment. So in recent weeks, I’d spent a couple hours on the phone with Cade, answering his questions about the rationality community, the history of my interactions with it, and why I thought SlateStarCodex spoke to so many readers. Alas, when word got around the rationality community that Cade was writing a story, a huge panic arose that he was planning on some sort of Gawker-style hit piece or takedown. Trying to tamp down the fire, I told Scott Alexander and others that I knew Cade, his intentions were good, he was only trying to understand the community, and everyone should help him by talking to him openly.

In a year of historic ironies, here’s another one: that it was the decent, reasonable, and well-meaning Cade Metz, rather than any of the SneerClubbers or Twitter-gangsters who despised Scott Alexander for sharing his honest thoughts on hot-button issues, who finally achieved the latter’s dark dream of exiling Scott from the public sphere.

The recent news had already been bad enough: Trump’s “temporary suspension” of J1 and H1B visas (which will deal a body blow to American universities this year, and to all the foreign scientists who planned to work at them), on top of the civil unrest, on top of the economic collapse, on top of the now-resurgent coronavirus. But with no more SlateStarCodex, now I really feel like my world is coming to an end.

I’ve considered SSC to be the best blog on the Internet since not long after discovering it five years ago.  Of course my judgment is colored by one of the most notorious posts in SSC’s history (“Untitled”) being a ferocious defense of me, when thousands were attacking me and it felt like my life was finished.  But that’s merely what brought me there in the first place. I stayed because of Scott’s insights about everything else, and because of the humor and humanity and craftsmanship of his prose.  Since then I had the privilege to become friends with Scott, not only virtually but in real life, and to meet dozens of others in the SSC community, in its Bay Area epicenter and elsewhere.

In my view, for SSC to be permanently deleted would be an intellectual loss on the scale of, let’s say, John Stuart Mill or Mark Twain burning their collected works.  That might sound like hyperbole, but not (I don’t think) to the tens of thousands who read Scott’s essays and fiction, particularly during their 2013-2016 heyday, and who went from casual enjoyment to growing admiration to the gradual recognition that they were experiencing, “live,” the works that future generations of teachers will assign their students when they cover the early twenty-first century.  The one thing that mitigates this tragedy is the hope that it will yet be reversed (and, of course, the fact that backups still exist in the bowels of the Internet).

When I discovered Scott Alexander in early 2015, the one issue that gave me pause was his strange insistence on maintaining pseudonymity, even as he was already then becoming more and more of a public figure. In effect, Scott was trying to erect a firewall between his Internet persona and his personal and professional identities, and was relying on the entire world’s goodwill not to breach that firewall.  I thought to myself, “this can’t possibly last!  Scott simply writes too well to evade mainstream notice forever—and once he’s on the world’s radar, he’ll need to make a choice, about who he is and whether he’s ready to own his gifts to posterity under his real name.”  In retrospect, what astonishes me is that Scott has been able to maintain the “double life” for as long as he has!

In his takedown notice, Scott writes that it’s considered vitally important in psychiatry for patients to know almost nothing about their doctors, beyond their names and their areas of expertise. That caused me to wonder: OK, but doesn’t the world already have enough psychiatrists who are ciphers to their patients?  Would it be so terrible to have one psychiatrist with a clear public persona—possibly even one who patients sought out because of his public persona, because his writings gave evidence that he’d have sympathy or insight about their conditions?  To become a psychiatrist, does one really need to take a lifelong vow of boringness—a vow never to do or say anything notable enough that one would be “outed” to one’s patients?  What would Freud, or Jung, or any of the other famous therapist-intellectuals of times past have thought about such a vow?

Scott also mentions that he’s gotten death threats, and harassing calls to his workplace, from people who hate him because of his blog (and who found his real name by sleuthing). I wish I knew a solution to that. For what it’s worth, my blogging has also earned me a death threat, and threats to sue me, and accusatory letters to the president of my university—although in my case, the worst threats came neither from Jew-hating neo-Nazis nor from nerd-bashing SJWs, but from crackpots enraged that I wouldn’t use my blog to credit their proof of P≠NP or their refutation of quantum mechanics.

When I started Shtetl-Optimized back in 2005, I remember thinking: this is it.  From now on, the only secrets I’ll have in life will be ephemeral and inconsequential ones.  From this day on, every student in my class, every prospective employer, every woman who I ask on a date (I wasn’t married yet), can know whatever they want to know about my political sympathies, my deepest fears and insecurities, any of it, with a five-second Google search.  Am I ready for that?  I decided that I was—partly just because I‘ve never had the mental space to maintain multiple partitioned identities anyway, to remember what each one is or isn’t allowed to know and say!  I won’t pretend that this is the right decision for everyone, but it was my decision, and I stuck with it, and it wasn’t always easy but I’m still here and so evidently are you.

I’d be overjoyed if Scott Alexander were someday to reach a place in his life where he felt comfortable deciding similarly.  That way, not only could he enjoy the full acclaim that he’s earned for what he’s given to the world, but (much more importantly) his tens of thousands of fans would be able to continue benefitting from his insights.

For now, though, the brute fact is that Scott is obviously not comfortable making that choice.  That being so, it seems to me that, if the NYT was able to respect the pseudonymity of Banksy and many others who it’s reported on in the past, when revealing their real names would serve no public interest, then it should also be able to respect Scott Alexander’s pseudonymity.  Especially now that Scott has sent the most credible signal imaginable of how much he values that pseudonymity, a signal that astonished even me.  The world does not exist only to serve its rare geniuses, but surely it can make such trivial concessions to them.

Time for a non-depressing post. Quantum Computing Since Democritus, which is already available in English and Russian, is about to be published in both Chinese and Japanese. (So if you read this blog, but have avoided tackling QCSD because your Chinese or Japanese is better than your English, today’s your day!) To go along with the new editions, Cambridge University Press asked me to write a new foreword, reflecting on what happened in the seven years since the book was published. The editor, Paul Dobson, kindly gave me permission to share the new foreword on my blog. So without further ado…

---

Quantum Computing Since Democritus began its life as a course that I taught at the University of Waterloo in 2006.  Seven years later, it became the book that you now hold.  Its preface ended with the following words:

Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 lecture notes were in 2013.

As I write this, in June 2020, a lot has happened that I would never have predicted in 2013.  Donald Trump is the President of the United States, and is up for reelection shortly.  This is not a political book, so let me resist the urge to comment further.  Meanwhile, the coronavirus pandemic is ravaging the world, killing hundreds of thousands of people, crashing economies, and shutting down schools and universities (including mine).  And in the past few weeks, protests against racism and police brutality started in America and then spread to the world, despite the danger of protesting during a pandemic.

Leaving aside the state of the world, my own life is also very different than it was seven years ago.  Along with my family, I’ve moved from MIT to the University of Texas in Austin.  My daughter, who was born at almost exactly the same time as Quantum Computing Since Democritus, is now a first-grader, and is joined by a 3-year-old son.  When my daughter’s school shut down due to the coronavirus, I began home-schooling her in math, computer science, and physics—in some of the exact same topics covered in this book.  I’m now engaged in an experiment to see what portion of this material can be made accessible to a 7-year-old.

But what about the material itself?  How has it held up over seven years?  Both the bad news and the (for you) good news, I suppose, is that it’s not particularly out of date.  The intellectual underpinnings of quantum computing and its surrounding disciplines remain largely as they were.  Still, let me discuss what has changed.

Between 2013 and 2020, the field of quantum computing made a striking transition, from a mostly academic pursuit to a major technological arms race.  The Chinese government, the US government, and the European Union have all pledged billions of dollars for quantum computing research.  Google, Microsoft, IBM, Amazon, Alibaba, Intel, and Honeywell also now all have well-funded groups tasked with building quantum computers, or providing quantum-computing-related software and services, or even just doing classical computing that’s “quantum-inspired.”  These giants are joined by dozens of startups focused entirely on quantum computing.

The new efforts vary greatly in caliber; some efforts seem rooted in visions of what quantum computers will be able to help with, and how soon, that I find to be wildly overoptimistic or even irresponsible.  But perhaps it’s always this way when a new technology moves from an intellectual aspiration to a commercial prospect.  Having joined the field around 1999, before there were any commercial efforts in quantum computing, I’ve found the change disorienting.

But while some of the new excitement is based on pure hype—on marketers now mixing some “quantum” into their word-salad of “blockchain,” “deep learning,” etc., with no particular understanding of any of the ingredients—there really have been some scientific advances in quantum computing since 2013, a fire underneath the smoke.

Surely the crowning achievement of quantum computing during this period was the achievement of “quantum supremacy,” which a team at Google announced in the fall of 2019.  For the first time, a programmable quantum computer was used to outperform any classical computer on earth, running any currently known algorithm.  Google’s device, called “Sycamore,” with 53 superconducting qubits cooled to a hundredth of a degree above absolute zero, solved a well-defined albeit probably useless sampling problem in about 3 minutes.  To compare, current state-of-the-art simulations on classical computers need a few days, even with hundreds of thousands of parallel processors.  Ah, but will a better classical simulation be possible?  That’s an open question in quantum complexity!  The discussion of that question draws on theoretical work that various colleagues and I did over the past decade.  That work in turn draws on my so-called PostBQP=PP theorem from 2004, explained in this book.

In the past seven years, there were also several breakthroughs in quantum computing theory—some of which resolved open problems mentioned in this book. 

In 2018, Ran Raz and Avishay Tal gave an oracle relative to which BQP (Bounded-Error Quantum Polynomial-Time) is not contained in PH (the Polynomial Hierarchy).  This solved one of the main open questions, since 1993, about where BQP fits in with classical complexity classes, at least in the black-box setting.  (What does that mean?  Read the book!)  Raz and Tal’s proof used a candidate problem that I had defined in 2009 and called “Forrelation.”

Also in 2018, Urmila Mahadev gave a protocol, based on cryptography, by which a polynomial-time quantum computer (i.e., a BQP machine) could always prove the results of its computation to a classical polynomial-time skeptic, purely by exchanging classical messages with the skeptic.  Following Urmila’s achievement, I was delighted to give her a $25 prize for solving the problem that I’d announced on my blog back in 2007.

Perhaps most spectacularly of all, in 2020, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP*=RE.  Here MIP* means the class of problems solvable using multi-prover interactive proof systems with quantumly entangled provers (and classical polynomial-time verifiers), while RE means Recursively Enumerable: a class that includes not only all the computable problems, but even the infamous halting problem (!).  To say it more simply, entangled provers can convince a polynomial-time verifier that an arbitrary Turing machine halts.  Besides its intrinsic interest, a byproduct of this breakthrough was to answer a decades-old question in pure math, the so-called Connes Embedding Conjecture (by refuting the conjecture).  To my knowledge, the new result represents the first time that quantum computing has reached “all the way up the ladder of hardness” to touch uncomputable problems.  It’s also the first time that non-relativizing techniques, like the ones central to the study of interactive proofs, were ever used in computability theory.

In a different direction, the last seven years have witnessed an astonishing convergence between quantum information and quantum gravity—something that was just starting when Quantum Computing Since Democritus appeared in 2013, and that I mentioned as an exciting new direction.  Since then, the so-called “It from Qubit” collaboration has brought together quantum computing theorists with string theorists and former string theorists—experts in things like the black hole information problem—to develop a shared language.  One striking proposal that’s emerged from this is a fundamental role for quantum circuit complexity—that is, the smallest number of 1- and 2-qubit gates needed to prepare a given n-qubit state from the all-0 state—in the so-called AdS/CFT (Anti de Sitter / Conformal Field Theory) correspondence.  AdS/CFT is a duality between physical theories involving different numbers of spatial dimensions; for more than twenty years, it’s been a central testbed for ideas about quantum gravity.  But the duality is extremely nonlocal: a “simple” quantity in the AdS theory, like the volume of a wormhole, can correspond to an incredibly “complicated” quantity in the dual CFT.  The new proposal is that the CFT quantity might be not just complicated, but literally circuit complexity itself.  Fanciful as that sounds, the truth is that no one has come up with any other proposal that passes the same sanity checks.  A related new insight is that the nonlocal mapping between the AdS and CFT theories is not merely analogous to, but literally an example of, a quantum error-correcting code: the same mathematical objects that will be needed to build scalable quantum computers.

When Quantum Computing Since Democritus was first published, some people thought it went too far in elevating computer science, and computational complexity in particular, to fundamental roles in understanding the physical world.  But even I wasn’t audacious enough to posit connections like the ones above, which are now more-or-less mainstream in quantum gravity research.

I’m proud that I wrote Quantum Computing Since Democritus, but as the years go by, I find that I have no particular desire to revise it, or even reread it.  It seems far better for the book to stand as a record of what I knew and believed and cared about at a certain moment in time.

The intellectual quest that’s defined my life—the quest to wrap together computation, physics, math, and philosophy into some sort of coherent picture of the world—might never end.  But it does need to start somewhere.  I’m honored that you chose Quantum Computing Since Democritus as a place to start or continue your own quest.  I hope you enjoy it.

Scott Aaronson
Austin, Texas
June 2020

(1) To start with some rare good news: I was delighted that the US Supreme Court, in a 5-4 holding led by Chief Justice Roberts (!), struck down the Trump administration’s plan to end DACA (Deferred Action for Childhood Arrivals). Dismantling DACA would’ve been a first step toward deporting 700,000 overwhelmingly blameless and peaceful people from, in many cases, the only homes they remember, for no particular reason other than to slake the resentment of Trump’s base. Better still was the majority’s argument: that when, by law, a federal agency has to supply a reason for a policy change (in this case, ending DACA), its reason can’t just be blatantly invented post facto.

To connect to my last post: I hope this gives some evidence that, if Trump refuses to accept an electoral loss in November, and if it ends up in the Supreme Court as Bush v. Gore did, then Roberts might once again break from the Court’s other four rightists, in favor of the continued survival of the Republic.

(2) Along with Steven Pinker, Scott Alexander, Sam Altman, Jonathan Haidt, Robert Solovay, and others who might be known to this blog’s readership, I decided after reflection to sign a petition in support of Steve Hsu, a theoretical physicist turned genomics researcher, and the Senior Vice President for Research and Innovation at Michigan State University.

Hsu now faces possible firing, because of a social media campaign apparently started by an MSU grad student and SneerClub poster named Kevin Bird. What are the charges? Hsu appeared in 2017 on an alt-right podcast (albeit, one that Noam Chomsky has also appeared on). On Hsu’s own podcast, he interviewed Ron Unz, who despite Jewish birth has become a nutcase Holocaust denier—yet somehow that topic never came up on the podcast. Hsu said that, as a scientist, he doesn’t know whether group differences in average IQ have a genetic component, but our commitment to anti-racism should never hinge on questions of biology (a view also espoused by Peter Singer, perhaps the leading liberal moral philosopher of our time). Hsu has championed genomics research that, in addition to medical uses, might someday help enable embryo screening for traits like IQ. Finally, Hsu supports the continued use of standardized tests in university admissions (yes, that’s one of the listed charges).

Crucially, it doesn’t matter for present purposes if you disagree with many of Hsu’s views. The question is more like: is agreement with Steven Pinker, Jonathan Haidt, and other mild-mannered, Obama-supporting thinkers featured in your local airport bookstore now a firing offense in academia? And will those who affirm that it is, claim in the next breath to be oppressed, marginalized, the Rebel Alliance?

To be fair to the cancelers, I think they have two reasonable arguments in their favor.

The first that they’re “merely” asking for Hsu to step down as vice president, not for him to lose his tenured professorship in physics. Only professors, say the activists, enjoy academic freedom; administrators need to uphold the values and public image of their university, as Larry Summers learned fifteen years ago. (And besides, we might add, what intellectual iconoclast in their right mind would ever become a university VP, or want to stay one??) I’d actually be fine with this if I had any confidence that it was going to end here. But I don’t. Given the now-enshrined standards—e.g., that professors hold positions of power, and that the powerful can oppress the powerless, or even do violence to them, just by expressing or entertaining thoughts outside an ever-shrinking range—why should Hsu trust any assurances that he’ll be left alone, if he does go back to being a physics professor? If the SneerClubbers can cancel him, then how long until they cancel Pinker, or Haidt, or me? (I hope the SneerClubbers enthusiastically embrace those ideas! If they do, then no one ever again gets to call me paranoid about Red Guards behind every bush.)

The second reasonable argument is that, as far as I can tell, Hsu really did grant undeserved legitimacy to a Holocaust denier, via a friendly interview about other topics on his podcast. I think it would help if, without ceding a word that he doesn’t believe, Hsu were now to denounce racism, Holocaust denial, and specifically Ron Unz’s flirtation with Holocaust denial in the strongest possible terms, and explain why he didn’t bring the topic up with his guest (e.g., did he not know Unz’s views?).

Will He Go?, by legal scholar Lawrence Douglas, is, at 120 pages, a slim volume focused on a single question: what happens if the 2020 US election delivers a narrow or disputed result favoring Biden, and Trump refuses to concede? This question will, of course, either be answered or rendered irrelevant in half a year. And yet, in my estimation, there’s at least a 15% probability that Will He Go? will enter the ranks of the most important and prescient books ever written. You should read it right now (or at least read this Vox interview), if you want to think through the contours of a civilizational Singularity that seems at least as plausible to me as the AI Singularity, but whose fixed date of November 3, 2020 we’re now hurtling toward.

In one of the defining memes of the past few years, a sign in a bookstore reads “Dear customers: post-apocalyptic fiction has been moved to the Current Affairs section.” I was reminded of that as Douglas dryly lays out his horror scenario: imagine, hypothetically, that a President of the United States gets elected on a platform of racism and lies, with welcomed assistance from a foreign adversary. Suppose that his every outrage only endears him further to his millions of followers. Suppose that, as this president’s deepest (and perhaps only) principle, he never backs down, never apologizes, never acknowledges any inconvenient fact, and never accepts the legitimacy of any contest that he loses—and this is perfectly rational for him, as he’s been richly rewarded for this strategy his entire life. Suppose that, during the final presidential debate, he pointedly refuses to promise to respect the election outcome if he loses—a first in American history. And suppose that, after eking out a narrow win in the Electoral College, he then turns around and disputes the election anyway (!)—claiming, ludicrously, that he would’ve won the popular vote too, if not for millions of fraudulent voters. Suppose that, for their own sordid reasons, Republican majorities in the Senate and Supreme Court enable this president’s chaotic rule, block his impeachment, and acquiesce to his daily cruelties and lies.

Then what happens in the next election?

Taking the existing catastrophe as given, Douglas asks: is America’s Constitutional machinery up to a challenge that it’s never yet faced, of a president who accepts democracy itself as legitimate only when he wins? Douglas concludes that it isn’t—and this is the book’s terrifying and non-obvious part. There are no checks or balances in the Constitution that will magically ensure a smooth transition of power. On the contrary, the design flaws of our antiquated system make a meltdown more likely.

OK, but then why hasn’t America’s Reactor of Democracy exploded yet (or at least, not since the Civil War)? Douglas spends a lot of time on historical parallels, including the Tilden-Hayes election of 1876 and the Bush-Gore election of 2000. In each case, he finds, collapse was averted not because of mythical safeguards in our rickety, Rube-Goldberg system, but only because the relevant people (e.g., Samuel Tilden, Al Gore) stood down, having internalized the norm that the national good required them to. But that’s precisely what Trump has telegraphed that he’ll never do.

The class of scenario that most worries Douglas runs as follows: just like last time, the election comes down to a few swing states, such as Pennsylvania, Wisconsin, and Michigan. Crucially, right now all three of those states have Democratic governors and Republican-controlled legislatures … and there’s no clear law about which of the two (the governor or the legislature) gets to certify election results and send them to Congress! So suppose Trump has a slight edge on election night, Fox News calls the race for him, but then an avalanche of absentee or provisional ballots shift things in Biden’s favor over the following week. Can you imagine Trump or his supporters accepting the latter?

Or suppose that, on election day, Russian hackers cut off electricity or voter registration databases in Philadelphia or Detroit, via computer systems that we know they already broke into and that remain exposed (!). Hundreds of thousands are unable to vote; the Democratic governor orders a revote; the Republican legislature tries to preempt that by sending the original tally to Congress.

The final authority over election results rests with Congress. The trouble is, the Senate is currently under Republican control and the House under Democratic control—and once again, the Constitution and federal law provide no clear guidance on how to resolve a deadlock between the two on presidential succession (!!). So what if Michigan or Pennsylvania or Wisconsin sends two separate sets of election results, and (predictably) the House accepts one and the Senate accepts the other? And what if there’s no resolution by noon EST on January 20, 2021? Then by law, the Speaker of the House, currently Nancy Pelosi, becomes acting president. Can you imagine Trump willingly vacating the Oval Office if that comes to pass?

Douglas seems to have finished writing Will He Go? just as the coronavirus shut down the planet; he includes some comments about how that will massively exacerbate the above problems. Election officials expect a historic number of absentee ballots, from people—disproportionately urban—who will (reasonably) consider it unsafe to wait in line for hours in a room packed with hundreds of strangers. Alas, Trump has already told his followers that voting by mail is a scam to be fiercely opposed, never mind that he uses it himself. Worse yet, the laws governing mail-in ballots—the signature, the postmark, the deadline for receipt—are byzantine, open to interpretation, and wildly different from county to county. So again: imagine if mail-in ballots overturn what looked like a Trump win on election night. The 2000 Florida recount battle was tea and cookies by comparison.

Douglas doesn’t mention, because it happened too recently, the nationwide Black Lives Matter protests (and in rarer cases, vandalism and looting) set off by the horrific murder of George Floyd, and the often shockingly militarized response. But assuming the protests continue through the fall, they’ll of course give the Trumpists even more pretexts to meddle with the election, in the name of imposing “order.”

This is not a sound statistical methodology, but if I imagine a gong every time the US inches perceptibly closer to collapse—gong when Trump got elected, gong when covid made landfall and the states were abandoned to fight each other over medical supplies, gong when George Floyd was murdered and staid, conformist liberals suddenly became anarchists demanding the complete abolition of all police—well, the gongs seem to be getting more frequent! Almost as if they were building toward a gongularity that was, I dunno, sometime around November!

Douglas never mentions the prospect of a second Civil War until literally the book’s last sentence, but it’s the undercurrent of everything he writes—particularly given Trump’s frequent glorifications of violence, and his heavily armed base. Having spent his career studying American jurisprudence, Douglas is willing to guide our imaginations all the way to the precipice but not over it. Part of me still finds the possibility of going over unthinkable—although wasn’t the first Civil War similarly unthinkable until shortly before it happened?

If there is to be a Chernobyl-like meltdown of the Founding Fathers’ machine, at least it would retrospectively make sense of a lot that’s confused me in the past few years. As I’m far from the only one to notice, “my” side, the left, has seemed less and less interested in debate and discussion, and more and more eager to denounce, ban, shame, and no-platform. As just one example, out of hundreds that would serve, last week a 28-year-old analyst named David Shor was fired from his job for politely tweeting about an academic paper offering evidence that peaceful protests are effective at winning public support for progressive, antiracist causes, while violence is ineffective. Hopefully I won’t now be fired for mentioning this!

Of course every cause has its extremists, but the puzzle is that I know plenty of people who will eagerly join whatever is the shaming or firing campaign du jour. And many of those people strike me as friendly, insightful, honest, balanced, wise—at least when the topic is apolitical, as (alas) less and less seems to be these days.

Thought experiment: two protesters meet on a street, carrying huge signs that say “BLACK LIVES MATTER” and “ALL LIVES MATTER” respectively. Can you imagine the following conversation ensuing: “Ah, my good fellow, it looks like you and I are allies, sharing deeply compatible moral messages with the world … one of us merely focused more on a special case, and the other on its generalization! Shall we sit in the park to discuss our joint strategy?”

I guess it takes an Aspbergery STEM nerd even to ask why that never happens. To spell it out: both sides are deploying English words, not for what they explicitly assert, but as markers of tribal affiliation, of which side they’re on.

It’s much the same with “Believe Women.” “Believe all women, always?” asks our hapless STEM nerd. “Women are goddesses who never lie? Feminism is no longer the radical notion that women are people?” “No, you sexist asshat,” replies the normie. “It means listen to women, empathize with women, believe women, be on their side, be on our side. What about that is so f-ing hard to understand?”

Or consider the slogans now conquering the world: “abolish the police” and “defund the police.” “You mean fundamentally reform the police, right?” asks the STEM nerd. “Eliminate qualified immunity, bust the unions that protect abusive cops, get rid of military gear, provide de-escalation training, stop treating homelessness and drug abuse as law enforcement problems, and all those other no-brainers? But not, like, literally end all law enforcement, leave the 911 calls unanswered as machete-wielding rapists run free, and let gangsters and warlords fill the vacuum?”

“No, abolish the police means abolish the police,” reply the activists sternly. “You refuse to listen. You’re not our ally.”

Imagine a ragtag guerilla army encamped in the jungle, surrounded by a brutal occupying force and facing impossible odds, constantly on the alert for turncoats and spies and fair-weather friends in its midst. Would it surprise you if these guerillas had a macabre initiation ritual for new recruits: say, slicing off the tips of recruits’ fingers?

Now suppose you reckoned that truth and justice were at least 3/4 on the guerillas’ side, and so decided to join them. At your initiation, would you ask the guerillas if they’d analyzed whether finger-slicing actually leads to greater effectiveness in battle? Or, as you swore the oath of eternal allegiance to the cause, with one hand on your heart and the other on your Kalashnikov, would you add: “… assuming that we continue to represent Enlightenment values like science, free speech, and intellectual charity”?

When the Nazis invaded the Soviet Union in 1941, it suddenly became reasonable to take the side of the bloodthirsty Stalin. And it would’ve been praiseworthy for a Russian to say: “I now pledge my life to fighting for the Soviet government—even if, likely as not, that government will thank me afterward by sending me to the gulag for an invented crime.”

Five years ago, thousands of woke activists shamed me for writing about my teenage experiences on this blog, a few even calling for an end to my career. Especially if those activists emerge victorious from a turbulent 2020—as I hope they will—I expect that they’ll come for me again. (Well, if they get around to it. I’m nowhere near the top of their list.)

And yet, if Lawrence Douglas’s scenario comes to pass—if, for example, the 2020 election leaves Trump barricaded in the White House with his loyalists, while a duly elected government waits in limbo—then I pledge to render whatever assistance I can, and even risk my life if needed, for the same side that the woke activists will be on.

I’d rather not, though. As Douglas points out, the more overwhelming we can make Trump’s electoral defeat, the less chance that it ever comes to this.