Shtetl-Optimized

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

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

Then what happens in the next election?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Today I woke up to the sad and shocking news that Jon Dowling (homepage / Twitter / Wikipedia)—physics professor at Louisiana State, guy who got the US government to invest in quantum computing back in the 90s, author of the popular book Schrödinger’s Killer App: Race to Build the World’s First Quantum Computer, investigator of BosonSampling among many other topics, owner of a “QUBIT” license plate, and one of my main competitors in the field of quantum computing humor—has passed away at age 65, apparently due to an aortic aneurysm.

Three months ago, right before covid shut down the world, the last travel I did was a seven-hour road trip from Austin to Baton Rouge, together with my postdoc Andrea Rocchetto, to deliver something called the Hearne Lecture at the Louisiana State physics department. My topic (unsurprisingly) was Google’s quantum supremacy experiment.

I’d debated whether to cancel the trip, as flying already seemed too dangerous. Dowling was the one who said “why not just drive here with one of your postdocs?”—which turned into a memorable experience for me and Andrea, complete with a personal tour of LIGO and a visit to an alligator hatchery. I had no inkling that it was the last time I’d ever see Jon Dowling, but am now super-glad that we made the visit.

At the dinner after my talk, Dowling was exactly the same as every other time I’d seen him: loud, piss-drunk, obnoxious, and hilarious. He dominated the conversation with stories and jokes, referring in every other sentence either to his Irishness or my Jewishness. His efforts to banter with the waitress, to elicit her deepest opinions about each appetizer and bottle of wine, were so over-the-top that I, sitting next to him, blushed, as if to say, “hey, I’m just the visitor here! I don’t necessarily endorse this routine!”

But Dowling got away with it because, no matter how many taboos he violated per sentence, there was never any hint of malice in it. He was an equal-opportunity offender, with his favorite target being himself. He loved to talk, for example, about my pathological obsession with airy-fairy abstractions, like some kind of “polynomial hierarchy” that hopefully wouldn’t “collapse”—with the punchline being that he, the hardheaded laser physicist, then needed to learn what that meant for his own research.

The quantum computing community of the southern US, not to mention of Twitter and Facebook, and indeed of the entire world, will be poorer without this inimitable, louder-than-life presence.

Feel free to share your own Dowling stories in the comments.

Scott’s foreword: Zeph Landau, a noted quantum computing theorist at UC Berkeley who’s worked closely with my adviser Umesh Vazirani, recently asked me if he could write a guest post about pooled testing for covid—an old idea that, Zeph argues, could play a crucial role in letting universities safely reopen this fall. Seeing a small chance to do a great good, I readily agreed.

I should confess that I’m more … fatalistic than Zeph. Not that I’m proud of it: I think that Zeph’s attitude is superior to mine. But, like, I’m a theoretical computer scientist with zero expertise in medical testing or statistics, and I knew about pooled testing and its WWII origins—so imagine how thoroughly the actual experts must know the idea. Just like they know all about variolation, and challenge trials, and copper fixtures, and UV light, and vitamin D supplements, and a dozen other possible tools against covid that future historians might ask why we didn’t try more.

As I’ve written before, I think our fundamental problem is not a lack of good ideas. It’s that, outside of some isolated pockets of progress, our entire civilization no longer has the will (or ability? is there a difference?) to implement good ideas, or even really to try them. For anything new that requires coordination, today there are just too many stakeholders who need to be brought on board, too many risks that need further study. So I see Zeph, and anyone like him, as occupying a tragic position, a bit like that of an Aztec advocating the use of the wheel. “Sure,” the Aztec elders might calmly reply, “wheeled transport is obvious enough that we’ve all considered it, but a moment’s thought reveals why, in our actually existing empire, it would be reckless, costly, and of at most marginal benefit…”

But I hope I’m wrong! Better, I hope this post is the one that proves me wrong! So without further ado, here’s…

Zeph Landau’s Guest Post

This post describes how every university could efficiently use modest testing resources to sensibly and extensively reduce the number of COVID-19 cases on their campus this fall.  It is meant as a call to action to the reader—because without a concerted effort to get the right people the necessary information and take immediate consequential action, a far worse alternative will be implemented almost everywhere. It is my sincere hope, that immediately after reading this post, you will take the following steps:

1) Figure out who is part of the reopening committee at your institution.

