Shtetl-Optimized (original) (raw)

Above my pay grade: Jensen Huang and the quantum computing stock market crash

January 9th, 2025

Update (Jan. 13): Readers might enjoy the Bankless Podcast, in which I and Justin Drake of the Ethereum engineering team discuss quantum computing and its impact on cryptocurrency. I learned something interesting from Justin—namely that Satoshi has about $90 billion worth of bitcoin that’s never been touched since the cryptocurrency’s earliest days, much of which (added: the early stuff, the stuff not additionally protected by a hash function) would be stealable by anyone who could break elliptic curve cryptography—for example, by using a scalable quantum computer. At what point in time, if any, would this stash acquire the moral or even legal status of (say) gold doubloons just lying on the bottom of the ocean? Arrr, ’tis avast Hilbert space!

Apparently Jensen Huang, the CEO of NVIDIA, opined on an analyst call this week that quantum computing was plausibly still twenty years away from being practical. As a direct result, a bunch of publicly-traded quantum computing companies (including IonQ, Rigetti, and D-Wave) fell 40% or more in value, and even Google/Alphabet stock fell on the news.

So then friends and family attuned to the financial markets started sending me messages asking for my reaction, as the world’s semi-unwilling Quantum Computing Opiner-in-Chief.

My reaction? Mostly just that it felt really weird for all those billions of dollars to change hands, or evaporate, based on what a microchip CEO offhandedly opined about my tiny little field, while I (like much of that field) could’ve remained entirely oblivious to it, were it not for all of their messages!

But was Jensen Huang right in his time estimate? And, relatedly, what is the “correct” valuation of quantum computing companies? Alas, however much more I know about quantum computing than Jensen Huang does, the knowledge does not enable me to answer to either question.

I can, of course, pontificate about the questions, as I can pontificate about anything.

To start with the question of timelines: yes, there’s a lot still to be done, and twenty years might well be correct. But as I’ve pointed out before, within the past year we’ve seen 2-qubit gates with ~99.9% fidelity, which is very near the threshold for practical fault-tolerance. And of course, Google has now demonstrated fault-tolerance that becomes more and more of a win with increasing code size. So no, I can’t confidently rule out commercially useful quantum simulations within the next decade. Like, it sounds fanciful, but then I remember how fanciful it would’ve seemed in 2012 that we’d have conversational AI by 2022. I was alive in 2012! And speaking of which, if you really believe (as many people now do) AI will match or exceed human capabilities in most fields in the next decade, then that will scramble all the other timelines too. And presumably Jensen Huang understands these points as well as anyone.

Now for the valuation question. On the one hand, Shtetl-Optimized readers will know that there’s been plenty of obfuscation and even outright lying, to journalists, the public, and investors, about what quantum computing will be good for and how soon. To whatever extent the previous valuations were based on that lying, a brutal correction was of course in order, regardless of what triggered it.

On the other hand, I can’t say with certainty that high valuations are wrong! After all, even if there’s only a 10% chance that something will produce 100Binvalue,thatwouldstilljustifya100B in value, that would still justify a 100Binvalue,thatwouldstilljustifya10B valuation. It’s a completely different way of thinking than what we’re used to in academia.

For whatever it’s worth, my own family’s money is just sitting in index funds and CDs. I have no quantum computing investments of any kind. I do sometimes accept consulting fees to talk to quantum computing startups and report back my thoughts. When I do, my highest recommendation is: “these people are smart and honest, everything they say about quantum algorithms is correct insofar as I can judge, and I hope they succeed. I wouldn’t invest my own money, but I’m very happy if you or anyone else does.” Meanwhile, my lowest recommendation is: “these people are hypesters and charlatans, and I hope they fail. But even then, I can’t say with confidence that their valuation won’t temporarily skyrocket, in which case investing in them would presumably have been the right call.”

So basically: it’s good that I became an academic rather than an investor.

Having returned from family vacation, I hope to get back to a more regular blogging schedule … let’s see how it goes!

Posted in Quantum, Speaking Truth to Parallelism | 39 Comments »

The Google Willow thing

December 10th, 2024

Yesterday I arrived in Santa Clara for the Q2B (Quantum 2 Business) conference, which starts this morning, and where I’ll be speaking Thursday on “Quantum Algorithms in 2024: How Should We Feel?” and also closing the conference via an Ask-Us-Anything session with John Preskill. (If you’re at Q2B, reader, come and say hi!)

And to coincide with Q2B, yesterday Google’s Quantum group officially announced “Willow,” its new 105-qubit superconducting chip with which it’s demonstrated an error-corrected surface code qubit as well as a new, bigger quantum supremacy experiment based on Random Circuit Sampling. I was lucky to be able to attend Google’s announcement ceremony yesterday afternoon at the Computer History Museum in Mountain View, where friend-of-the-blog-for-decades Dave Bacon and other Google quantum people explained exactly what was done and took questions (the technical level was surprisingly high for this sort of event). I was also lucky to get a personal briefing last week from Google’s Sergio Boixo on what happened.

Meanwhile, yesterday Sundar Pichai tweeted about Willow, and Elon Musk replied “Wow.” It cannot be denied that those are both things that happened.

Anyway, all yesterday, I then read comments on Twitter, Hacker News, etc. complaining that, since there wasn’t yet a post on Shtetl-Optimized, how could anyone possibly know what to think of this?? For 20 years I’ve been trying to teach the world how to fish in Hilbert space, but (sigh) I suppose I’ll just hand out some more fish. So, here are my comments:

Yes, this is great. Yes, it’s a real milestone for the field. To be clear: for anyone who’s been following experimental quantum computing these past five years (say, since Google’s original quantum supremacy milestone in 2019), there’s no particular shock here. Since 2019, Google has roughly doubled the number of qubits on its chip and, more importantly, increased the qubits’ coherence time by a factor of 5. Meanwhile, their 2-qubit gate fidelity is now roughly 99.7% (for controlled-Z gates) or 99.85% (for “iswap” gates), compared to ~99.5% in 2019. They then did the more impressive demonstrations that predictably become possible with more and better qubits. And yet, even if the progress is broadly in line with what most of us expected, it’s still of course immensely gratifying to see everything actually work! Huge congratulations to everyone on the Google team for a well-deserved success.
I already blogged about this!!! Specifically, I blogged about Google’s fault-tolerance milestone when its preprint appeared on the arXiv back in August. To clarify, what we’re all talking about now is the same basic technical advance that Google already reported in August, except now with the PR blitz from Sundar Pichai on down, a Nature paper, an official name for the chip (“Willow”), and a bunch of additional details about it.
Scientifically, the headline result is that, as they increase the size of their surface code, from 3×3 to 5×5 to 7×7, Google finds that their encoded logical qubit stays alive for longer rather than shorter. So, this is a very important threshold that’s now been crossed. As Dave Bacon put it to me, “eddies are now forming”—or, to switch metaphors, after 30 years we’re now finally tickling the tail of the dragon of quantum fault-tolerance, the dragon that (once fully awoken) will let logical qubits be preserved and acted on for basically arbitrary amounts of time, allowing scalable quantum computation.
Having said that, Sergio Boixo tells me that Google will only consider itself to have created a “true” fault-tolerant qubit, once it can do fault-tolerant two-qubit gates with an error of ~10-6 (and thus, on the order of a million fault-tolerant operations before suffering a single error). We’re still some ways from that milestone: after all, in this experiment Google created only a single encoded qubit, and didn’t even try to do encoded operations on it, let alone on multiple encoded qubits. But all in good time. Please don’t ask me to predict how long, though empirically, the time from one major experimental QC milestone to the next now seems to be measured in years, which are longer than weeks but shorter than decades.
Google has also announced a new quantum supremacy experiment on its 105-qubit chip, based on Random Circuit Sampling with 40 layers of gates. Notably, they say that, if you use the best currently-known simulation algorithms (based on Johnnie Gray’s optimized tensor network contraction), as well as an exascale supercomputer, their new experiment would take ~300 million years to simulate classically if memory is not an issue, or ~1025 years if memory is an issue (note that a mere ~1010 years have elapsed since the Big Bang). Probably some people have come here expecting me to debunk those numbers, but as far as I know they’re entirely correct, with the caveats stated. Naturally it’s possible that better classical simulation methods will be discovered, but meanwhile the experiments themselves will also rapidly improve.
Having said that, the biggest caveat to the “1025 years” result is one to which I fear Google drew insufficient attention. Namely, for the exact same reason why (as far as anyone knows) this quantum computation would take ~1025 years for a classical computer to simulate, it would also take ~1025 years for a classical computer to directly verify the quantum computer’s results!! (For example, by computing the “Linear Cross-Entropy” score of the outputs.) For this reason, all validation of Google’s new supremacy experiment is indirect, based on extrapolations from smaller circuits, ones for which a classical computer can feasibly check the results. To be clear, I personally see no reason to doubt those extrapolations. But for anyone who wonders why I’ve been obsessing for years about the need to design efficiently verifiable near-term quantum supremacy experiments: well, this is why! We’re now deeply into the unverifiable regime that I warned about.
In his remarks yesterday, Google Quantum AI leader Hartmut Neven talked about David Deutsch’s argument, way back in the 1990s, that quantum computers should force us to accept the reality of the Everettian multiverse, since “where else could the computation have happened, if it wasn’t being farmed out to parallel universes?” And naturally there was lots of debate about that on Hacker News and so forth. Let me confine myself here to saying that, in my view, the new experiment doesn’t add anything new to this old debate. It’s yet another confirmation of the predictions of quantum mechanics. What those predictions mean for our understanding of reality can continue to be argued as it’s been since the 1920s.
Cade Metz did a piece about Google’s announcement for the New York Times. Alas, when Cade reached out to me for comment, I decided that it would be too awkward, after what Cade did to my friend Scott Alexander almost four years ago. I talked to several other journalists, such as Adrian Cho for Science.
No doubt people will ask me what this means for superconducting qubits versus trapped-ion or neutral-atom or photonic qubits, or for Google versus its many competitors in experimental QC. And, I mean, it’s not bad for Google or for superconducting QC! These past couple years I’d sometimes commented that, since Google’s 2019 announcement of quantum supremacy via superconducting qubits, the trapped-ion and neutral-atom approaches had seemed to be pulling ahead, with spectacular results from Quantinuum (trapped-ion) and QuEra (neutral atoms) among others. One could think of Willow as Google’s reply, putting the ball in competitors’ courts likewise to demonstrate better logical qubit lifetime with increasing code size (or, better yet, full operations on logical qubits exceeding that threshold, without resorting to postselection). The great advantage of trapped-ion qubits continues to be that you can move the qubits around (and also, the two-qubit gate fidelities seem somewhat ahead of superconducting). But to compensate, superconducting qubits have the advantage that the gates are a thousand times faster, which makes feasible to do experiments that require collecting millions of samples.
Of course the big question, the one on everyone’s lips, was always how quantum computing skeptic Gil Kalai was going to respond. But we need not wonder! On his blog, Gil writes: “We did not study yet these particular claims by Google Quantum AI but my general conclusion apply to them ‘Google Quantum AI’s claims (including published ones) should be approached with caution, particularly those of an extraordinary nature. These claims may stem from significant methodological errors and, as such, may reflect the researchers’ expectations more than objective scientific reality.’ ” Most of Gil’s post is devoted to re-analyzing data from Google’s 2019 quantum supremacy experiment, which Gil continues to believe can’t possibly have done what was claimed. Gil’s problem is that the 2019 experiment was long ago superseded anyway: besides the new and more inarguable Google result, IBM, Quantinuum, QuEra, and USTC have now all also reported Random Circuit Sampling experiments with good results. I predict that Gil, and others who take it as axiomatic that scalable quantum computing is impossible, will continue to have their work cut out for them in this new world.

Update: Here’s Sabine Hossenfelder’s take. I don’t think she and I disagree about any of the actual facts; she just decided to frame things much more negatively. Ironically, I guess 20 years of covering hyped, dishonestly-presented non-milestones in quantum computing has inclined me to be pretty positive when a group puts in this much work, demonstrates a real milestone, and talks about it without obvious falsehoods!

Posted in Quantum | 138 Comments »

Podcasts!

December 4th, 2024

Update (Dec. 9): For those who still haven’t gotten enough, check out a 1-hour Zoom panel discussion about quantum algorithms, featuring yours truly along with my distinguished colleagues Eddie Farhi, Aram Harrow, and Andrew Childs, moderated by Barry Sanders, as part of the QTML’2024 conference held in Melbourne (although, it being Thanksgiving week, none of the four panelists were actually there in person). Part of the panel devolves into a long debate between me and Eddie about how interesting quantum algorithms are if they don’t achieve speedups over classical algorithms, and whether some quantum algorithms papers mislead people by not clearly addressing the speedup question (you get one guess as to which side I took). I resolved going in to keep my comments as civil and polite as possible—you can judge for yourself how well I succeeded! Thanks very much to Barry and the other QTML organizers for making this happen.

Do you like watching me spout about AI alignment, watermarking, my time at OpenAI, the P versus NP problem, quantum computing, consciousness, Penrose’s views on physics and uncomputability, university culture, wokeness, free speech, my academic trajectory, and much more, despite my slightly spastic demeanor and my many verbal infelicities? Then holy crap are you in luck today! Here’s 2.5 hours of me talking to former professional poker players (and now wonderful Austin-based friends) Liv Boeree and her husband Igor Kurganov about all of those topics. (Or 1.25 hours if you watch at 2x speed, as I strongly recommend.)

But that’s not all! Here I am talking to Harvard’s Hrvoje Kukina, in a much shorter (45-minute) podcast focused on quantum computing, cosmological bounds on information processing, and the idea of the universe as a computer:

Last but not least, here I am in an hour-long podcast (this one audio-only) with longtime friend Kelly Weinersmith and her co-host Daniel Whiteson, talking about quantum computing.

Enjoy!

Posted in Announcements, Complexity, Metaphysical Spouting, Quantum, Speaking Truth to Parallelism | 33 Comments »

