Shtetl-Optimized

Scott’s foreword: Today I’m honored to turn over Shtetl-Optimized to a guest post from Michigan theoretical computer scientist Seth Pettie, who writes about a SOSA Best Paper Award newly renamed in honor of the late Mihai Pătrașcu. Mihai, who I knew from his student days, was a brash, larger-than-life figure in theoretical computer science, for a brief few years until brain cancer tragically claimed him at the age of 29. Mihai and I didn’t always agree—indeed, I don’t think he especially liked me, or this blog—but as I wrote when he passed, his death made any squabbles seem trivial in retrospect. He was a lion of data structures, and it’s altogether fitting that this award be named for him. –SA

Seth’s guest post:

The SIAM Symposium on Simplicity in Algorithms (SOSA) was created in 2018 and has been awarding a Best Paper Award since 2020. This year the Steering Committee renamed this award after Mihai Pătrașcu, an extraordinary researcher in theoretical computer science who passed away before his time, in 2012.

Mihai’s research career lasted just a short while, from 2004-2012, but in that span of time he had a huge influence on research in geometry, graph algorithms, data structures, and especially lower bounds. He revitalized the entire areas of cell-probe lower bounds and succinct data structures, and laid the foundation for fine-grained complexity with the first 3SUM-hardness proof for graph problems. He lodged the most successful attack to date on the notorious dynamic optimality conjecture, then recast it
as a pure geometry problem. If you are too young to have met Mihai personally, I encourage you to pick up one of his now-classic papers. They are a real joy to read—playful and full of love for theoretical computer science.

The premise of SOSA is that simplicity is extremely valuable, rare, and inexplicably undervalued. We wanted to create a venue where the chief metrics of success were simplicity and insight. It is fitting that the SOSA Best Paper Award be named after Mihai. He brought “fresh eyes” to every problem he worked on, and showed that the cure for our problems is usually one key insight (and of course some mathematical gymnastics).

Let me end by thanking the SOSA 2026 Program Committee, co-chaired by Sepehr Assadi and Eva Rotenberg, and congratulating the authors of the SOSA 2026 Mihai Pătrașcu Best Paper:

• A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
  Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov, Vaishali Surianarayanan

This award will be given at the SODA/SOSA business meeting in Vancouver, Canada, on January 12, 2026.

Follow

A 9-year-old named Kai (“The Quantum Kid”) and his mother interviewed me about closed timelike curves, wormholes, Deutsch’s resolution of the Grandfather Paradox, and the implications of time travel for computational complexity:

This is actually one of my better podcasts (and only 24 minutes long), so check it out!

Here’s a podcast I did a few months ago with “632nm” about P versus NP and my other usual topics:

For those who still can’t get enough, here’s an interview about AI alignment for the “Hidden Layers” podcast that I did a year ago, and that I think I forgot to share on this blog at the time:

What else is in the back-catalog? Ah yes: the BBC interviewed me about quantum computing for a segment on Moore’s Law.

As you may have heard, Steven Pinker recently wrote a fantastic popular book about the concept of common knowledge, entitled When Everyone Knows That Everyone Knows… Steve’s efforts render largely obsolete my 2015 blog post Common Knowledge and Aumann’s Agreement Theorem, one of the most popular posts in this blog’s history. But I’m willing to live with that, not only because Steven Pinker is Steven Pinker, but also because he used my post as a central source for the topic. Indeed, you should watch his podcast with Richard Hanania, where Steve lucidly explains Aumann’s Agreement Theorem, noting how he first learned about it from this blog.

Follow

Tomorrow I’m headed to Berkeley for the Inkhaven blogging residency, whose participants need to write one blog post per day or get kicked out. I’ll be there to share my “wisdom” as a distinguished elder blogger (note that Shtetl-Optimized is now in its twentieth year). I’m acutely aware of the irony, that I myself can barely muster the willpower these days to put up a post every other week.

And it’s not as if nothing is happening in this blog’s traditional stomping-ground of quantum computing! In fact, the issue is just the opposite: way too much is happening for me to do it any sort of justice. Who do people think I am, Zvi Mowshowitz? The mere thought of being comprehensive, of responsibly staying on top of all the latest QC developments, makes me want to curl up in bed, and either scroll through political Substacks or take a nap.

But then, you know, eventually a post gets written. Let me give you some vignettes about what’s new in QC, any one of which could easily have been its own post if I were twenty years younger.

