Was Scientific American Sokal’d?

September 24th, 2021

Here’s yesterday’s clickbait offering from Scientific American, the once-legendary home of Martin Gardner’s Mathematical Games column:

Why the Term ‘JEDI’ Is Problematic for Describing Programs That Promote Justice, Equity, Diversity and Inclusion

The sad thing is, I see few signs that this essay was meant as a Sokal-style parody, although in many ways it’s written as one. The essay actually develops a 100% cogent, reasoned argument: namely, that the ideology of the Star Wars films doesn’t easily fit with the new ideology of militant egalitarianism at the expense of all other human values, including irony, humor, joy, and the nurturing of unusual talents. The authors are merely oblivious to the conclusion that most people would draw from their argument: namely, so much the worse for the militant egalitarianism then!

I predict that this proposal—to send the acronym “JEDI” the way of “mankind,” “blacklist,” and, err, “quantum supremacy”—will meet with opposition even from the wokeists themselves, a huge fraction of whom (in my experience) have soft spots for the Star Wars franchise. Recall for example that in 2014, Laurie Penny used Star Wars metaphors in her interesting response to my comment-171, telling male nerds like me that we need to learn to accept that “[we’re] not the Rebel Alliance, [we’re] actually part of the Empire and have been all along.” Admittedly, I’ve never felt like part of an Empire, although I’ll confess to some labored breathing lately when ascending flights of stairs.

As for me, I spent much of my life opposed in principle to Star Wars—I hated how the most successful “science fiction” franchise of all time became that way precisely by ditching any pretense of science and fully embracing mystical woo—but sure, when the chips are down, I’m crazy and radical enough to take the side of Luke Skywalker, even if a team of woke theorists is earnestly, unironically explaining to me that lightsabers are phallocentric and that Vader ranks higher on the intersectional oppression axis because of his breathing problem.

Meantime, of course, the US continues to careen toward its worst Constitutional crisis since the Civil War, as Trump prepares to run again in 2024, and as this time around, the Republicans are systematically purging state governments of their last Brad Raffenspergers, of anyone who might stand in the way of them simply setting aside the vote totals and declaring Trump the winner regardless of the actual outcome. It’s good to know that my fellow progressives have their eyes on the ball—so that when that happens, at least universities will no longer be using offensive acronyms like “JEDI”!

My ACM TechTalk on quantum supremadvantage

September 15th, 2021

This Erev Yom Kippur, I wish to repent for not putting enough quantum computing content on this blog. Of course, repentance is meaningless unless accompanied by genuine reform. That being the case, please enjoy the YouTube video of my ACM TechTalk from last week about quantum supremacy—although, as you’ll see if you watch the thing, I oscillate between quantum supremacy and other terms like “quantum advantage” and even “quantum supremadvantage.” This represents the first time ever that I got pushback about a talk before I’d delivered it for political reasons—the social-justice people, it turns out, are actually serious about wanting to ban the term “quantum supremacy”—but my desire to point out all the difficulties with their proposal competed with my desire not to let that issue overshadow my talk.

And there’s plenty to talk about! While regular Shtetl-Optimized readers will have already heard (or read) most of what I say, I make some new comments, including about the new paper from last week, the night before my talk (!), by the USTC group in China, where they report a quantum supremacy experiment based on random circuit sampling with a superconducting chip, this time with a record-setting 60 qubits and 24 layers of gates. On the other hand, I also stress how increasing the circuit fidelity has become a much more urgent issue than further increasing the number of qubits (or in the case of BosonSampling, the number of photons), if our goal is for these experiments to remain a couple steps ahead of classical spoofing algorithms.

Anyway, I hope you enjoy my lovingly handcrafted visuals. Over the course of this pandemic, I’ve become a full convert to writing out my talks with a stylus pen rather than PowerPointing them—not only is it faster for me, not only does it allow for continuous scrolling rather than arbitrary divisions into slides, but it enforces simplicity and concision in ways they should be enforced.

While there was only time for me to field a few questions at the end of the talk, I later supplied written answers to 52 questions (!!) that I hadn’t gotten to. If you have a question, please check to see if it’s already there, and otherwise ask away in the comments!

Thanks so much to Yan Timanovsky for inviting and organizing this talk, and to whurley for hosting it.

Open Problems Related to Quantum Query Complexity

September 14th, 2021

Way back in 2005, I posed Ten Semi-Grand Challenges for Quantum Computing Theory, on at least half of which I’d say there’s been dramatic progress in the 16 years since (most of the challenges were open-ended, so that it’s unclear when to count them as “solved”). I posed more open quantum complexity problems in 2010, and some classical complexity problems in 2011. In the latter cases, I’d say there’s been dramatic progress on about a third of the problems. I won’t go through the problems one by one, but feel free to ask in the comments about any that interest you.

Shall I push my luck as a problem-poser? Shall or shall not, I have.

My impetus, this time around, was a kind invitation by Travis Humble, the editor-in-chief of the new ACM Transactions on Quantum Computing, to contribute a perspective piece to that journal on the occasion of my ACM Prize. I agreed—but only on the condition that, rather than ponderously pontificate about the direction of the field, I could simply discuss a bunch of open problems that I wanted to see solved. The result is below. It’s coming soon to an arXiv near you, but Shtetl-Optimized readers get it first.

Open Problems Related to Quantum Query Complexity (11 pages, PDF)

by Scott Aaronson

Abstract: I offer a case that quantum query complexity still has loads of enticing and fundamental open problems—from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.

Some of the problems on my new hit-list are ones that I and others have flogged for years or even decades, but others, as far as I know, appear here for the first time. If your favorite quantum query complexity open problem, or a problem I’ve discussed in the past, is missing, that doesn’t mean that it’s been solved or is no longer interesting—it might mean I simply ran out of time or energy before I got to it.

Enjoy! And tell me what I missed or got wrong or has a trivial solution that I overlooked.

Exciting opportunities at Kabul University!

September 5th, 2021

Update (Sept. 6): Alright, as promised in this post, I’ve now matched a reader’s generosity by donating $2,000 to NARAL’s Avow fund, which is fighting for abortion rights for women in Texas. Woke people on Twitter, I invite you/youse/y’all to figure out some creative ways to condemn me for that.


Normally, early fall is the time when I’d use this blog to advertise positions in quantum information and theoretical computer science at the University of Texas at Austin, for prospective PhD students, postdocs, and faculty. This year, you might say, anyone trying to recruit academics to Texas has a … teensy bit of a PR problem. We already had PR problems, first over the “failure by design” of our electrical grid in the winter, second over Governor Abbott’s battle against local mask mandates, which has made Texas the second-most notoriously covid-friendly state after Florida.

Now, of course, Texas has effectively outlawed abortion—well, after the 6th week, which is before many women even realize they’re pregnant, and when the fetus is still the size of a grain of rice and looks like this.

There are no exceptions for rape or incest, and—this is the “novel” part—there’s a bounty system, with $10,000+ fines for anyone who helps in any way with an abortion, payable to anyone who snitches on them. Texas has openly defied Roe v. Wade and, for the first time in half a century, has gotten five Supreme Court justices (three appointed by Donald Trump) to go along with it. Roe v. Wade is de facto no longer the law of the United States.

With a 15-week cutoff, a right to abortion would still functionally exist. At 6 weeks, it no longer functionally exists.

And as for our recruiting at UT Austin … I fear we might as well now be trying to recruit colleagues to Kabul University. It’s like, imagine some department chair at Kabul U., this week, trying to woo a star female physicist from abroad: “Oh, don’t worry … you’ll get used to wearing a burqa in no time! And the ban on being alone with unrelated males is actually a plus for you; it just means you’ll be freed from onerous teaching and committee assignments. Best yet, I’ve received personal assurances from our local Taliban commander that you almost certainly won’t be stoned for your licentiousness and whoredom. Err … no offense, those were his words, not mine.”

For five years, my recruiting pitches for UT Austin have often involved stressing how Austin is a famously hip, tolerant, high-tech, educated city—a “blueberry in the tomato soup,” as Rick Perry put it—and how Texas itself might indeed turn blue any election cycle, given the explosive growth of its metropolitan population, and how the crazy state politics is unlikely to affect an Austinite’s personal life—at least, by noticeably more than the crazy national politics would affect their personal life. I can no longer make this pitch with a straight face, or certainly not to women.

