Shtetl-Optimized

2020 sucks.

Yesterday I learned that David Poulin, a creative and widely-beloved quantum computing and information theorist, has died at age 43, of an aggressive brain cancer. After studying under many of the field’s legends—Gilles Brassard, Wojciech Zurek, Ray Laflamme, Gerard Milburn, John Preskill—David became a professor at the University of Sherbrooke in Quebec. There he played a leading role in CIFAR (the Canadian Institute For Advanced Research), eventually co-directing its quantum information science program with Aephraim Steinberg. Just this fall (!), David moved to Microsoft Research to start a new phase of his career. He’s survived by a large family.

While I can’t claim any deep knowledge of David’s work—he and I pursued very different problems—it seems appropriate to mention some of his best-known contributions. With David Kribs, Ray Laflamme, and Maia Lesosky, he introduced the formalism of operator quantum error correction, and made many other contributions to the theory of quantum error-correction and fault-tolerance (including the estimation of thresholds). He and coauthors showed in a Nature paper how to do quantum state tomography on 1D matrix product states efficiently. With Pavithran Iyer, he proved that optimal decoding of stabilizer codes is #P-hard.

And if none of that makes a sufficient impression on Shtetl-Optimized readers: well, back in 2013, when D-Wave was claiming to have achieved huge quantum speedups, David Poulin was one of the few experts willing to take a clear skeptical stance in public (including right in my comment section—see here for example).

I vividly remember being officemates with David back in 2003, at the Perimeter Institute in Waterloo—before Perimeter had its sleek black building, when it still operated out of a converted tavern. (My and David’s office was in the basement, reached via a narrow staircase.) David liked to tease me: for example, if I found him in conversation with someone else and asked what it was about, he’d say, “oh, nothing to do with computational efficiency, no reason for you to care.” (And yet, much of David’s work ultimately would have to do with computational efficiency.)

David was taken way too soon and will be missed by everyone who knew him. Feel free to share David stories in the comments.

Follow

Time for a non-depressing post. Quantum Computing Since Democritus, which is already available in English and Russian, is about to be published in both Chinese and Japanese. (So if you read this blog, but have avoided tackling QCSD because your Chinese or Japanese is better than your English, today’s your day!) To go along with the new editions, Cambridge University Press asked me to write a new foreword, reflecting on what happened in the seven years since the book was published. The editor, Paul Dobson, kindly gave me permission to share the new foreword on my blog. So without further ado…

Quantum Computing Since Democritus began its life as a course that I taught at the University of Waterloo in 2006.  Seven years later, it became the book that you now hold.  Its preface ended with the following words:

Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 lecture notes were in 2013.

As I write this, in June 2020, a lot has happened that I would never have predicted in 2013.  Donald Trump is the President of the United States, and is up for reelection shortly.  This is not a political book, so let me resist the urge to comment further.  Meanwhile, the coronavirus pandemic is ravaging the world, killing hundreds of thousands of people, crashing economies, and shutting down schools and universities (including mine).  And in the past few weeks, protests against racism and police brutality started in America and then spread to the world, despite the danger of protesting during a pandemic.

Leaving aside the state of the world, my own life is also very different than it was seven years ago.  Along with my family, I’ve moved from MIT to the University of Texas in Austin.  My daughter, who was born at almost exactly the same time as Quantum Computing Since Democritus, is now a first-grader, and is joined by a 3-year-old son.  When my daughter’s school shut down due to the coronavirus, I began home-schooling her in math, computer science, and physics—in some of the exact same topics covered in this book.  I’m now engaged in an experiment to see what portion of this material can be made accessible to a 7-year-old.

But what about the material itself?  How has it held up over seven years?  Both the bad news and the (for you) good news, I suppose, is that it’s not particularly out of date.  The intellectual underpinnings of quantum computing and its surrounding disciplines remain largely as they were.  Still, let me discuss what has changed.