(1) Google announced verifiable quantum advantage based on Out-of-Time-Order-Correlators (OTOC)—this is actually from back in June, but it’s gotten more and more attention as Google has explained it more thoroughly. See especially this recent 2-page note by King, Kothari, et al., explaining Google’s experiment in theoretical computer science language. Basically, what they do is, starting from the all-|0⟩ state, to apply a random circuit C, then a single gate g, then C^-1, then another gate h, then C again, then g again, then C^-1, and then measure a qubit. If C is shallow, then the qubit is likely to still be |0⟩. If C is too deep, then the qubit is likely to be in the maximally mixed state, totally uncorrelated with its initial state—the gates g and h having caused a “butterfly effect” that completely ruined all the cancellation between C and C^-1. Google claims that, empirically, there’s an intermediate regime where the qubit is neither |0⟩ nor the maximally mixed state, but a third thing—and that this third thing seems hard to determine classically, using tensor network algorithms or anything else they’ve thrown at it, but it can of course be determined by running the quantum computer. Crucially, because we’re just trying to estimate a few parameters here, rather than sample from a probability distribution (as with previous quantum supremacy experiments), the output can be checked by comparing it against the output of a second quantum computer, even though the problem still isn’t in NP. Incidentally, if you’re wondering why they go back and forth between C and C^-1 multiple times rather than just once, it’s to be extra confident that there’s not a fast classical simulation. Of course there might turn out to be a fast classical simulation anyway, but if so, it will require a new idea: gauntlet thrown.

(2) Quantinuum, the trapped-ion QC startup in Colorado, announced its Helios processor. Quick summary of the specs: 98 qubits, all-to-all 2-qubit gates with 99.92% fidelity, the ability to choose which gates to apply “just in time” (rather than fixing the whole circuit in advance, as was needed with their previous API), and an “X”-shaped junction for routing qubits one way or the other (the sort of thing that a scalable trapped-ion quantum computer will need many of). This will enable, and is already enabling, more and better demonstrations of quantum advantage.

(3) Quantinuum and JP Morgan Chase announced the demonstration of a substantially improved version of my and Shih-Han-Hung’s protocol for generating cryptographically certified random bits, using quantum supremacy experiments based on random circuit sampling. They did their demo on Quantinuum’s new Helios processor. Compared to the previous demonstration, the new innovation is to send the circuit to the quantum computer one layer at a time, rather than all at once (something that, again, Quantinuum’s new API allows). The idea is that a cheating server, who wanted to spoof the randomness deterministically, now has much less time: using the most competitive known methods (e.g., those based on tensor network contraction), it seems the cheater would need to swing into action only after learning the final layer of gates, so would now have mere milliseconds to spoof rather than seconds, making Internet latency the dominant source of spoofing time in practice. While a complexity-theoretic analysis of the new protocol (or, in general, of “layer-by-layer” quantum supremacy protocols like it) is still lacking, I like the idea a lot.

(4) The startup company BlueQubit announced a candidate demonstration of verifiable quantum supremacy via obfuscated peaked random circuits, again on a Quantinuum trapped-ion processor (though not Helios). In so doing, BlueQubit is following the program that Yuxuan Zhang and I laid out last year: namely, generate a quantum circuit C that hopefully looks random to any efficient classical algorithm, but that conceals a secret high-probability output string x, which pops out if you run C on a quantum computer on the all-0 initial state. To try to hide x, BlueQubit uses at least three different circuit obfuscation techniques, which already tells you that they can’t have complete confidence in any one of them (since if they did, why the other two?). Nevertheless, I’m satisfied that they tried hard to break their own obfuscation, and failed. Now it’s other people’s turn to try.

(5) Deshpande, Fefferman, et al. announced a different theoretical proposal for quantum advantage from peaked quantum circuits, based on error-correcting codes. This seems tempting to try to demonstrate along the way to quantum fault-tolerance.

(6) A big one: John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry announced a proof of a classical oracle separation between the complexity classes QMA and QCMA, something that they’ve been working on for well over a year. Their candidate problem is basically a QMA-ified version of my Forrelation, which Raz and Tal previously used to achieve an oracle separation between BQP and PH. I caution that their paper is 91 pages long and hasn’t yet been vetted by independent experts, and there have been serious failed attempts on this exact problem in this past. If this stands, however, it finally settles a problem that’s been open since 2002 (and which I’ve worked on at various points starting in 2002), and shows a strong sense in which quantum proofs are more powerful than classical proofs. Note that in 2006, Greg Kuperberg and I gave a quantum oracle separation between QMA and QCMA—introducing the concept of quantum oracles for the specific purpose of that result—and since then, there’s been progress on making the oracle steadily “more classical,” but the oracle was always still randomized or “in-place” or had restrictions on how it could be queried.