Like, I’m lucky that none of the women in my close family have ever needed an abortion, and that if they did, it would be easy for them to travel out of Texas to get one. But having carried to term two healthy but difficult pregnancies, my wife Dana has often stressed to me how insane she finds the very idea of being forced by the government to go through with such an ordeal. If women considering moving to Texas feel likewise, I can’t argue with them. More than that: if Texas continues on what half the country sees as a journey back to the Middle Ages, with no opt-outs allowed for the residents of its left-leaning urban centers, Dana and I will not be able to remain here, and many of our friends won’t either.

So why aren’t we packing our bags already? Partly because the current situation is inherently, obviously unstable. SB8 can’t long remain the law of Texas while Roe v. Wade remains the law of the United States: one of them has to give. I confess to being confused about why some abortion provider in Texas, with funding from national pro-choice groups, hasn’t already broken the law, welcomed a lawsuit, and forced the courts to rule explicitly on whether Roe v. Wade still stands and why or why not, rather than gutting a core part of American jurisprudence literally under cover of night. I’m also confused about why some solid blue state, like Massachusetts or Hawaii, isn’t right now passing a law that would let any citizen sue any other for carrying a firearm—thereby forcing the five Supreme Hypocrites, in striking down that law, to admit that they don’t believe after all that state laws get to trample what the Supreme Court has held to be constitutional rights, merely by outsourcing the enforcement to random vigilantes.

My best guess is that Thomas, Alito, Gorsuch, Kavanaugh, and Barrett are already plotting to replace Roe by something much more restrictive, albeit probably not quite as shockingly draconian as Texas’s current ban on all abortions after six weeks, nor quite as breathtakingly insane as its bounty system for anyone who snitches about abortions. My best guess is that they saw last week’s ruling as a way to test the waters and soften the country up: if you’re going to rescind what multiple generations of Americans have grown up seeing as a fundamental right, best not to do it too suddenly. My best guess is that Democrats will respond by making abortion a central campaign issue in 2022 and 2024, and that given the public’s 58%-32% support for Roe, the Democrats will do pretty well with that—to the point where, like the proverbial dog that finally catches the car, Republicans might come to regret actually sinking their jaws into Roe, rather than just conspicuously chasing it down the street for half a century.

I have friends who are sincere, thoughtful pro-lifers. I admire, if nothing else, their principled dedication to a moral stance that regularly gets condemned in academia. But I’d also say to them: even if you think of abortion as murder, a solid majority of Americans don’t, and it’s hard to see a stable way of getting what you want that skips the step where you change those Americans’ minds. Indeed, there’s long been a pro-choice critique of Roe, which says that, by short-circuiting the political loosening of abortion restrictions that was already underway in the 70s, Roe fueled the growth of the radical right that’s now all but destroyed America. For Roe falsely convinced pro-lifers that all they needed to do was seize control of the Supreme Court, by any means fair or foul, when what they really needed to do was convince the public.

And, let’s be honest, convincing the public means convincing them to adopt a religious as opposed to secular framework for morality. (And not just any religious framework: Orthodox Jews, for example, while not exactly fans of abortion, are fine with it under many circumstances. In the Jewish view, so the old classic goes, the fetus attains full personhood only after graduating medical school.) Of the Americans who want abortion to be illegal in all or most cases, 94% are at least “fairly certain” that God exists, and 79% are “absolutely certain”—consistent with my experience of having met highly intelligent and articulate pro-lifers, but never secular ones. Modulo Lizardman’s Constant, virtually all pro-lifers have metaphysical commitments about God and the soul that presumably do some of the heavy lifting for them. If the case for a blanket abortion ban can be made in terms that are compelling to a secular, rationalist, tradeoffs-based morality, no one seems to have done it yet.

From the standpoint of secular moral philosophy, my own opinion is that no one has ever improved on the searching analysis of the abortion question that Carl Sagan and Ann Druyan published in 1990. After painstakingly laying out scientific facts, moral hypotheticals, and commonsense principles, Sagan and Druyan ultimately conclude that the right question to ask is when the fetus develops something that’s recognizably a human brain, processing thoughts and emotions. In practice, that probably means drawing a hard line at the end of the second trimester. Coincidentally, that’s almost exactly where Roe v. Wade drew the line, but Sagan and Druyan’s reasoning is completely different: they reject Roe‘s criterion of viability outside the womb, as both morally irrelevant and contingent on medical technology.

Reasonable people could disagree with the details of Sagan and Druyan’s analysis. But if we agree that

(1) a sperm and unfertizilied egg have a “personhood” of 0,

(2) a newborn baby has a “personhood” of 1, and

(3) whatever “personhood” is, it’s somehow tied to the gradual growth of neurons and dendrites in the physical universe, rather than to a mystical and discontinuous moment of ensoulment,

… then by the intermediate value theorem, for all p∈(0,1), there’s going to be some stage of fetal development where the fetus has a personhood of p. Which means that we’re going to be drawing a debatable line, making a compromise, just like the majority did in Roe. To me, one of the strangest aspects of the abortion debate is how both sides came to view Roe v. Wade as the “pro-choice maximalist position,” forgetting how it itself was an attempted compromise between conflicting moral intuitions.

Another strange aspect of the debate is how the most visible representatives of both sides seem to have given up, decades ago, on actually arguing for their positions. Maybe it’s because people simply threw up their hands in futility; or because all the ground had been covered with nothing left to say; or because the debate was so obviously entangled with religion, and we have a polite norm of not arguing about religion; or because both positions hardened into tribal identity markers, to be displayed rather than defended. Whatever the reason, though, by the mid-90s everything became about border skirmishes one or two steps removed from the actual question: e.g., if the woman is under 18, should her parents be notified? should she be shown pictures of her fetus and given a 24-hour waiting period in hopes she’ll reconsider? is this judicial nominee hiding his or her anti-abortion views?

Now that Texas and five Supreme Court justices have launched a frontal assault on Roe—it’s impossible to see it any other way—it seems to me that the long armistice is over. The pro-life side will have to make the case for its moral framework to a populace that will suddenly be paying more attention—and that includes tens of millions of Americans who hadn’t even been born the last time mainstream figures debated abortion head-on. The pro-choice side can then counterargue for its moral framework. If any pro-lifers are raring for this fight, I’ll point out that one of the most dramatic demographic changes, since the last time abortion was a “hot war,” has been a doubling in the percentage of Americans who are atheist, agnostic, or religiously unaffiliated.

Let me close this post with two things.

Firstly, if anyone is still unclear where I stand: over the next week, I will match Shtetl-Optimized readers’ donations to NARAL up to $2,000. If you’d like to participate, just leave a comment with the amount you donated. If I’ve argued with certain strains of feminism on this blog, that gives me all the more obligation to support the strains that I regard as fundamentally correct.

Secondly, come join us at the University of Kab … I mean Texas at Austin! For grad students, see here; for faculty, see here; for postdocs, email me a CV and recent publications and have two reference letters sent to me by December 31st. In the US, the east coast is now being ravaged beyond recognition by hurricanes and the west coast by wildfires. Here in Texas, all we have to deal with is extreme heat, a failing electrical grid, runaway covid, and now the ban on abortion. Hook ’em Hadamards!

“The Chair”: A Straussian interpretation

August 31st, 2021

[Warning: spoilers follow!]

Last week Dana and I watched the full first season of The Chair, the Netflix drama that stars Sandra Oh as Ji-Yoon Kim, incoming chairwoman of the English department at the fictional Pembroke University. As the rave reviews promised, I found the show to be brilliantly written and acted. At times, The Chair made me think about that other academia-centered sitcom, The Big Bang Theory, which I freely confess I also enjoyed. But The Chair is much more highbrow (and more political), it’s about the humanities rather than STEM, and it’s mostly about academics who are older than the ones in Big Bang, both biologically and professionally.

