Shtetl-Optimized

[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.

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?

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)ⁿ (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.]

---

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.

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 (N^1-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(N^1-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 ~Ω(N^1-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(N^1-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(N^1-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 |v₁⟩,…,|v_m⟩, in Cⁿ. 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 |⟨v_i|v_j⟩|—i.e., the absolute value of the inner product—for any i≠j. From that information, we want to recover |v₁⟩,…,|v_m⟩ themselves—or rather, their relative configuration in n-dimensional space, isometries being irrelevant.

It seemed to me and Sabee that, if we knew ⟨v_i|v_j⟩ for all i≠j, then we’d get linear equations that iteratively constrained each |v_j⟩ in terms of ⟨v_i|v_j⟩ 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 ⟨v_i|v_j⟩. It seemed further to us that, while it was true that the measurements only revealed |⟨v_i|v_j⟩| rather than ⟨v_i|v_j⟩ itself, the “phase information” in ⟨v_i|v_j⟩ was manifestly irrelevant, as it in any case depended on the irrelevant global phases of |v_i⟩ and |v_j⟩ 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 R³:

|⟨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 |v₁⟩,…,|v_m⟩ 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 ⟨v_i|v_j⟩.

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 BQP_CTC, 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 BQP_CTC ⊆ SQG—as follows from my and Watrous’s 2008 result that BQP_CTC = 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!

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.