(7) Oxford Ionics (which is now owned by IonQ) announced a 2-qubit gate with 99.99% fidelity: a record, and significantly past the threshold for quantum fault-tolerance. However, as far as I know, it remains to demonstrate this sort of fidelity in a large programmable system with dozens of qubits and hundreds of gates.

(8) Semi-announcement: Quanta reports that “Physicists Take the Imaginary Numbers Out of Quantum Mechanics,” and this seems to have gone viral on my social media. The article misses the opportunity to explain that “taking the imaginary numbers out” is as trivial as choosing to call each complex amplitude “just an ordered pair of reals, obeying such-and-such rules, which happen to mimic the rules for complex numbers.” Thus, the only interesting question here is whether one can take imaginary numbers out of QM in various more-or-less “natural” ways: a technical debate that the recent papers are pushing forward. For what it’s worth, I don’t expect that anything coming out of this line of work will ever be “natural” enough for me to stop explaining QM in terms of complex numbers in my undergraduate class, for example.

(9) The list of accepted talks for the annual QIP conference, to be held January 24-30 in Riga, Latvia, is now out. Lots of great stuff as always.

(10) There are probably other major recent developments in QC that I should’ve put into this post but forgot about. You can remind me about them in the comments.

(11) Indeed there are! I completely forgot that Phasecraft announced two simulations of fermionic systems that might achieve quantum advantage, one using Google’s Willow superconducting chip and the other using a Quantinuum device.

To summarize three takeaways:

• Evidence continues to pile up that we are not living in the universe of Gil Kalai and the other quantum computing skeptics. Indeed, given the current staggering rate of hardware progress, I now think it’s a live possibility that we’ll have a fault-tolerant quantum computer running Shor’s algorithm before the next US presidential election. And I say that not only because of the possibility of the next US presidential election getting cancelled, or preempted by runaway superintelligence!
  
• OK, but what will those quantum computers be useful for? Anyone who’s been reading this blog for the past 20 years, or any non-negligible fraction thereof, hopefully already has a calibrated sense of that, so I won’t belabor. But briefly: yes, our knowledge of useful quantum algorithms has slowly been expanding over the past thirty years. The central difficulty is that our knowledge of useful classical algorithms has also been expanding, and the only thing that matters is the differential between the two! I’d say that the two biggest known application areas for QC remain (a) quantum simulation and (b) the breaking of public-key cryptography, just as they were thirty years ago. In any case, none of the exciting developments that I’ve chosen to highlight in this post directly address the “what is it good for?” question, with the exception of the certified randomness thing.
  
• In talks over the past three years, I’ve advocated “verifiable quantum supremacy on current hardware” as perhaps the central challenge right now for quantum computing theory. (As I love to point out, we do know how to achieve any two of (a) quantum supremacy that’s (b) verifiable and (c) runs on current hardware!) So I’m gratified that three of the recent developments that I chose to highlight, namely (1), (4), and (5), directly address this challenge. Of course, we’re not yet sure whether any of these three attempts will stand—that is, whether they’ll resist all attempts to simulate them classically. But the more serious shots on goal we have (and all three of these are quite serious), the better the chances that at least one will stand! So I’m glad that people are sticking their necks out, proposing these things, and honestly communicating what they know and don’t know about them: this is exactly what I’d hoped would happen. Of course, complexity-theoretic analysis of these proposals would also be great, perhaps from people with more youth and/or energy than me. Now it’s time for me to sleep.

Follow

A month ago William Inboden, the provost of UT Austin (where I work), invited me to join a university-wide “Faculty Working Group on Academic Integrity.” The name made me think that it would be about students cheating on exams and the like. I didn’t relish the prospect but I said sure.

Shortly afterward, Jim Davis, the president of UT Austin, sent out an email listing me among 21 faculty who had agreed to serve on an important working group to decide UT Austin’s position on academic free speech and the responsibilities of professors in the classroom (!). Immediately I started getting emails from my colleagues, thanking me for my “service” and sharing their thoughts about what this panel needed to say in response to the Trump administration’s Compact on Higher Education. For context: the Compact would involve universities agreeing to do all sorts of things that the Trump administration wants—capping international student enrollment, “institutional neutrality,” freezing tuition, etc. etc.—in exchange for preferential funding. UT Austin was one of nine universities originally invited to join the Compact, along with MIT, Penn, Brown, Dartmouth, and more, and is the only one that hasn’t yet rejected it. It hasn’t accepted it either.

Formally, it was explained to me, UT’s Working Group on Academic Integrity had nothing to do with Trump’s Compact, and no mandate to either accept or reject it. But it quickly became obvious to me that my faculty colleagues would see everything we did exclusively in light of the Compact, and of other efforts by the Trump administration and the State of Texas to impose conservative values on universities. While not addressing current events directly, what we could do would be to take a strong stand for academic freedom, and more generally, for the role of intellectually independent universities in a free society.

