Shtetl-Optimized

It is the duty of good people, always and everywhere, to condemn, reject, and disavow the use of political violence.

Even or especially when evildoers would celebrate the use of political violence against us.

It is our duty always to tell the truth, always to play by the rules — even when evil triumphs by lying, by sneeringly flouting every rule.

It appears to be an iron law of Fate that whenever good tries to steal a victory by evil means, it fails. This law is so infallible that any good that tries to circumvent it thereby becomes evil.

When Sam Bankman-Fried tries to save the world using financial fraud — he fails. Only the selfish succeed through fraud.

When kind, nerdy men, in celibate desperation, try to get women to bed using “Game” and other underhanded tactics — they fail. Only the smirking bullies get women that way.

Quantum mechanics is false, because its Born Rule speaks of randomness.

But randomness can’t explain why a bullet aimed at a destroyer of American democracy must inevitably miss by inches, while a bullet aimed at JFK or RFK or MLK or Gandhi or Rabin must inevitably meet its target.

Yet for all that, over the millennia, good has made actual progress. Slavery has been banished to the shadows. Children survive to adulthood. Sometimes altruists become billionaires, or billionaires altruists. Sometimes the good guy gets the girl.

Good has progressed not by lucky breaks — for good never gets lucky breaks — but only because the principles of good are superior.

There’s a kind of cosmic solace that could be offered even to the Jewish mother in the gas chamber watching her children take their last breaths, though the mother could be forgiven for rejecting it.

The solace is that good will triumph — if not in the next four years, then in the four years after that.

Or if not in four, then in a hundred.

Or if not in a hundred, then in a thousand.

Or if not in the entire history of life in on this planet, then on a different planet.

Or if not in this universe, then in a different universe.

Let us commit to fighting for good using good methods only. Fate has decreed in any case that, for us, those are the only methods that work.

Let us commit to use good methods only even if it means failure, heartbreak, despair, the destruction of democratic institutions and ecosystems multiplied by a thousand or a billion or any other constant — with the triumph of good only in the asymptotic limit.

Good will triumph, when it does, only because its principles are superior.

Endnote: I’ve gotten some pushback for this prayer from one of my scientific colleagues … specifically, for the part of the prayer where I deny the universal validity of the Born rule. And yet a less inflammatory way of putting the same point would simply be: I am not a universal Bayesian. There are places where my personal utility calculations do a worst-case analysis rather than averaging over possible futures for the world.

Endnote 2: It is one thing to say, never engage in political violence because the expected utility will come out negative. I’m saying something even stronger than that. Namely, even if the expected utility comes out positive, throw away the whole framework of being an expected-utility maximizer before you throw away that you’re never going to endorse political violence. There’s a class of moral decisions for which you’re allowed to use, even commendable for using, expected-utility calculations, and this is outside that class.

Endnote 3: If you thought that Trump’s base was devoted before, now that the MAGA Christ-figure has sacrificed his flesh — or come within a few inches of doing so — on behalf of the Nation, they will go to the ends of the earth for him, as much as any followers did for any ruler in human history. Now the only questions, assuming Trump wins (as he presumably will), are where he chooses to take his flock, and what emerges in the aftermath for what we currently call the United States. I urge my left-leaning American friends to look into second passports. Buckle up, and may we all be here to talk about it on the other end.

Perhaps like the poor current President of the United States, I can feel myself fading, my memory and verbal facility and attention to detail failing me, even while there’s so much left to do to battle the nonsense in the world. I started my career on an accelerated schedule—going to college at 15, finishing my PhD at 22, etc. etc.—and the decline is (alas) also hitting me early, at the ripe age of 43.

Nevertheless, I do seem to remember that this was once primarily a quantum computing blog, and that I was known to the world as a quantum computing theorist. And exciting things continue to happen in quantum computing…

---

First, a company in the UK called Oxford Ionics has announced that it now has a system of trapped-ion qubits in which it’s prepared two-qubit maximally entangled states with 99.97% fidelity. If true, this seems extremely good. Indeed, it seems better than the numbers from bigger trapped-ion efforts, and quite close to the ~99.99% that you’d want for quantum fault-tolerance. But maybe there’s a catch? Will they not be able to maintain this kind of fidelity when doing a long sequence of programmable two-qubit gates on dozens of qubits? Can the other trapped-ion efforts actually achieve similar fidelities in head-to-head comparisons? Anyway, I was surprised to see how little attention the paper got on SciRate. I look forward to hearing from experts in the comment section.

---

Second, I almost forgot … but last week Quantinuum announced that it’s done a better quantum supremacy experiment based on Random Circuit Sampling with 56 qubits—similar to what Google and USTC did in 2019-2020, but this time using 2-qubit gates with 99.84% fidelities (rather than merely ~99.5%). This should set a new standard for those looking to simulate these things using tensor network methods.

---

Third, a new paper by Schuster, Haferkamp, and Huang gives a major advance on k-designs and pseudorandom unitaries. Roughly speaking, the paper shows that even in one dimension, a random n-qubit quantum circuit, with alternating brickwork layers of 2-qubit gates, forms a “k-design” after only O(k polylog k log n) layers of gates. Well, modulo one caveat: the “random circuit” isn’t from the most natural ensemble, but has to have some of its 2-qubit gates set to the identity, namely those that straddle certain contiguous blocks of log n qubits. This seems like a purely technical issue—how could randomizing those straddling gates make the mixing behavior worse?—but future work will be needed to address it. Notably, the new upper bound is off from the best-possible k layers by only logarithmic factors. (For those tuning in from home: a k-design informally means a collection of n-qubit unitaries such that, from the perspective of degree-k polynomials, choosing a unitary randomly from the collection looks the same as choosing randomly among all n-qubit unitary transformations—i.e., from the Haar measure.)