Between 2013 and 2020, the field of quantum computing made a striking transition, from a mostly academic pursuit to a major technological arms race.  The Chinese government, the US government, and the European Union have all pledged billions of dollars for quantum computing research.  Google, Microsoft, IBM, Amazon, Alibaba, Intel, and Honeywell also now all have well-funded groups tasked with building quantum computers, or providing quantum-computing-related software and services, or even just doing classical computing that’s “quantum-inspired.”  These giants are joined by dozens of startups focused entirely on quantum computing.

The new efforts vary greatly in caliber; some efforts seem rooted in visions of what quantum computers will be able to help with, and how soon, that I find to be wildly overoptimistic or even irresponsible.  But perhaps it’s always this way when a new technology moves from an intellectual aspiration to a commercial prospect.  Having joined the field around 1999, before there were any commercial efforts in quantum computing, I’ve found the change disorienting.

But while some of the new excitement is based on pure hype—on marketers now mixing some “quantum” into their word-salad of “blockchain,” “deep learning,” etc., with no particular understanding of any of the ingredients—there really have been some scientific advances in quantum computing since 2013, a fire underneath the smoke.

Surely the crowning achievement of quantum computing during this period was the achievement of “quantum supremacy,” which a team at Google announced in the fall of 2019.  For the first time, a programmable quantum computer was used to outperform any classical computer on earth, running any currently known algorithm.  Google’s device, called “Sycamore,” with 53 superconducting qubits cooled to a hundredth of a degree above absolute zero, solved a well-defined albeit probably useless sampling problem in about 3 minutes.  To compare, current state-of-the-art simulations on classical computers need a few days, even with hundreds of thousands of parallel processors.  Ah, but will a better classical simulation be possible?  That’s an open question in quantum complexity!  The discussion of that question draws on theoretical work that various colleagues and I did over the past decade.  That work in turn draws on my so-called PostBQP=PP theorem from 2004, explained in this book.

In the past seven years, there were also several breakthroughs in quantum computing theory—some of which resolved open problems mentioned in this book. 

In 2018, Ran Raz and Avishay Tal gave an oracle relative to which BQP (Bounded-Error Quantum Polynomial-Time) is not contained in PH (the Polynomial Hierarchy).  This solved one of the main open questions, since 1993, about where BQP fits in with classical complexity classes, at least in the black-box setting.  (What does that mean?  Read the book!)  Raz and Tal’s proof used a candidate problem that I had defined in 2009 and called “Forrelation.”

Also in 2018, Urmila Mahadev gave a protocol, based on cryptography, by which a polynomial-time quantum computer (i.e., a BQP machine) could always prove the results of its computation to a classical polynomial-time skeptic, purely by exchanging classical messages with the skeptic.  Following Urmila’s achievement, I was delighted to give her a $25 prize for solving the problem that I’d announced on my blog back in 2007.

Perhaps most spectacularly of all, in 2020, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP*=RE.  Here MIP* means the class of problems solvable using multi-prover interactive proof systems with quantumly entangled provers (and classical polynomial-time verifiers), while RE means Recursively Enumerable: a class that includes not only all the computable problems, but even the infamous halting problem (!).  To say it more simply, entangled provers can convince a polynomial-time verifier that an arbitrary Turing machine halts.  Besides its intrinsic interest, a byproduct of this breakthrough was to answer a decades-old question in pure math, the so-called Connes Embedding Conjecture (by refuting the conjecture).  To my knowledge, the new result represents the first time that quantum computing has reached “all the way up the ladder of hardness” to touch uncomputable problems.  It’s also the first time that non-relativizing techniques, like the ones central to the study of interactive proofs, were ever used in computability theory.