So, led by Provost Inboden, over two meetings and a bunch of emails we hashed out a document. You can now read the Texas Statement on Academic Integrity, and I’d encourage you to do so. The document takes a pretty strong swing for academic freedom:

Academic freedom lies at the core of the academic enterprise.  It is foundational to the excellence of the American higher education system, and is non-negotiable. In the words of the U.S. Supreme Court, academic freedom is “a special concern of the First Amendment.” The world’s finest universities are in free societies, and free societies honor academic freedom.

The statement also reaffirms UT Austin’s previous commitments to the Chicago Principles of Free Expression, and the 1940 and 1967 academic freedom statements of the American Association of University Professors.

Without revealing too much about my role in the deliberations, I’ll say that I was especially pleased by the inclusion of the word “non-negotiable.” I thought that that word might acquire particular importance, and this was confirmed by the headline in yesterday’s Chronicle of Higher Education: As Trump’s Compact Looms, UT-Austin Affirms ‘Non-Negotiable’ Commitment to Academic Freedom (warning: paywall).

At the same time, the document also talks about the responsibility of a public university to maintain the trust of society, and about the responsibilities of professors in the classroom:

Academic integrity obligates the instructor to protect every student’s academic freedom and right to learn in an environment of open inquiry. This includes the responsibilities:

• to foster classroom cultures of trust in which all students feel free to voice their questions and beliefs, especially when those perspectives might conflict with those of the instructor or other students;
• to fairly present differing views and scholarly evidence on reasonably disputed matters and unsettled issues;
• to equip students to assess competing theories and claims, and to use reason and appropriate evidence to form their own conclusions about course material; and
• to eschew topics and controversies that are not germane to the course.

All stuff that I’ve instinctively followed, in nearly 20 years of classroom teaching, without the need for any statement telling me to. Whatever opinions I might get goaded into expressing on this blog about Trump, feminism, or Israel/Palestine, I’ve always regarded the classroom as a sacred space. (I have hosted a few fierce classroom debates about the interpretation of quantum mechanics, but even there, I try not to tip my own hand!)

I’m sure that there are commenters, on both ends of the political spectrum, who will condemn me for my participation in the faculty working group, and for putting my name on the statement. At this point in this blog’s history, commenters on both ends of the political spectrum would condemn me for saying that freshly baked chocolate chip cookies are delicious. But I like the statement, and find nothing in it that any reasonable person should disagree with. Overall, my participation in this process increased my confidence that UT Austin will be able to navigate this contentious time for the state, country, and world while maintaining its fundamental values. It made me proud to be a professor here.

Follow

This year for STOC, we decided to run an experiment to explore the use of Large Language Models in the theoretical computer science community, and we’re inviting the entire community to participate.

We—a team from the STOC PC—are offering authors the chance to get automated pre-submission feedback from an advanced, Gemini-based LLM tool that’s been optimized for checking mathematical rigor. The goal is simple: to provide constructive suggestions and, potentially, help find technical mistakes before the paper goes to the PC. Some important points:

• This is 100% optional and opt-in.
  
• The reviews generated WILL NOT be passed on to the PC. They are for your eyes only.
  
• Data Privacy is Our #1 Commitment. We commit that your submitted paper will NOT be logged, stored, or used for training.
  
• Please do not publicly share these reviews without contacting the organizing team first.

This tool is specifically optimized for checking a paper’s mathematical rigor. It’s a hopefully useful way to check the correctness of your arguments. Note that sometimes it does not possess external, area-specific knowledge (like “folklore” results). This means it may flag sections that rely on unstated assumptions, or it might find simple omissions or typos.

Nevertheless, we hope you’ll find this feedback valuable for improving the paper’s overall clarity and completeness.

If you’re submitting to STOC, we encourage you to opt-in. You’ll get (we hope) useful feedback, and you’ll be providing invaluable data as we assess this tool for future theory conferences.

The deadline to opt-in on the HotCRP submission form is November 1 (5pm EST).

You can read the full “Terms of Participation” (including all privacy and confidentiality details) at the link below.

This experiment is being run by PC members David Woodruff (CMU) and Rajesh Jayaram (Google), as well as Vincent Cohen-Addad (Google) and Jon Schneider (Google).

We’re excited to offer this resource to the community.

Please see the STOC Call for Papers here and specific details on the experiment here.

Follow

Today, of course, is the second anniversary of the genocidal Oct. 7 invasion of Israel—the deadliest day for Jews since the Holocaust, and the event that launched the current wars that have been reshaping the Middle East for better and/or worse. Regardless of whether their primary concern is for Israelis, Palestinians, or both, I’d hope all readers of this blog could at least join me in wishing this barbaric invasion had never happened, and in condemning the celebrations of it taking place around the world.