Anyway, even in my current decrepit state, I can see that such a result would have implications for … well, all sorts of things that quantum computing and information theorists care about. Again I welcome any comments from experts!

---

Incidentally, congratulations to Peter Shor for winning the Shannon Award!

In Michael Sipser’s Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this:

• Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)

The correct answer is that yes, f is computable. Why? Because the constant 1 function is computable, and so is the constant 0 function, so if f is one or the other, then it’s computable.

If you’re still tempted to quibble, then consider the following parallel question:

• Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?

The answer is again yes: even though n hasn’t been completely mathematically specified, it’s been specified enough for us to say that it’s prime (just like if we’d said, “n is an element of the set {3,5}; is n prime?”). Similarly, f has been specified enough for us to say that it’s computable.

The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.

---

Dozens of times in the past 25 years, I’ve gotten some variant on the following question, always with the air that I’m about to bowled over by its brilliance:

• Could the P versus NP question itself be NP-hard, and therefore impossible to solve?

Every time I get this one, I struggle to unpack the layers of misconceptions. But for starters: the concept of “NP-hard” applies to functions or languages, like 3SAT or Independent Set or Clique or whatnot, all of which take an input (a Boolean formula, a graph, etc) and produce a corresponding output. NP-hardness means that, if you had a polynomial-time algorithm to map the inputs to the outputs, then you could convert it via reductions into a polynomial-time algorithm for any language or function in the class NP.

P versus NP, by contrast, is an individual yes-or-no question. Its answer (for all we know) could be independent of the Zermelo-Fraenkel axioms of set theory, but there’s no sense in which the question could be uncomputable or NP-hard. Indeed, a fast program that correctly answers the P vs. NP question trivially exists:

• If P=NP, then the program prints “P=NP.”
• If P≠NP, then the program prints “P≠NP.”

---

In the comments of last week’s post on the breakthrough determination of Busy Beaver 5, I got several variants on the following question:

• What’s the smallest n for which the value of BB(n) is uncomputable? Could BB(6) already be uncomputable?

Once again, I explained that the Busy Beaver function is uncomputable, but the concept of computability doesn’t apply to individual integers like BB(6). Indeed, whichever integer k turns out to equal BB(6), the program “print k” clearly exists, and it clearly outputs that integer!

Again, we can ask for the smallest n such that the value of BB(n) is unprovable in ZF set theory (or some other system of axioms)—precisely the question that Adam Yedidia and I did ask in 2016 (the current record stands at n=745, improving my and Adam’s n=8000). But every specific integer is “computable”; it’s only the BB function as a whole that’s uncomputable.

Alas, in return for explaining this, I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue.

---

So, I’ve come to think of this as the Zombie Misconception of Theoretical Computer Science: this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems. (Or, relatedly: the constant conflation of the uncomputability of the halting problem with Gödel incompleteness. While they’re closely related, only Gödel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.)

Anyway, I’m writing this post mostly just so that I have a place to link the next time this pedagogical zombie rises from its grave, muttering “UNCOMPUTABLE INTEGERRRRRRS….” But also so I can query my readers: what are your ideas for how to keep this zombie down?

The news these days feels apocalyptic to me—as if we’re living through, if not the last days of humanity, then surely the last days of liberal democracy on earth.

All the more reason to ignore all of that, then, and blog instead about the notorious Busy Beaver function! Because holy moly, what news have I got today. For lovers of this super-rapidly-growing sequence of integers, I’ve honored to announce the biggest Busy Beaver development that there’s been since 1983, when I slept in a crib and you booted up your computer using a 5.25-inch floppy. That was the year when Allen Brady determined that BusyBeaver(4) was equal to 107. (Tibor Radó, who invented the Busy Beaver function in the 1960s, quickly proved with his student Shen Lin that the first three values were 1, 6, and 21 respectively. The fourth value was harder.)

Only now, after an additional 41 years, do we know the fifth Busy Beaver value. Today, an international collaboration called bbchallenge is announcing that it’s determined, and even formally verified using the Coq proof system, that BB(5) is equal to 47,176,870—the value that’s been conjectured since 1990, when Heiner Marxen and Jürgen Buntrock discovered a 5-state Turing machine that runs for exactly 47,176,870 steps before halting, when started on a blank tape. The new bbchallenge achievement is to prove that all 5-state Turing machines that run for more steps than 47,176,870, actually run forever—or in other words, that 47,176,870 is the maximum finite number of steps for which any 5-state Turing machine can run. That’s what it means for BB(5) to equal 47,176,870.

For more on this story, see Ben Brubaker’s superb article in Quanta magazine, or bbchallenge’s own announcement. For more background on the Busy Beaver function, see my 2020 survey, or my 2017 big numbers lecture, or my 1999 big numbers essay, or the Googology Wiki page, or Pascal Michel’s survey.

---

The difficulty in pinning down BB(5) was not just that there are a lot of 5-state Turing machines (16,679,880,978,201 of them to be precise, although symmetries reduce the effective number). The real difficulty is, how do you prove that some given machine runs forever? If a Turing machine halts, you can prove that by simply running it on your laptop until halting (at least if it halts after a “mere” ~47 million steps, which is child’s-play). If, on the other hand, the machine runs forever, via some never-repeating infinite pattern rather than a simple infinite loop, then how do you prove that? You need to find a mathematical reason why it can’t halt, and there’s no systematic method for finding such reasons—that was the great discovery of Gödel and Turing nearly a century ago.