Thanksgiving

November 28th, 2024

I’m thankful to the thousands of readers of this blog. Well, not the few who submit troll comments from multiple pseudonymous handles, but the 99.9% who don’t. I’m thankful that they’ve stayed here even when events (as they do more and more often) send me into a spiral of doomscrolling and just subsisting hour-to-hour—when I’m left literally without words for weeks.

I’m thankful for Thanksgiving itself. As I often try to explain to non-Americans (and to my Israeli-born wife), it’s not primarily about the turkey but rather about the sides: the stuffing, the mashed sweet potatoes with melted marshmallows, the cranberry jello mold. The pumpkin pie is good too.

I’m thankful that we seem to be on the threshold of getting to see the birth of fault-tolerant quantum computing, nearly thirty years after it was first theorized.

I’m thankful that there’s now an explicit construction of pseudorandom unitaries — and that, with further improvement, this would lead to a Razborov-Rudich natural proofs barrier for the quantum circuit complexity of unitaries, explaining for the first time why we don’t have superpolynomial lower bounds for that quantity.

I’m thankful that there’s been recent progress on QMA versus QCMA (that is, quantum versus classical proofs), with a full classical oracle separation now possibly in sight.

I’m thankful that, of the problems I cared about 25 years ago — the maximum gap between classical and quantum query complexities of total Boolean functions, relativized BQP versus the polynomial hierarchy, the collision problem, making quantum computations classically verifiable — there’s now been progress if not a full solution for almost all of them. And yet I’m thankful as well that lots of great problems remain open.

I’m thankful that the presidential election wasn’t all that close (by contemporary US standards, it was a ““landslide,”” 50%-48.4%). Had it been a nail-biter, not only would I fear violence and the total breakdown of our constitutional order, I’d kick myself that I hadn’t done more to change the outcome. As it is, there’s no denying that a plurality of Americans actually chose this, and now they’re going to get it good and hard.

I’m thankful that, while I absolutely do see Trump’s return as a disaster for the country and for civilization, it’s not a 100% unmitigated disaster. The lying chaos monster will occasionally rage for things I support rather than things I oppose. And if he actually plunges the country into another Great Depression through tariffs, mass deportations, and the like, hopefully that will make it easier to repudiate his legacy in 2028.

I’m thankful that, whatever Jews around the world have had to endure over the past year — both the physical attacks and the moral gaslighting that it’s all our fault — we’ve already endured much worse on both fronts, not once but countless times over 3000 years, and this is excellent Bayesian evidence that we’ll survive the latest onslaught as well.

I’m thankful that my family remains together, and healthy. I’m thankful to have an 11-year-old who’s a striking wavy-haired blonde who dances and does gymnastics (how did that happen?) and wants to be an astrophysicist, as well as a 7-year-old who now often beats me in chess and loves to solve systems of two linear equations in two unknowns.

I’m thankful that, compared to what I imagined my life would be as an 11-year-old, my life is probably in the 50th percentile or higher. I haven’t saved the world, but I haven’t flamed out either. Even if I do nothing else from this point, I have a stack of writings and results that I’m proud of. And I fully intend to do something else from this point.

I’m thankful that the still-most-powerful nation on earth, the one where I live, is … well, more aligned with good than any other global superpower in the miserable pageant of human history has been. I’m thankful to live in the first superpower in history that has some error-correction machinery built in, some ability to repudiate its past sins (and hopefully its present sins, in the future). I’m thankful to live in the first superpower that has toleration of Jews and other religious minorities built in as a basic principle, with the possible exception of the Persian Empire under Cyrus.

I’m thankful that all eight of my great-grandparents came to the US in 1905, back when Jewish mass immigration was still allowed. Of course there’s a selection effect here: if they hadn’t made it, I wouldn’t be here to ponder it. Still, it seems appropriate to express gratitude for the fact of existing, whatever metaphysical difficulties might inhere in that act.

I’m thankful that there’s now a ceasefire between Israel and Lebanon that Israel’s government saw fit to agree to. While I fear that this will go the way of all previous ceasefires — Hezbollah “obeys” until it feels ready to strike again, so then Israel invades Lebanon again, then more civilians die, then there’s another ceasefire, rinse and repeat, etc. — the possibility always remains that this time will be the charm, for all people on both sides who want peace.

I’m thankful that our laws of physics are so constructed that G, c, and ℏ, three constants that are relatively easy to measure, can be combined to tell us the fundamental units of length and time, even though those units — the Planck time, 10-43 seconds, and the Planck length, 10-33 centimeters — are themselves below the reach of any foreseeable technology, and to atoms as atoms are to the solar system.

I’m thankful that, almost thirty years after I could have and should have, I’ve now finally learned the proof of the irrationality of π.

I’m thankful that, if I could go back in time to my 14-year-old self, I could tell him firstly, that female heterosexual attraction to men is a real phenomenon in the world, and secondly, that it would sometimes fixate on him (the future him, that is) in particular.

I’m thankful for red grapefruit, golden mangos, seedless watermelons, young coconuts (meat and water), mangosteen, figs, dates, and even prunes. Basically, fruit is awesome, the more so after whatever selective breeding and genetic engineering humans have done to it.

I’m thankful for Futurama, and for the ability to stream every episode of it in order, as Dana, the kids, and I have been doing together all fall. I’m thankful that both of my kids love it as much as I do—in which case, how far from my values and worldview could they possibly be? Even if civilization is destroyed, it will have created 100 episodes of something this far out on the Pareto frontier of lowbrow humor, serious intellectual content, and emotional depth for a future civilization to discover. In short: “good news, everyone!”

Posted in Announcements, Quantum, The Fate of Humanity | 57 Comments »

Letter to a Jewish voter in Pennsylvania

November 3rd, 2024

Election Day Update: For anyone who’s still undecided (?!?), I can’t beat this from Sam Harris.

When I think of Harris winning the presidency this week, it’s like watching a film of a car crash run in reverse: the windshield unshatters; stray objects and bits of metal converge; and defenseless human bodies are hurled into states of perfect repose. Normalcy descends out of chaos.

Important Announcement: I don’t in any way endorse voting for Jill Stein, or any other third-party candidate. But if you are a Green Party supporter who lives in a swing state, then please at least vote for Harris, and use SwapYourVote.org to arrange for two (!) people in safe states to vote for Jill Stein on your behalf. Thanks so much to friend-of-the-blog Linchuan Zhang for pointing me to this resource.

Added on Election Day: And, if you swing that way, click here to arrange to have your vote for Kamala in a swing state traded for two votes for libertarian candidate Chase Oliver in safe states. In any case, if you’re in a swing state and you haven’t yet voted (for Kamala Harris and for the norms of civilization), do!

For weeks I’d been wondering what I could say right before the election, at this momentous branch-point in the wavefunction, that could possibly do any good. Then, the other day, a Jewish voter in Pennsylvania and Shtetl-Optimized fan emailed me to ask my advice. He said that he’d read my Never-Trump From Here to Eternity FAQ and saw the problems with Trump’s autocratic tendencies, but that his Israeli friends and family wanted him to vote Trump anyway, believing him better on the narrow question of “Israel’s continued existence.” I started responding, and then realized that my response was the election-eve post I’d been looking for. So without further ado…