Now for the happy part: today is also the day when the Nobel Prize in Physics is announced. I was delighted to wake up to the news that this year, the prize goes to John Clarke of Berkeley, John Martinis of UC Santa Barbara, and Michel Devoret of UC Santa Barbara (formerly Yale), for their experiments in the 1980s that demonstrated the reality of macroscopic quantum tunneling in superconducting circuits. Among other things, this work laid the foundation for the current effort by Google, IBM, and many others to build quantum computers with superconducting qubits. To clarify, though, today’s prize is not for quantum computing per se, but for the earlier work.

While I don’t know John Clarke, and know Michel Devoret only a little, I’ve been proud to count John Martinis as a good friend for the past decade—indeed, his name has often appeared on this blog. When Google hired John in 2014 to build the first programmable quantum computer capable of demonstrating quantum supremacy, it was clear that we’d need to talk about the theory, so we did. Through many email exchanges, calls, and visits to Google’s Santa Barbara Lab, I came to admire John for his iconoclasm, his bluntness, and his determination to make sampling-based quantum supremacy happen. After Google’s success in 2019, I sometimes wondered whether John might eventually be part of a Nobel Prize in Physics for his experimental work in quantum computing. That may have become less likely today, now that he’s won the Nobel Prize in Physics for his work before quantum computing, but I’m guessing he doesn’t mind! Anyway, huge congratulations to all three of the winners.

Follow

Update (September 24): A sympathetic correspondent wrote to tip me off that this blog post has caused me to get added to a list, maintained by MAGA activists and circulated by email, of academics and others who ought to “[face] some consequences for maligning the patriotic MAGA movement.” Needless to say, not only did this post unequivocally condemn Charlie Kirk’s murder, it even mentioned areas of common ground between me and Kirk, and my beefs with the social-justice left. If someone wants to go to the Texas Legislature to get me fired, literally the only thing they’ll have on me is that I “maligned the patriotic MAGA movement,” i.e. expressed political views shared by the majority of Americans.

Still, it’s a strange honor to have had people on both extremes of the ideological spectrum wanting to cancel me for stuff I’ve written on this blog. What is tenure for, if not this?

Another Update: In a dark and polarized age like ours, one thing that gives hope is the prospect of rational agents updating on each others’ knowledge to come to agreement. On that note, please enjoy this recent podcast, in which a 95-year-old Robert Aumann explains Aumann’s agreement theorem in his own words (see here for my old post about it, one of the most popular in the history of this blog).

From 2016 until last week, as the Trump movement dismantled one after another of the obvious bipartisan norms of the United States that I’d taken for granted since my childhood—e.g., the loser conceding an election and attending the winner’s inauguration, America being proudly a nation of immigrants, science being good, vaccines being good, Russia invading its neighbors being bad, corruption (when it occurred) not openly boasted about—I often consoled myself that at least the First Amendment, the motor of our whole system since 1791, was still in effect. At least you could still call Trump a thug and a conman without fear. Yes, Trump constantly railed against hostile journalists and comedians and protesters, threatened them at his rallies, filed frivolous lawsuits against them, but none of it seemed to lead to any serious program to shut them down. Oceans of anti-Trump content remained a click away.

I even wondered whether this was Trump’s central innovation in the annals of authoritarianism: proving that, in the age of streaming and podcasts and social media, you no longer needed to bother with censorship in order to build a regime of lies. You could simply ensure that the truth remained one narrative among others, that it never penetrated the epistemic bubble of your core supporters, who’d continue to be algorithmically fed whatever most flattered their prejudices.

Last week, that all changed. Another pillar of the previous world fell. According to the new norm, if you’re a late-night comedian who says anything Trump doesn’t like, he’ll have the FCC threaten your station’s affiliates’ broadcast licenses, and they’ll cave, and you’ll be off the air, and he’ll gloat about it. We ought to be clear that, even conditioned on everything else, this is a huge further step toward how things work in Erdogan’s Turkey or Orban’s Hungary, and how they were never supposed to work in America.

At risk of stating the obvious:

• I was horrified by the murder of Charlie Kirk. Political murder burns our societal commons and makes the world worse in every way. I’d barely been aware of Kirk before the murder, but it seems clear he was someone with whom I’d have countless disagreements, but also some common ground, for example about Israel. Agree or disagree is beside the point, though. One thing we can all hopefully take from the example of Kirk’s short life, regardless of our beliefs, is his commitment to “Prove Me Wrong” and “Change My Mind”: to showing up on campus (or wherever people are likeliest to disagree with us) and exchanging words rather than bullets.
  