2) Find the right people and engage with them either as a fellow faculty member or, better yet, through a connection to get them good information about the information posted here.

3) Then stay engaged and keep pushing. (See below for links to sample documents.)

OK, here we go.

The Problem

How can we safely open a university or college campus such that we ensure that the number of cases does not drastically increase through the newfound interactions between the population?

One obvious, albeit impractical, solution to opening universities is to test everyone, everyday and isolate those that test positive quickly. Unfortunately, we can’t do that due to costs ($100 per student per day) and availability of tests (on the order of 1000 tests per day at university testing labs).

Turns out there is a solution that uses drastically fewer tests and is commensurate in detecting an outbreak. It is called pooled screening which is a variant of pooled testing.

The missing piece: early detection surveillance

So how do we detect most contagious people quickly if we don’t have the resources to test everyone regularly?  The answer is by pooled testing—or to be more accurate (I’ll be clear about why this distinction is important later) pooled screening. The idea of pooling is old (attributed to Dorfman in the 40’s), simple, and has been used over and over in all kinds of scenarios. Pooled testing works by mixing samples together from a group and then administering a single test to the mixture. The test is designed to be sensitive enough to come up positive whenever at least one underlying sample is positive. Instead of testing each sample individually, you test the mixture, and then only those groups that test positive undergo a second round of testing of each individual sample. The individuals do not need to deliver a second sample; there is more than enough biological material for multiple tests per sample. When prevalence of a disease is low, most pools come up negative and you save a large amount of testing resources and time.  (For those more visually inclined, here is a one minute video on pooled testing.)

So what would a good early detection surveillance system look like?  Here is a reasonable and doable framework:

• Divide the campus population into three groups (call them A, B, and C).
• Collect samples from each group twice a week, (e.g. Group A: M/Th, Group B: Tu/Fri, Group C Wed/Sat).
• Pool test the samples in groups of 16.

What kinds of resources would this use?

• For a 10,000 person campus, you’d need about 200 tests per day, 6 days a week.  The universities that have implemented testing labs typically have the capacity to do on the order of 1000 tests a day.
• Assuming a rough cost of $100 a test (which should be an overestimate if they are using their own lab), it would amount to a $12 a student/ per week.  

What would it accomplish?  It would quickly find outbreaks and new cases.  Under a few different assumptions of the time-course of the viral load in a person, the expected time for detecting an infectious person in this scheme is under 3 days. Those cases would then need to be fed into an existing contact tracing and quarantine protocol.  The result: an outbreak suppressed before it had a chance to get going.

So why aren’t we already doing this?  Read on…

The fear of false negatives in pooling

The general concern to implementing pooling  for Covid-19 in the US is two-fold. 

1. Without the creation of a better test the dilution effect will make the test less sensitive and in turn produce more false negatives.  
2. Even if you could solve the scientific sensitivity issue, navigating the process of getting government approval is a big barrier.

Let’s take each of these concerns in turn.  The first is definitely a concern if the goal is 1:1 medical testing.  If a sample can be barely seen as positive in an individual test, then the risk is that the dilution effect when pooled with others will cause the group test to come out negative—giving a wrong result to the positive individual.  The word for this is “sensitivity”, i.e. if a test has 95% sensitivity it means that it’ll be accurate 95% of the time and produce a false negative 5% of the time.  So how sensitive would a pooled test be where you combined 16 individual samples into 1 and just ran it through an existing 1:1 test?  Lab data suggests it would have at least 70% sensitivity.  For 1:1 testing this is a non-starter, however, the goal is early detection of an outbreak, which is different and as we shall see, a 70% sensitivity does fine for this purpose.

Suppose you are doing early detection surveillance and imagine that an outbreak starts.  Imagine 3 people are infected.  Because you are sampling every 3 days, you’ll be getting at least 6 positive samples, and the chances that your 70% screen misses all 6 is tiny.  As soon as it catches one, a contact tracing protocol is initiated and the others will be found.

Another way to formulate what is going on is that you are trading sensitivity for speed (in the form of capacity and cost)—and that is a huge win.  The pooling and more frequent testing gives you that speed versus sensitivity tradeoff.  Sure, Lebron James (a 70% free-throw shooter) won’t make every free throw, but the chance that he misses 6 in a row is tiny.

For some, the above thinking is straightforward.  However, for the medical testing paradigm—where the goal is the most accurate test for an individual using the one sample you have—this point of view is foreign and in many ways almost out of reach.   