I wouldn’t call The Chair “realistic”: the sets, stuffed with imposing bookshelves, paintings of great scholars, etc., look like how a TV producer might imagine university buildings, rather than the relatively humdrum reality. But in less than three hours, the show tackles a staggering number of issues that will be recognizable and relevant to anyone in academia: cratering enrollments, a narrow-minded cost-cutting dean, a lack of free time and a desperate search for childcare, a tenure case that turns into a retention case, a woke scandal (about which more later), a faculty revolt against Ji-Yoon culminating in a vote of no confidence, and much more. There’s also an elaborate side plot involving the actor (and real-life former literary scholar) David Duchovny, who portrays himself, being invited to lecture at Pembroke, which is not the sort of thing most academics have experience with, but which I suppose many viewers will enjoy.

The show is written at a high enough level that its stumbles are those of a daring acrobat. In the main narrative arc of the first season, the writers set themselves an absurdly ambitious (and, I think, laudable) goal: namely, to dramatize a conflict between a free-spirited professor, and woke students trying to cancel that professor for a classroom “microaggression,” in a way that fully empathizes with both sides. I don’t know if the show actually succeeds at this, but that’s partly because I don’t know if it’s possible to succeed.

To start with some background: in Pembroke’s English department, there are old, traditionalist white males, who give lectures extolling the Great Men of Literature, and who apparently still wield considerable power. Meanwhile, critical theorists are presented as young, exciting upstarts bravely challenging the status quo. People with recent experience of English departments should correct me if I’m wrong, but my sense is that this is pretty anachronistic—i.e., that the last powerful traditionalists in humanities departments were routed by the 80s or 90s at the latest, so that students in the Twitter-and-smartphone era (when The Chair is set) would be about as likely to encounter them as they would professors sitting around in charcoal suits smoking pipes.

There were also some of what felt to me like … intersectional oversights? Ji-Yoon, being Korean-American, is repeatedly approached by Black female students and faculty as a “fellow woman of color,” with whom they can commiserate about the entrenched power of the department’s white males. The show never examines how woke discourse has increasingly reclassified Asian-Americans as “white-adjacent”—as, for example, in the battles over gifted and magnet programs or admissions to Harvard. Likewise, woke students are shown standing arm-in-arm with Pembroke’s Jewish community, to denounce (what we in the audience know to be) a phantom antisemitic incident. Left unexplored is how, in the modern woke hierarchy, Jews have become just another kind of privileged white person (worse, of course, if they have ties to Israel).

This brings me to the first season’s central conflict, which revolves around Bill Dobson, a handsome middle-aged white male professor who’s revered as the department’s greatest genius on the basis of his earlier work, but who, after the death of his wife, is now washed-up, flippant, and frequently drunk or high. In one class session, while lecturing about intellectuals who found the strength to resist fascism despite their own nihilistic impulses, Bill makes a Nazi salute and shouts “Heil Hitler!,” as a theatrical reminder to the students about the enormity of what those intellectuals were fighting. Alas, a woke student captures that moment on their smartphone camera and shares it on social media. The clip of Bill making the Heil salute goes viral, shorn of all exculpatory context. Soon, crowds of students are waving placards and screaming “No Nazis at Pembroke!” outside the English building. In a desperate effort to make his PR crisis go away, the dean initiates termination proceedings against Bill—the principles of academic freedom and even Bill’s tenure be damned. Ji-Yoon, of course, as Bill’s chair, is caught smack in the middle of this. It’s complicated even further by Ji-Yoon’s and Bill’s romantic feelings for each other, and further still by Bill’s role as the babysitter of Ji-Yoon’s adopted daughter.

As all of this unfolds, the show seems immensely interested in pinning the blame on Bill’s “tragic flaws,” minor though they seemed to me—mostly just pride and unseriousness. (E.g., trying to lampoon the absurd charge of Nazism, Bill offhandedly mentions that he’s always wanted to visit Hitler’s mountain retreat, and on another occasion belts out “Springtime for Hitler” from The Producers.) The woke students, by contrast, are portrayed as earnest, understandably upset, and legitimately terrified about hate crimes on campus. If they, too, have opportunistic motives to attack Bill, the show never examines them.

In one sentence, then, here’s my beef with The Chair: its script portrays a mob, step by step, destroying an innocent man’s life over nothing, and yet it wants me to feel the mob’s pain, and be disappointed in its victim for mulishly insisting on his innocence (even though he is, in fact, innocent).

With real-life woke controversies, there often lingers the question of whether the accused might really be a racist, fascist, sexual predator, or whatever else, adequate proof or no. What’s different here is that we know that Bill Dobson is none of those things, we know he’s decent to his core, because the writers have painstakingly shown us that. And yet, in a weird narrative pretzel, we’re nevertheless supposed to be mad at him, and to sympathize with the campaign to cancel him.

A casual perusal of other reviews of The Chair told me that these reactions were far from universal. Here, for example, is what one viewer wrote:

I can appreciate that this is probably close to the reality that most women/of color experience in higher education. I enjoyed watching the scenes with Joan and Yaz [two female professors] the most but the rest was a drag. I couldn’t understand why Ji-Yoon was into Bill, or why anyone was into Bill. I found him to be an insufferable man-baby. That is such a turn off. So she’d put him straight but then still be pining for him. He wreaked [sic] of entitled, white male, tenured privilege and never showed any contrition for his actions or even awareness of their impact. i’m so tired of the “brilliant _” being used to justify coddling someone. And for the rest of the stuffy old patriarchal farts– boot them out! They weren’t good teachers and weren’t able to meet the needs of today’s students.

I asked myself: did this person watch the same show? It’s like, the script couldn’t possibly have been clearer about Bill’s character, the fact that he’s the polar opposite of the woke students’ mental construct. And yet, if the show had drawn an unambiguous corollary from Bill’s goodness—namely, that the effort to cancel him is a moral travesty—then The Chair itself might have been denounced as conservative (or at least classical liberal) propaganda, and those who’d otherwise form its core viewership wouldn’t have watched.

So, if I were a literary critic like the ones on the show, I might argue that The Chair begs for a Straussian interpretation. Sure, there’s an “overt” reading, wherein Bill Dobson is done in by his own hubris, or wherein it’s a comedy of errors with no one to blame. But then there’s also an “esoteric” reading, wherein Bill is the victim of an extremely specific modern-day collective insanity, one that future generations might look back on with little more ambivalence than we look back on McCarthyism. The writers of The Chair might hint at this latter reading, through their sympathetic portrayal of Bill and the obviousness of the injustice done to him, but they can never make it too explicit, because of the political and cultural constraints under which they themselves operate.

Under this theory, it presumably falls to those slightly outside the world portrayed in The Chair—like, let’s imagine, a theoretical computer science blogger who himself was denounced for woke heresies to the point where he has little more to lose in that direction—to make the esoteric reading explicit. Unless and until, of course, a second season comes along to undermine that reading entirely.

Please cheer me up

August 27th, 2021


Update: Come to think of it, let’s circle back to the thing about kids under 13 getting banned from taking the SAT, as a ridiculous unintended consequence of some federal regulation. I wonder whether this is a campaign this blog could spearhead that would have an actual chance of making a positive difference in the world (!!), rather than just giving me space to express myself, to vent my impotent rage at the tragic failures of our civilization and the blankfaces who sleep soundly despite knowing that they caused those failures.  What if, like, a whole bunch of us wrote to the College Board, or whatever federal agency enforces the regulation that the College Board is worried about, and we asked them whether a solution might be found in which parents gave permission on the web form for their under-13s to take the SAT, given how memorable this opportunity was for many of us, how it was a nerd rite of passage, and how surely none of us have any wish to deny that opportunity to the next generation, so let’s work together to solve this?


I’m depressed that, all over the world, the values of the Enlightenment are humiliated and in retreat, while the values of the Taliban are triumphant. The literal Taliban of course, but also a thousand mini-Talibans of every flavor, united in their ideological certainty.

I’m depressed that now and for the future, the image of the United States before the world—deservedly so—is one of desperate Afghans plunging to their deaths from the last airplanes out of Kabul. I’m depressed that, while this historic calamity was set in motion by Donald Trump, the president who bears direct, immediate moral responsibility for it is the one I voted for. And knowing what I know now, I’d still have voted for him—but with an ashen face.