Thanks for writing. Of course this is ultimately between you and your conscience (and your empirical beliefs), but I can tell you what my Israeli-American wife and I did. We voted for Kamala, without the slightest doubt or hesitation. We’d do it again a thousand quadrillion times. We would’ve done the same in the swing state of Pennsylvania, where I grew up (actually in Bucks, one of the crucial swing counties).

And later this week, along with tens of millions of others, I’ll refresh the news with heart palpitations, looking for movement toward blue in Pennsylvania and Wisconsin. I’ll be joyous and relieved if Kamala wins. I’ll be ashen-faced if she doesn’t. (Or if there’s a power struggle that makes the 2021 insurrection look like a dress rehearsal.) And I’ll bet anyone, at 100:1 odds, that at the end of my life I’ll continue to believe that voting Kamala was the right decision.

I, too, have pro-Israel friends who urged me to switch to Trump, on the ground that if Kamala wins, then (they say) the Jews of Israel are all but doomed to a second Holocaust. For, they claim, the American Hamasniks will then successfully prevail on Kamala to prevent Israel from attacking Iran’s nuclear sites, or will leave Israel to fend for itself if it does. And therefore, Iran will finish and test nuclear weapons in the next couple years, and then it will rebuild the battered Hamas and Hezbollah under its nuclear umbrella, and then it will fulfill its stated goal since 1979, of annihilating the State of Israel, by slaughtering all the Jews who aren’t able to flee. And, just to twist the knife, the UN diplomats and NGO officials and journalists and college students and Wikipedia editors who claimed such a slaughter was a paranoid fantasy, they’ll all cheer it when it happens, calling it “justice” and “resistance” and “intifada.”

And that, my friends say, will finally show me the liberal moral evolution of humanity since 1945, in which I’ve placed so much stock. “See, even while they did virtually nothing to stop the first Holocaust, the American and British cultural elites didn’t literally cheer the Holocaust as it happened. This time around, they’ll cheer.”

My friends’ argument is that, if I’m serious about “Never Again” as a moral lodestar of my life, then the one issue of Israel and Iran needs to override everything else I’ve always believed, all my moral and intellectual repugnance at Trump and everything he represents, all my knowledge of his lies, his evil, his venality, all the former generals and Republican officials who say that he’s unfit to serve and an imminent danger to the Republic. I need to vote for this madman, this pathological liar, this bullying autocrat, because at least he’ll stand between the Jewish people and the darkness that would devour them, as it devoured them in my grandparents’ time.

My friends add that it doesn’t matter that Kamala’s husband is Jewish, that she’s mouthed all the words a thousand times about Israel’s right to defend itself, that Biden and Harris have indeed continued to ship weapons to Israel with barely a wag of their fingers (even as they’ve endured vituperation over it from their left, even as Kamala might lose the whole election over it). Nor does it matter that a commanding majority of American Jews will vote for Kamala, or that … not most Israelis, but most of the Israelis in academia and tech who I know, would vote for Kamala if they could. They could all be mistaken about their own interests. But you and I, say my right-wing friends, realize that what actually matters is Iran, and what the next president will do about Iran. Trump would unshackle Israel to do whatever it takes to prevent nuclear-armed Ayatollahs. Kamala wouldn’t.

Anyway, I’ve considered this line of thinking. I reject it with extreme prejudice.

To start with the obvious, I’m not a one-issue voter. Presumably you aren’t either. Being Jewish is a fundamental part of my humanity—if I didn’t know that before I’d witnessed the world’s reaction to October 7, then I certainly know now. But only in the fantasies of antisemites would I vote entirely on the basis of “is this good for the Jews?” The parts of me that care about the peaceful transfer of power, about truth, about standing up to Putin, about the basic sanity of the Commander-in-Chief in an emergency, about climate change and green energy and manufacturing, about not destroying the US economy through idiotic tariffs, about talented foreign scientists getting green cards, about the right to abortion, about RFK and his brainworm not being placed in charge of American healthcare, even about AI safety … all those parts of me are obviously for Kamala.

More interestingly, though, the Jewish part of me is also for Kamala—if possible, even more adamantly than other parts. It’s for Kamala because…

Well, after these nine surreal years, how does one even spell out the Enlightenment case against Trump? How does one say what hasn’t already been said a trillion times? Now that the frog is thoroughly boiled, how does one remind people of the norms that used to prevail in America—even after Newt Gingrich and Sarah Palin and the rest had degraded them—and how those norms were what stood between us and savagery … and how laughably unthinkable is the whole concept of Trump as president, the instant you judge him according to those norms?

Kamala, whatever her faults, is basically a normal politician. She lies, but only as normal politicians lie. She dodges questions, changes her stances, says different things to different audiences, but only as normal politicians do. Trump is something else entirely. He’s one of the great flimflam artists of human history. He believes (though “belief” isn’t quite the right word) that truth is not something external to himself, but something he creates by speaking it. He is the ultimate postmodernist. He’s effectively created a new religion, one of grievance and lies and vengeance against outsiders, and converted a quarter of Americans to his religion, while another quarter might vote it into power because of what they think is in it for them.

And this cult of lies … this is what you ask if Jewish people should enter into a strategic alliance with? Do you imagine this cult is a trustworthy partner, one likely to keep its promises?

For centuries, Jews have done consistently well under cosmopolitan liberal democracies, and consistently poorly—when they remained alive at all—under nativist tyrants. Do you expect whatever autocratic regime follows Trump, a regime of JD Vance and Tucker Carlson and the like, to be the first exception to this pattern in history?

For I take it as obvious that a second Trump term, and whatever follows it, will make the first Trump term look like a mere practice run, a Beer Hall Putsch. Trump I was restrained by John Kelly, by thousands of civil service bureaucrats and judges, by the generals, and in the last instance, by Mike Pence. But Trump II will be out for the blood of his enemies—he says so himself at his rallies—and will have nothing to restrain him, not even any threat of criminal prosecution. Do you imagine this goes well for the Jews, or for pretty much anyone?

It doesn’t matter if Trump has no personal animus against Jews—excepting, of course, the majority who vote against him. Did the idealistic Marxist intellectuals of Russia in 1917 want Stalin? Did the idealistic Iranian students of Iran in 1979 want Khomeini? It doesn’t matter: what matters is what they enabled. Turn over the rock of civilization, and everything that was wriggling underneath is suddenly loosed on the world.

How much time have you spent looking at pro-Israel people on Twitter (Hen Mazzig, Haviv Rettig Gur, etc.), and then—crucially—reading their replies? I spend at least an hour or two per day on that, angry and depressed though it makes me, perhaps because of an instinct to stare into the heart of darkness, not to look away from a genocidal evil arrayed against my family.