OK.  So with the concern of sensitivity laid to rest, what about the second concern?  That the regulations will get in the way.  It turns out that this isn’t an issue though again, it is slightly counterintuitive for those who work in medical testing.  The task is surveillance, and therefore the pooling test is being used as a screen (not a medical test): negative group tests are not reported to the individual as a negative test result.   Positive groups are deconvoluted for individual testing and results returned to the person who is positive individually.  HHS/CLIA has indicated there aren’t regulatory restrictions as long as you don’t return test results due to the pooled test.

It is important to re-emphasize that the above is for pooled screening (where negative results are not returned), which is in contrast to pooled testing (where negative pools are reported as negative test results for each individual).  For pooled testing, which has received a jump of coverage due to its use recently in Wuhan, there are large regulatory hurdles—the CDC is just formulating criteria for clearing those hurdles and the science looks like, for now, that most labs wouldn’t be able to get above pools of size 5 or so.

How do you safely collect so many samples?

A different direction of concern for early detection surveillance is the logistics and feasibility around collecting samples.  To date, the gold standard for sampling is a deep nasal swab that requires a professional to do it, requires PPE equipment, and is not a pleasant experience.  Using this method wouldn’t work logistically on campus.

However, there are other sampling techniques that allow people to self-sample, both in the form of a shallow nasal swab and saliva based techniques.  The stated concern is obvious: there is a worry that these sampling techniques are less sensitive.  There is some evidence that this is not the case (and even the opposite) but regardless, as has been discussed— in early detection surveillance it is OK to take a hit on sensitivity.  The system remains robust because of the frequent testing and the goal of detecting an outbreak, not every individual.

Being able to self-sample removes a huge bottleneck.  The picture is very much simplified.  Students/faculty/staff self-sample on their prescribed days (either in the presence of a medical professional or not depending on the approved protocol) and then drop off their sample at any of various drop-off stations on campus.  Those stations deliver the samples to the testing facility for pooling and testing.

You can help to get this done

Is what I’m describing a new idea?  As far as I can tell, the answer is both no and yes.  Pooled testing is in the news both as a theoretical idea and now as being implemented at some scale—in Israel, in a lab in Nebraska, and most recently in Wuhan.   But using pooling as a screen (not a medical test) within an early detection surveillance system that repeatedly screens everyone is, as far as I know, not in the discussion.

What seems clear is that right now—reopening committees and labs are perhaps aware of the idea of pooling but only as a theoretical idea of a technology that might be coming at some vague time in the future.  They are unaware that in the form of early detection surveillance, it is right in front of them ready to go.  They’d need a matter of weeks to convert a 1:1 lab into a lab that could handle both pooled screening and 1:1 testing (this lab did it, here is a brief outline of the steps).  In the same timeline, they could develop a system for handling the logistics of sampling large numbers of people.

And that is where each of you come in…   you can help get these ideas to the right people.  It needs to be done quickly because decisions are being made now as to what to do.  The right people are your colleagues—you just have to find out who they are and reach out to them personally.  You can find out who is on the reopening committee, you can track down faculty members in public health and microbiology. They are often busy and might be skeptical of what an outsider can offer, but keep trying because my experience has been that if you keep at it and follow up, they will listen and be grateful for the information.

Here is a sample letter you could use.

Here is a crowdsourced spreadsheet for potential contact people at various universities.  If your university isn’t yet there, we ask that you enter the info that you find for your university in this form which is linked to the above spreadsheet (or enter it directly into the spreadsheet).

If you want to know more or would like to craft your own letter, here are some relevant links:

Covid-19 early detection surveillance on a 240 person facility using 5 tests a day

Covid-19 early detection surveillance for a campus of 24,000 using 500 tests a day

And here is a simple analysis of the mean time between contagion and detection that an early detection scheme could accomplish.

If anyone wants to follow up with me, I’m happy to do so.  You can reach me at:  zeph dot landau at gmail dot com 

Thanks.

Zeph Landau
Dept. of Computer Science
University of California, Berkeley

Today, I interrupt the news of the rapid disintegration of the United States of America, on every possible front at once (medical, economic, social…), to bring you something far more important: a long-planned two-hour podcast, where theoretical physicist and longtime friend-of-the-blog Sean Carroll interviews yours truly about complexity theory! Here’s Sean’s description of this historic event:

There are some problems for which it’s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem, and actually proving it will win you a million dollars. This kind of question falls under the rubric of “computational complexity theory,” which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world’s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.

So, OK, I guess I should also comment on the national disintegration thing. As someone who was once himself the victim of a crazy police overreaction (albeit, trivial compared to what African-Americans regularly deal with), I was moved by the scenes of police chiefs in several American towns taking off their helmets and joining protesters to cheers. Not only is that a deeply moral thing to do, but it serves a practical purpose of quickly defusing the protests. Right now, of course, is an even worse time than usual for chaos in the streets, with a lethal virus still spreading that doesn’t care whether people are congregating for good or for ill. If rational discussion of policy still matters, I support the current push to end the “qualified immunity” doctrine, end the provision of military training and equipment to police, and generally spur the nation’s police to rein in their psychopath minority.

I was seriously depressed for the last week, by noticeably more than my baseline amount for the new pandemic-ravaged world. The depression seems to have been triggered by two pieces of news:

1. The US Food and Drug Administration—yes, the same FDA whose failure to approve covid tests in February infamously set the stage for the deaths of 100,000 Americans—has now also banned the Gates Foundation’s program for at-home covid testing. This, it seems to me, is not the sort of thing that could happen in a still-functioning society, one where people valued their own and their neighbors’ physical survival, and viewed rules and regulations as merely instruments to that end. It’s the sort of thing that one imagines in the waning years of a doomed empire, when no one pretends anymore that they can fix or improve the Leviathan; they’re all just scurrying to flee the Leviathan as it collapses with a thud. More broadly, I still don’t think that the depth of America’s humiliation and downfall has sunk in to most Americans. For me, it starts and ends with a single observation: where fifty years ago we landed humans on the moon, today we can no longer make or distribute paper masks, even when hundreds of thousands of lives depend on it. Look, there are many countries, like Taiwan and New Zealand, that managed to protect both their economies and their vulnerable citizens’ lives, by crushing the virus early. Then there are countries that waited, until they faced an excruciating choice between the two. But here in the US, we’ve somehow achieved the worst of both worlds—triggering a second Great Depression while also utterly failing to control the virus. Can we abandon the charade of treating this as a legible “policy choice,” to be debated in earnest thinkpieces? To me, it just feels like the death-spasm of a collapsing Leviathan.
2. Something that, at first glance, might seem trivial by comparison, but isn’t: the University of California system—ignoring the advice of its own Academic Senate, and at the apparent insistence of its chancellor Janet Napolitano—will now permanently end the use of the SAT and ACT in undergraduate admissions. This is widely expected, probably correctly, to trigger a chain reaction, whereby one US university after the next will abandon standardized tests. As a result, admissions to the top US universities—and hence, most chances for social advancement in the US—will henceforth be based entirely on shifting and nebulous criteria that rich, well-connected kids and their parents spend most of their lives figuring out, rather than merely mostly based on such criteria. The last side door for smart noncomformist kids is now being slammed shut. From now on, in the US, the only paths to success that clearly delineate their rules will be sports, gambling, reality TV, and the like. In case it matters to anyone reading this, I feel certain that a 15-year-old me wouldn’t stand a chance in the emerging regime—any more than nerdy Jewish kids did in the USSR of the 1970s, or the US of the 1920s. (As I’ve previously recounted on this blog, the US’s “holistic” college admissions system, with its baffling-to-foreigners emphasis on “character,” “leadership,” “well-roundedness,” etc. rather than test scores, originated in a successful push a century ago by the presidents of Harvard, Princeton, and Yale to keep Jewish enrollments down. Today the system fulfills precisely the same function, except against Asian-Americans rather than Jews.) Ironically but predictably, the death of the SAT—i.e., of one of the most fearsome weapons against entrenched wealth and power ever devised—is being celebrated by the self-described champions of the underdog. I have one question for those champions: do you not understand what your system will actually do to society’s underdogs? Or do you understand perfectly well, and approve?

To put it bluntly—since events like these leave no room for euphemism—a hundred thousand Americans are now dead from covid, and hundreds of thousands more are poised to die, because smart people are no longer in charge. And the death of the SAT will help ensure that smart people will never be back in charge. Obama might be remembered by history as America’s last smart-person-in-charge, its last competent technocrat—but one man couldn’t stop a tidal wave of stupid.