In a different direction, the last seven years have witnessed an astonishing convergence between quantum information and quantum gravity—something that was just starting when Quantum Computing Since Democritus appeared in 2013, and that I mentioned as an exciting new direction.  Since then, the so-called “It from Qubit” collaboration has brought together quantum computing theorists with string theorists and former string theorists—experts in things like the black hole information problem—to develop a shared language.  One striking proposal that’s emerged from this is a fundamental role for quantum circuit complexity—that is, the smallest number of 1- and 2-qubit gates needed to prepare a given n-qubit state from the all-0 state—in the so-called AdS/CFT (Anti de Sitter / Conformal Field Theory) correspondence.  AdS/CFT is a duality between physical theories involving different numbers of spatial dimensions; for more than twenty years, it’s been a central testbed for ideas about quantum gravity.  But the duality is extremely nonlocal: a “simple” quantity in the AdS theory, like the volume of a wormhole, can correspond to an incredibly “complicated” quantity in the dual CFT.  The new proposal is that the CFT quantity might be not just complicated, but literally circuit complexity itself.  Fanciful as that sounds, the truth is that no one has come up with any other proposal that passes the same sanity checks.  A related new insight is that the nonlocal mapping between the AdS and CFT theories is not merely analogous to, but literally an example of, a quantum error-correcting code: the same mathematical objects that will be needed to build scalable quantum computers.

When Quantum Computing Since Democritus was first published, some people thought it went too far in elevating computer science, and computational complexity in particular, to fundamental roles in understanding the physical world.  But even I wasn’t audacious enough to posit connections like the ones above, which are now more-or-less mainstream in quantum gravity research.

I’m proud that I wrote Quantum Computing Since Democritus, but as the years go by, I find that I have no particular desire to revise it, or even reread it.  It seems far better for the book to stand as a record of what I knew and believed and cared about at a certain moment in time.

The intellectual quest that’s defined my life—the quest to wrap together computation, physics, math, and philosophy into some sort of coherent picture of the world—might never end.  But it does need to start somewhere.  I’m honored that you chose Quantum Computing Since Democritus as a place to start or continue your own quest.  I hope you enjoy it.

Scott Aaronson
Austin, Texas
June 2020

Follow

Today I woke up to the sad and shocking news that Jon Dowling (homepage / Twitter / Wikipedia)—physics professor at Louisiana State, guy who got the US government to invest in quantum computing back in the 90s, author of the popular book Schrödinger’s Killer App: Race to Build the World’s First Quantum Computer, investigator of BosonSampling among many other topics, owner of a “QUBIT” license plate, and one of my main competitors in the field of quantum computing humor—has passed away at age 65, apparently due to an aortic aneurysm.

Three months ago, right before covid shut down the world, the last travel I did was a seven-hour road trip from Austin to Baton Rouge, together with my postdoc Andrea Rocchetto, to deliver something called the Hearne Lecture at the Louisiana State physics department. My topic (unsurprisingly) was Google’s quantum supremacy experiment.

I’d debated whether to cancel the trip, as flying already seemed too dangerous. Dowling was the one who said “why not just drive here with one of your postdocs?”—which turned into a memorable experience for me and Andrea, complete with a personal tour of LIGO and a visit to an alligator hatchery. I had no inkling that it was the last time I’d ever see Jon Dowling, but am now super-glad that we made the visit.

At the dinner after my talk, Dowling was exactly the same as every other time I’d seen him: loud, piss-drunk, obnoxious, and hilarious. He dominated the conversation with stories and jokes, referring in every other sentence either to his Irishness or my Jewishness. His efforts to banter with the waitress, to elicit her deepest opinions about each appetizer and bottle of wine, were so over-the-top that I, sitting next to him, blushed, as if to say, “hey, I’m just the visitor here! I don’t necessarily endorse this routine!”

But Dowling got away with it because, no matter how many taboos he violated per sentence, there was never any hint of malice in it. He was an equal-opportunity offender, with his favorite target being himself. He loved to talk, for example, about my pathological obsession with airy-fairy abstractions, like some kind of “polynomial hierarchy” that hopefully wouldn’t “collapse”—with the punchline being that he, the hardheaded laser physicist, then needed to learn what that meant for his own research.

The quantum computing community of the southern US, not to mention of Twitter and Facebook, and indeed of the entire world, will be poorer without this inimitable, louder-than-life presence.

Feel free to share your own Dowling stories in the comments.

Follow

Today, I interrupt the news of the rapid disintegration of the United States of America, on every possible front at once (medical, economic, social…), to bring you something far more important: a long-planned two-hour podcast, where theoretical physicist and longtime friend-of-the-blog Sean Carroll interviews yours truly about complexity theory! Here’s Sean’s description of this historic event:

There are some problems for which it’s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem, and actually proving it will win you a million dollars. This kind of question falls under the rubric of “computational complexity theory,” which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world’s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.

So, OK, I guess I should also comment on the national disintegration thing. As someone who was once himself the victim of a crazy police overreaction (albeit, trivial compared to what African-Americans regularly deal with), I was moved by the scenes of police chiefs in several American towns taking off their helmets and joining protesters to cheers. Not only is that a deeply moral thing to do, but it serves a practical purpose of quickly defusing the protests. Right now, of course, is an even worse time than usual for chaos in the streets, with a lethal virus still spreading that doesn’t care whether people are congregating for good or for ill. If rational discussion of policy still matters, I support the current push to end the “qualified immunity” doctrine, end the provision of military training and equipment to police, and generally spur the nation’s police to rein in their psychopath minority.

Follow

Two years ago, I posted detailed lecture notes on this blog for my Intro to Quantum Information Science undergrad course at UT Austin. Today, with enormous thanks to UT PhD student Corey Ostrove, we’ve gotten the notes into a much better shape (for starters, they’re now in LaTeX). You can see the results here (7MB)—it’s basically a 260-page introductory quantum computing textbook in beta form, covering similar material as many other introductory quantum computing textbooks, but in my style for those who like that. It’s missing exercises, as well as material on quantum supremacy experiments, recent progress in hardware, etc., but that will be added in the next version if there’s enough interest. Enjoy!

Unrelated Announcement: Bjorn Poonen at MIT pointed me to researchseminars.org, a great resource for finding out about technical talks that are being held online in the era of covid. The developers recently added CS as a category, but so far there are very few CS talks listed. Please help fix that!

Follow

In the past week or two, four striking papers appeared on quant-ph. Rather than doing my usual thing—envisioning a huge, meaty blog post about each paper, but then procrastinating on writing them until the posts are no longer even relevant—I thought I’d just write a paragraph about each paper and then open things up for discussion.

(1) Matt Hastings has announced the first provable superpolynomial black-box speedup for the quantum adiabatic algorithm (in its original, stoquastic version). The speedup is only quasipolynomial (n^log(n)) rather than exponential, and it’s for a contrived example (just like in the important earlier work by Freedman and Hastings, which separated the adiabatic algorithm from Quantum Monte Carlo), and there are no obvious near-term practical implications. But still! Twenty years after Farhi and his collaborators wrote the first paper on the quantum adiabatic algorithm, and 13 years after D-Wave made its first hype-laden announcement, this is (to my mind) the first strong theoretical indication that adiabatic evolution with no sign problem can ever get a superpolynomial speedup over not only simulated annealing, not only Quantum Monte Carlo, but all possible classical algorithms. (This had previously been shown only for a variant of the adiabatic algorithm that jumps up to the first excited state, by Nagaj, Somma, and Kieferova.) As such, assuming the result holds up, Hastings resolves a central question that I (for one) had repeatedly asked about for almost 20 years. Indeed, if memory serves, at an Aspen quantum algorithms meeting a few years ago, I strongly urged Hastings to work on the problem. Congratulations to Matt!

(2) In my 2009 paper “Quantum Copy-Protection and Quantum Money,” I introduced the notion of copy-protected quantum software: a state |ψ_f⟩ that you could efficiently use to evaluate a function f, but not to produce more states (whether |ψ_f⟩ or anything else) that would let others evaluate f. I gave candidate constructions for quantumly copy-protecting the simple class of “point functions” (e.g., recognizing a password), and I sketched a proof that quantum copy-protection of arbitrary functions (except for those efficiently learnable from their input/output behavior) was possible relative to a quantum oracle. Building on an idea of Paul Christiano, a couple weeks ago my PhD student Jiahui Liu, Ruizhe Zhang, and I put a preprint on the arXiv improving that conclusion, to show that quantum copy-protection of arbitrary unlearnable functions is possible relative to a classical oracle. But my central open problem remained unanswered: is quantum copy-protection of arbitrary (unlearnable) functions possible in the real world, with no oracle? A couple days ago, Ananth and La Placa put up a preprint where they claim to show that the answer is no, assuming that there’s secure quantum Fully Homomorphic Encryption (FHE) of quantum circuits. I haven’t yet understood the construction, but it looks plausible, and indeed closely related to Barak et al.’s seminal proof of the impossibility of obfuscating arbitrary programs in the classical world. If this holds up, it (conditionally) resolves another of my favorite open problems—indeed, one that I recently mentioned in the Ask-Me-Anything session!