More precisely, the Busy Beaver function grows faster than any function that can be computed, and we know that because if a systematic method existed to compute arbitrary BB(n) values, then we could use that method to determine whether a given Turing machine halts (if the machine has n states, just check whether it runs for more than BB(n) steps; if it does, it must run forever). This is the famous halting problem, which Turing proved to be unsolvable by finite means. The Busy Beaver function is Turing-uncomputability made flesh, a finite function that scrapes the edge of infinity.

There’s also a more prosaic issue. Proofs that particular Turing machines run forever tend to be mind-numbingly tedious. Even supposing you’ve found such a “proof,” why should other people trust it, if they don’t want to spend days staring at the outputs of your custom-written software?

And so for decades, a few hobbyists picked away at the BB(5) problem. One, who goes by the handle “Skelet”, managed to reduce the problem to 43 holdout machines whose halting status was still undetermined. Or maybe only 25, depending who you asked? (And were we really sure about the machines outside those 43?)

The bbchallenge collaboration improved on the situation in two ways. First, it demanded that every proof of non-halting be vetted carefully. While this went beyond the original mandate, a participant named “mxdys” later upped the standard to fully machine-verifiable certificates for every non-halting machine in Coq, so that there could no longer be any serious question of correctness. (This, in turn, was done via “deciders,” programs that were crafted to recognize a specific type of parameterized behavior.) Second, the collaboration used an online forum and a Discord server to organize the effort, so that everyone knew what had been done and what remained to be done.

Despite this, it was far from obvious a priori that the collaboration would succeed. What if, for example, one of the 43 (or however many) Turing machines in the holdout set turned out to encode the Goldbach Conjecture, or one of the other great unsolved problems of number theory? Then the final determination of BB(5) would need to await the resolution of that problem. (We do know, incidentally, that there’s a 27-state Turing machine that encodes Goldbach.)

But apparently the collaboration got lucky. Coq proofs of non-halting were eventually found for all the 5-state holdout machines.

As a sad sidenote, Allen Brady, who determined the value of BB(4), apparently died just a few days before the BB(5) proof was complete. He was doubtful that BB(5) would ever be known. The reason, he wrote in 1988, was that “Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.”

---

Maybe I should say a little at this point about what the 5-state Busy Beaver—i.e., the Marxen-Buntrock Turing machine that we now know to be the champion—actually does. Interpreted in English, the machine iterates a certain integer function g, which is defined by

• g(x) = (5x+18)/3 if x = 0 (mod 3),
• g(x) = (5x+22)/3 if x = 1 (mod 3),
• g(x) = HALT if x = 2 (mod 3).

Starting from x=0, the machine computes g(0), g(g(0)), g(g(g(0))), and so forth, halting if and if it ever reaches … well, HALT. The machine runs for millions of steps because it so happens that this iteration eventually reaches HALT, but only after a while:

0 → 6 → 16 → 34 → 64 → 114 → 196 → 334 → 564 → 946 → 1584 → 2646 → 4416 → 7366 → 12284 → HALT.

(And also, at each iteration, the machine runs for a number of steps that grows like the square of the number x.)

Some readers might be reminded of the Collatz Conjecture, the famous unsolved problem about whether, if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. As Scott Alexander would say, this is not a coincidence because nothing is ever a coincidence. (Especially not in math!)

---

It’s a fair question whether humans will ever know the value of BB(6). Pavel Kropitz discovered, a couple years ago, that BB(6) is at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 (i.e., 10 raised to itself 15 times). Obviously Kropitz didn’t actually run a 6-state Turing machine for that number of steps until halting! Instead he understood what the machine did—and it turned out to apply an iterative process similar to the g function above, but this time involving an exponential function. And the process could be proven to halt after ~15 rounds of exponentiation.

Meanwhile Tristan Stérin, who coordinated the bbchallenge effort, tells me that a 6-state machine was recently discovered that “iterates the Collatz-like map {3x/2, (3x-1)/2} from the number 8 and halts if and only if the number of odd terms ever gets bigger than twice the number of even terms.” This shows that, in order to determine the value of BB(6), one would first need to prove or disprove the Collatz-like conjecture that that never happens.

Basically, if and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7).

---

I first learned about the BB function in 1996, when I was 15 years old, from a book called The New Turing Omnibus by A. K. Dewdney.  From what I gather, Dewdney would go on to become a nutty 9/11 truther.  But that’s irrelevant to the story.  What matters was that his book provided my first exposure to many of the key concepts of computer science, and probably played a role in my becoming a theoretical computer scientist at all.

And of all the concepts in Dewdney’s book, the one I liked the most was the Busy Beaver function. What a simple function! You could easily explain its definition to Archimedes, or Gauss, or any of the other great mathematicians of the past. And yet, by using it, you could name definite positive integers (BB(10), for example) incomprehensibly larger than any that they could name.

It was from Dewdney that I learned that the first four Busy Beaver numbers were the unthreatening-looking 1, 6, 21, and 107 … but then that the fifth value was already unknown (!!), and at any rate at least 47,176,870. I clearly remember wondering whether BB(5) would ever be known for certain, and even whether I might be the one to determine it. That was almost two-thirds of my life ago.

As things developed, I played no role whatsoever in the determination of BB(5) … except for this. Tristan Stérin tells me that reading my survey article, The Busy Beaver Frontier, was what inspired him to start and lead the bbchallenge collaboration that finally cracked the problem. It’s hard to express how gratified that makes me.

---

Why care about determining particular values of the Busy Beaver function? Isn’t this just a recreational programming exercise, analogous to code golf, rather than serious mathematical research?