I know from experience what many will readers will say to all this: “instead of wallowing in gloom, Scott, why don’t you just make falsifiable predictions about the bad outcomes you expect from these developments, and then score yourself later?”

So here’s the thing about that.

Shortly after Trump was elected, I changed this blog’s background to black, as a small way to mourn the United States that I’d grown up thinking that I lived in, the one that had at least some ideals. Today, with four years of hindsight, my thinking then feels overly optimistic: why plain black? Why not, like, images of rotting corpses in a pit?

And yet, were I foolish enough to register predictions in 2016, I would’ve said that within one year, Trump’s staggering incompetence would surely cause some catastrophe or other to grip the country—a really obvious one, with mass death and even Trump’s beloved stock market cratering.

And then after a year, commenters would ridicule me, because none of that had happened. After two years, they’d ridicule me again because it still hadn’t happened, and after three years they’d ridicule me a third time.

Now it’s happened.

America, we now know, is like the cartoon character who runs off a cliff: it dangled in midair for three years, defying physics, before it finally looked down.

Look, I’m a theoretical computer scientist. By training, I deal in asymptotics, not in constant factors. I don’t often make predictions with deadlines; when I do, I often regret it. It’s a good thing that I became an academic rather than an investor! For I’ve learned that the only “oracular power” I have is to make statements like:

My eyes, my brain, and the pit of my stomach are all blaring at me that the asymptotics of this situation just took a sharp turn for the worse. Sure, for an unknown length of time, noise and constant factors could mask the effects. But eventually, either (1) society will need to reverse what it just did, or else (2) terrible effects will spring from it, or else (3) the entire universe no longer makes sense.

When I’ve felt this way in the past, option (3) rarely turned out to be the right answer.

So, what can anyone say that will make me less depressed? Thanks in advance!

Update (May 30): Woohoo!! Avoiding yet another tragedy, after years of setbacks and struggles, it looks like today the US has finally launched humans into orbit, thereby recapitulating a technological achievement from 1961 that the US had already vastly surpassed by 1969. I hereby retract the pessimism of this post.

Two years ago, I posted detailed lecture notes on this blog for my Intro to Quantum Information Science undergrad course at UT Austin. Today, with enormous thanks to UT PhD student Corey Ostrove, we’ve gotten the notes into a much better shape (for starters, they’re now in LaTeX). You can see the results here (7MB)—it’s basically a 260-page introductory quantum computing textbook in beta form, covering similar material as many other introductory quantum computing textbooks, but in my style for those who like that. It’s missing exercises, as well as material on quantum supremacy experiments, recent progress in hardware, etc., but that will be added in the next version if there’s enough interest. Enjoy!

Unrelated Announcement: Bjorn Poonen at MIT pointed me to researchseminars.org, a great resource for finding out about technical talks that are being held online in the era of covid. The developers recently added CS as a category, but so far there are very few CS talks listed. Please help fix that!

In the past week or two, four striking papers appeared on quant-ph. Rather than doing my usual thing—envisioning a huge, meaty blog post about each paper, but then procrastinating on writing them until the posts are no longer even relevant—I thought I’d just write a paragraph about each paper and then open things up for discussion.

(1) Matt Hastings has announced the first provable superpolynomial black-box speedup for the quantum adiabatic algorithm (in its original, stoquastic version). The speedup is only quasipolynomial (n^log(n)) rather than exponential, and it’s for a contrived example (just like in the important earlier work by Freedman and Hastings, which separated the adiabatic algorithm from Quantum Monte Carlo), and there are no obvious near-term practical implications. But still! Twenty years after Farhi and his collaborators wrote the first paper on the quantum adiabatic algorithm, and 13 years after D-Wave made its first hype-laden announcement, this is (to my mind) the first strong theoretical indication that adiabatic evolution with no sign problem can ever get a superpolynomial speedup over not only simulated annealing, not only Quantum Monte Carlo, but all possible classical algorithms. (This had previously been shown only for a variant of the adiabatic algorithm that jumps up to the first excited state, by Nagaj, Somma, and Kieferova.) As such, assuming the result holds up, Hastings resolves a central question that I (for one) had repeatedly asked about for almost 20 years. Indeed, if memory serves, at an Aspen quantum algorithms meeting a few years ago, I strongly urged Hastings to work on the problem. Congratulations to Matt!

