Shtetl-Optimized

Update: In the comments, Craig Gidney points out that Ronit’s O(n log² n) quantum circuits for the exact QFT were already published by Cleve and Watrous in 2000 (in a paper whose main point was something else, parallelization). Ronit’s O(n (log log n)²) circuits for the approximate QFT still appear to be new (Gidney says he and others knew related techniques but had never explicitly combined them). Of course, while the exact result was Platonically “known,” it wasn’t sufficiently well known that any of the four quantum algorithms experts I’d consulted had heard of it! Hopefully this very post will go some way toward fixing the situation.

Another Update: Richard Cleve writes in to say that the approximate QFT circuits were known also—albeit, in an unpublished 2-page abstract by Ahokas, Hales, and himself from the 2003 ERATO conference, as well as a followup Master’s thesis by Ahokas. Unlike with the exact case, I’m not kicking myself trying to understand how I missed these.

Ironically, I hope this post helps get this prior work a well-deserved mention when the QFT is covered in introductory quantum information classes.

Meanwhile, my hope that Ronit returns to do more theory is undiminished! When I was a kid, I too started by rediscovering things (like the integral for the length of a curve) that were centuries old, then rediscovering things (like an efficient algorithm for isotonic regression) that were decades old, then rediscovering things (like BQP⊆PP) that were about a year old … until I finally started discovering things (like the collision lower bound) that were zero years old. This is the way.

---

In my last post, I tried to nudge the arc of history back onto the narrow path of reasoned dialogue, walking the mile-high tightrope between shrill, unsupported accusation and naïve moral blindness. For my trouble, I was condemned about equally by leftists for my right-wing sympathies and by rightists for my left-wing ones. So today, I’ll ignore the fate of civilization and return to quantum computing theory: a subject that’s reliably brought joy to my life for a quarter-century, and still does, even as my abilities fade. It turns out there is a consolation for advancing age and senility, and it’s called “students.”

This fall, I returned from my two-year leave at OpenAI to teach my undergrad Introduction to Quantum Information Science course at UT Austin. This course doesn’t pretend to bring students all the way to the research frontier, and yet sometimes it’s done so anyway. It was in my first offering of Intro to QIS, eight years ago, that I encountered the then 17-year-old Ewin Tang, who broke the curve and then wanted an independent study project. So I gave her the problem of proving that the Kerenidis-Prakash quantum algorithm achieves an exponential speedup over any classical algorithm for the same task, not expecting anything to come of it. But after a year of work, Ewin refuted my conjecture by dequantizing the K-P algorithm—a breakthrough that led to the demolition of many other hopes for quantum machine learning. (Demolishing people’s hopes? In complexity theory, we call that a proud day’s work.)

Today I’m delighted to announce that my undergrad quantum course has led to another quantum advance. One day, after my lecture, a junior named Ronit Shah came to me with an idea for how best to distinguish three possible states of a qubit, rather than only two. For some reason I didn’t think much of it at the time, even though it would later turn out that Ronit had essentially rediscovered the concept of POVMs, the Pretty Good Measurement (PGM), and the 2002 theorem that the PGM is optimal for distinguishing sets of states subject to a transitive group action.

Later, after I’d lectured about Shor’s algorithm, and one of its centerpieces, the O(n²)-gate recursive circuit for the Quantum Fourier Transform, Ronit struck a second time. He told me it should be possible to give a smaller circuit by recursively reducing the n-qubit QFT to two (n/2)-qubit QFTs, rather than to a single (n-1)-qubit QFT.

This was surely just a trivial confusion, perfectly excusable in an undergrad. Did Ronit perhaps not realize that an n-qubit unitary is actually a 2ⁿ×2ⁿ matrix, so he was proposing to pass directly from 2ⁿ×2ⁿ to 2^n/2×2^n/2, rather than to 2^n-1×2^n-1?

No, he said, he understood that perfectly well. He still thought the plan would work. Then he emailed me a writeup—claiming to implement the exact n-qubit QFT in O(n log²n) gates, the first-ever improvement over O(n²), and also the approximate n-qubit QFT in O(n (log log n)²) gates, the first-ever improvement over O(n log n). He used fast integer multiplication algorithms to make the new recursions work.

At that point, I did something I’m still ashamed of: I sat on Ronit’s writeup for three weeks. When I at last dug it out of my inbox and read it, I could discover no reason why it was wrong, or unoriginal, or unimportant. But I didn’t trust myself, so with Ronit’s permission I sent the work to some of my oldest quantum friends: Ronald de Wolf, Cris Moore, Andrew Childs, and Wim van Dam. They agreed, after some back-and-forth, that the new circuits looked legit. A keystone of Shor’s algorithm, of quantum computing itself, and of my undergrad class had seen its first real improvement since 1994.