I like to answer that question with another question: why care about humans landing on the moon, or Mars? Those otherwise somewhat arbitrary goals, you might say, serve as a hard-to-fake gauge of human progress against the vastness of the cosmos. In the same way, the quest to determine the Busy Beaver numbers is one concrete measure of human progress against the vastness of the arithmetical cosmos, a vastness that we learned from Gödel and Turing won’t succumb to any fixed procedure. The Busy Beaver numbers are just … there, Platonically, as surely as 13 was prime long before the first caveman tried to arrange 13 rocks into a nontrivial rectangle and failed. And yet we might never know the sixth of these numbers and only today learned the fifth.

Anyway, huge congratulations to the bbchallenge team on their accomplishment. At a terrifying time for the world, I’m happy that, whatever happens, at least I lived to see this.

Dana, the kids, and I got back to the US last week after a month spent in England and then Israel. We decided to visit Israel because … uhh, we heard there’s never been a better time.

We normally go every year to visit Dana’s family and our many friends there, and to give talks. Various well-meaning friends suggested that maybe we should cancel or postpone this year—given, you know, the situation. To me, though, the situation felt like all the more reason to go. To make Israel seem more and more embattled, dangerous, isolated, abnormal, like not an acceptable place to visit (much less live), in order to crater its economy, demoralize its population, and ultimately wipe it from the face of earth … that is explicitly much of the world’s game plan right now, laid out with shocking honesty since October 7 (a day that also showed us what the “decolonization” will, concretely, look like). So, if I oppose this plan, then how could I look myself in the mirror while playing my tiny part in it? Shouldn’t I instead raise a middle finger to those who’d murder my family, and go?

Besides supporting our friends and relatives, though, I wanted to see the post-October-7 reality for myself, rather than just spending hours per day reading about it on social media. I wanted to form my own impression of the mood in Israel: fiercely determined? angry? hopeless? just carrying on like normal?

Anyway, in two meeting-packed weeks, mostly in Tel Aviv but also in Jerusalem, Haifa, and Be’er Sheva, I saw stuff that could support any of those narratives. A lot was as I’d expected, but not everything. In the rest of this post, I’ll share eleven observations:

(1) This presumably won’t shock anyone, but in post-October-7 Israel, you indeed can’t escape October 7. Everywhere you look, on every building, in every lobby, hanging from every highway overpass, there are hostage posters and “Bring Them Home Now” signs and yellow ribbons—starting at the airport, where every single passenger is routed through a long corridor of hostage posters, each one signed and decorated by the hostage’s friends and family. It sometimes felt as though Yad Vashem had expanded to encompass the entire country. Virtually everyone we talked to wanted to share their stories and opinions about the war, most of all their depression and anger. While there was also plenty of discussion about quantum error mitigation and watermarking of large language models and local family events, no one even pretended to ignore the war.

(2) Having said that, the morning after we landed, truthfully, the first thing that leapt out at me wasn’t anything to do with October 7, hostages, or Gaza. It was the sheer number of children playing outside, in any direction you looked. Full, noisy playgrounds on block after block. It’s one thing to know intellectually that Israel has by far the highest birthrate of any Western country, another to see it for yourself. The typical secular family probably has three kids; the typical Orthodox family has more. (The Arab population is of course also growing rapidly, both in Israel and in the West Bank and Gaza.) New apartment construction is everywhere you look in Tel Aviv, despite building delays caused by the war. And it all seems perfectly normal … unless you’ve lived your whole life in environments where 0.8 or 1.2 children per couple is the norm.

This, of course, has giant implications for anyone interested in Israel’s future. It’s like, a million Israeli leftists could get fed up and flee to the US or Canada or Switzerland, and Israel would still have a large and growing Jewish population—because having a big family is “just what people do” in a state that was founded to defy the Holocaust. In particular: anyone who dreams of dismantling the illegal, settler-colonial, fascist Zionist ethnostate, and freeing Palestine from river to sea, had better have some plan for what they’re going to do with all these millions of young Jews, who don’t appear to be going anywhere.

(3) The second thing I noticed was the heat—comparable to the Texas summer heat that we try to escape when possible. Because of the roasting sun, our own two pampered offspring mostly refused to go outside during daytime, and we mostly met friends indoors. I more than once had the dark thought that maybe Israel will survive Hamas, Hezbollah, Iran, and its own Jewish extremists … only to be finished off in the end (along with much of the rest of the planet) by global warming. I wonder whether Israel will manage to engineer its way out of the crisis, as it dramatically engineered its way out of its water crisis via desalination. The Arab petrostates have been trying to engineer their way out of the Middle East’s increasingly Mercury-like climate, albeit with decidedly mixed results.

(4) But nu, what did our Israeli friends say about the war? Of course it’s a biased sample, because our friends are mostly left-wing academics and tech workers. But, at risk of overgeneralizing: they’re unhappy. Very, very unhappy. As for Bibi and his far-right yes-men? Our friends’ rage at them was truly a sight to behold. American progressives are, like, mildly irked by Trump in comparison. Yes, our friends blame Bibi for the massive security and intelligence failures that allowed October 7 to happen. They blame him for dragging out the war to stave off elections. They blame him for empowering the contemptible Ben-Gvir and Smotrich. They blame him for his failure to bring back the remaining hostages. Most of all, they blame him for refusing even to meet with the hostage families, and more broadly, for evading responsibility for all that he did wrong, while arrogating credit for any victories (like the rescue of Noa Argamani).

(5) One Israeli friend offered to take me along to the giant anti-Bibi rally that now happens every Saturday night in Azrieli Center in Tel Aviv. (She added that, if I left before 9pm, it would reduce the chances of the police arresting me.) As the intrepid blogger-investigator I am, of course I agreed.