Many replies are the usual: “Shut the fuck up, Zio, and stop murdering babies.” “Two-state solution? I have a different solution: that all you land-thieves pack your bags and go back to Poland.” But then, every time, you reach tweets like “you Jews have been hated and expelled from all the world’s countries for thousands of years, yet you never consider that the common factor is you.” “Your Talmud commands you to kill goyim children, so that’s why you’re doing it.” “Even while you maintain apartheid in Palestine, you cynically import millions of third-world savages to White countries, in order to destroy them.” None of this is the way leftists talk, not even the most crazed leftists. We’ve now gone all the way around the horseshoe. Or, we might say, we’re no longer selecting on the left or right of politics at all, but simply on the bottom.

And then you see that these bottom-feeders often have millions of followers each. They command armies. The bottom-feeders—left, right, Islamic fundamentalist, and unclassifiably paranoid—are emboldened as never before. They’re united by a common enemy, which turns out to be the same enemy they’ve always had.

Which brings us to Elon Musk. I personally believe that Musk, like Trump, has nothing against the Jews, and is if anything a philosemite. But it’s no longer a question of feelings. Through his changes to Twitter, Musk has helped his new ally Trump flip over the boulder, and now all the demons that were wriggling beneath are loosed on civilization.

Should we, as Jews, tolerate the demons in exchange for Trump’s tough-guy act on Iran? Just like the evangelicals previously turned a blind eye to Trump’s philandering, his sexual assaults, his gleeful cruelty, his spitting on everything Christianity was ever supposed to stand for, simply because he promised them the Supreme Court justices to overturn Roe v. Wade? Faced with a man who’s never had a human relationship in his life that wasn’t entirely transactional, should we be transactional ourselves?

I’m not convinced that even if we did, we’d be getting a good bargain. Iran is no longer alone, but part of an axis that includes China, Russia, and North Korea. These countries prop up each other’s economies and militaries; they survive only because of each other. As others have pointed out, the new Axis is actually more tightly integrated than the Axis powers ever were in WWII. The new Axis has already invaded Ukraine and perhaps soon Taiwan and South Korea. It credibly threatens to end the Pax Americana. And to face Hamas or Hezbollah is to face Iran is to face the entire new Axis.

Now Kamala is not Winston Churchill. But at least she doesn’t consider the tyrants of Russia, China, and North Korea to be her personal friends, trustworthy because they flatter her. At least she, unlike Trump, realizes that the current governments of China, Russia, North Korea, and Iran do indeed form a new axis of evil, and she has the glimmers of consciousness that the founders of the United States stood for something different from what those tyrannies stand for, and that this other thing that our founders stood for was good. If war does come, at least she’ll listen to the advice of generals, rather than clowns and lackeys. And if Israel or America do end up in wars of survival, from the bottom of my heart she’s the one I’d rather have in charge. For if she’s in charge, then through her, the government of the United States is still in charge. Our ripped and tattered flag yet waves. If Trump is in charge, who or what is at the wheel besides his own unhinged will, or that of whichever sordid fellow-gangster currently has his ear?

So, yes, as a human being and also as a Jew, this is why I voted early for Kamala, and why I hope you’ll vote for her too. If you disagree with her policies, start fighting those policies once she’s inaugurated on January 20, 2025. At least there will still be a republic, with damaged but functioning error-correcting machinery, in which you can fight.

All the best,
Scott

More Resources: Be sure to check out Scott Alexander’s election-eve post, which (just like in 2016) endorses any listed candidate other than Trump, but specifically makes the case to voters put off (as Scott is) by Democrats’ wokeness. Also check out Garry Kasparov’s epic tweet-thread on why he supports Kamala, and his essay The United States Cannot Descend Into Authoritarianism.

Posted in The Fate of Humanity | 178 Comments »

Steven Rudich (1961-2024)

November 2nd, 2024

I was sure my next post would be about the election—the sword of Damocles hanging over the United States and civilization as a whole. Instead, I have sad news, but also news that brings memories of warmth, humor, and complexity-theoretic insight.

Steven Rudich—professor at Carnegie Mellon, central figure of theoretical computer science since the 1990s, and a kindred spirit and friend—has died at the too-early age of 63. While I interacted with him much more seldom than I wish I had, it would be no exaggeration to call him one of the biggest influences on my life and career.

I first became aware of Steve at age 17, when I read the Natural Proofs paper that he coauthored with Razborov. I was sitting in the basement computer room at Telluride House at Cornell, and still recall the feeling of awe that came over me with every page. This one paper changed my scientific worldview. It expanded my conception of what the P versus NP problem was about and what theoretical computer science could even _do_—showing how it could turn in on itself, explain its own difficulties in proving problems hard in terms of the truth of those same problems’ hardness, and thereby transmute defeat into victory. I may have been bowled over by the paper’s rhetoric as much as by its results: it was like, you’re allowed to write that way?

I was nearly as impressed by Steve’s PhD thesis, which was full of proofs that gave off the appearance of being handwavy, “just phoning it in,” but were in reality completely rigorous. The result that excited me the most said that, if a certain strange combinatorial conjecture was true, then there was essentially no hope of proving that P≠NP∩coNP relative to a random oracle with probability 1. I played around with the combinatorial conjecture but couldn’t make headway on it; a year or two later, I was excited when I met Clifford Smyth and he told me that he, Kahn, and Saks had just proved it. Rudich’s conjecture directly inspired me to work on what later became the Aaronson-Ambainis Conjecture, which is still unproved, but which if true, similarly implies that there’s no hope of proving P≠BQP relative to a random oracle with probability 1.

When I applied to CS PhD programs in 1999, I wrote about how I wanted to sing the ideas of theoretical computer science from the rooftops—just like Steven Rudich had done, with the celebrated Andrew’s Leap summer program that he’d started at Carnegie Mellon. (How many other models were there? Indeed, how many other models are there today?) I was then honored beyond words when Steve called me on the phone, before anyone else had, and made an hourlong pitch for me to become his student. “You’re what I call a ‘prefab’,” he said. “You already have the mindset that I try to instill in students by the end of their PhDs.” I didn’t have much self-confidence then, which is why I can still quote Steve’s words a quarter-century later. In the ensuing years, when (as often) I doubted myself, I’d think back to that phone call with Steve, and my burning desire to be what he apparently thought I was.

Alas, when I arrived in Pittsburgh for CMU’s visit weekend, I saw Steve holding court in front of a small crowd of students, dispensing wisdom and doing magic tricks. I was miffed that he never noticed or acknowledged me: had he already changed his mind about me, lost interest? It was only later that I learned that Steve was going blind at the time, and literally hadn’t seen me.

In any case, while I came within a hair of accepting CMU’s offer, in the end I chose Berkeley. I wasn’t yet 100% sure that I wanted to do quantum computing (as opposed to AI or classical complexity theory), but the lure of the Bay Area, of the storied CS theory group where Steve himself had studied, and of Steve’s academic sibling Umesh Vazirani proved too great.

Full of regrets about the road not taken, I was glad that, in the summer between undergrad and PhD, I got to attend the PCMI summer school on computational complexity at the Institute for Advanced Study in Princeton, where Steve gave a spectacular series of lectures. By that point, Steve was almost fully blind. He put transparencies up, sometimes upside-down until the audience corrected him, and then lectured about them entirely from memory. He said that doing CS theory sightless was a new, more conceptual experience for him.

