Shtetl-Optimized

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Let me close this post with two things.

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

---

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Alright everyone:

1. Victor Galitski has an impassioned rant against out-of-control quantum computing hype, which I enjoyed and enthusiastically recommend, although I wished Galitski had engaged a bit more with the strongest arguments for optimism (e.g., the recent sampling-based supremacy experiments, the extrapolations that show gate fidelities crossing the fault-tolerance threshold within the next decade). Even if I’ve been saying similar things on this blog for 15 years, I clearly haven’t been doing so in a style that works for everyone. Quantum information needs as many people as possible who will tell the truth as best they see it, unencumbered by any competing interests, and has nothing legitimate to fear from that. The modern intersection of quantum theory and computer science has raised profound scientific questions that will be with us for decades to come. It’s a lily that need not be gilded with hype.
   
2. Last month Limaye, Srinivasan, and Tavenas posted an exciting preprint to ECCC, which apparently proves the first (slightly) superpolynomial lower bound on the size of constant-depth arithmetic circuits, over fields of characteristic 0. Assuming it’s correct, this is another small victory in the generations-long war against the P vs. NP problem.
   
3. I’m grateful to the Texas Democratic legislators who fled the state to prevent the legislature, a couple miles from my house, having a quorum to enact new voting restrictions, and who thereby drew national attention to the enormity of what’s at stake. It should go without saying that, if a minority gets to rule indefinitely by forcing through laws to suppress the votes of a majority that would otherwise unseat it, thereby giving itself the power to force through more such laws, etc., then we no longer live in a democracy but in a banana republic. And there’s no symmetry to the situation: no matter how terrified you (or I) might feel about wokeists and their denunciation campaigns, the Democrats have no comparable effort to suppress Republican votes. Alas, I don’t know of any solutions beyond the obvious one, of trying to deal the conspiracy-addled grievance party crushing defeats in 2022 and 2024.
   
4. Added: Here’s the video of my recent Astral Codex Ten ask-me-anything session.

Happy 4th to those in the US!

The group of Chaoyang Lu and Jianwei Pan, based at USTC in China, has been on a serious quantum supremacy tear lately. Recall that last December, USTC announced the achievement of quantum supremacy via Gaussian BosonSampling, with 50-70 detected photons—the second claim of sampling-based quantum supremacy, after Google’s in Fall 2019. However, skeptics then poked holes in the USTC claim, showing how they could spoof the results with a classical computer, basically by reproducing the k-photon correlations for relatively small values of k. Debate over the details continues, but the Chinese group seeks to render the debate largely moot with a new and better Gaussian BosonSampling experiment, with 144 modes and up to 113 detected photons. They say they were able to measure k-photon correlations for k up to about 19, which if true would constitute a serious obstacle to the classical simulation strategies that people discussed for the previous experiment.

In the meantime, though, an overlapping group of authors had put out another paper the day before (!) reporting a sampling-based quantum supremacy experiment using superconducting qubits—extremely similar to what Google did (the same circuit depth and everything), except now with 56 qubits rather than 53.

I confess that I haven’t yet studied either paper in detail—among other reasons, because I’m on vacation with my family at the beach, and because I’m trying to spend what work-time I have on my own projects. But anyone who has read them, please use the comments of this post to discuss! Hopefully I’ll learn something.

To confine myself to some general comments: since Google’s announcement in Fall 2019, I’ve consistently said that sampling-based quantum supremacy is not yet a done deal. I’ve said that quantum supremacy seems important enough to want independent replications, and demonstrations in other hardware platforms like ion traps and photonics, and better gate fidelity, and better classical hardness, and better verification protocols. Most of all, I’ve said that we needed a genuine dialogue between the “quantum supremacists” and the classical skeptics: the former doing experiments and releasing all their data, the latter trying to design efficient classical simulations for those experiments, and so on in an iterative process. Just like in applied cryptography, we’d only have real confidence in a quantum supremacy claim once it had survived at least a few years of attacks by skeptics. So I’m delighted that this is precisely what’s now happening. USTC’s papers are two new volleys in this back-and-forth; we all eagerly await the next volley, whichever side it comes from.