I’m depressed that, on social media, the same people who seven years ago floridly denounced me, because, while explaining how as a young person I overcame the urge to suicide and finally achieved some semblance of a normal life, I made a passing reference to a vanished culture of arranged marriages, to which I seemed better-adapted than to the world of today—these very same people are the ones sagely resigned to millions of Afghan women and girls actually forced into unwanted marriages, tortured, and raped, who explain that there’s nothing the US can or should do about this, even that it was folly to imagine we could impose parochial Western values, like women’s rights, on a culture that doesn’t want them. These are the people who saw fit to lecture me on my feminist failings.

I’m depressed that there’s an exceedingly good chance that both of my kids will get covid, as they’ve returned to school and preschool in Austin, TX, where the Delta variant is raging out of control, new reports of cases among the kids’ schoolmates come almost every day, Daniel has been quarantined at home for the past week because of one such case, there’s no vaccination mandate (and a looming battle over mask mandates), and—crucially, tragically, incredibly—the FDA has not only slow-walked approval of covid vaccines for children under 12, but has pushed back the approval even further than it previously planned, ignoring unprecedented public objections from the American Academy of Pediatrics. The FDA blankfaces have done this in spite of the reality, obvious to anyone with eyes and a brain, that they’re thereby consigning thousands of children to their deaths, that whatever ultra-rare risks the vaccine poses to children are infinitesimal compared to the overwhelming benefit.

Since I worry that I wasn’t clear enough, how about this: in a just world, the FDA in its current form would be dismantled, and all those who needlessly delayed the delivery of covid vaccines to children would be tried for manslaughter [while I still think the case for authorizing covid vaccines for kids right now is overwhelmingly clear, I hereby retract this particular remark, which was based on a factor 5-10 overestimate of the covid mortality risk for kids—for more, see this comment]. The blankfaces have already killed more people through pointlessly delaying the approval of covid vaccines than their agency could plausibly have saved through its entire history: do they need to take the children as well? As far as I’m concerned, those who defend the status quo—those who meet the on-the-ground reality of overflowing pediatric hospitals with obfuscatory words about procedures and best practices and the need for yet more data—are no better either morally or intellectually than the anti-vaxx conspiracy theorists, their rightly-reviled cousins.

As icing on the cake, I’m depressed that the College Board is no longer administering the SAT to children under 13, apparently because of federal regulations—-which means that Johns Hopkins CTY’s famed Study of Exceptional Talent, a program that made a big difference in my life three decades ago, has been suspended indefinitely. Imagine being a nerdy 11-year-old in 2021: no more tracking, no more gifted programs, no more magnet schools, no more acceleration, no getting vaccinated against deadly disease (!!), … oh, and if perchance you felt the urge to take the SAT, just to prove that you could outscore the grownups who decided to impose all this on you, then no, you’re no longer allowed to do that either.

The one bright spot in the endlessly bleak picture is that Daniel, my 4-year-old son, now plays a pretty mean chess game, if not quite at the level of Beth Harmon. Having just learned the rules a few months ago, Daniel now gives me and Dana (admittedly, no one would mistake either of us for Magnus Carlsen) extremely competitive matches; just yesterday he beat several adults in a park. Daniel has come to spend much of his free time (and now that he’s quarantined, he has a lot) playing chess against his iPad and watching chess videos. To be clear, he has very little emotional maturity even for a 4-year-old, and unlike me at the same age, he has no overwhelming passion for numbers or counting, but with chess I’ve finally found a winner. Now I just need to hope that they don’t ban chess-playing for children under 13.

So that’s it, it’s off my chest. Commenters: what else have you got that might cheer me up?

Stephen Wiesner (1942-2021)

August 13th, 2021

Photo credit: Lev Vaidman

These have not been an auspicious few weeks for Jewish-American-born theoretical physicists named Steve who made epochal contributions to human knowledge in the late 1960s, and who I had the privilege to get to know a bit when they were old.

This morning, my friend and colleague Or Sattath brought me the terrible news that Stephen Wiesner has passed away in Israel. [Because people have asked: I’ve now also heard directly from Wiesner’s daughter Sarah.]

Decades ago, Wiesner left academia, embraced Orthodox Judaism, moved from the US to Israel, and took up work there as a construction laborer—believing (or so he told me) that manual labor was good for the soul. In the late 1960s, however, Wiesner was still a graduate student in physics at Columbia University, when he wrote Conjugate Coding: arguably the foundational document of the entire field of quantum information science. Famously, this paper was so far ahead of its time that it was rejected over and over from journals, taking nearly 15 years to get published. (Fascinatingly, Gilles Brassard tells me that this isn’t true: it was rejected once, from IEEE Transactions on Information Theory, and then Wiesner simply shelved it.) When it finally appeared, in 1983, it was in SIGACT News—a venue that I know and love, where I’ve published too, but that’s more like the house newsletter for theoretical computer scientists than an academic journal.

But it didn’t matter. By the early 1980s, Wiesner’s ideas had been successfully communicated to Charlie Bennett and Gilles Brassard, who refashioned them into the first scheme for quantum key distribution—what we now call BB84. Even as Bennett and Brassard received scientific acclaim for the invention of quantum cryptography—including, a few years ago, the Wolf Prize (often considered second only to the Nobel Prize), at a ceremony in the Knesset in Jerusalem that I attended—the two B’s were always careful to acknowledge their massive intellectual debt to Steve Wiesner.


Let me explain what Wiesner does in the Conjugate Coding paper. As far as I know, this is the first paper ever to propose that quantum information—what Wiesner called “polarized light” or “spin-1/2 particles” but we now simply call qubits—works differently than classical bits, in ways that could actually be useful for achieving cryptographic tasks that are impossible in a classical world. What could enable these cryptographic applications, wrote Wiesner, is the fact that there’s no physical means for an attacker or eavesdropper to copy an unknown qubit, to produce a second qubit in the same quantum state. This observation—now called the No-Cloning Theorem—would only be named and published in 1982, but Wiesner treats it in his late-1960s manuscript as just obvious background.

Wiesner went further than these general ideas, though, to propose an explicit scheme for quantum money that would be physically impossible to counterfeit—a scheme that’s still of enormous interest half a century later (I teach it every year in my undergraduate course). In what we now call the Wiesner money scheme, a central bank prints “quantum bills,” each of which contains a classical serial number as well as a long string of qubits. Each qubit is prepared in one of four possible quantum states:

  • |0⟩,
  • |1⟩,
  • |+⟩ = (|0⟩+|1⟩)/√2, or
  • |-⟩ = (|0⟩-|1⟩)/√2.

The bank, in a central database, stores the serial number of every bill in circulation, as well as the preparation instructions for each of the bill’s qubits. If you want to verify a bill as genuine—this, as Wiesner knew, is the big drawback—you have to bring it back to the bank. The bank, using its secret knowledge of how each qubit was prepared, measures each qubit in the appropriate basis—the {|0⟩,|1⟩} basis for |0⟩ or |1⟩ qubits, the {|+⟩,|-⟩} basis for |+⟩ or |-⟩ qubits—and checks that it gets the expected outcomes. If even one qubit yields the wrong outcome, the bill is rejected as counterfeit.

Now consider the situation of a counterfeiter, who holds a quantum bill but lacks access to the bank’s secret database. When the counterfeiter tries to copy the bill, they won’t know the right basis in which to measure each qubit—and if they make the wrong choice, then it’s not only that they fail to make a copy; it’s that the measurement destroys even the original copy! For example, measuring a |+⟩ or |-⟩ qubit in the {|0⟩,|1⟩} basis will randomly collapse the qubit to either |0⟩ or |1⟩—so that, when the bank later measures the same qubit in the correct {|+⟩,|-⟩} basis, it will see the wrong outcome, and realize that the bill has been compromised, with 1/2 probability (with the probability increasing to nearly 1 as we repeat across hundreds or thousands of qubits).