Even in his new condition, Steve’s showmanship hadn’t left him; he held the audience spellbound as few academics do. And in a special lecture on “how to give talks,” he spilled his secrets.

“What the speaker imagines the audience is thinking,” read one slide. And then, inside the thought bubbles: “MORE! HARDER! FASTER! … Ahhhhh yes, QED! Truth is beauty.”

“What the audience is actually thinking,” read the next slide, below which: “When is this over? I need to pee. Can I get a date with the person next to me?” (And this was before smartphones.) And yet, Steve explained, rather than resenting the many demands on the audience’s attention, a good speaker would break through, meet people where they were, just as he was doing right then.

I listened, took mental notes, resolved to practice this stuff. I reflected that, even if my shtick only ever became 10% as funny or fluid as Steve’s, I’d still come out way ahead.

It’s possible that the last time I saw Steve was in 2007, when I visited Carnegie Mellon to give a talk about algebrization, a new barrier to solving P vs. NP (and other central problems of complexity theory) that Avi Wigderson and I had recently discovered. When I started writing the algebrization paper, I very consciously modeled it after the Natural Proofs paper; the one wouldn’t have been thinkable without the other. So you can imagine how much it meant to me when Steve liked algebrization—when, even though he couldn’t see my slides, he got enough from the spoken part of the talk to burst with “conceptual” questions and comments.

Steve not only peeled back the mystery of P vs NP insofar as anyone has. He did it with exuberance and showmanship and humor and joy and kindness. I won’t forget him.

I’ve written here only about the tiniest sliver of Steve’s life: namely, the sliver where it intersected mine. I wish that sliver were a hundred times bigger, so that there’d be a hundred times more to write. But CS theory, and CS more broadly, are communities. When I posted about Steve’s passing on Facebook, I got inundated by comments from friends of mine who (as it turned out) had taken Steve’s courses, or TA’d for him, or attended Andrew’s Leap, or otherwise knew him, and on whom he’d left a permanent impression—and I hadn’t even known any of this.

So I’ll end this post with a request: please share your Rudich stories in the comments! I’d especially love specific recollections of his jokes, advice, insights, or witticisms. We now live in a world where, even in the teeth of the likelihood that P≠NP, powerful algorithms running in massive datacenters nevertheless try to replicate the magic of human intelligence, by compressing and predicting all the text on the public Internet. I don’t know where this is going, but I can’t imagine that it would hurt for the emerging global hive-mind to know more about Steven Rudich.

Posted in Announcements, Complexity | 11 Comments »

My podcast with Brian Greene

October 18th, 2024

Yes, he’s the guy from The Elegant Universe book and TV series. Our conversation is 1 hour 40 minutes; as usual I strongly recommend listening at 2x speed. The topics, chosen by Brian, include quantum computing (algorithms, hardware, error-correction … the works), my childhood, the interpretation of quantum mechanics, the current state of AI, the future of sentient life in the cosmos, and mathematical Platonism. I’m happy with how it turned out; in particular, my verbal infelicities seem to have been at a minimum this time. I recommend skipping the YouTube comments if you want to stay sane, but do share your questions and reactions in the comments here. Thanks to Brian and his team for doing this. Enjoy!

Update (Oct. 28): If that’s not enough Scott Aaronson video content for you, please enjoy another quantum computing podcast interview, this one with Ayush Prakash and shorter (clocking in at 45 minutes). Ayush pitched this podcast to me as an opportunity to explain quantum computing to Gen Z. Thus, I considered peppering my explanations of interference and entanglement with such phrases as ‘fo-shizzle’ and ‘da bomb,’ but I desisted after reflecting that whatever youth slang I knew was probably already outdated whenever I’d picked it up, back in the twentieth century.

Posted in Complexity, Quantum, Speaking Truth to Parallelism | 64 Comments »

My Nutty, Extremist Beliefs

October 13th, 2024

In nearly twenty years of blogging, I’ve unfortunately felt more and more isolated and embattled. It now feels like anything I post earns severe blowback, from ridicule on Twitter, to pseudonymous comment trolls, to scary and aggressive email bullying campaigns. Reflecting on this, though, I came to see that such strong reactions are an understandable response to my extremist stances. When your beliefs smash the Overton Window into tiny shards like mine do, what do you expect? Just consider some of the intransigent, hard-line stances I’ve taken here on Shtetl-Optimized:

(1) US politics. I’m terrified of right-wing authoritarian populists and their threat to the Enlightenment. For that and many other reasons, I vote straight-ticket Democrat, donate to Democratic campaigns, and encourage everyone else to do likewise. But I also wish my fellow Democrats would rein in the woke stuff, stand up more courageously to the world’s autocrats, and study more economics, so they understand why rent control, price caps, and other harebrained interventions will always fail.

(2) Quantum computing. I’m excited about the prospects of QC, so much that I’ve devoted most of my career to that field. But I also think many of QC’s commercial applications have been wildly oversold to investors, funding agencies, and the press, and I haven’t been afraid to say so.

(3) AI. I think the spectacular progress of AI over the past few years raises scary questions about where we’re headed as a species. I’m neither in the camp that says “we’ll almost certainly die unless we shut down AI research,” nor the camp that says “the good guys need to race full-speed ahead to get AGI before the bad guys get it.” I’d like us to proceed in AI research with caution and guardrails and the best interests of humanity in mind, rather than the commercial interests of particular companies.

(4) Climate change. I think anthropogenic climate change is 100% real and one of the most urgent problems facing humanity, and those who deny this are being dishonest or willfully obtuse. But because I think that, I also think it’s way past time to explore technological solutions like modular nuclear reactors, carbon capture, and geoengineering. I think we can’t virtue-signal or kumbaya our way out of the climate crisis.

(5) Feminism and dating. I think the emancipation of women is one of the modern world’s greatest triumphs. I reserve a special hatred for misogynistic, bullying men. But I also believe, from experience, that many sensitive, nerdy guys severely overcorrected on feminist messaging, to the point that they became terrified of the tiniest bit of assertiveness or initiative in heterosexual courtship. I think this terror has led millions of them to become bitter “incels.” I want to figure out ways to disrupt the incel pipeline, by teaching shy nerdy guys to have healthy, confident dating lives, without thereby giving asshole guys license to be even bigger assholes.

(6) Israel/Palestine. I’m passionately in favor of Israel’s continued existence as a Jewish state, without which my wife’s family and many of my friends’ and colleagues’ families would have been exterminated. However, I also despise Bibi and the messianic settler movement to which he’s beholden. I pray for a two-state solution where Israelis and Palestinians will coexist in peace, free from their respective extremists.

(7) Platonism. I think that certain mathematical questions, like the Axiom of Choice or the Continuum Hypothesis, might not have any Platonic truth-value, there being no fact of the matter beyond what can be proven from various systems of axioms. But I also think, with Gödel, that statements of elementary arithmetic, like the Goldbach Conjecture or P≠NP, are just Platonically true or false independent of any axiom system.