(3) Speaking of Boaz Barak: he, Chi-Ning Chou, and Xun Gao have a new preprint about a fast classical way to spoof Google’s linear cross-entropy benchmark for shallow random quantum circuits (with a bias that degrades exponentially with the depth, remaining detectable up to a depth of say ~√log(n)). As the authors point out, this by no means refutes Google’s supremacy experiment, which involved a larger depth. But along with other recent results in the same direction (e.g. this one), it does show that some exploitable structure is present even in random quantum circuits. Barak et al. achieve their result by simply looking at the marginal distributions on the individual output qubits (although the analysis to show that this works gets rather hairy). Boaz had told me all about this work when I saw him in person—back when traveling and meeting people in person was a thing!—but it’s great to see it up on the arXiv.

(4) Peter and Raphaël Clifford have announced a faster classical algorithm to simulate BosonSampling. To be clear, their algorithm is still exponential-time, but for the special case of a Haar-random scattering matrix, n photons, and m=n input and output modes, it runs in only ~1.69ⁿ time, as opposed to the previous bound of ~2ⁿ. The upshot is that, if you want to achieve quantum supremacy using BosonSampling, then either you need more photons than previously thought (maybe 90 photons? 100?), or else you need a lot of modes (in our original paper, Arkhipov and I recommended at least m~n² modes for several reasons, but naturally the experimentalists would like to cut any corners they can).

And what about my own “research program”? Well yesterday, having previously challenged my 7-year-old daughter Lily with instances of comparison sorting, Eulerian tours, undirected connectivity, bipartite perfect matching, stable marriage, factoring, graph isomorphism, unknottedness, 3-coloring, subset sum, and traveling salesman, I finally introduced her to the P vs. NP problem! Even though Lily can’t yet formally define “polynomial,” let alone “algorithm,” I’m satisfied that she understands something of what’s being asked. But, in an unintended echo of one of my more controversial recent posts, Lily insists on pronouncing NP as “nip.”

Follow

Update (May 10): Extremely sorry to everyone who wanted to attend my SlateStarCodex talk on quantum necromancy, but wasn’t able due to technical problems! My PowerPoint slides are here; a recording might be made available later. Thanks to everyone who attended and asked great questions. Even though there were many, many bugs to be worked out, I found giving my first talk in virtual reality a fascinating experience; thanks so much to Patrick V. for inviting me and setting it up.

(1) I’ll be giving an online talk at SlateStarCodex (actually, in a VR room where you can walk around with your avatar, mingle, and even try to get “front-row seating”), this coming Sunday at 10:30am US Pacific time = 12:30pm US Central time (i.e., me) = 1:30pm US Eastern time = … Here’s the abstract:

Schrödinger’s Cat and Quantum Necromancy

I’ll try, as best I can, to give a 10-minute overview of the century-old measurement problem of quantum mechanics.  I’ll then discuss a new result, by me and Yosi Atia, that might add a new wrinkle to the problem.  Very roughly, our result says that if you had the technological ability, as measured by (say) quantum circuit complexity, to prove that a cat was in a coherent superposition of the alive and dead states, then you’d necessarily also have the technological ability to bring a dead cat back to life.  Of course, this raises the question of in what sense such a cat was ever “dead” in the first place.

(2) Robin Kothari has a beautiful blog post about a new paper by me, him, Avishay Tal, and Shalev Ben-David, which uses Huang’s recent breakthrough proof of the Sensitivity Conjecture to show that D(f)=O(Q(f)⁴) for all total Boolean functions f, where D(f) is the deterministic query complexity of f and Q(f) is the quantum query complexity—thereby resolving another longstanding open problem (the best known relationship since 1998 had been D(f)=O(Q(f)⁶)). Check out his post!