• I’m horrified that there are fringe figures on social media who’ve celebrated Kirk’s murder or made light of it. I’m fine with such people losing their jobs, as I’d be with those who celebrate any political murder.
  
• It looks like Kirk’s murderer was a vaguely left-wing lunatic, with emphasis on the “lunatic” part (as often with these assassins, his worldview wasn’t particularly coherent). Jimmy Kimmel was wrong to insinuate that the murderer was a MAGA conservative. But he was “merely” wrong. By no stretch of the imagination did Kimmel justify or celebrate Kirk’s murder.
  
• If the new rule is that anyone who spreads misinformation gets cancelled by force of government, then certainly Fox News, One America News, Joe Rogan, and MAGA’s other organs of support should all go dark immediately.
  
• Yes, I’m aware (to put it mildly) that, especially between 2015 and 2020, the left often used its power in media, academia, and nonprofits to try to silence those with whom it disagreed, by publicly shaming them and getting them blacklisted and fired. That was terrible too. I opposed it at the time, and in the comment-171 affair, I even risked my career to stand up to it.
  
• But censorship backed by the machinery of state is even worse than social-media shaming mobs. As I and many others discovered back then, to our surprised relief, there are severe limits to the practical power of angry leftists on Twitter and Reddit. That was true then, and it’s even truer today. But there are far fewer limits to the power of a government, especially one that’s been reorganized on the principle of obedience to one man’s will. The point here goes far beyond “two wrongs don’t make a right.” As pointed out by that bleeding-heart woke, Texas Senator Ted Cruz, new weapons are being introduced that the other side will also be tempted to use when it retakes power. The First Amendment now has a knife to its throat, as it didn’t even at the height of the 2015-2020 moral panic.
  
• Yes, five years ago, the federal government pressured Facebook and other social media platforms to take down COVID ‘misinformation,’ some of which turned out not to be misinformation at all. That was also bad, and indeed it dramatically backfired. But let’s come out and say it: censoring medical misinformation because you’re desperately trying to save lives during a global pandemic is a hundred times more forgivable than censoring comedians because they made fun of you. And no one can deny that the latter is the actual issue here, because Trump and his henchmen keep saying the quiet part out loud.

Anyway, I keep hoping that my next post will be about quantum complexity theory or AI alignment or Busy Beaver 6 or whatever. Whenever I feel backed into a corner, however, I will risk my career, and the Internet’s wrath, to blog my nutty, extreme, embarrassing, totally anodyne liberal beliefs that half or more of Americans actually share.

Follow

I’m thrilled that our paper entitled Demonstrating an unconditional separation between quantum and classical information resources, based on a collaboration between UT Austin and Quantinuum, is finally up on the arXiv. I’m equally thrilled that my coauthor and former PhD student William Kretschmer — who led the theory for this project, and even wrote much of the code — is now my faculty colleague at UT Austin! My physics colleague Nick Hunter-Jones and my current PhD student Sabee Grewal made important contributions as well. I’d especially like to thank the team at Quantinuum for recognizing a unique opportunity to test and showcase their cutting-edge hardware, and collaborating with us wild-eyed theorists to make it happen. This is something that, crucially, would not have been feasible with the quantum computing hardware of only a couple years ago.

Here’s our abstract, which I think explains what we did clearly enough, although do read the paper for more:

A longstanding goal in quantum information science is to demonstrate quantum computations that cannot be feasibly reproduced on a classical computer. Such demonstrations mark major milestones: they showcase fine control over quantum systems and are prerequisites for useful quantum computation. To date, quantum advantage has been demonstrated, for example, through violations of Bell inequalities and sampling-based quantum supremacy experiments. However, both forms of advantage come with important caveats: Bell tests are not computationally difficult tasks, and the classical hardness of sampling experiments relies on unproven complexity-theoretic assumptions. Here we demonstrate an unconditional quantum advantage in information resources required for a computational task, realized on Quantinuum’s H1-1 trapped-ion quantum computer operating at a median two-qubit partial-entangler fidelity of 99.941(7)%. We construct a task for which the most space-efficient classical algorithm provably requires between 62 and 382 bits of memory, and solve it using only 12 qubits. Our result provides the most direct evidence yet that currently existing quantum processors can generate and manipulate entangled states of sufficient complexity to access the exponentiality of Hilbert space. This form of quantum advantage — which we call quantum information supremacy — represents a new benchmark in quantum computing, one that does not rely on unproven conjectures.

I’m very happy to field questions about this paper in the comments section.