(8) Science and religion. As a secular rationalist, I’m acutely aware that no ancient religion can be “true,” in the sense believed by either the ancients or modern fundamentalists. Still, the older I’ve gotten, the more I’ve come to see religions as vast storehouses containing (among much else) millennia of accumulated wisdom about how humans can or should live. As in the parable of Chesterton’s Fence, I think this wisdom is often far from obvious and nearly impossible to derive from first principles. So I think that, at the least, secularists will need to figure out their own long-term methods to encourage many of the same things that religion once did—such as stable families, childbirth, self-sacrifice and courage in defending one’s community, and credible game-theoretic commitments to keeping promises and various other behaviors.

(9) Foreign policy and immigration. I’d like the US to stand more courageously against evil regimes, such as those of China, Russia, and Iran. At the same time, I’d like the US to open our gates much wider to students, scientists, and dissidents from those nations who seek freedom in the West. I think our refusal to do enough of this is a world-historic self-own.

(10) Academia vs. industry. I think both have advantages and disadvantages for people in CS and other technical fields. At their best, they complement each other. When advising a student which path to pursue, I try to find out all I can about the student’s goals and personality.

(11) Population ethics. I’m worried about how the earth will support 9 or 10 billion people with first-world living standards, which is part of why I’d like career opportunities for women, girls’ education, contraception, and (early-term) abortion to become widely available everywhere on earth. All the same, I’m not an antinatalist. I think raising one or more children in a loving home should generally be celebrated as a positive contribution to the world.

(12) The mind-body problem. I think it’s possible that there’s something profound we don’t yet understand about consciousness and its relation to the physical world. At the same time, I think the burden is clearly on the mind-body dualists to articulate what that something might be, and how to reconcile it with the known laws of physics. I admire the audacity of Roger Penrose in tackling this question head-on, but I don’t think his solution works.

(13) COVID response. I think the countries that did best tended to be those that had some coherent stategy—whether that was “let the virus rip, keep schools open, quarantine only the old and sick,” or “aggressively quarantine everyone and wait for a vaccine.” I think countries torn between these strategies, like the US, tended to get the worst of all worlds. On the other hand, I think the US did one huge thing right, which was greatly to accelerate (by historical standards) the testing and distribution of the mRNA vaccines. For the sake of the millions who died and the billions who had their lives interrupted, I only wish we’d rushed the vaccines much more. We ought now to be spending trillions on a vaccine pipeline that’s ready to roll within weeks as soon as the next pandemic hits.

(14) P versus NP. From decades of intuition in math and theoretical computer science, I think we can be fairly confident of P≠NP—but I’d “only” give it, say, 97% odds. Here as elsewhere, we should be open to the possibility of world-changing surprises.

(15) Interpretation of QM. I get really annoyed by bad arguments against the Everett interpretation, which (contrary to a popular misconception) I understand to result from scientifically conservative choices. But I’m also not an Everettian diehard. I think that, if you push questions like “but is anyone home in the other branches?” hard enough, you arrive at questions about personal identity and consciousness that were profoundly confusing even before quantum mechanics. I hope we someday learn something new that clarifies the situation.

Anyway, with extremist, uncompromising views like those, is it any surprise that I get pilloried and denounced so often?

All the same, I sometimes ask myself: what was the point of becoming a professor, seeking and earning the hallowed protections of tenure, if I can’t then freely express radical, unbalanced, batshit-crazy convictions like the ones in this post?

Posted in Complexity, Metaphysical Spouting, Obviously I'm Not Defending Aaronson, Quantum, The Fate of Humanity | 288 Comments »

My October 7 post

October 7th, 2024

For weeks I agonized over what, if anything, this post should say. How does one commemorate a tragedy that isn’t over for millions of innocents on either side? How do I add to what friend-of-the-blog Boaz Barak and countless others have already written?

Do I review the grisly details of Black Shabbat, tell the stories of those murdered or still held hostage? Do I rage about the shocking intelligence and operational failures that allowed it to happen? Talk about the orders-of-magnitude spikes in antisemitic incidents all over the world in the past year, which finally answered the question of whether I was going to deal with “the burden of having been born Jewish” as a central concern of my life, rather than only a matter for holidays and history books and museums? Mourn the friends I’ve lost—not, interestingly, my Iranian friends (who were the first to ask after the safety of my Israeli family after October 7) or my other Gentile friends, but mostly my far-left Jewish former friends, the ones who now ludicrously argue that worldwide violence against Jews is justified, and will stop if only we give in and dismantle Israel? I wrote many drafts only to delete them.

The core problem was that there seemed to be nothing I could say that would move the needle, that wouldn’t just be a waste of electrons. From the many times I’d already waded into this minefield of minefields since October 7, 2023, I already knew exactly how it would play out:

Those who support Israel’s continued existence (Jews and non-Jews) would applaud what I said—but they wouldn’t need to hear it anyway.
Those who oppose Israel’s continued existence would send me hate mail, spam my comment section with threats and attacks under invented identities, and otherwise do what they could to make my life miserable.
Everyone else would ignore my post, waiting for me to get back to quantum computing or AI.

What could I do to break through? What could I say to all the people who call themselves “anti-Israel but not antisemitic” that would actually move the conversation forward?

Finally I came up with something. Look: you say you despise Zionism, and consider October 7 to have been perfectly understandable (if somewhat distasteful) resistance by the oppressed? Fine, then.

I urge you to lobby your country to pass a law granting automatic refugee status and citizenship to any current citizen of Israel—as an ultimate insurance policy to incentivize Israel to take greater risks for peace, even with neighbors who openly proclaim the Jews’ extermination as their goal.

When the Jews of Europe faced annihilation in my grandparents’ time, not one country offered to rescue them in more than token numbers. That’s a central reason why, in 1947, the newly-formed UN voted to partition the former British Mandate for Palestine and give the Jews a piece of it: not only because of Jews’ historic connection to the land, predating the Islamic conquest of the Middle East by thousands of years, but also, crucially, because the survivors literally had nowhere else on earth to go.

So, you say you want the hated “settler-colonialists” to leave Palestine. Very well then: give them a place to go. All of them, not just the minority who are dual citizens or otherwise have options.

If the US or UK or Australia or France or Germany or any other country actually passed such an immigration law—well, I can’t determine how the Israelis would respond. I expect that tens of thousands of Israelis would quickly take your country up on its offer, while the majority wouldn’t. I expect that some Jewish and Israeli institutions would criticize you, seeing a desire for Israel’s end in your offer even if you were careful never to say as much.

But I can tell you how I’d respond, and I don’t think I’d be alone in this. I would move to the left on Israel/Palestine. For the first time, the Israeli Jews would plausibly no longer be in an existential struggle, a struggle not to be exterminated by neighbors who tried to exterminate them at every opportunity from 1929 to 1948 to 1967 to 1973 to 2002 to 2023. For the first time there’d be a viable backup plan.

As a direct consequence, I’d advocate that the Israelis take bigger gambles for peace: for example, that they unilaterally withdraw from the West Bank to allow a Palestinian state there, even at the risk that the West Bank turns into a much bigger Gaza, another Hamas staging-ground from which to invade Israel and destroy it. At least there’d be an insurance policy if that happened.