Admittedly, the handwavy argument above, which Wiesner offered, is far from a security proof by cryptographers’ standards. In 2011, I pointed that out on StackExchange. My post, I’m happy to say, spurred Molina, Vidick, and Watrous to write a beautiful 2012 paper, where they rigorously proved for the first time that in Wiesner’s money scheme, no counterfeiter consistent with the laws of quantum mechanics can turn a single n-qubit bill into two bills that both pass the bank’s verification with success probability greater than (3/4)n (and this is tight). But the intuition was already clear enough to Wiesner in the 1960s.

In 2003—when I was already a PhD student in quantum information, but incredibly, had never heard of Stephen Wiesner or his role in founding my field—I rediscovered the idea of quantum states |ψ⟩ that you could store, measure, and feed into a quantum computer, but that would be usefully uncopyable. (My main interest was in whether you could create “unpiratable quantum software programs.”) Only in 2006, at the University of Waterloo, did Michele Mosca and his students make the connection for me to quantum money, Stephen Wiesner, and his Conjugate Coding paper, which I then read with amazement—along with a comparably amazing followup work by Bennett, Brassard, Breidbart, and Wiesner.

But it was clear that there was still a great deal to do. Besides unpiratable software, Wiesner and his collaborators had lacked the tools in the early 1980s seriously to tackle the problem of secure quantum money that anybody could verify, not only the bank that had created the money. I realized that, if such a thing was possible at all, then just like unpiratable software, it would require cryptographic hardness assumptions, a restriction to polynomial-time counterfeiters, and (hence) ideas from quantum computational complexity. The No-Cloning Theorem couldn’t do the job on its own.

That realization led to my 2009 paper Quantum Copy-Protection and Quantum Money, and from there, to the “modern renaissance” of Wiesner’s old idea of quantum money, with well over a hundred papers (e.g., my 2012 paper with Paul Christiano, Farhi et al.’s quantum state restoration paper, their quantum money from knots paper, Mark Zhandry’s 2017 quantum lightning paper, Dmitry Gavinsky’s improvement of Wiesner’s scheme wherein the money is verified by classical communication with the bank, Broduch et al.’s adaptive attack on Wiesner’s original scheme, my shadow tomography paper proving the necessity for the bank to keep a giant database in information-theoretic quantum money schemes like Wiesner’s, Daniel Kane’s strange scheme based on modular forms…). The purpose of many of these papers was either to break the quantum money schemes proposed in previous papers, or to patch the schemes that were previously broken.

After all this back-and-forth, spanning more than a decade, I’d say that Wiesner’s old idea of quantum money is now in good enough theoretical shape that the main obstacle to its practical realization is merely the “engineering difficulty”—namely, how to get the qubits in a bill, sitting in your pocket or whatever, to maintain their quantum coherence for more than a few nanoseconds! (Or possibly a few hours, if you’re willing to schlep a cryogenic freezer everywhere you go.) It’s precisely because quantum key distribution doesn’t have this storage problem—because there the qubits are simply sent across a channel and then immediately measured on arrival—that QKD is actually practical today, although the market for it has proven to be extremely limited so far.

In the meantime, while the world waits for the quantum error-correction that could keep qubits alive indefinitely, there’s Bitcoin. The latter perversely illustrates just how immense the demand for quantum money might someday be: the staggering lengths to which people will go, diverting the electricity to power whole nations into mining rigs, to get around our current inability to realize Wiesner’s elegant quantum-mechanical solution to the same problem. When I first learned about Bitcoin, shortly after its invention, it was in the context of: “here’s something I’d better bring up in my lectures on quantum money, in order to explain how much better WiesnerCoin could eventually be, when it’s the year 2200 or whatever and we all have quantum computers wired up by a quantum Internet!” It never occurred to me that I should forget about the year 2200, liquidate my life savings, and immediately buy up all the Bitcoin I could. [Added: I’ve since learned that Wiesner’s daughter Sarah is a professional in the Bitcoin space.]


Photo credit: Or Sattath

In his decades as a construction laborer, Wiesner had (as far as I know) no Internet presence; many of my colleagues didn’t even realize he was still alive. Even then, though, Wiesner never turned his back so far on his previous life, his academic life, that the quantum information faculty at Hebrew University in Jerusalem couldn’t entice him to participate in some seminars there. Those seminars are where I had the privilege to meet and talk to him several times over the last decade. He was thoughtful and kind, listening with interest as I told him how I and others were trying to take quantum money into the modern era by making it publicly verifiable.

I also vividly remember a conversation in 2013 where Steve shared his fears about the American physics establishment and military-industrial complex, and passionately urged me to

  1. quit academia and get a “real job,” and
  2. flee the US immediately and move my family to Israel, because of a wave of fascism and antisemitism that was about to sweep the US, just like with Germany in the 1930s.

I politely nodded along, pointing out that my Israeli wife and I had considered living in Israel but the job opportunities were better in US, silently wondering when Steve had gone completely off his rocker. Today, Steve’s urgent warning about an impending fascist takeover of the US seems … uh, slightly less crazy than in 2013? Maybe, just like with quantum money, Wiesner was simply too far ahead of his time to sound sane.

Wiesner also talked to me about his father, Jerome Wiesner, who was a legendary president of MIT—still spoken about in reverent tones when I taught there—as well as the chief science advisor to John F. Kennedy. One of JFK’s most famous decisions was to override the elder Wiesner’s fervent opposition to sending humans to the moon (Wiesner thought it a waste of money, as robots could do the same science for vastly cheaper).

While I don’t know all the details (I hope someone someday researches it and writes a book), Steve Wiesner made it clear to me that he did not get along with his famous father at all—in fact they became estranged. Steve told me that his embrace of Orthodox Judaism was, at least in part, a reaction against everything his father had stood for, including militant scientific atheism. I suppose that in the 1960s, millions of young Americans defied their parents via sex, drugs, and acoustic guitar; only a tiny number did so by donning tzitzit and moving to Israel to pray and toil with their hands. The two groups of rebels did, however, share a tendency to grow long beards.

Wiesner’s unique, remarkable, uncloneable life trajectory raises the question: who are the young Stephen Wiesners of our time? Will we be faster to recognize their foresight than Wiesner’s contemporaries were to recognize his?


Feel free to share any other memories of Stephen Wiesner or his influence in the comments.


Update (Aug. 14): See also Or Sattath’s memorial post, which (among other things) points out something that my narrative missed: namely, besides quantum money, Wiesner also invented superdense coding in 1970, although he and Bennett only published the idea 22 years later (!).

And I have more photos! Here’s Wiesner with an invention of his and another photo (thanks to his daughter Sarah). Here’s another photo from 1970 and Charlie Bennett’s handwritten notes (!) after first meeting Wiesner in 1970 (thanks to Charlie Bennett).

Another Update: Stephen’s daughter Sarah gave me the following fascinating information to share.

In the 70’s he lived in California where he worked in various Silicon Valley startups while also working weekends as part of a produce (fruits and vegetables) distribution co-op. During this time he became devoted to the ideas of solar energy, clean energy and space migration and exploration. He also became interested in Judaism. He truly wanted to help and make our world more peaceful and safe with his focus being on clean energy and branching out into space. He also believed that instead of fighting over the temple mount in Jerusalem, the Third Temple should be built in outer-space or in a structure above the original spot, an idea he tried to promote to prevent wars over land.

Yet more mistakes in papers

August 10th, 2021

Amazing Update (Aug. 19): My former PhD student Daniel Grier tells me that he, Sergey Bravyi, and David Gosset have an arXiv preprint, from February, where they give a corrected proof of my and Andris Ambainis’s claim that any k-query quantum algorithm can be simulated by an O (N1-1/2k)-query classical randomized algorithm (albeit, not of our stronger statement, about a randomized algorithm to estimate any bounded low-degree real polynomial). The reason I hadn’t known about this is that they don’t mention it in the abstract of their paper (!!). But it’s right there in Theorem 5.


In my last post, I came down pretty hard on the blankfaces: people who relish their power to persist in easily-correctable errors, to the detriment of those subject to their authority. The sad truth, though, is that I don’t obviously do better than your average blankface in my ability to resist falsehoods on early encounter with them. As one of many examples that readers of this blog might know, I didn’t think covid seemed like a big deal in early February 2020—although by mid-to-late February 2020, I’d repented of my doofosity. If I have any tool with which to unblank my face, then it’s only my extreme self-consciousness when confronted with evidence of my own stupidities—the way I’ve trained myself over decades in science to see error-correction as a or even the fundamental virtue.