(2) In my 2009 paper “Quantum Copy-Protection and Quantum Money,” I introduced the notion of copy-protected quantum software: a state |ψ_f⟩ that you could efficiently use to evaluate a function f, but not to produce more states (whether |ψ_f⟩ or anything else) that would let others evaluate f. I gave candidate constructions for quantumly copy-protecting the simple class of “point functions” (e.g., recognizing a password), and I sketched a proof that quantum copy-protection of arbitrary functions (except for those efficiently learnable from their input/output behavior) was possible relative to a quantum oracle. Building on an idea of Paul Christiano, a couple weeks ago my PhD student Jiahui Liu, Ruizhe Zhang, and I put a preprint on the arXiv improving that conclusion, to show that quantum copy-protection of arbitrary unlearnable functions is possible relative to a classical oracle. But my central open problem remained unanswered: is quantum copy-protection of arbitrary (unlearnable) functions possible in the real world, with no oracle? A couple days ago, Ananth and La Placa put up a preprint where they claim to show that the answer is no, assuming that there’s secure quantum Fully Homomorphic Encryption (FHE) of quantum circuits. I haven’t yet understood the construction, but it looks plausible, and indeed closely related to Barak et al.’s seminal proof of the impossibility of obfuscating arbitrary programs in the classical world. If this holds up, it (conditionally) resolves another of my favorite open problems—indeed, one that I recently mentioned in the Ask-Me-Anything session!

(3) Speaking of Boaz Barak: he, Chi-Ning Chou, and Xun Gao have a new preprint about a fast classical way to spoof Google’s linear cross-entropy benchmark for shallow random quantum circuits (with a bias that degrades exponentially with the depth, remaining detectable up to a depth of say ~√log(n)). As the authors point out, this by no means refutes Google’s supremacy experiment, which involved a larger depth. But along with other recent results in the same direction (e.g. this one), it does show that some exploitable structure is present even in random quantum circuits. Barak et al. achieve their result by simply looking at the marginal distributions on the individual output qubits (although the analysis to show that this works gets rather hairy). Boaz had told me all about this work when I saw him in person—back when traveling and meeting people in person was a thing!—but it’s great to see it up on the arXiv.

(4) Peter and Raphaël Clifford have announced a faster classical algorithm to simulate BosonSampling. To be clear, their algorithm is still exponential-time, but for the special case of a Haar-random scattering matrix, n photons, and m=n input and output modes, it runs in only ~1.69ⁿ time, as opposed to the previous bound of ~2ⁿ. The upshot is that, if you want to achieve quantum supremacy using BosonSampling, then either you need more photons than previously thought (maybe 90 photons? 100?), or else you need a lot of modes (in our original paper, Arkhipov and I recommended at least m~n² modes for several reasons, but naturally the experimentalists would like to cut any corners they can).

And what about my own “research program”? Well yesterday, having previously challenged my 7-year-old daughter Lily with instances of comparison sorting, Eulerian tours, undirected connectivity, bipartite perfect matching, stable marriage, factoring, graph isomorphism, unknottedness, 3-coloring, subset sum, and traveling salesman, I finally introduced her to the P vs. NP problem! Even though Lily can’t yet formally define “polynomial,” let alone “algorithm,” I’m satisfied that she understands something of what’s being asked. But, in an unintended echo of one of my more controversial recent posts, Lily insists on pronouncing NP as “nip.”

Update (May 10): Extremely sorry to everyone who wanted to attend my SlateStarCodex talk on quantum necromancy, but wasn’t able due to technical problems! My PowerPoint slides are here; a recording might be made available later. Thanks to everyone who attended and asked great questions. Even though there were many, many bugs to be worked out, I found giving my first talk in virtual reality a fascinating experience; thanks so much to Patrick V. for inviting me and setting it up.

(1) I’ll be giving an online talk at SlateStarCodex (actually, in a VR room where you can walk around with your avatar, mingle, and even try to get “front-row seating”), this coming Sunday at 10:30am US Pacific time = 12:30pm US Central time (i.e., me) = 1:30pm US Eastern time = … Here’s the abstract:

Schrödinger’s Cat and Quantum Necromancy