Unrelated Announcement: As some of you might have seen, yesterday’s Wall Street Journal carried a piece by Dan Kagan-Kans on “The Rise of ‘Conspiracy Physics.'” I talked to the author for the piece, and he quoted this blog in the following passage:

This resentment of scientific authority figures is the major attraction of what might be called “conspiracy physics.” Most fringe theories are too arcane for listeners to understand, but anyone can grasp the idea that academic physics is just one more corrupt and self-serving establishment. The German physicist Sabine Hossenfelder has attracted 1.72 million YouTube subscribers in part by attacking her colleagues: “Your problem is that you’re lying to the people who pay you,” she declared. “Your problem is that you’re cowards without a shred of scientific integrity.”

In this corner of the internet, the scientist Scott Aaronson has written, “Anyone perceived as the ‘mainstream establishment’ faces a near-insurmountable burden of proof, while anyone perceived as ‘renegade’ wins by default if they identify any hole whatsoever in mainstream understanding.”

Follow

(1) My 8-year-old son asked me last week, “daddy, did you hear that GPT-5 is now out?” So yes, I’m indeed aware that GPT-5 is now out! I’ve just started playing around with it. For detailed reports on what’s changed and how impressive it is compared to previous models, see for example Zvi #1, #2, #3. Briefly, it looks like there are major reductions in hallucinations and sycophancy, and improvements in practical usefulness for coding and other tasks, even while the “raw intelligence” is unlikely to blow away someone who was already well-acquainted with o3 and Opus 4 other state-of-the-art models, the way ChatGPT and then GPT-4 blew away people who had no idea what was possible in late 2022 and early 2023. Partly how impressive a result you see depends on which of several GPT-5 models your query gets routed to, which you don’t entirely control. Anyway, there’s grist here for the people who claim that progress toward AGI is slowing down, but also grist for the people who claim that it continues pretty much as expected within our post-ChatGPT reality!

(2) In other belated news, OpenAI and DeepMind (and then, other companies) announced that they achieved Gold Medal performance on the International Math Olympiad, by solving 5 of the 6 problems (there was one problem, the 6th and hardest, that all of the AIs struggled with). Most importantly, this means that I’ve won $100 from my friend Ernest Davis, AI expert at NYU, who bet me $100 that no AI would earn a Gold Medal at the International Math Olympiad by December 4, 2026. Even though I’m normally risk-averse and reluctant to take bets, I considered this one to be extremely safe, and indeed I won it with more than a year to spare.

(3) I’ve signed an open letter to OpenAI, along with many of my fellow former OpenAI employees as well as distinguished scientists and writers (Geoffrey Hinton, Stuart Russell, Sheldon Glashow, Sean Carroll, Matt Yglesias…), asking for more transparency about OpenAI’s continuing efforts to change its own structure. The questions basically ask OpenAI to declare, in writing, whether it has or hasn’t now completely abandoned the original nonprofit goals with which the organization was founded in 2015.

(4) At Lighthaven, the rationalist meeting space in Berkeley that I recently visited (and that our friend Cade Metz recently cast aspersions on in the New York Times), there’s going to be a writer’s residency called Inkhaven for the whole month of November. The idea—which I love—is that you either write a new blog post every day, or else you get asked to leave (while you also attend workshops, etc. to improve your writing skills). I’d attend myself for the month if teaching and family obligations didn’t conflict; someone standing over me with a whip to make me write is precisely what I need these days! As it is, I’m one of the three advisors to Inkhaven, along with Scott Alexander and Gwern, and I’ll be visiting for a long weekend to share my blogging wisdom, such as I have. Apply now if you’re interested!

(5) Alas, the Springer journal Frontiers of Computer Science has published a nonsense paper, entitled “SAT requires exhaustive search,” claiming to solve (or dissolve, or reframe, or something) the P versus NP problem. It looks indistinguishable from the stuff I used to get in my inbox every week—and now, in the ChatGPT era, get every day. That this was published indicates a total breakdown of the peer review process. Worse, when Eric Allender, Ryan Williams, and others notified the editors of this, asking for the paper to be retracted, the editor-in-chief declined to do so: see this guest post on Lance’s blog for a detailed account. As far as I’m concerned, Frontiers of Computer Science has now completely discredited itself as a journal; publication there means nothing more than publication in viXra. Minus 10 points for journals themselves as an institution, plus 10 points for just posting stuff online and letting it be filtered by experts who care.