(3) For all the people who’ve been emailing me, and leaving blog comments, about Stephen Wolfram’s new model of fundamental physics (his new new kind of science?)—Adam Becker now has an excellent article for Scientific American, entitled Physicists Criticize Stephen Wolfram’s “Theory of Everything.” The article quotes me, friend-of-the-blog Daniel Harlow, and several others. The only thing about Becker’s piece that I disagreed with was the amount of space he spent on process (e.g. Wolfram’s flouting of traditional peer review). Not only do I care less and less about such things, but I worry that harping on them feeds directly into Wolfram’s misunderstood-genius narrative. Why not use the space to explain how Wolfram makes a hash of quantum mechanics—e.g., never really articulating how he proposes to get unitarity, or the Born rule, or even a Hilbert space? Anyway, given the demand, I guess I’ll do a separate blog post about this when I have time. (Keep in mind that, with my kids home from school, I have approximately 2 working hours per day.)

(4) Oh yeah, I forgot! Joshua Zelinsky pointed me to a website by Martin Ugarte, which plausibly claims to construct a Turing machine with only 748 states whose behavior is independent of ZF set theory—beating the previous claimed record of 985 states due to Stefan O’Rear (see O’Rear’s GitHub page), which in turn beat the 8000 states of me and Adam Yedidia (see my 2016 blog post about this). I should caution that, to my knowledge, the new construction hasn’t been peer-reviewed, let alone proved correct in a machine-checkable way (well, the latter hasn’t yet been done for any of these constructions). For that matter, while an absolutely beautiful interface is provided, I couldn’t even find documentation for the new construction. Still, Turing machine and Busy Beaver aficionados will want to check it out!

Follow

1. This is really getting depressing. One of the only things that makes it bearable—even though in some sense it shouldn’t—is that most of humanity is in this together. For once, there’s no question of “why me?”
2. Having watched the eighth and final episode of Devs, the thought occurred to me: if I’d had the opportunity to restart the world from 8 months ago, even inside a simulation, I’d seize the chance and never look back.
3. I think I finally figured out how to explain the issue with Devs to my literary sophisticate readers. Namely: Devs consists, precisely, of the cultural appropriation of quantum computing. Now, I never felt like cultural appropriation was the world’s worst problem—not even before a pandemic started overflowing the morgues—so I wouldn’t say I was offended by Alex Garland appropriating the images and buzzwords of my quantum computing tribe for a basically unrelated purpose, but it is what it is. Again: Devs is the show for you, if you want a haunting, slow-paced, well-produced meditation about free will and determinism and predicting the future and parallel worlds and “what if the whole universe is a simulation?,” and the various ideas I would’ve had about such topics around the age of 11. It’s just not a show about quantum computing. I hope that makes it clear.
4. I read with interest this anonymous but PGP-signed article, laying out the case that it’s plausible that covid accidentally leaked from either the Wuhan Institute of Virology or the Wuhan CDC, rather than originating at the Huanan seafood market. Or, as an intermediate hypothesis, that an infected animal from one of those labs ended up at the seafood market. (Note that this is completely different from the hypothesis that covid was purposefully engineered—the authors of the article find that totally implausible, and I agree with them.) Notably, the Wuhan labs are known to have experimented with bat coronaviruses very much like covid, and are known to have performed “gain-of-function” experiments on them, and were probably the central labs in China for such experiments. And viruses are known to have leaked from other labs in China on other occasions, and the nature → seafood market route has unresolved issues, like where exactly the crossover from bats to pangolins (or some other intermediate species) is supposed to have happened, such that people would only start getting infected at the seafood market and not at its faraway suppliers, and … well, anyway, read the article and form your own judgment!
5. I find it interesting that three months ago, I would’ve hesitated even to share such a link, because my internal critic would’ve screamed “this looks too much like tinfoil-hat stuff—are you ready for all the people you respect sneering at you?” But the me of three months ago is not the me of today. I make no apologies for adapting my thoughts to the freak branch of the multiverse where I actually find myself.

Follow