Many will ask: shouldn’t the Palestinians also be offered refuge in other lands? I say, by all means! But crucially, that’s not for me to advocate: if I did, I’d be accused of secretly plotting ethnic cleansing and Israeli expansionism. This is between the Palestinian people and all the other nations, in the Middle East and elsewhere, that for generations could’ve offered refuge to displaced Palestinians (as Israel offered refuge to the displaced Jews from Arab lands) but that chose not to.

And what of all the world’s other oppressed peoples? I promise to praise and honor any nation that saves anyone from oppression or genocide by offering them refuge. But, particularly since last October, the left is obsessed with Israel, which it considers uniquely evil among all nations to have ever existed—so that’s the conflict about which I’m proposing a positive step.

And if the anti-Israel people throw the proposal back in my face, tell me it’s not their job to resettle the hated settlers: then at least we know where we stand. They’ve then told me, not merely that they want half the world’s Jews evicted from their homes, but that they’re totally unconcerned with _what happens to them afterward_—fully aware that last time, the answer was pits full of corpses, piles of ash, plumes of black smoke.

And that’s the exact point where we reach the end of discussion and argument, such as can happen on blogs. The remaining disagreement can (alas) only be settled on the battlefield. For whatever it’s worth, the Jews famously outlasted the Egyptians, Assyrians, Babylonians, Seleucids, Romans, Soviets, Nazis, and other continent-spanning empires that tried to destroy us. Whether we need missiles, planes, ground invasions, or (yes) exploding pagers, I predict that we’ll survive this latest existential war too, against the Ayatollah regime and its proxies and its millions of Western dupes. Or at least, I predict that we’ll win in the physical world, even while our enemies continue to dominate Facebook and Twitter and the comments section of the Washington Post, where they’ll continue ordering Israelis to “GO BACK TO POLAND,” totally uninterested in the question of whether Poland will take them. I can probably teach myself to live with that. At any rate, better offline victory and online defeat than the other way around.

Posted in The Fate of Humanity | 143 Comments »

Quantum advantage for NP approximation? For REAL this time?

October 5th, 2024

The other night I spoke at a quantum computing event and was asked—for the hundredth time? the thousandth?—whether I agreed that the quantum algorithm called QAOA was poised revolutionize industries by finding better solutions to NP-hard optimization problems. I replied that while serious, worthwhile research on that algorithm continues, alas, so far I have yet to see a single piece of evidence that QAOA outperforms the best classical heuristics on any problem that anyone cares about. (Note added: in the comments, Ashley Montanaro shares a paper with empirical evidence that QAOA provides a modest polynomial speedup over known classical heuristics for random k-SAT. This is the best/only such evidence I’ve seen, and which still stands as far as I know!)

I added I was sad to see the arXiv flooded with thousands of relentlessly upbeat QAOA papers that dodge the speedup question by simply never raising it at all. I said that, in my experience, these papers reliably led outsiders to conclude that surely there must be lots of excellent known speedups from QAOA—since otherwise, why would so many people be writing papers about it?

Anyway, the person right after me talked about a “quantum dating app” (!) they were developing.

I figured that, as usual, my words had thudded to the ground with zero impact, truth never having had a chance against what sounds good and what everyone wants to hear.

But then, the morning afterward, someone from the audience emailed me that, incredulous at my words, he went through a bunch of QAOA papers, looking for the evidence of its beating classical algorithms that he knew must be in them, and was shocked to find the evidence missing, just as I had claimed! So he changed his view.

That one message filled me with renewed hope about my ability to inject icy blasts of reality into the quantum algorithms discourse.

So, with that prologue, surely I’m about to give you yet another icy blast of quantum algorithms not helping for optimization problems?

Aha! Inspired by Scott Alexander, this is the part of the post where, having led you one way, I suddenly jerk you the other way. My highest loyalty, you see, is not to any narrative, but only to THE TRUTH.

And the truth is this: this summer, my old friend Stephen Jordan and seven coauthors, from Google and elsewhere, put out a striking preprint about a brand-new quantum algorithm for optimization problems that they call Decoded Quantum Interferometry (DQI). This week Stephen was gracious enough to explain the new algorithm in detail when he visited our group at UT Austin.

DQI can be used for a variety of NP-hard optimization problems, at least in the regime of approximation where they aren’t NP-hard. But a canonical example is what the authors call “Optimal Polynomial Intersection” or OPI, which involves finding a low-degree polynomial that intersects as many subsets as possible from a given list. Here’s the formal definition:

OPI. Given integers n<p with p prime, we’re given as input subsets S1,…,Sp-1 of the finite field Fp. The goal is to find a degree-(n-1) polynomial Q that maximizes the number of y∈{1,…,p-1} such that Q(y)∈Sy, i.e. that intersects as many of the subsets as possible.

For this problem, taking as an example the case p-1=10n and |Sy|=⌊p/2⌋ for all y, Stephen et al. prove that DQI satisfies a 1/2 + (√19)/20 ≈ 0.7179 fraction of the p-1 constraints in polynomial time. By contrast, they say the best classical polynomial-time algorithm they were able to find satisfies an 0.55+o(1) fraction of the constraints.

To my knowledge, this is the first serious claim to get a better approximation ratio quantumly for an NP-hard problem, since Farhi et al. made the claim for QAOA solving something called MAX-E3LIN2 back in 2014, and then my blogging about it led to a group of ten computer scientists finding a classical algorithm that got an even better approximation.

So, how did Stephen et al. pull this off? How did they get around the fact that, again and again, exponential quantum speedups only seem to exist for algebraically structured problems like factoring or discrete log, and not for problems like 3SAT or Max-Cut that lack algebraic structure?

Here’s the key: they didn’t. Instead they leaned into the fact, by targeting an optimization problem that (despite being NP-hard) has loads of algebraic structure! The key insight, in their new DQI algorithm, is that the Quantum Fourier Transform can be used to reduce other NP-hard problems to problems of optimal decoding of a suitable error-correcting code. (This insight built on the breakthrough two years ago by Yamakawa and Zhandry, giving a quantum algorithm that gets an exponential speedup for an NP search problem relative to a random oracle.)

Now, sometimes the reduction to a coding theory problem is “out of the frying pan and into the fire,” as the new optimization problem is no easier than the original one. In the special case of searching for a low-degree polynomial, however, the optimal decoding problem ends up being for the Reed-Solomon code, where we’ve known efficient classical algorithms for generations, famously including the Berlekamp-Welch algorithm.

One open problem that I find extremely interesting is whether OPI, in the regime where DQI works, is in coNP or coAM, or has some other identifiable structural feature that presumably precludes its being NP-hard.

Regardless, though, as of this week, the hope of using quantum computers to get better approximation ratios for NP-hard optimization problems is back in business! Will that remain so? Or will my blogging about such an attempt yet again lead to its dequantization? Either way I’m happy.

Posted in Complexity, Quantum, Speaking Truth to Parallelism | 30 Comments »