Which brings me to today’s post. Continuing what’s become a Shtetl-Optimized tradition—see here from 2014, here from 2016, here from 2017—I’m going to fess up to two serious mistakes in research papers on which I was a coauthor.


In 2015, Andris Ambainis and I had a STOC paper entitled Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. We gave two main results there:

  1. A Ω((√N)/log(N)) lower bound on the randomized query complexity of my “Forrelation” problem, which was known to be solvable with only a single quantum query.
  2. A proposed way to take any k-query quantum algorithm that queries an N-bit string, and simulate it using only O(N1-1/2k) classical randomized queries.

Later, Bansal and Sinha and independently Sherstov, Storozhenko, and Wu showed that a k-query generalization of Forrelation, which I’d also defined, requires ~Ω(N1-1/2k) classical randomized queries, in line with my and Andris’s conjecture that k-fold Forrelation optimally separates quantum and classical query complexities.

A couple months ago, alas, my former grad school officemate Andrej Bogdanov, along with Tsun Ming Cheung and Krishnamoorthy Dinesh, emailed me and Andris to say that they’d discovered an error in result 2 of our paper (result 1, along with the Bansal-Sinha and Sherstov-Storozhenko-Wu extensions of it, remained fine). So, adding our own names, we’ve now posted a preprint on ECCC that explains the error, while also showing how to recover our result for the special case k=1: that is, any 1-query quantum algorithm really can be simulated using only O(√N) classical randomized queries.

Read the preprint if you really want to know the details of the error, but to summarize it in my words: Andris and I used a trick that we called “variable-splitting” to handle variables that have way more influence than average on the algorithm’s acceptance probability. Alas, variable-splitting fails to take care of a situation where there are a bunch of variables that are non-influential individually, but that on some unusual input string, can “conspire” in such a way that their signs all line up and their contribution overwhelms those from the other variables. A single mistaken inequality fooled us into thinking such cases were handled, but an explicit counterexample makes the issue obvious.

I still conjecture that my original guess was right: that is, I conjecture that any problem solvable with k quantum queries is solvable with O(N1-1/2k) classical randomized queries, so that k-fold Forrelation is the extremal example, and so that no problem has constant quantum query complexity but linear randomized query complexity. More strongly, I reiterate the conjecture that any bounded degree-d real polynomial, p:{0,1}N→[0,1], can be approximated by querying only O(N1-1/d) input bits drawn from some suitable distribution. But proving these conjectures, if they’re true, will require a new algorithmic idea.


Now for the second mea culpa. Earlier this year, my student Sabee Grewal and I posted a short preprint on the arXiv entitled Efficient Learning of Non-Interacting Fermion Distributions. In it, we claimed to give a classical algorithm for reconstructing any “free fermionic state” |ψ⟩—that is, a state of n identical fermionic particles, like electrons, each occupying one of m>n possible modes, that can be produced using only “fermionic beamsplitters” and no interaction terms—and for doing so in polynomial time and using a polynomial number of samples (i.e., measurements of where all the fermions are, given a copy of |ψ⟩). Alas, after trying to reply to confused comments from readers and reviewers (albeit, none of them exactly putting their finger on the problem), Sabee and I were able to figure out that we’d done no such thing.

Let me explain the error, since it’s actually really interesting. In our underlying problem, we’re trying to find a collection of unit vectors, call them |v1⟩,…,|vm⟩, in Cn. Here, again, n is the number of fermions and m>n is the number of modes. By measuring the “2-mode correlations” (i.e., the probability of finding a fermion in both mode i and mode j), we can figure out the approximate value of |⟨vi|vj⟩|—i.e., the absolute value of the inner product—for any i≠j. From that information, we want to recover |v1⟩,…,|vm⟩ themselves—or rather, their relative configuration in n-dimensional space, isometries being irrelevant.

It seemed to me and Sabee that, if we knew ⟨vi|vj⟩ for all i≠j, then we’d get linear equations that iteratively constrained each |vj⟩ in terms of ⟨vi|vj⟩ for j<i, so all we’d need to do is solve those linear systems, and then (crucially, and this was the main work we did) show that the solution would be robust with respect to small errors in our estimates of each ⟨vi|vj⟩. It seemed further to us that, while it was true that the measurements only revealed |⟨vi|vj⟩| rather than ⟨vi|vj⟩ itself, the “phase information” in ⟨vi|vj⟩ was manifestly irrelevant, as it in any case depended on the irrelevant global phases of |vi⟩ and |vj⟩ themselves.

Alas, it turns out that the phase information does matter. As an example, suppose I told you only the following about three unit vectors |u⟩,|v⟩,|w⟩ in R3:

|⟨u|v⟩| = |⟨u|w⟩| = |⟨v|w⟩| = 1/2.

Have I thereby determined these vectors up to isometry? Nope! In one class of solution, all three vectors belong to the same plane, like so:

|u⟩=(1,0,0),
|v⟩=(1/2,(√3)/2,0),
|w⟩=(-1/2,(√3)/2,0).

In a completely different class of solution, the three vectors don’t belong to the same plane, and instead look like three edges of a tetrahedron meeting at a vertex:

|u⟩=(1,0,0),
|v⟩=(1/2,(√3)/2,0),
|w⟩=(1/2,1/(2√3),√(2/3)).

These solutions correspond to different sign choices for |⟨u|v⟩|, |⟨u|w⟩|, and |⟨v|w⟩|—choices that collectively matter, even though each of them is individually irrelevant.

It follows that, even in the special case where the vectors are all real, the 2-mode correlations are not enough information to determine the vectors’ relative positions. (Well, it takes some more work to convert this to a counterexample that could actually arise in the fermion problem, but that work can be done.) And alas, the situation gets even gnarlier when, as for us, the vectors can be complex.

Any possible algorithm for our problem will have to solve a system of nonlinear equations (albeit, a massively overconstrained system that’s guaranteed to have a solution), and it will have to use 3-mode correlations (i.e., statistics of triples of fermions), and quite possibly 4-mode correlations and above.

But now comes the good news! Googling revealed that, for reasons having nothing to do with fermions or quantum physics, problems extremely close to ours had already been studied in classical machine learning. The key term here is “Determinantal Point Processes” (DPPs). A DPP is a model where you specify an m×m matrix A (typically symmetric or Hermitian), and then the probabilities of various events are given by the determinants of various principal minors of A. Which is precisely what happens with fermions! In terms of the vectors |v1⟩,…,|vm⟩ that I was talking about before, to make this connection we simply let A be the m×m covariance matrix, whose (i,j) entry equals ⟨vi|vj⟩.

I first learned of this remarkable correspondence between fermions and DPPs a decade ago, from a talk on DPPs that Ben Taskar gave at MIT. Immediately after the talk, I made a mental note that Taskar was a rising star in theoretical machine learning, and that his work would probably be relevant to me in the future. While researching this summer, I was devastated to learn that Taskar died of heart failure in 2013, in his mid-30s and only a couple of years after I’d heard him speak.

The most relevant paper for me and Sabee was called An Efficient Algorithm for the Symmetric Principal Minor Assignment Problem, by Rising, Kulesza, and Taskar. Using a combinatorial algorithm based on minimum spanning trees and chordless cycles, this paper nearly solves our problem, except for two minor details:

  1. It doesn’t do an error analysis, and
  2. It considers complex symmetric matrices, whereas our matrix A is Hermitian (i.e., it equals its conjugate transpose, not its transpose).

So I decided to email Alex Kulezsa, one of Taskar’s surviving collaborators who’s now a research scientist at Google NYC, to ask his thoughts about the Hermitian case. Alex kindly replied that they’d been meaning to study that case—a reviewer had even asked about it!—but they’d ran into difficulties and didn’t know what it was good for. I asked Alex whether he’d like to join forces with me and Sabee in tackling the Hermitian case, which (I told him) was enormously relevant in quantum physics. To my surprise and delight, Alex agreed.