While I’ve been trying for years to move away from the expectation that I blog about each and every QC announcement that someone messages me about, maybe I’ll also say a word about the recent announcement by IBM of a quantum advantage in space complexity (see here for popular article and here for arXiv preprint). There appears to be a nice theoretical result here, about the ability to evaluate any symmetric Boolean function with a single qubit in a branching-program-like model. I’d love to understand that result better. But to answer the question I received, this is another case where, once you know the protocol, you know both that the experiment can be done and exactly what its result will be (namely, the thing predicted by QM). So I think the interest is almost entirely in the protocol itself.

Happy birthday to Alan Turing!

This week I’m participating virtually in STOC’2021, which today had a celebration of the 50th anniversary of NP-completeness (featuring Steve Cook, Richard Karp, Leonid Levin, Christos Papadimitriou, and Avi Wigderson), and which tomorrow will have a day’s worth of quantum computing content, including a tutorial on MIP*=RE, two quantum sessions, and an invited talk on quantum supremacy by John Martinis. I confess that I’m not a fan of GatherTown, the platform being used for STOC. Basically, you get a little avatar who wanders around a virtual hotel lobby and enters sessions—but it seems to reproduce all of the frustrating and annoying parts of experience without any of the good parts.

Ah! But I got the surprising news that Alex Arkhipov and I are among the winners of STOC’s first-ever “Test of Time Award,” for our paper on BosonSampling. It feels strange to win a “Test of Time” award for work that we did in 2011, which still seems like yesterday to me. All the more since the experimental status and prospects of quantum supremacy via BosonSampling are still very much live, unresolved questions.

Speaking of which: on Monday, Alexey Rubtsov, of the Skolkovo Institute in Moscow, gave a talk for our quantum information group meeting at UT, about his recent work with Popova on classically simulating Gaussian BosonSampling. From the talk, I learned something extremely important. I had imagined that their simulation must take advantage of the high rate of photon loss in actual experiments (like the USTC experiment from late 2020), because how else are you going to simulate BosonSampling efficiently? But Rubtsov explained that that’s not how it works at all. While their algorithm is heuristic and remains to be rigorously analyzed, numerical studies suggest that it works even with no photon losses or other errors. Having said that, their algorithm works:

• only for Gaussian BosonSampling, not Fock-state BosonSampling (as Arkhipov and I had originally proposed),
• only for threshold detectors, not photon-counting detectors, and
• only for a small number of modes (say, linear in the number of photons), not for a large number of modes (say, quadratic in the number of photons) as in the original proposal.

So, bottom line, it now looks like the USTC experiment, amazing engineering achievement though it was, is not hard to spoof with a classical computer. If so, this is because of multiple ways in which the experiment differed from my and Arkhipov’s original theoretical proposal. We know exactly what those ways are—indeed, you can find them in my earlier blog posts on the subject—and hopefully they can be addressed in future experiments. All in all, then, we’re left with a powerful demonstration of the continuing relevance of formal hardness reductions, and the danger of replacing them with intuitions and “well, it still seems hard to me.” So I hope the committee won’t rescind my and Arkhipov’s Test of Time Award based on these developments in the past couple weeks!

I now have a feature article up at Quanta magazine, entitled “What Makes Quantum Computing So Hard To Explain?” I.e., why do journalists, investors, etc. so consistently get central points wrong, even after the subject has been in public consciousness for more than 25 years? Perhaps unsurprisingly, I found it hard to discuss that meta-level question, as Quanta‘s editors asked me to do, without also engaging in the object-level task of actually explaining QC. For regular Shtetl-Optimized readers, there will be nothing new here, but I’m happy with how the piece turned out.

Accompanying the Quanta piece is a 10-minute YouTube explainer on quantum computing, which (besides snazzy graphics) features interviews with me, John Preskill, and Dorit Aharonov.

On a different note, my colleague Mark Wilde has recorded a punk-rock song about BosonSampling. I can honestly report that it’s some of the finest boson-themed music I’ve heard in years. It includes the following lyrics:

Quantum computer, Ain’t no loser
Quantum computer, Quantum computer