This is my first post in more than a month that’s totally unrelated to the covid crisis. Or rather, it’s related only insofar as it’s about a Hulu miniseries, the sort of thing that many of us have more occasion to watch while holed up at home.

Three weeks ago, a journalist named Ben Lindbergh—who’d previously asked me to comment on the scientific accuracy of Avengers: Endgame—asked me the same question about the miniseries Devs, which I hadn’t previously heard of.

[Warning: Spoilers follow]

‘Devs,’ I learned, is a spooky sci-fi action thriller about a secretive Silicon Valley company that builds a quantum computer that can perfectly reconstruct the past, down to what Jesus looked like on the cross, and can also (at least up to a point) predict the future.

And I was supposed, not only to endure such a show, but to comment on the accuracy of its invocations of quantum computing? This didn’t sound promising.

But, y’know, I was at home quarantined. So I agreed to watch the first episode. Which quickly turned into the second, third, fourth, fifth, sixth, and seventh episodes (the eighth and final one isn’t out yet).

It turns out that ‘Devs’ isn’t too bad, except that it’s not particularly about quantum computers. The latter is simply a buzzword chosen by the writers for a plot concept that would’ve been entirely familiar to the ancient Greeks, who called it the Delphic Oracle. You know, the mysterious entity that prophesies your fate, so then you try to escape the prophecy, but your very evasive maneuvers make the prophecy come true? Picture that, except with qubits—and for some reason, in a gleaming golden laboratory that has components that float in midair.

At this point, I’ll just link you to Ben Lindbergh’s article about the show: Making Sense of the Science and Philosophy of ‘Devs.’ His long and excellent piece quotes me extensively enough that I see no need also to analyze the show in this blog post. (It also quotes several academic philosophers.)

Instead, I’ll just share a few tidbits that Ben left out, but that might be amusing to quantum computing fans.

• The first episode opens with a conversation between two characters about how even “elliptical curve” cryptography is insecure against attack by quantum computers. So I immediately knew both that the writers had one or more consultants who actually knew something about QC, and also that those consultants were not as heavily involved as they could’ve been.

• Similarly: in a later scene, some employees at the secretive company hold what appears to be a reading group about Shor’s algorithm. They talk about waves that interfere and cancel each other out, which is great, but beyond that their discussion sounded to me like nonsense. In particular, their idea seemed to be that the waves would reinforce at the prime factors p and q themselves, rather than at inverse multiples of the period of a periodic function that only indirectly encodes the factoring problem. (What do you say: should we let this one slide?)

• “How many qubits does this thing have?” “A number that there would be no point in describing as a number.” ROFL

• In the show, a crucial break comes when the employees abandon a prediction algorithm based on the deBroglie-Bohm pilot wave interpretation, and substitute one based on Everett’s many-worlds interpretation. Which I could actually almost believe, except that the many-worlds interpretation seems to contradict the entire premise of the rest of the show?

• A new employee, after he sees the code of the superpowerful quantum computer for the first time, is so disoriented and overwhelmed that he runs and vomits into a toilet. I, too, have had that reaction to the claims of certain quantum computing companies, although in some sense for the opposite reason.

Anyway, none of the above addresses the show’s central conceit: namely, that the Laplace demon can be made real, the past and future rendered fully knowable (with at most occasional breaks and exceptions) by a machine that’s feasible to build. This conceit is fascinating to explore, but also false.

In the past, if you’d asked me to justify its falsity, I would’ve talked about chaos, and quantum mechanics, and the unknowability of the fine details of the universe’s state; I might’ve even pointed you to my Ghost in the Quantum Turing Machine essay. I also would’ve mentioned the severe conceptual difficulties in forcing Nature to find a fixed-point of a universe where you get to see your own future and act on that information (these difficulties are just a variant of the famous Grandfather Paradox).

But it occurs to me that, just as the coronavirus has now made plain the nature of exponential growth, even to the world’s least abstract-minded person, so too it’s made plain the universe’s unpredictability. Let’s put it this way: do you find it plausible that the quantum computer from ‘Devs,’ had you booted it up six months ago, would’ve known the exact state of every nucleotide in every virus in every bat in Wuhan? No? Then it wouldn’t have known our future.