(6) Uma Girish and Rocco Servedio released an arXiv preprint called Forrelation is Extremally Hard. Recall that, in the Forrelation problem, you’re given oracle access to two n-bit Boolean functions f and g, and asked to estimate the correlation between f and the Fourier transform of g. I introduced this problem in 2009, as a candidate for an oracle separation between BQP and the polynomial hierarchy—a conjecture that Ran Raz and Avishay Tal finally proved in 2018. What I never imagined was that Forrelation could lead to an oracle separation between EQP (that is, Exact Quantum Polynomial Time) and the polynomial hierarchy. For that, I thought you’d need to go back to the original Recursive Fourier Sampling problem of Bernstein and Vazirani. But Uma and Rocco show, using “bent Boolean functions” (get bent!) and totally contrary to my intuition, that the exact (zero-error) version of Forrelation is already classically hard, taking Ω(2^n/4) queries by any randomized algorithm. They leave open whether exact Forrelation needs ~Ω(2^n/2) randomized queries, which would match the upper bound, and also whether exact Forrelation is not in PH.

(7) The Google quantum group, to little fanfare, published a paper entitled Constructive interference at the edge of quantum ergodic dynamics. Here, they use their 103-qubit superconducting processor to measure Out-of-Time-Order Correlators (OTOCs) in a many-body scrambling process, and claim to get a verifiable speedup over the best classical methods. If true, this is a great step toward verifiable quantum supremacy for a useful task, for some definition of “useful.”

(8) Last night, on the arXiv, the team at USTC in China reported that it’s done Gaussian BosonSampling with 3,050 photons and 8,176 modes. They say that this achieves quantum supremacy, much more clearly than any previous BosonSampling demonstration, beating (for example) all existing simulations based on tensor network contraction. Needless to say, this still suffers from the central problem of all current sampling-based quantum supremacy experiments, namely the exponential time needed for direct classical verification of the outputs.

Follow

For overdetermined reasons, I’ve lately found the world an increasingly terrifying and depressing place. It’s gotten harder and harder to concentrate on research, or even popular science writing. Every so often, though, something breaks through that wakes my inner child, reminds me of why I fell in love with research thirty years ago, and helps me forget about the triumphantly strutting factions working to destroy everything I value.

Back in 2022, I reported an exciting advance in BusyBeaverology: namely, whereas we previously knew merely that BB(6) > 10^36,534, Pavel Kropitz managed to show that

BB(6) > ¹⁵10.

For those tuning in from home, here BB(6) is the 6^th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphabet can take before halting, when run on an initially all-0 input tape. Also, the left-superscript means tetration, or iterated exponentiation: for example, ¹⁵10 means 10 to the 10 to the 10 and so on 15 times.

By comparison, last year the international “BBchallenge” team determined that BB(5) is “merely” 47,176,870 (see also Quanta magazine’s superb feature article on that milestone). So, between 5 and 6 is where the Busy Beaver function makes its leap, from the millions to beyond the bounds of observable reality.

But if you thought that was the end of the BB(6) story, think again! Eleven days ago, Tristan Sterin, who organized the BBchallenge the team, emailed to tell me that a team member with the handle “mxdys” improved the BB(6) bound yet further, to

BB(6) > ^10,000,00010

(i.e., 10 to the 10 to the 10 and so on 10 million times), with a correctness proof in Coq. Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to

$$ BB(6) \gt ^{^{{^9}2}2}2 $$

I.e., BB(6) is at least 2 tetrated to the 2 tetrated to the 2 tetrated to the 9. So in particular, BB(6) is at least 2 pentated to the 5, where pentation is iterated tetration, i.e. the operation that is to tetration as tetration is to exponentiation, exponentiation is to multiplication, and multiplication is to addition.

Last week, when we “merely” knew that BB(6) > ^10,000,00010, I talked to a journalist who asked me to give an intuitive sense of how big such a number is. So I said, imagine you had ^10,000,00010 grains of sand. Then you could … well, uh … you could fill about ^10,000,00010 copies of the observable universe with that sand. I hope that helps people visualize it!

The journalist also asked: have these new discoveries about BB(6) caused me to rethink any broader beliefs about the Busy Beaver function? And I mean, yes and no: it was always completely within the realm of possibility that BB(6) would already be, not some puny little thing like 10^36,534, but way out in iteration land. Now that we know for sure that it is, though, maybe I ought to conjecture that the value of BB(n) becomes independent of the ZFC axioms of set theory already when n is 7 or 8 or 9, rather than when it’s 20 or 30 or whatever. (Currently, we know that BB(n) becomes independent of ZFC only when n=643.)

Unrelated Update: I’m just now returning to the US from STOC’2025 in Prague, where I saw lots of old friends and learned many interesting new things, again helping to distract me from the state of the world! Many I’ll write about some of those things in a future post. For now, though, anyone who’s interested in my STOC plenary lecture, entitled “The Status of Quantum Speedups,” can check out the PowerPoint slides here.

Follow