So we’ve been working on the problem together, making progress, and I’m optimistic that we’ll have some nice result. By using the 3-mode correlations, at least “generically” we can recover the entries of the matrix A up to complex conjugation, but further ideas will be needed to resolve the complex conjugation ambiguity, to whatever extent it actually matters.

In short: on the negative side, there’s much more to the problem of learning a fermionic state than we’d realized. But on the positive side, there’s much more to the problem than we’d realized! As with the simulation of k-query quantum algorithms, my coauthors and I would welcome any ideas. And I apologize to anyone who was misled by our premature (and hereby retracted) claims.


Update (Aug. 11): Here’s a third bonus retraction, which I thank my colleague Mark Wilde for bringing to my attention. Way back in 2005, in my NP-complete Problems and Physical Reality survey article, I “left it as an exercise for the reader” to prove that BQPCTC, or quantum polynomial time augmented with Deutschian closed timelike curves, is contained in a complexity class called SQG (Short Quantum Games). While it turns out to be true that BQPCTC ⊆ SQG—as follows from my and Watrous’s 2008 result that BQPCTC = PSPACE, combined with Gutoski and Wu’s 2010 result that SQG = PSPACE—it’s not something for which I could possibly have had a correct proof back in 2005. I.e., it was a harder exercise than I’d intended!

On blankfaces

August 2nd, 2021

For years, I’ve had a private term I’ve used with my family. To give a few examples of its use:

No, I never applied for that grant. I spent two hours struggling to log in to a web portal designed by the world’s top blankfaces until I finally gave up in despair.

No, I paid for that whole lecture trip out of pocket; I never got the reimbursement they promised. Their blankface administrator just kept sending me back the form, demanding more and more convoluted bank details, until I finally got the hint and dropped it.

No, my daughter Lily isn’t allowed in the swimming pool there. She easily passed their swim test last year, but this year the blankface lifeguard made up a new rule on the spot that she needs to retake the test, so Lily took it again and passed even more easily, but then the lifeguard said she didn’t like the stroke Lily used, so she failed her and didn’t let her retake it. I complained to their blankface athletic director, who launched an ‘investigation.’ The outcome of the ‘investigation’ was that, regardless of the ground truth about how well Lily can swim, their blankface lifeguard said she’s not allowed in the pool, so being blankfaces themselves, they’re going to stand with the lifeguard.

Yeah, the kids spend the entire day indoors, breathing each other’s stale, unventilated air, then they finally go outside and they aren’t allowed on the playground equipment, because of the covid risk from them touching it. Even though we’ve known for more than a year that covid is an airborne disease. Everyone I’ve talked there agrees that I have a point, but they say their hands are tied. I haven’t yet located the blankface who actually made this decision and stands by it.

What exactly is a blankface? He or she is often a mid-level bureaucrat, but not every bureaucrat is a blankface, and not every blankface is a bureaucrat. A blankface is anyone who enjoys wielding the power entrusted in them to make others miserable by acting like a cog in a broken machine, rather than like a human being with courage, judgment, and responsibility for their actions. A blankface meets every appeal to facts, logic, and plain compassion with the same repetition of rules and regulations and the same blank stare—a blank stare that, more often than not, conceals a contemptuous smile.

The longer I live, the more I see blankfacedness as one of the fundamental evils of the human condition. Yes, it contains large elements of stupidity, incuriosity, malevolence, and bureaucratic indifference, but it’s not reducible to any of those. After enough experience, the first two questions you ask about any organization are:

  1. Who are the blankfaces here?
  2. Who are the people I can talk with to get around the blankfaces?

As far as I can tell, blankfacedness cuts straight across conventional political ideology, gender, and race. (Age, too, except that I’ve never once encountered a blankfaced child.) Brilliance and creativity do seem to offer some protection against blankfacedness—possibly because the smarter you are, the harder it is to justify idiotic rules to yourself—but even there, the protection is far from complete.


Twenty years ago, all the conformists in my age cohort were obsessed with the Harry Potter books and movies—holding parties where they wore wizard costumes, etc. I decided that the Harry Potter phenomenon was a sort of collective insanity: from what I could tell, the stories seemed like startlingly puerile and unoriginal mass-marketed wish-fulfillment fantasies.

Today, those same conformists in my age cohort are more likely to condemn the Harry Potter series as Problematically white, male, and cisnormative, and J. K. Rowling herself as a monstrous bigot whose acquaintances’ acquaintances should be shunned. Naturally, then, there was nothing for me to do but finally read the series! My 8-year-old daughter Lily and I have been partner-reading it for half a year; we’re just finishing book 5. (After we’ve finished the series, we might start on Harry Potter and the Methods of Rationality … which, I confess, I’ve also never read.)

From book 5, I learned something extremely interesting. The most despicable villain in the Harry Potter universe is not Lord Voldemort, who’s mostly just a faraway cipher and abstract embodiment of pure evil, no more hateable than an earthquake. Rather, it’s Dolores Jane Umbridge, the toadlike Ministry of Magic bureaucrat who takes over Hogwarts school, forces out Dumbledore as headmaster, and terrorizes the students with increasingly draconian “Educational Decrees.” Umbridge’s decrees are mostly aimed at punishing Harry Potter and his friends, who’ve embarrassed the Ministry by telling everyone the truth that Voldemort has returned and by readying themselves to fight him, thereby defying the Ministry’s head-in-the-sand policy.

Anyway, I’ll say this for Harry Potter: Rowling’s portrayal of Umbridge is so spot-on and merciless that, for anyone who knows the series, I could simply define a blankface to be anyone sufficiently Umbridge-like.


This week I also finished reading The Premonition, the thrilling account of the runup to covid by Michael Lewis (who also wrote The Big Short, Moneyball, etc). Lewis tells the stories of a few individuals scattered across US health and government bureaucracies who figured out over the past 20 years that the US was breathtakingly unprepared for a pandemic, and who struggled against official indifference, mostly unsuccessfully, to try to fix that. As covid hit the US in early 2020, these same individuals frantically tried to pull the fire alarms, even as the Trump White House, the CDC, and state bureaucrats all did everything in their power to block and sideline them. We all know the results.

It’s no surprise that, in Lewis’s telling, Trump and his goons come in for world-historic blame: however terrible you thought they were, they were worse. It seems that John Bolton, in particular, gleefully took an ax to everything the two previous administrations had done to try to prepare the federal government for pandemics—after Tom Bossert, the one guy in Trump’s inner circle who’d actually taken pandemic preparation seriously, was forced out for contradicting Trump about Russia and Ukraine.

But the left isn’t spared either. The most compelling character in The Premonition is Charity Dean, who escaped from the Christian fundamentalist sect in which she was raised to put herself through medical school and become a crusading public-health officer for Santa Barbara County. Lewis relates with relish how, again and again, Dean startled the bureaucrats around her by taking matters into her own hands in her war against pathogens—e.g., slicing into a cadaver herself to take samples when the people whose job it was wouldn’t do it.

In 2019, Dean moved to Sacramento to become California’s next chief public health officer, but then Governor Gavin Newsom blocked her expected promotion, instead recruiting someone from the outside named Sonia Angell, who had no infectious disease experience but to whom Dean would have to report. Lewis reports the following as the reason:

“It was an optics problem,” says a senior official in the Department of Health and Human Services. “Charity was too young, too blond, too Barbie. They wanted a person of color.” Sonia Angell identified as Latina.

After it became obvious that the White House and the CDC were both asleep at the wheel, the competent experts’ Plan B was to get California to set a national standard, one that would shame all the other states into acting, by telling the truth about covid and by aggressively testing, tracing, and isolating. And here comes the tragedy: Charity Dean spent from mid-January till mid-March trying to do exactly that, and Sonia Angell blocked her. Angell—who comes across as a real-life Dolores Umbridge—banned Dean from using the word “pandemic,” screamed at her for her insubordination, and systematically shut her out of meetings. Angell’s stated view was that, until and unless the CDC said that there was a pandemic, there was no pandemic—regardless of what hospitals across California might be reporting to the contrary.

As it happens, California was the first state to move aggressively against covid, on March 19—basically because as the bodies started piling up, Dean and her allies finally managed to maneuver around Angell and get the ear of Governor Newsom directly. Had the response started earlier, the US might have had an outcome more in line with most industrialized countries. Half of the 630,000 dead Americans might now be alive.