People out on the streets
They don’t know what it is
They think it finds the cliques
Or finds graph colorings
But it don’t solve anything
Said it don’t solve anything
Bosonic slot machine
My lil’ photonic dream

Speaking of BosonSampling, A. S. Popova and A. N. Rubtsov, of the Skolkovo Institute in Moscow, have a new preprint entitled Cracking the Quantum Advantage threshold for Gaussian Boson Sampling. In it, they claim to give an efficient classical algorithm to simulate noisy GBS experiments, like the one six months ago from USTC in China. I’m still unsure how well this scales from 30-40 photons up to 50-70 photons; which imperfections of the USTC experiment are primarily being taken advantage of (photon losses?); and how this relates to the earlier proposed classical algorithms for simulating noisy BosonSampling, like the one by Kalai and Kindler. Anyone with any insight is welcome to share!

OK, one last announcement: the Simons Institute for the Theory of Computing, in Berkeley, has a new online lecture series called “Breakthroughs,” which many readers of this blog might want to check out.

1. Hooray, I’m today’s “Featured ACM Member”! Which basically means, yet another interview with me about quantum computing, with questions including what’s most surprised me about the development of QC, and what students should do to get into the field.
2. I’m proud to announce that An Automated Approach to the Collatz Conjecture, a paper by Emre Yolcu, myself, and Marijn Heule that we started working on over four years ago, is finally available on the arXiv, and will be presented at the 2021 Conference on Automated Deduction. Long story short: no, we didn’t prove Collatz, but we have an approach that can for the first time prove certain Collatz-like statements in a fully automated way, so hopefully that’s interesting! There was also a Quanta article even before our paper had come out (I wasn’t thrilled about the timing).
3. The legendary Baba Brinkman has a new rap about quantum computing (hat tip to blog commenter YD). Having just watched the music video, I see it as one of the better popularization efforts our field has seen in the past 25 years—more coherent than the average journalistic account and with a much better backbeat. (I do, however, take a more guarded view than Brinkman of the potential applications, especially to e.g. autonomous driving and supply-chain optimization.)

1. For those who read my reply to Richard Borcherds on “teapot supremacy”: seeking better data, I ordered a dozen terra cotta flowerpots, and smashed eight of them on my driveway with my 4-year-old son, dropping each one from approximately 2 meters. For each flowerpot, we counted how many pieces it broke into, seeking insight about the distribution over that number. Unfortunately, it still proved nearly impossible to get good data, for a reason commenters had already warned me about: namely, there were typically 5-10 largeish shards, followed by “long tail” of smaller and smaller shards (eventually, just terra cotta specks), with no obvious place to draw the line and stop counting. Nevertheless, when I attempted to count only the shards that were “fingernail-length or larger,” here’s what I got: 1 pot with 9 shards, 1 with 11 shards, 2 with 13 shards, 2 with 15 shards, 1 with 17 shards, 1 with 19 shards. This is a beautiful (too beautiful?) symmetric distribution centered around a mean of 14 shards, although it’s anyone’s guess whether it approximates a Gaussian or something else. I have no idea why every pot broke into an odd number of shards, unless of course it was a 1-in-256-level fluke, or some cognitive bias that made me preferentially stop counting the shards at odd numbers.
   
2. Thanks so much to everyone who congratulated me for the ACM Prize, and especially those who (per my request) suggested charities to which to give bits of the proceeds! Tonight, after going through the complete list of suggestions, I made my first, but far from last, round of donations: $1000 each to the Deworm the World Initiative, GiveDirectly, the World Wildlife Fund, the Nature Conservancy, and Canada/USA Mathcamp (which had a huge impact on me when I attended it as a 15-year-old). One constraint, which might never arise in a decade of moral philosophy seminars, ended up being especially important in practice: if the donation form was confusing or buggy, or if it wouldn’t accept my donation without some onerous confirmation step involving a no-longer-in-use cellphone, then I simply moved on to the next charity.
   
3. Bobby Kleinberg asked me to advertise the call for nominations for the brand-new STOC Test of Time Award. The nomination deadline is coming up soon: May 24.