And I see now that I’ve violated my promise that this post would have nothing to do with covid.

Follow

Several people asked me to comment on the recent announcement by Honeywell that they’ll soon have what they call “the most powerful” quantum computer (see here for press release, here for Forbes article, here for paper).

I’m glad that Honeywell, which many people might know as an air-conditioner manufacturer, has entered the race for trapped-ion QC. I wish them success. I’ve known about what they were doing in part because Drew Potter, my friend and colleague in UT Austin’s physics department, took a one-year leave from UT to contribute to their effort.

Here I wanted to comment about one detail in Honeywell’s announcement: namely, the huge emphasis on “quantum volume” as the central metric for judging quantum computing progress, and the basis for calling their own planned device the “most powerful.” One journalist asked me to explain why quantum volume is such an important measure. I had to give her an honest answer: I don’t know whether it is.

Quantum volume was invented a few years ago by a group at IBM. According to one of their papers, it can be defined roughly as 2^k, where k is the largest number such that you can run a k-qubit random quantum circuit, with depth k and with any-to-any connectivity, and have at least (say) 2/3 probability of measuring an answer that passes some statistical test. (In the paper, they use what Lijie Chen and I named Heavy Output Generation, though Google’s Linear Cross-Entropy Benchmark is similar.)

I don’t know why IBM takes the “volume” to be 2^k rather than k itself. Leaving that aside, though, the idea was to invent a single “goodness measure” for quantum computers that can’t be gamed either by building a huge number of qubits that don’t maintain nearly enough coherence (what one might call “the D-Wave approach”), or by building just one perfect qubit, or by building qubits that behave well in isolation but don’t interact easily. Note that the any-to-any connectivity requirement makes things harder for architectures with nearest-neighbor interactions only, like the 2D superconducting chips being built by Google, Rigetti, or IBM itself.

You know the notion of a researcher’s h-index—defined as the largest h such that she’s published h papers that garnered h citations each? Quantum volume is basically an h-index for quantum computers. It’s an attempt to take several different yardsticks of experimental progress, none terribly useful in isolation, and combine them into one “consumer index.”

Certainly I sympathize with the goal of broadening people’s focus beyond the “but how many qubits does it have?” question—since the answer to that question is meaningless without further information about what the qubits can do. From that standpoint, quantum volume seems like a clear step in the right direction.

Alas, Goodhart’s Law states that “as soon as a measure becomes a target, it ceases to be a good measure.” That happened years ago with the h-index, which now regularly pollutes academic hiring and promotion decisions, to the point where its inventor expressed regrets. Quantum volume is now looking to me like another example of Goodhart’s Law at work.

The position of Honeywell’s PR seems to be that, if they can build a device that can apply 6 layers of gates to 6 qubits, with full connectivity and good fidelity, that will then count as “the world’s most powerful quantum computer,” since it will have the largest volume. One problem here is that such a device could be simulated by maintaining a vector of only 2⁶=64 amplitudes. This is nowhere near quantum supremacy (i.e., beating classical computers at some well-defined task), which is a necessary though not sufficient condition for doing anything useful.

Think of a university that achieves an average faculty-to-student ratio of infinity by holding one class with zero students. It gets the “best score” only by exploiting an obvious defect in the scoring system.

So what’s the alternative? The policy I prefer is simply to tell the world all your system specs, as clearly as you can, with no attempts made to bury the lede. How many qubits do you have? With what coherence times? With what connectivity? What are the 1- and 2-qubit gate fidelities? What depth of circuit can you do? What resources do the standard classical algorithms need to simulate your system? Most importantly: what’s the main drawback of your system, the spec that’s the worst, the one you most need to improve? What prevents you from having a scalable quantum computer right now? And are you going to tell me, or will you make me scour Appendix III.B in your paper, or worse yet, ask one of your competitors?

I confess that the answers to the above questions are hard to summarize in a single number (unless you, like, concatenated binary encodings of them or something). But they can be ineffably combined, to produce a progress metric that one of my postdocs suggested calling “quantum scottness,” and which roughly equals the number of expressions of wide-eyed surprise minus the number of groans.

Follow