While many of the protesters simply called for new elections to replace Netanyahu (a cause that I 3000% support), others went further, demanding a deal to free the hostages and an immediate end to the war (even if, as they understood, that would leave Hamas in power).

Watching the protesters, smelling their pot smoke that filled the air, I was seized by a thought: these Israeli leftists actually see eye-to-eye with the anti-Israel American leftists on a huge number of issues. In a different world, they could be marching together as allies. Except, of course, for one giant difference: namely, the Tel Aviv protesters are proudly waving Israeli flags (sometimes modified to add anti-Bibi images, or to depict the Star of David “crying”), rather than burning or stomping on those flags. They’re marching to save the Israel that they know and remember, rather than to destroy it.

(6) We did meet one ultra-right-wing (and Orthodox) academic colleague. He was virtually the only person we met on this trip who seemed cheerful and optimistic about Israel’s future. He brought me to his synagogue to celebrate the holiday of Shavuot, while he himself stood guarding the door of the synagogue with a gargantuan rifle (his volunteer duty since October 7). He has six kids.

(7) Again and again, our secular liberal friends told us they’re thinking about moving from Israel, because if the Bibi-ists entrench their power (and of course the demographics are trending in that direction), then they don’t see that the country has any worthwhile future for them or their children. Should this be taken more seriously than the many Americans who promise that this time, for real, they’ll move to Canada if Trump wins? I’m not sure. I can only report what I heard.

(8) At the same time, again and again I got the following question from Israelis (including the leftist ones): how bad is the situation for Jews in the US? Have the universities been taken over by militant anti-Zionists, like it shows in the news? I had to answer: it’s complicated. Because I live my life enbubbled in the STEM field of computer science, surrounded by friends and colleagues of many backgrounds, ethnicities, religions, and political opinions who are thoughtful and decent (otherwise, why would they be my friends and colleagues?), I’m able to live a very nice life even in the midst of loud protesters calling to globalize the intifada against my family.

If, on the other hand, I were in a typical humanities department? Yeah, then I’d be pretty terrified. My basic options would be to (a) shut up about my (ironically) moderate, middle-of-the-road opinions on Israel/Palestine, such as support for the two-state solution; (b) live a miserable and embattled existence; or (c) pack up and move, for example to Israel.

An astounding irony right now is that, just as Israeli leftists are talking about moving from Israel, some of my American Jewish friends have talked to me about moving to Israel, to escape a prejudice that they thought died with their grandparents. I don’t know where the grass is actually greener (or is it brown everywhere?). Nor do I know how many worriers will actually follow through. What’s clear is that, both in Israel and in the diaspora, Jews are feeling an existential fear that they haven’t felt for generations.

(9) Did I fear for my own family’s safety during the trip? Not really. Maybe I should have. When we visited Haifa, we found that GPS was scrambled all across northern Israel, to make targeting harder for Hezbollah missiles. As a result, we couldn’t use Google Maps, got completely lost driving, and had to change plans with our friends. For the first time, now I really feel angry at Hezbollah: they made my life worse and it’s personal!

The funniest part, though, was how the scrambling was implemented: when you opened Google Maps anywhere in the north, it told you that you were in Beirut. It then dutifully gave you walking or driving directions to wherever you were going in Israel, passing through Syria close to Damascus (“warning: this route passes through multiple countries”).

(10) The most darkly comical thing that I heard on the entire trip: “oh, no, I don’t object in the slightest if the anti-Zionists want to kill us all. I only object if they want to kill us because of an incorrect understanding of the relevant history.” Needless to say, this was a professor.

(11) After my two-week investigation, what grand insight can I offer about Israel’s future? Not much, but maybe this: I think we can definitively rule out the scenario where Israel, having been battered by October 7, and bracing itself to be battered worse by Hezbollah, just sort of … withers away and disappears. Yes, Israel might get hotter, more crowded, more dangerous, more right-wing, and more Orthodox. But it will stay right where it is, unless and until its enemies destroy it in a cataclysmic war. You can’t scare people away, break their will, if they believe they have nowhere else on the planet to go. You can only kill them or else live next to them in peace, as the UN proposed in 1947 and as Oslo proposed in the 1990s. May we live to see peace.

---

Anyway, on that pleasant note, time soon to tune in to the Trump/Biden debate! I wonder who these two gentlemen are, and what they might stand for?

(See here for Boaz Barak’s obituary, and here for Lance Fortnow’s—they cover different aspects of Luca’s legacy from each other and from this post. Also, click here to register for a free online TCS4All talk that Luca was scheduled to give, and that will now be given in his memory, this Monday at 3:30pm Eastern time.)

---

Luca Trevisan, one of the world’s leading theoretical computer scientists, has succumbed to cancer in Italy, at only 52 years old. I was privileged to know Luca for a quarter-century, first as my complexity theory and cryptography professor at UC Berkeley and as a member of my dissertation committee, and then as a friend and colleague and fellow CS theory blogger.

I regret that I learned of the seriousness of Luca’s condition only a few days ago. So yesterday morning I wrote him a farewell email, under the impression that, while he was now in hospice care, he had at least a few more weeks. Alas, he probably never saw it. So I’m hereby making the email into a memorial post, with small changes mostly to protect people’s privacy.

---

Dear Luca,

Dana, the kids, and I were traveling in Israel for the past two weeks, when I received the shocking and sad news that this might be my last chance to write to you.

At risk of stating the obvious — you had a very large and positive effect on my life and career.  Starting with the complexity theory summer school at the Institute for Advanced Study in 2000, which was the first time we met and also the first time I really experienced the glories of complexity at full blast.  And then continuing at Berkeley, TA’ing your algorithms class, which you had to cancel on 9/11 (although students still somehow showed up for office hours lugging their CLRS books…), and dealing with that student who obviously cheated on the midterm although I had stupidly given back to her the evidence that would prove it.