Last night Ronit’s paper appeared on the arXiv where you can read it.

In case anyone asks: no, this probably has no practical implication for speeding up factoring on a quantum computer, since the QFT wasn’t the expensive part of Shor’s algorithm anyway—that’s the modular exponentiation—and also, the O(n log n) approximate QFT would already have been used in practice. But it’s conceivable that Ronit’s circuits could speed up other practical quantum computing tasks! And no, we have no idea what’s the ultimate limit here, as usual in circuit complexity. Could the exact n-qubit QFT even be doable in O(n) gates?

I’d love for Ronit to continue in quantum computing theory. But in what’s surely a sign of the times, he’s just gone on leave from UT to intern at an AI hardware startup. I hope he returns and does some more theory, but if he doesn’t, I’m grateful that he shared this little gem with us on his way to more world-changing endeavors.

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 $100B in value, that would still justify a $10B 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!

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:

1. 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.
   
2. 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.
   
3. 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.
   
4. 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.
   
5. 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 ~10²⁵ years if memory is an issue (note that a mere ~10¹⁰ 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.
   
6. Having said that, the biggest caveat to the “10²⁵ 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 ~10²⁵ years for a classical computer to simulate, it would also take ~10²⁵ 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.
   
7. 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.
   
8. 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.
   
9. 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.
   
10. 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!

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!

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!”

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.

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?

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 S₁,…,S_p-1 of the finite field F_p. The goal is to find a degree-(n-1) polynomial Q that maximizes the number of y∈{1,…,p-1} such that Q(y)∈S_y, i.e. that intersects as many of the subsets as possible.

For this problem, taking as an example the case p-1=10n and |S_y|=⌊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.

So, back in June the White House announced that UCLA would host a binational US/India workshop, for national security officials from both countries to learn about the current status of quantum computing and post-quantum cryptography. It fell to my friend and colleague Rafail Ostrovsky to organize the workshop, which ended up being held last week. When Rafi invited me to give the opening talk, I knew he’d keep emailing until I said yes. So, on the 3-hour flight to LAX, I wrote the following talk in a spiral notebook, which I then delivered the next morning with no slides. I called it “Quantum Computing: Between Hope and Hype.” I thought Shtetl-Optimized readers might be interested too, since it contains my reflections on a quarter-century in quantum computing, and prognostications on what I expect soon. Enjoy, and let me know what you think!

---

Quantum Computing: Between Hope and Hype
by Scott Aaronson
September 16, 2024

When Rafi invited me to open this event, it sounded like he wanted big-picture pontification more than technical results, which is just as well, since I’m getting old for the latter. Also, I’m just now getting back into quantum computing after a two-year leave at OpenAI to think about the theoretical foundations of AI safety. Luckily for me, that was a relaxing experience, since not much happened in AI these past two years. [Pause for laughs] So then, did anything happen in quantum computing while I was away?

This, of course, has been an extraordinary time for both quantum computing and AI, and not only because the two fields were mentioned for the first time in an American presidential debate (along with, I think, the problem of immigrants eating pets). But it’s extraordinary for quantum computing and for AI in very different ways. In AI, practice is wildly ahead of theory, and there’s a race for scientific understanding to catch up to where we’ve gotten via the pure scaling of neural nets and the compute and data used to train them. In quantum computing, it’s just the opposite: there’s right now a race for practice to catch up to where theory has been since the mid-1990s.

I started in quantum computing around 1998, which is not quite as long as some people here, but which does cover most of the time since Shor’s algorithm and the rest were discovered. So I can say: this past year or two is the first time I’ve felt like the race to build a scalable fault-tolerant quantum computer is actually underway. Like people are no longer merely giving talks about the race or warming up for the race, but running the race.

Within just the last few weeks, we saw the group at Google announce that they’d used the Kitaev surface code, with distance 7, to encode one logical qubit using 100 or so physical qubits, in superconducting architecture. They got a net gain: their logical qubit stays alive for maybe twice as long as the underlying physical qubits do. And crucially, they find that their logical coherence time increases as they pass to larger codes, with higher distance, on more physical qubits. With superconducting, there are still limits to how many physical qubits you can stuff onto a chip, and eventually you’ll need communication of qubits between chips, which has yet to be demonstrated. But if you could scale Google’s current experiment even to 1500 physical qubits, you’d probably be below the threshold where you could use that as a building block for a future scalable fault-tolerant device.

Then, just last week, a collaboration between Microsoft and Quantinuum announced that, in the trapped-ion architecture, they applied pretty substantial circuits to logically-encoded qubits—-again in a way that gets a net gain in fidelity over not doing error-correction, modulo a debate about whether they’re relying too much on postselection. So, they made a GHZ state, which is basically like a Schrödinger cat, out of 12 logically encoded qubits. They also did a “quantum chemistry simulation,” which had only two logical qubits, but which required three logical non-Clifford gates—which is the hard kind of gate when you’re doing error-correction.

Because of these advances, as well as others—what QuEra is doing with neutral atoms, what PsiQuantum and Xanadu are doing with photonics, etc.—I’m now more optimistic than I’ve ever been that, if things continue at the current rate, either there are useful fault-tolerant QCs in the next decade, or else something surprising happens to stop that. Plausibly we’ll get there not just with one hardware architecture, but with multiple ones, much like the Manhattan Project got a uranium bomb and a plutonium bomb around the same time, so the question will become which one is most economic.

If someone asks me why I’m now so optimistic, the core of the argument is 2-qubit gate fidelities. We’ve known for years that, at least on paper, quantum fault-tolerance becomes a net win (that is, you sustainably correct errors faster than you introduce new ones) once you have physical 2-qubit gates that are ~99.99% reliable. The problem has “merely” been how far we were from that. When I entered the field, in the late 1990s, it would’ve been like a Science or Nature paper to do a 2-qubit gate with 50% fidelity. But then at some point the 50% became 90%, became 95%, became 99%, and within the past year, multiple groups have reported 99.9%. So, if you just plot the log of the infidelity as a function of year and stare at it—yeah, you’d feel pretty optimistic about the next decade too!

Or pessimistic, as the case may be! To any of you who are worried about post-quantum cryptography—by now I’m so used to delivering a message of, maybe, eventually, someone will need to start thinking about migrating from RSA and Diffie-Hellman and elliptic curve crypto to lattice-based crypto, or other systems that could plausibly withstand quantum attack. I think today that message needs to change. I think today the message needs to be: yes, unequivocally, worry about this now. Have a plan.

So, I think this moment is a good one for reflection. We’re used to quantum computing having this air of unreality about it. Like sure, we go to conferences, we prove theorems about these complexity classes like BQP and QMA, the experimenters do little toy demos that don’t scale. But if this will ever be practical at all, then for all we know, not for another 200 years. It feels really different to think of this as something plausibly imminent. So what I want to do for the rest of this talk is to step back and ask, what are the main reasons why people regarded this as not entirely real? And what can we say about those reasons in light of where we are today?

---

Reason #1

For the general public, maybe the overriding reason not to take QC seriously has just been that it sounded too good to be true. Like, great, you’ll have this magic machine that’s gonna exponentially speed up every problem in optimization and machine learning and finance by trying out every possible solution simultaneously, in different parallel universes. Does it also dice peppers?

For this objection, I’d say that our response hasn’t changed at all in 30 years, and it’s simply, “No, that’s not what it will do and not how it will work.” We should acknowledge that laypeople and journalists and unfortunately even some investors and government officials have been misled by the people whose job it was to explain this stuff to them.

I think it’s important to tell people that the only hope of getting a speedup from a QC is to exploit the way that QM works differently from classical probability theory — in particular, that it involves these numbers called amplitudes, which can be positive, negative, or even complex. With every quantum algorithm, what you’re trying to do is choreograph a pattern of interference where for each wrong answer, the contributions to its amplitude cancel each other out, whereas the contributions to the amplitude of the right answer reinforce each other. The trouble is, it’s only for a few practical problems that we know how to do that in a way that vastly outperforms the best known classical algorithms.

What are those problems? Here, for all the theoretical progress that’s been made in these past decades, I’m going to give the same answer in 2024 that I would’ve given in 1998. Namely, there’s the simulation of chemistry, materials, nuclear physics, or anything else where many-body quantum effects matter. This was Feynman’s original application from 1981, but probably still the most important one commercially. It could plausibly help with batteries, drugs, solar cells, high-temperature superconductors, all kinds of other things, maybe even in the next few years.

And then there’s breaking public-key cryptography, which is not commercially important, but is important for other reasons well-known to everyone here.

And then there’s everything else. For problems in optimization, machine learning, finance, and so on, there’s typically a Grover’s speedup, but that of course is “only” a square root and not an exponential, which means that it will take much longer before it’s relevant in practice. And one of the earliest things we learned in quantum computing theory is that there’s no “black-box” way to beat the Grover speedup. By the way, that’s also relevant to breaking cryptography — other than the subset of cryptography that’s based on abelian groups and can be broken by Shor’s algorithm or the like. The centerpiece of my PhD thesis, twenty years ago, was the theorem that you can’t get more than a Grover-type polynomial speedup for the black-box problem of finding collisions in cryptographic hash functions.

So then what remains? Well, there are all sorts heuristic quantum algorithms for classical optimization and machine learning problems — QAOA (Quantum Approximate Optimization Algorithm), quantum annealing, and so on — and we can hope that sometimes they’ll beat the best classical heuristics for the same problems, but it will be trench warfare, not just magically speeding up everything. There are lots of quantum algorithms somehow inspired by the HHL (Harrow-Hassidim-Lloyd) algorithm for solving linear systems, and we can hope that some of those algorithms will get exponential speedups for end-to-end problems that matter, as opposed to problems of transforming one quantum state to another quantum state. We can of course hope that new quantum algorithms will be discovered. And most of all, we can look for entirely new problem domains, where people hadn’t even considered using quantum computers before—new orchards in which to pick low-hanging fruit. Recently, Shih-Han Hung and I, along with others, have proposed using current QCs to generate cryptographically certified random numbers, which could be used in post-state cryptocurrencies like Ethereum. I’m hopeful that people will find other protocol applications of QC like that one — “proof of quantum work.” [Another major potential protocol application, which Dan Boneh brought up after my talk, is quantum one-shot signatures.]

Anyway, taken together, I don’t think any of this is too good to be true. I think it’s genuinely good and probably true!

---

Reason #2

A second reason people didn’t take seriously that QC was actually going to happen was the general thesis of technological stagnation, at least in the physical world. You know, maybe in the 40s and 50s, humans built entirely new types of machines, but nowadays what do we do? We issue press releases. We make promises. We argue on social media.

Nowadays, of course, pessimism about technological progress seems hard to square with the revolution that’s happening in AI, another field that spent decades being ridiculed for unfulfilled promises and that’s now fulfilling the promises. I’d also speculate that, to the extent there is technological stagnation, most of it is simply that it’s become really hard to build new infrastructure—high-speed rail, nuclear power plants, futuristic cities—for legal reasons and NIMBY reasons and environmental review reasons and Baumol’s cost disease reasons. But none of that really applies to QC, just like it hasn’t applied so far to AI.

---

Reason #3

A third reason people didn’t take this seriously was the sense of “It’s been 20 years already, where’s my quantum computer?” QC is often compared to fusion power, another technology that’s “eternally just over the horizon.” (Except, I’m no expert, but there seems to be dramatic progress these days in fusion power too!)

My response to the people who make that complaint was always, like, how much do you know about the history of technology? It took more than a century for heavier-than-air flight to go from correct statements of the basic principle to reality. Universal programmable classical computers surely seemed more fantastical from the standpoint of 1920 than quantum computers seem today, but then a few decades later they were built. Today, AI provides a particularly dramatic example where ideas were proposed a long time ago—neural nets, backpropagation—those ideas were then written off as failures, but no, we now know that the ideas were perfectly sound; it just took a few decades for the scaling of hardware to catch up to the ideas. That’s why this objection never had much purchase by me, even before the dramatic advances in experimental quantum error-correction of the last year or two.

---

Reason #4

A fourth reason why people didn’t take QC seriously is that, a century after the discovery of QM, some people still harbor doubts about quantum mechanics itself. Either they explicitly doubt it, like Leonid Levin, Roger Penrose, or Gerard ‘t Hooft. Or they say things like, “complex Hilbert space in 2ⁿ dimensions is a nice mathematical formalism, but mathematical formalism is not reality”—the kind of thing you say when you want to doubt, but not take full intellectual responsibility for your doubts.

I think the only thing for us to say in response, as quantum computing researchers—and the thing I consistently have said—is man, we welcome that confrontation! Let’s test quantum mechanics in this new regime. And if, instead of building a QC, we have to settle for “merely” overthrowing quantum mechanics and opening up a new era in physics—well then, I guess we’ll have to find some way to live with that.

---

Reason #5

My final reason why people didn’t take QC seriously is the only technical one I’ll discuss here. Namely, maybe quantum mechanics is fine but fault-tolerant quantum computing is fundamentally “screened off” or “censored” by decoherence or noise—and maybe the theory of quantum fault-tolerance, which seemed to indicate the opposite, makes unjustified assumptions. This has been the position of Gil Kalai, for example.

The challenge for that position has always been to articulate, what is true about the world instead? Can every realistic quantum system be simulated efficiently by a classical computer? If so, how? What is a model of correlated noise that kills QC without also killing scalable classical computing?—which turns out to be a hard problem.

In any case, I think this position has been dealt a severe blow by the Random Circuit Sampling quantum supremacy experiments of the past five years. Scientifically, the most important thing we’ve learned from these experiments is that the fidelity seems to decay exponentially with the number of qubits, but “only” exponentially — as it would if the errors were independent from one gate to the next, precisely as the theory of quantum fault-tolerance assumes. So for anyone who believes this objection, I’d say that the ball is now firmly in their court.

---

So, if we accept that QC is on the threshold of becoming real, what are the next steps? There are the obvious ones: push forward with building better hardware and using it to demonstrate logical qubits and fault-tolerant operations on them. Continue developing better error-correction methods. Continue looking for new quantum algorithms and new problems for those algorithms to solve.

But there’s also a less obvious decision right now. Namely, do we put everything into fault-tolerant qubits, or do we continue trying to demonstrate quantum advantage in the NISQ (pre-fault-tolerant) era? There’s a case to be made that fault-tolerance will ultimately be needed for scaling, and anything you do without fault-tolerance is some variety of non-scalable circus trick, so we might as well get over the hump now.

But I’d like to advocate putting at least some thought into how to demonstrate a quantum advantage in the near-term. Thay could be via cryptographic protocols, like those that Kahanamoku-Meyer et al. have proposed. It could be via pseudorandom peaked quantum circuits, a recent proposal by me and Yuxuan Zhang—if we can figure out an efficient way to generate the circuits. Or we could try to demonstrate what William Kretschmer, Harry Buhrman, and I have called “quantum information supremacy,” where, instead of computational advantage, you try to do an experiment that directly shows the vastness of Hilbert space, via exponential advantages for quantum communication complexity, for example. I’m optimistic that that might be doable in the very near future, and have been working with Quantinuum to try to do it.

On the one hand, when I started in quantum computing 25 years ago, I reconciled myself to the prospect that I’m going to study what fundamental physics implies about the limits of computation, and maybe I’ll never live to see any of it experimentally tested, and that’s fine. On the other hand, once you tell me that there is a serious prospect of testing it soon, then I become kind of impatient. Some part of me says, let’s do this! Let’s try to achieve forthwith what I’ve always regarded as the #1 application of quantum computers, more important than codebreaking or even quantum simulation: namely, disproving the people who said that scalable quantum computing was impossible.

Dan Faggella recorded an unusual podcast with me that’s now online. He introduces me as a “quantum physicist,” which is something that I never call myself (I’m a theoretical computer scientist) but have sort of given up on not being called by others. But the ensuing 85-minute conversation has virtually nothing to do with physics, or anything technical at all.

Instead, Dan pretty much exclusively wants to talk about moral philosophy: my views about what kind of AI, if any, would be a “worthy successor to humanity,” and how AIs should treat humans and vice versa, and whether there’s any objective morality at all, and (at the very end) what principles ought to guide government regulation of AI.

So, I inveigh against “meat chauvinism,” and expand on the view that locates human specialness (such as it is) in what might be the unclonability, unpredictability, and unrewindability of our minds, and plead for comity among the warring camps of AI safetyists.

The central point of disagreement between me and Dan ended up centering around moral realism: Dan kept wanting to say that a future AGI’s moral values would probably be as incomprehensible to us as are ours to a sea snail, and that we need to make peace with that. I replied that, firstly, things like the Golden Rule strike me as plausible candidates for moral universals, which all thriving civilizations (however primitive or advanced) will agree about in the same way they agree about 5 being a prime number. And secondly, that if that isn’t true—if the morality of our AI or cyborg descendants really will be utterly alien to us—then I find it hard to have any preferences at all about the future they’ll inhabit, and just want to enjoy life while I can! That which (by assumption) I can’t understand, I’m not going to issue moral judgments about either.

Anyway, rewatching the episode, I was unpleasantly surprised by my many verbal infelicities, my constant rocking side-to-side in my chair, my sometimes talking over Dan in my enthusiasm, etc. etc., but also pleasantly surprised by the content of what I said, all of which I still stand by despite the terrifying moral minefields into which Dan invited me. I strongly recommend watching at 2x speed, which will minimize the infelicities and make me sound smarter. Thanks so much to Dan for making this happen, and let me know what you think!

Added: See here for other podcasts in the same series and on the same set of questions, including with Nick Bostrom, Ben Goertzel, Dan Hendrycks, Anders Sandberg, and Richard Sutton.