Sonia Angell fully deserves to have her name immortalized by history as one of the blankest of blankfaces. But of course, Angell was far from alone. Robert Redfield, Trump’s CDC director, was a blankface extraordinaire. Nancy Messonnier, who lied to stay in Trump’s good graces, was a blankface too. The entire CDC and FDA seem to have teemed with blankfaces. As for Anthony Fauci, he became a national hero, maybe even deservedly so, merely by not being 100% a blankface, when basically every other “expert” in the US with visible power was. Fauci cleared a depressingly low bar, one that the people profiled by Lewis cleared at Simone-Biles-like heights.

In March 2020, the fundamental question I had was: where are the supercompetent rule-breaking American heroes from the disaster movies? What’s taking them so long? The Premonition satisfyingly answers that question. It turns out that the heroes did exist, scattered across the American health bureaucracy. They were screaming at the top of their lungs. But they were outvoted by the critical mass of blankfaces that’s become one of my country’s defining features.


Some people will object that the term “blankface” is dehumanizing. The reason I disagree is that a blankface is someone who freely chose to dehumanize themselves: to abdicate their human responsibility to see what’s right in front of them, to act like malfunctioning pieces of electronics even though they, like all of us, were born with the capacity for empathy and reason.

With many other human evils and failings, I have a strong inclination toward mercy, because I understand how someone could’ve succumbed to the temptation—indeed, I worry that I myself might’ve succumbed to it “but for the grace of God.” But here’s the thing about blankfaces: in all my thousands of dealings with them, not once was I ever given cause to wonder whether I might have done the same in their shoes. It’s like, of course I wouldn’t have! Even if I were forced (by my own higher-ups, an intransigent computer system, or whatever else) to foist some bureaucratic horribleness on an innocent victim, I’d be sheepish and apologetic about it. I’d acknowledge the farcical absurdity of what I was making the other person do, or declaring that they couldn’t do. Likewise, even if I were useless in a crisis, at least I’d get out of the way of the people trying to solve it. How could I live with myself otherwise?

The fundamental mystery of the blankfaces, then, is how they can be so alien and yet so common.


Update (Aug. 3): Surprisingly many people seem to have read this post, and come away with the notion that a “blankface” is simply anyone who’s a stickler for rules and formalized procedures. They’ve then tried to refute me with examples of where it’s good to be a stickler, or where I in particular would believe that it’s good.

But no, that’s not it at all.

Rules can be either good or bad. All things considered, I’d probably rather be on a plane piloted by a robotic stickler for safety rules, than by someone who ignored the rules at his or her discretion. And as I said in the post, in the first months of covid, it was ironically the anti-blankfaces who were screaming for rules, regulations, and lockdowns; the blankfaces wanted to continue as though nothing had changed!

Also, “blankface” (just like “homophobe” or “antisemite”) is a serious accusation. I’d never call anyone a blankface merely for sticking with a defensible rule when it turned out, in hindsight, that the rule could’ve been relaxed.

Here’s how to tell a blankface: suppose you see someone enforcing or interpreting a rule in a way that strikes you as obviously absurd. And suppose you point it out to them.

Do they say “I disagree, here’s why it actually does make sense”? They might be mistaken but they’re not a blankface.

Do they say “tell me about it, it makes zero sense, but it’s above my pay grade to change”? You might wish they were more dogged or courageous but again they’re not a blankface.

Or do they ignore all your arguments and just restate the original rule—seemingly angered by what they understood as a challenge to their authority, and delighted to reassert it? That’s the blankface.

Striking new Beeping Busy Beaver champion

July 27th, 2021

For the past few days, I was bummed about the sooner-than-expected loss of Steven Weinberg. Even after putting up my post, I spent hours just watching old interviews with Steve on YouTube and reading his old essays for gems of insight that I’d missed. (Someday, I’ll tackle Steve’s celebrated quantum field theory and general relativity textbooks … but that day is not today.)

Looking for something to cheer me up, I was delighted when Shtetl-Optimized reader Nick Drozd reported a significant new discovery in BusyBeaverology—one that, I’m proud to say, was directly inspired by my Busy Beaver survey article from last summer (see here for blog post).

Recall that BB(n), the nth Busy Beaver number (technically, “Busy Beaver shift number”), is defined as the maximum number of steps that an n-state Turing machine, with 1 tape and 2 symbols, can make on an initially all-0 tape before it invokes a Halt transition. Famously, BB(n) is not only uncomputable, it grows faster than any computable function of n—indeed, computing anything that grows as quickly as Busy Beaver is equivalent to solving the halting problem.

As of 2021, here is the extent of human knowledge about concrete values of this function:

  • BB(1) = 1 (trivial)
  • BB(2) = 6 (Lin 1963)
  • BB(3) = 21 (Lin 1963)
  • BB(4) = 107 (Brady 1983)
  • BB(5) ≥ 47,176,870 (Marxen and Buntrock 1990)
  • BB(6) > 7.4 × 1036,534 (Kropitz 2010)
  • BB(7) > 102×10^10^10^18,705,352 (“Wythagoras” 2014)

As you can see, the function is reasonably under control for n≤4, then “achieves liftoff” at n=5.

In my survey, inspired by a suggestion of Harvey Friedman, I defined a variant called Beeping Busy Beaver, or BBB. Define a beeping Turing machine to be a TM that has a single designated state where it emits a “beep.” The beeping number of such a machine M, denoted b(M), is the largest t such that M beeps on step t, or ∞ if there’s no finite maximum. Then BBB(n) is the largest finite value of b(M), among all n-state machines M.

I noted that the BBB function grows uncomputably even given an oracle for the ordinary BB function. In fact, computing anything that grows as quickly as BBB is equivalent to solving any problem in the second level of the arithmetical hierarchy (where the computable functions are in the zeroth level, and the halting problem is in the first level). Which means that pinning down the first few values of BBB should be even more breathtakingly fun than doing the same for BB!

In my survey, I noted the following four concrete results:

  • BBB(1) = 1 = BB(1)
  • BBB(2) = 6 = BB(2)
  • BBB(3) ≥ 55 > 21 = BB(3)
  • BBB(4) ≥ 2,819 > 107 = BB(4)

The first three of these, I managed to get on my own, with the help of a little program I wrote. The fourth one was communicated to me by Nick Drozd even before I finished my survey.

So as of last summer, we knew that BBB coincides with the ordinary Busy Beaver function for n=1 and n=2, then breaks away starting at n=3. We didn’t know how quickly BBB “achieves liftoff.”

But Nick continued plugging away at the problem all year, and he now claims to have resolved the question. More concretely, he claims the following two results:

  • BBB(3) = 55 (via exhaustive enumeration of cases)
  • BBB(4) ≥ 32,779,478 (via a newly-discovered machine)

For more, see Nick’s announcement on the Foundations of Mathematics email list, or his own blog post.

Nick actually writes in terms of yet another Busy Beaver variant, which he calls BLB, or “Blanking Beaver.” He defines BLB(n) to be the maximum finite number of steps that an n-state Turing machine can take before it first “wipes its tape clean”—that is, sets all the tape squares to 0, as they were at the very beginning of the computation, but as they were not at intermediate times. Nick has discovered a 4-state machine that takes 32,779,477 steps to blank out its tape, thereby proving that

  • BLB(4) ≥ 32,779,477.

Nick’s construction, when investigated, turns out to be based on a “Collatz-like” iterative process—exactly like the BB(5) champion and most of the other strong Busy Beaver contenders currently known. A simple modification of his construction yields the lower bound on BBB.

Note that the Blanking Beaver function does not have the same sort of super-uncomputable growth that Beeping Busy Beaver has: it merely grows “normally” uncomputably fast, like the original BB function did. Yet we see that BLB, just like BBB, already “achieves liftoff” by n=4, rather than n=5. So the real lesson here is that 4-state Turing machines can already do fantastically complicated things on blank tapes. It’s just that the usual definitions of the BB function artificially prevent us from seeing that; they hide the uncomputable insanity until we get to 5 states.