And then your graduate complexity course, where I was very proud to get 100% on your exam, having handwritten it on a train while everyone else used LaTeX (which, embarrassingly, I was still learning).  I was a bit less proud to present the Razborov-Rudich paper to the class, and to get questions from you that proved that I understood it less thoroughly than I thought.  I emerged from your course far better prepared to do complexity theory than when I entered it.

Later I took your cryptography course, where I came to you afterwards one day to point out that with a quantum computer, you could pull out big Fourier coefficients without all the bother of the Goldreich-Levin theorem.  And you said sure, but then you would need a quantum computer.  Over 20 years later, Goldreich and Levin (and you?) can say with satisfaction that we still don’t have that scalable quantum computer … but we’re much much closer, I swear!

I still feel bad about the theory lunch talk I gave in 2003, on my complexity-theoretic version of Aumann’s agreement theorem, where I used you and Umesh as characters instead of Alice and Bob, and which then led to unintended references to “Luca’s posterior” (probability distribution, I meant).

I also feel bad about delaying so long the completion of my PhD thesis, until well after I’d started my postdoc in Princeton, so that my former officemate needed to meet you on a street corner in San Francisco to sign the signature page the night before the deadline.

But then a few years later, when Avi and I did the algebrization paper, the fact that you seemed to like it mattered more to me than just about anything else.

Thank you for the excellent dinner when I met you some years ago in Rome.  Thank you for the Trevisan-Tulsiani-Vadhan paper, which answered a question we had about BosonSampling (and you probably didn’t even know you were doing quantum computing when you wrote that paper!).  Thank you for your blog.  Thank you for everything you did for me.

I always enjoyed your dry humor, much of which might sadly be lost to time, unless others wrote it down or it’s on YouTube or something. Two examples spring to my mind across the decades:

• “From my previous lecture, you may have gotten the impression that everything in derandomization is due to Nisan and Wigderson, but this is not the case: Avi has been working with other people as well.”
• After I’d explained that I’d be spending a semester in Jerusalem to work with Avi, despite (at that time) knowing only the most rudimentary Hebrew, such as how to say “please” and “excuse me”: “you mean there are words in Hebrew for ‘please’ and ‘excuse me’?”

Speaking of which, my current trip to Israel has given me many opportunities to reflect on mortality — for all the obvious war-related reasons of course, but also because while we were here, we unexpectedly had to attend two shivas of people in our social circle who died during our trip, one of them from cancer.  And we learned about a close friend whose stepson has a brain tumor and might or might not make it.  Cancer is a bitch.

Anyway, there’s much more I could write, but I imagine you’re getting flooded with emails right now from all the people whose lives you’ve touched, so I won’t take up more of your time.  You’ve made a real difference to the world, to theoretical computer science, and to your friends and colleagues, one that many people would envy.

Best,
Scott

My friend Leopold Aschenbrenner, who I got to know and respect on OpenAI’s now-disbanded Superalignment team before he left the company under disputed circumstances, just released “Situational Awareness,” one of the most extraordinary documents I’ve ever read. With unusual clarity, concreteness, and seriousness, and with a noticeably different style than the LessWrongers with whom he shares some key beliefs, Leopold sets out his vision of how AI is going to transform civilization over the next 5-10 years. He makes a case that, even after ChatGPT and all that followed it, the world still hasn’t come close to “pricing in” what’s about to hit it. We’re still treating this as a business and technology story like personal computing or the Internet, rather than (also) a national security story like the birth of nuclear weapons, except more so. And we’re still indexing on LLMs’ current capabilities (“fine, so they can pass physics exams, but they still can’t do original physics research“), rather than looking at the difference between now and five years ago, and then trying our best to project forward an additional five years.

Leopold makes an impassioned plea for the US to beat China and its other autocratic adversaries in the race to superintelligence, and to start by preventing frontier model weights from being stolen. He argues that the development of frontier AI models will inevitably be nationalized, once governments wake up to the implications, so we might as well start planning for that now. Parting ways from the Yudkowskyans despite their obvious points of agreement, Leopold is much less worried about superintelligence turning us all into paperclips than he is about it doing the bidding of authoritarian regimes, although he does worry about both.

Leopold foresaw the Covid lockdowns, as well as the current AI boom, before most of us did, and apparently made a lot of money as a result. I don’t know how his latest predictions will look from the standpoint of 2030. In any case, though, it’s very hard for me to imagine anyone in the US national security establishment reading Leopold’s document without crapping their pants. Is that enough to convince you to read it?

I am, of course, sad that Jan Leike and Ilya Sutskever, the two central people who recruited me to OpenAI and then served as my “bosses” there—two people for whom I developed tremendous admiration—have both now resigned from the company. Ilya’s resignation followed the board drama six months ago, but Jan’s resignation last week came as a shock to me and others. The Superalignment team, which Jan and Ilya led and which I was part of, is being split up and merged into other teams at OpenAI.

See here for Ilya’s parting statement, and here for Jan’s. See here for Zvi Mowshowitz’s perspective and summary of reporting on these events. For additional takes, see pretty much the entire rest of the nerd Internet.

As for me? My two-year leave at OpenAI was scheduled to end this summer anyway. It seems pretty clear that I ought to spend my remaining months at OpenAI simply doing my best for AI safety—for example, by shepherding watermarking toward deployment. After a long delay, I’m gratified that interest in watermarking has spiked recently, not only within OpenAI and other companies but among legislative bodies in the US and Europe.