Last week I got an email from Dina Katabi, my former MIT colleague, asking me to call her urgently. Am I in trouble? For what, though?? I haven’t even worked at MIT for five years!

Luckily, Dina only wanted to tell me that I’d been selected to receive the 2020 ACM Prize in Computing, a mid-career award founded in 2007 that comes with $250,000 from Infosys. Not the Turing Award but I’d happily take it! And I could even look back on 2020 fondly for something.

I was utterly humbled to see the list of past ACM Prize recipients, which includes amazing computer scientists I’ve been privileged to know and learn from (like Jon Kleinberg, Sanjeev Arora, and Dan Boneh) and others who I’ve admired from afar (like Daphne Koller, Jeff Dean and Sanjay Ghemawat of Google MapReduce, and David Silver of AlphaGo and AlphaZero).

I was even more humbled, later, to read my prize citation, which focuses on four things:

1. The theoretical foundations of the sampling-based quantum supremacy experiments now being carried out (and in particular, my and Alex Arkhipov’s 2011 paper on BosonSampling);
2. My and Avi Wigderson’s 2008 paper on the algebrization barrier in complexity theory;
3. Work on the limitations of quantum computers (in particular, the 2002 quantum lower bound for the collision problem); and
4. Public outreach about quantum computing, including through QCSD, popular talks and articles, and this blog.

I don’t know if I’m worthy of such a prize—but I know that if I am, then it’s mainly for work I did between roughly 2001 and 2012. This honor inspires me to want to be more like I was back then, when I was driven, non-jaded, and obsessed with figuring out the contours of BQP and efficient computation in the physical universe. It makes me want to justify the ACM’s faith in me.

I’m grateful to the committee and nominators, and more broadly, to the whole quantum computing and theoretical computer science communities—which I “joined” in some sense around age 16, and which were the first communities where I ever felt like I belonged. I’m grateful to the mentors who made me what I am, especially Chris Lynch, Bart Selman, Lov Grover, Umesh Vazirani, Avi Wigderson, and (if he’ll allow me to include him) John Preskill. I’m grateful to the slightly older quantum computer scientists who I looked up to and tried to emulate, like Dorit Aharonov, Andris Ambainis, Ronald de Wolf, and John Watrous. I’m grateful to my wonderful colleagues at UT Austin, in the CS department and beyond. I’m grateful to my students and postdocs, the pride of my professional life. I’m grateful, of course, to my wife, parents, and kids.

By coincidence, my last post was also about prizes to theoretical computer scientists—in that case, two prizes that attracted controversy because of the recipient’s (or would-be recipient’s) political actions or views. It would understate matters to point out that not everyone has always agreed with everything I’ve said on this blog. I’m ridiculously lucky, and I know it, that even living through this polarized and tumultuous era, I never felt forced to choose between academic success and the freedom to speak my conscience in public under my real name. If there’s been one constant in my public stands, I’d like to think that—inspired by memories of my own years as an unknown, awkward, self-conscious teenager—it’s been my determination to nurture and protect talented young scientists, whatever they look like and wherever they come from. And I’ve tried to live up to that ideal in real life, and I welcome anyone’s scrutiny as to how well I’ve done.

What should I do with the prize money? I confess that my first instinct was to donate it, in its entirety, to some suitable charity—specifically, something that would make all the strangers who’ve attacked me on Twitter, Reddit, and so forth over the years realize that I’m fundamentally a good person. But I was talked out of this plan by my family, who pointed out that
(1) in all likelihood, nothing will make online strangers stop hating me,
(2) in any case this seems like a poor basis for making decisions, and
(3) if I really want to give others a say in what to do with the winnings, then why not everyone who’s stood by me and supported me?

So, beloved commenters! Please mention your favorite charitable causes below, especially weird ones that I wouldn’t have heard of otherwise. If I support their values, I’ll make a small donation from my prize winnings. Or a larger donation, especially if you donate yourself and challenge me to match. Whatever’s left after I get tired of donating will probably go to my kids’ college fund.

Update: And by an amusing coincidence, today is apparently “World Quantum Day”! I hope your Quantum Day is as pleasant as mine (and stable and coherent).