I’ll try, as best I can, to give a 10-minute overview of the century-old measurement problem of quantum mechanics.  I’ll then discuss a new result, by me and Yosi Atia, that might add a new wrinkle to the problem.  Very roughly, our result says that if you had the technological ability, as measured by (say) quantum circuit complexity, to prove that a cat was in a coherent superposition of the alive and dead states, then you’d necessarily also have the technological ability to bring a dead cat back to life.  Of course, this raises the question of in what sense such a cat was ever “dead” in the first place.

(2) Robin Kothari has a beautiful blog post about a new paper by me, him, Avishay Tal, and Shalev Ben-David, which uses Huang’s recent breakthrough proof of the Sensitivity Conjecture to show that D(f)=O(Q(f)⁴) for all total Boolean functions f, where D(f) is the deterministic query complexity of f and Q(f) is the quantum query complexity—thereby resolving another longstanding open problem (the best known relationship since 1998 had been D(f)=O(Q(f)⁶)). Check out his post!

(3) For all the people who’ve been emailing me, and leaving blog comments, about Stephen Wolfram’s new model of fundamental physics (his new new kind of science?)—Adam Becker now has an excellent article for Scientific American, entitled Physicists Criticize Stephen Wolfram’s “Theory of Everything.” The article quotes me, friend-of-the-blog Daniel Harlow, and several others. The only thing about Becker’s piece that I disagreed with was the amount of space he spent on process (e.g. Wolfram’s flouting of traditional peer review). Not only do I care less and less about such things, but I worry that harping on them feeds directly into Wolfram’s misunderstood-genius narrative. Why not use the space to explain how Wolfram makes a hash of quantum mechanics—e.g., never really articulating how he proposes to get unitarity, or the Born rule, or even a Hilbert space? Anyway, given the demand, I guess I’ll do a separate blog post about this when I have time. (Keep in mind that, with my kids home from school, I have approximately 2 working hours per day.)

(4) Oh yeah, I forgot! Joshua Zelinsky pointed me to a website by Martin Ugarte, which plausibly claims to construct a Turing machine with only 748 states whose behavior is independent of ZF set theory—beating the previous claimed record of 985 states due to Stefan O’Rear (see O’Rear’s GitHub page), which in turn beat the 8000 states of me and Adam Yedidia (see my 2016 blog post about this). I should caution that, to my knowledge, the new construction hasn’t been peer-reviewed, let alone proved correct in a machine-checkable way (well, the latter hasn’t yet been done for any of these constructions). For that matter, while an absolutely beautiful interface is provided, I couldn’t even find documentation for the new construction. Still, Turing machine and Busy Beaver aficionados will want to check it out!

Update (May 5): Here’s a Quillette article making the case for human challenge trials. I think there’s an actual non-negligible chance that this cause will win—but every wasted day means thousands more dead.

I’ve asked myself again and again over the last few months: why are human challenge trials for covid vaccines not an ethical no-brainer? What am I missing that all the serious medical experts see? And what are we waiting for: for 10 million more to die? 20 million? So it made me feel a little less crazy that the world’s most famous living ethicist agrees.

I loved the way James Miller put it on my Facebook:

This is the trolley problem where the fat man wants to jump knowing his chance of death is below 1% and our decision is whether to stop him.

Like, suppose someone willingly sacrificed themselves so that doctors could use their body parts to save 10 million people. We might say: we would’ve lacked the strength to do the same in their place. We might say: we hope they weren’t pressured or coerced into it. But after the deed is done, is there anything to call this person but a hero, or even a martyr? Whatever we feel about the fireman who sacrifices his life in the course of saving 10 kids from a burning building, shouldn’t we feel it about this person a million times over? And of course, I deliberately made this vastly more extreme than the actual situation faced by young, healthy volunteers in a covid challenge trial, who in all likelihood would recover and be fine.

Regarding the obvious question: so would I volunteer to take an unproved vaccine, followed by a deliberate covid injection? Sure! Unfortunately, I might no longer be a candidate: I’m now nearing middle age and pre-diabetic, I help watch two young kids, and I live with two immunocompromised parents. But on the principle of walking the walk: if it were a vaccine candidate that I considered promising (and there are now several), and if it were practical to isolate me away from home for the requisite time, and if I could actually be of use, then absolutely, jab me.