And afterwards? I’ll certainly continue thinking about how AI is changing the world and how (if at all) we can steer its development to avoid catastrophes, because how could I not think about that? I spent 15 years mostly avoiding the subject, and that now seems like a huge mistake, and probably like enough of that mistake for one lifetime.

So I’ll continue looking for juicy open problems in complexity theory that are motivated by interpretability, or scalable oversight, or dangerous capability evaluations, or other aspects of AI safety—I’ve already identified a few such problems! And without giving up on quantum computing (because how could I?), I expect to reorient at least some of my academic work toward problems at the interface of theoretical computer science and AI safety, and to recruit students who want to work on those problems, and to apply for grants about them. And I’ll presumably continue giving talks about this stuff, and doing podcasts and panels and so on—anyway, as long as people keep asking me to!

And I’ll be open to future sabbaticals or consulting arrangements with AI organizations, like the one I’ve done at OpenAI. But I expect that my main identity will always be as an academic. Certainly I never want to be in a position where I have to speak for an organization rather than myself, or censor what I can say in public about the central problems I’m working on, or sign a nondisparagement agreement or anything of the kind.

I can tell you this: in two years at OpenAI, hanging out at the office and meeting the leadership and rank-and-file engineers, I never once found a smoke-filled room where they laugh at all the rubes who take the talk about “safety” and “alignment” seriously. While my interactions were admittedly skewed toward safetyists, the OpenAI folks I met were invariably smart and earnest and dead serious about the mission of getting AI right for humankind.

It’s more than fair for outsiders to ask whether that’s enough, whether even good intentions can survive bad incentives. It’s likewise fair of them to ask: what fraction of compute and other resources ought to be set aside for alignment research? What exactly should OpenAI do on alignment going forward? What should governments force them and other AI companies to do? What should employees and ex-employees be allowed, or encouraged, to share publicly?

I don’t know the answers to these questions, but if you do, feel free to tell me in the comments!

When I learned of Jim Simons’s passing, I was actually at the Simons Foundation headquarters in lower Manhattan, for the annual board meeting of the unparalleled Quanta Magazine, which Simons founded and named. The meeting was interrupted to share the sad news, before it became public … and then it was continued, because that’s obviously what Simons would’ve wanted. An oil portrait of Simons in the conference room took on new meaning.

See here for the Simons Foundation’s announcement, or here for the NYT’s obituary.

Although the Simons Foundation has had multiple significant influences on my life—funding my research, founding the Simons Institute for Theory of Computing in Berkeley that I often visit (including two weeks ago), and much more—I’ve exchanged all of a few sentences with Jim Simons himself. At a previous Simons Foundation meeting, I think he said he’d heard I’d moved from MIT to UT Austin, and asked whether I’d bought a cowboy hat yet. I said I did but I hadn’t yet worn it non-ironically, and he laughed at that. (My wife Dana knew him better, having spent a day at a brainstorming meeting for what became the Simons Institute, his trademark cigar smoke filling the room.)

I am, of course, in awe of what Jim Simons achieved in all three phases of his career — firstly, in mathematical research, where he introduced the Chern-Simons form and other pioneering contributions and led the math department at Stony Brook; secondly, in founding Renaissance and making insane amounts of money (“disproving the Efficient Market Hypothesis,” as some have claimed); and thirdly, in giving his money away to support basic research and the public understanding of it.

I’m glad that Simons, as a lifelong chain smoker, made it all the way to age 86. And I’m glad that the Simons Foundation, which I’m told will continue in perpetuity with no operational changes, will stand as a testament to his vision for the world.

Unrelated Announcements: See here for a long interview with me in The Texas Orator, covering the usual stuff (quantum computing, complexity theory, AI safety). And see here for a podcast with me and Spencer Greenberg about a similar mix of topics.

---

A couple weeks ago, I helped organize UmeshFest: Don’t Miss This Flight, a workshop at UC Berkeley’s Simons Institute to celebrate the 2⁶th birthday of my former PhD adviser Umesh Vazirani. Peter Shor, John Preskill, Manuel Blum, Madhu Sudan, Sanjeev Arora, and dozens of other luminaries of quantum and classical computation were on hand to help tell the story of quantum computing theory and Umesh’s central role in it. There was also constant roasting of Umesh—of his life lessons from the squash court, his last-minute organizational changes and phone calls at random hours. I was delighted to find that my old coinage of “Umeshisms” was simply standard usage among the attendees.

---

At Berkeley, many things were as I remembered them—my favorite Thai eatery, the bubble tea, the Campanile—but not everything was the same. Here I am in front of Berkeley’s Gaza encampment, a.k.a. its “Anti Zionism Zone” or what was formerly Sproul Plaza (zoom into the chalk):

I felt a need to walk through the Anti Zionism Zone day after day (albeit unassumingly, neither draped in an Israeli flag nor looking to start an argument with anyone), for more-or-less the same reasons why the US regularly sends aircraft carriers through the Strait of Taiwan.

---

Back in the more sheltered environment of the Simons Institute, it was great to be among friends, some of whom I hadn’t seen since before Covid. Andris Ambainis and I worked together for a bit on an open problem in quantum query complexity, for old times’ sake (we haven’t solved it yet).

And then there were talks! I thought I’d share my own talk, which was entitled The Story of BQP (Bounded-Error Quantum Polynomial-Time). Here are the PowerPoint slides, but I’ll also share screen-grabs for those of you who constantly complain that you can’t open PPTX files.

I was particularly proud of the design of my title slide:

Moving on:

The class BQP/qpoly, I should explain, is all about an advisor who’s all-wise and perfectly benevolent, but who doesn’t have a lot of time to meet with his students, so he simply doles out the same generic advice to all of them, regardless of their thesis problem x.

I then displayed my infamous “Umeshisms” blog post from 2005—one of the first posts in the history of this blog:

As I explained, now that I hang out with the rationalist and AI safety communities, which are also headquartered in Berkeley, I’ve learned that my “Umeshisms” post somehow took on a life of its own. Once, when dining at one of the rationalists’ polyamorous Berkeley group houses, I said this has been lovely but I’ll now need to leave, to visit my PhD former adviser Umesh Vazirani. “You mean the Umesh?!” the rationalists excitedly exclaimed. “Of Umeshisms? If you’ve never missed a flight?”

But moving on:

(Note that by “QBPP,” Bethiaume and Brassard meant what we now call BQP.)

Feynman and Deutsch asked exactly the right question—does simulating quantum mechanics on a classical computer inherently produce an exponential slowdown, or not?—but they lacked most of the tools to start formally investigating the question. A factor-of-two quantum speedup for the XOR function could be dismissed as unimpressive, while a much greater quantum speedup for the “constant vs. balanced” problem could be dismissed as a win against only deterministic classical algorithms, rather than randomized algorithms. Deutsch-Jozsa may have been the first time that an apparent quantum speedup faltered in an honest comparison against classical algorithms. It certainly wasn’t the last!

Ah, but this is where Bernstein and Vazirani enter the scene.

Bernstein and Vazirani didn’t merely define BQP, which remains the central object of study in quantum complexity theory. They also established its most basic properties:

And, at least in the black-box model, Bernstein and Vazirani gave the first impressive quantum speedup for a classical problem that survived in a fair comparison against the best classical algorithm:

The Recursive Bernstein-Vazirani problem, also called Recursive Fourier Sampling, is constructed as a “tree” of instances of the Bernstein-Vazirani problem, where to query the Boolean function at any given level, you need to solve a Bernstein-Vazirani problem for a Boolean function at the level below it, and then run the secret string s through a fixed Boolean function g. For more, see my old paper Quantum Lower Bound for Recursive Fourier Sampling.

Each Bernstein-Vazirani instance has classical query complexity n and quantum query complexity 1. So, if the tree of instances has depth d, then overall the classical query complexity is n^d, while the quantum query complexity is only 2^d. Where did the 2 come from? From the need to uncompute the secret strings s at each level, to enable quantum interference at the next level up—thereby forcing us to run the algorithm twice. A key insight.

The Recursive Fourier Sampling separation set the stage for Simon’s algorithm, which gave a more impressive speedup in the black-box model, and thence for the famous Shor’s algorithm for factoring and discrete log:

But Umesh wasn’t done establishing the most fundamental properties of BQP! There’s also the seminal 1994 paper by Bennett, Bernstein, Brassard, and Vazirani:

In light of the BV and BBBV papers, let’s see how BQP seems to fit with classical complexity classes—an understanding that’s remained largely stable for the past 30 years:

We can state a large fraction of the research agenda of the whole field, to this day, as questions about BQP:

I won’t have time to discuss all of these questions, but let me at least drill down on the first few.

Many people hoped the list of known problems in BQP would now be longer than it is. So it goes: we don’t decide the truth, we only discover it.

As a 17-year-old just learning about quantum computing in 1998 by reading the Bernstein-Vazirani paper, I was thrilled when I managed to improve their containment BQP ⊆ P^#P to BQP ⊆ PP. I thought that would be my big debut in quantum complexity theory. I was then crushed when I learned that Adleman, DeMarrais, and Huang had proved the same thing a year prior. OK, but at least it wasn’t, like, 50 years prior! Maybe if I kept at it, I’d reach the frontier soon enough.

Umesh, from the very beginning, raised the profound question of BQP’s relation to the polynomial hierarchy. Could we at least construct an oracle relative to which BQP⊄PH—or, closely related, relative to which P=NP≠BQP? Recursive Fourier Sampling was a already candidate for such a separation. I spent months trying to prove that candidate wasn’t in PH, but failed. That led me eventually to propose a very different problem, Forrelation, which seemed like a stronger candidate, although I couldn’t prove that either. Finally, in 2018, after four years of effort, Ran Raz and Avishay Tal proved that my Forrelation problem was not in PH, thereby resolving Umesh’s question after a quarter century.

We now know three different ways by which a quantum computer can not merely solve any BQP problem efficiently, but prove its answer to a classical skeptic via an interactive protocol! Using quantum communication, using two entangled (but non-communicating) quantum computers, or using cryptography (this last a breakthrough of Umesh’s PhD student Urmila Mahadev). It remains a great open problem, first posed to my knowledge by Daniel Gottesman, whether one can do it with none of these things.

To see many of the advantages of quantum computation over classical, we’ve learned that we need to broaden our vision beyond BQP (which is a class of languages), to promise problems (like estimating the expectation values of observables), sampling problems (like BosonSampling and Random Circuit Sampling), and relational problems (like the Yamakawa-Zhandry problem, subject of a recent breakthrough). It’s conceivable that quantum advantage could remain for such problems even if it turned out that P=BQP.

A much broader question is whether BQP captures all languages that can be efficiently decided using “reasonable physical resources.” What about chiral quantum field theories, like the Standard Model of elementary particles? What about quantum theories of gravity? Good questions!

Since it was Passover during the talk, I literally said “Dayenu” to Umesh: “if you had only given us BQP, that would’ve been enough! but you didn’t, you gave us so much more!”

Happy birthday Umesh!! We look forward to celebrating again on all your subsequent power-of-2 birthdays.