On a somewhat related note: Last night I watched the Ender’s Game movie with my 7-year-old daughter Lily (neither of us had seen it; I’d read the book but only as a kid). Not surprisingly, the movie was a huge hit with Lily; she’s already begging to see it again. As for me, my first thought was: what a hackneyed sci-fi premise, that the entire human race is under attack from some alien species, and that all human children grow up in the shadow of that knowledge. Nothing whatsoever like the real world of 2020! My second thought was: what a quaint concept, that faced with a threat to humanity, the earth-authorities would immediately respond “quick, we need to find and train and cultivate super-geniuses willing to break the rules, and put them in command!” Only in the movies, never in real life! Except in, y’know, WWII, where that mindset was pretty crucial to the Allied victory? But 75 years later, yes, it reads to us as science fiction.

To inject a tiny note of optimism, I’m hopeful that we will eventually see some fruits of genius commensurate with the threat, whether in the realm of treatments or vaccines or contact-tracing apps or PPE or something else that no one’s thought of yet. Right now, though, the sad fact is this: as far as I know, the only indisputable work of genius to have arisen in response to the covid crisis has been the Twitter account for steak-umms.

Update (May 1): Check out this Forbes interview, where Martinis explains his reasons for leaving Google in much more detail.

As if we didn’t have enough to worry us, this week brought the sad news that John Martinis, who for five years was the leader and public face of Google’s experimental quantum computing effort, has quit Google and returned to his earlier post at UC Santa Barbara. I’ve spoken about what happened both with John and with Hartmut Neven, the head of Google’s Quantum AI Lab. Without betraying confidences, or asserting anything that either side would disagree with, I think I can say that it came down to a difference in management philosophies. Google tends to be consensus-driven, whereas John is of the view that building a million-qubit, error-corrected quantum computer will take more decisive leadership. I can add: I’d often wondered how John had time to travel the world, giving talks about quantum supremacy, while also managing the lab’s decisions on a day-to-day basis. It looks now like I was right to wonder! Potential analogies flood the mind: is this like a rock band that breaks up right after its breakout hit? Is it like Steve Jobs leaving Apple? Anyway, I wish the Google team the best in John’s absence, and I also wish John the best with whatever he does next.

I was never big on HBO (e.g., I still haven’t seen a single minute of Game of Thrones), but in the last couple of weeks, Dana and I found ourselves watching two absolutely compelling HBO shows—one a fictional miniseries and the other a documentary, but both on the theme of the fragility of American democracy.

The Plot Against America, based on the 2004 Philip Roth novel of the same name (which Dana read and which I now plan to read), is about an alternate history where the aviator Charles Lindbergh defeats FDR in the 1940 presidential election, on a fascist and isolationist platform, in events that—as countless people have pointed out—are eerily, terrifyingly prescient of what would actualy befall the US in 2016. The series follows a Jewish insurance salesman and his family in Newark, NJ—isn’t that what it always is with Philip Roth?—as they try to cope with the country’s gradual, all-too-plausible slide downward, from the genteel antisemitism that already existed in our timeline’s 1940 all the way to riots, assassinations, and pogroms (although never to an American Holocaust). One of the series’ final images is of paper ballots, in a rematch presidential election, being carted away and burned, underscoring just how much depends here on the mundane machinery of democracy.

Which brings me to Kill Chain: The Cyber War on America’s Elections, a documentary about the jaw-droppingly hackable electronic voting machines used in US elections and the fight to do something about them. The show mostly follows the journey of Harri Hursti, a Finnish-born programmer who’s made this issue his life’s work, but it also extensively features my childhood best friend Alex Halderman. OK, but isn’t this a theoretical issue, one that (perhaps rightly) exercises security nerds like Alex, but surely hasn’t changed the outcomes of actual elections?

Yeah, so about that. You know Brian Kemp, the doofus governor of Georgia, who’s infamously announced plans to reopen the state right away, ignoring the pleading of public health experts—a act that will fill Georgia’s ICUs and morgues as surely as night follows day? And you know how Kemp defeated the Democrat, Stacey Abrams, by a razor-thin margin, in a 2018 election of which Kemp himself was the overseer? It turns out that Kemp’s office distributed defective memory cards to African-American and Democratic precincts, though not to white and Republican ones. There’s also striking statistical evidence that at least some voting machines were hacked, although because there was no paper trail it can never be proved.

In short, what The Plot Against America and Kill Chain have in common is that they would be desperately needed warnings about the ease with which democracy could collapse in the US, except for the detail that much of what they warn about has already happened, and now it’s not clear how we get back.