Shtetl-Optimized

Update (April 5, 2021): So it turns out that Adam Chalcraft and Michael Greene already proved the essential result of this post back in 1994 (hat tip to commenter Dylan). Not terribly surprising in retrospect!

---

My son Daniel had his fourth birthday a couple weeks ago. For a present, he got an electric train set. (For completeness—and since the details of the train set will be rather important to the post—it’s called “WESPREX Create a Dinosaur Track”, but this is not an ad and I’m not getting a kickback for it.)

As you can see, the main feature of this set is a Y-shaped junction, which has a flap that can control which direction the train goes. The logic is as follows:

• If the train is coming up from the “bottom” of the Y, then it continues to either the left arm or the right arm, depending on where the flap is. It leaves the flap as it was.

• If the train is coming down the left or right arms of the Y, then it continues to the bottom of the Y, pushing the flap out of its way if it’s in the way. (Thus, if the train were ever to return to this Y-junction coming up from the bottom, not having passed the junction in the interim, it would necessarily go to the same arm, left or right, that it came down from.)

The train set also comes with bridges and tunnels; thus, there’s no restriction of planarity. Finally, the train set comes with little gadgets that can reverse the train’s direction, sending it back in the direction that it came from:

These gadgets don’t seem particularly important, though, since we could always replace them if we wanted by a Y-junction together with a loop.

Notice that, at each Y-junction, the position of the flap stores one bit of internal state, and that the train can both “read” and “write” these bits as it moves around. Thus, a question naturally arises: can this train set do any nontrivial computations? If there are n Y-junctions, then can it cycle through exp(n) different states? Could it even solve PSPACE-complete problems, if we let it run for exponential time? (For a very different example of a model-train-like system that, as it turns out, is able to express PSPACE-complete problems, see this recent paper by Erik Demaine et al.)

Whatever the answers regarding Daniel’s train set, I knew immediately on watching the thing go that I’d have to write a “paperlet” on the problem and publish it on my blog (no, I don’t inflict such things on journals!). Today’s post constitutes my third “paperlet,” on the general theme of a discrete dynamical system that someone showed me in real life (e.g. in a children’s toy or in biology) having more structure and regularity than one might naïvely expect. My first such paperlet, from 2014, was on a 1960s toy called the Digi-Comp II; my second, from 2016, was on DNA strings acted on by recombinase (OK, that one was associated with a paper in Science, but my combinatorial analysis wasn’t the main point of the paper).

Anyway, after spending an enjoyable evening on the problem of Daniel’s train set, I was able to prove that, alas, the possible behaviors are quite limited (I classified them all), falling far short of computational universality.

If you feel like I’m wasting your time with trivialities (or if you simply enjoy puzzles), then before you read any further, I encourage you to stop and try to prove this for yourself!

Back yet? OK then…

---

Theorem: Assume a finite amount of train track. Then after a linear amount of time, the train will necessarily enter a “boring infinite loop”—i.e., an attractor state in which at most two of the flaps keep getting toggled, and the rest of the flaps are fixed in place. In more detail, the attractor must take one of four forms:

I. a line (with reversing gadgets on both ends),
II. a simple cycle,
III. a “lollipop” (with one reversing gadget and one flap that keeps getting toggled), or
IV. a “dumbbell” (with two flaps that keep getting toggled).

In more detail still, there are seven possible topologically distinct trajectories for the train, as shown in the figure below.

Here the red paths represent the attractors, where the train loops around and around for an unlimited amount of time, while the blue paths represent “runways” where the train spends a limited amount of time on its way into the attractor. Every degree-3 vertex is assumed to have a Y-junction, while every degree-1 vertex is assumed to have a reversing gadget, unless (in IIb) the train starts at that vertex and never returns to it.

The proof of the theorem rests on two simple observations.

Observation 1: While the Y-junctions correspond to vertices of degree 3, there are no vertices of degree 4 or higher. This means that, if the train ever revisits a vertex v (other than the start vertex) for a second time, then there must be some edge e incident to v that it also traverses for a second time immediately afterward.

Observation 2: Suppose the train traverses some edge e, then goes around a simple cycle (meaning, one where no edges or vertices are reused), and then traverses e again, going in the same direction as the first time. Then from that point forward, the train will just continue around the same simple cycle forever.

The proof of Observation 2 is simply that, if there were any flap that might be in the train’s way as it continued around the simple cycle, then the train would already have pushed it out of the way its first time around the cycle, and nothing that happened thereafter could possibly change the flap’s position.

Using the two observations above, let’s now prove the theorem. Let the train start where it will, and follow it as it traces out a path. Since the graph is finite, at some point some already-traversed edge must be traversed a second time. Let e be the first such edge. By Observation 1, this will also be the first time the train’s path intersects itself at all. There are then three cases:

Case 1: The train traverses e in the same direction as it did the first time. By Observation 2, the train is now stuck in a simple cycle forever after. So the only question is what the train could’ve done before entering the simple cycle. We claim that at most, it could’ve traversed a simple path. For otherwise, we’d contradict the assumption that e was the first edge that the train visited twice on its journey. So the trajectory must have type IIa, IIb, or IIc in the figure.

Case 2: Immediately after traversing e, the train hits a reversing gadget and traverses e again the other way. In this case, the train will clearly retrace its entire path and then continue past its starting point; the question is what happens next. If it hits another reversing gadget, then the trajectory will have type I in the figure. If it enters a simple cycle and stays in it, then the trajectory will have type IIb in the figure. If, finally, it makes a simple cycle and then exits the cycle, then the trajectory will have type III in the figure. In this last case, the train’s trajectory will form a “lollipop” shape. Note that there must be a Y-junction where the “stick” of the lollipop meets the “candy” (i.e., the simple cycle), with the base of the Y aligned with the stick (since otherwise the train would’ve continued around and around the candy). From this, we deduce that every time the train goes around the candy, it does so in a different orientation (clockwise or counterclockwise) than the time before; and that the train toggles the Y-junction’s flap every time it exits the candy (although not when it enters the candy).

Case 3: At some point after traversing e in the forward direction (but not immediately after), the train traverses e in the reverse direction. In this case, the broad picture is analogous to Case 2. So far, the train has made a lollipop with a Y-junction connecting the stick to the candy (i.e. cycle), the base of the Y aligned with the stick, and e at the very top of the stick. The question is what happens next. If the train next hits a reversing gadget, the trajectory will have type III in the figure. If it enters a new simple cycle, disjoint from the first cycle, and never leaves it, the trajectory will have type IId in the figure. If it enters a new simple cycle, disjoint from the first cycle, and does leave it, then the trajectory now has a “dumbbell” pattern, type IV in the figure (also shown in the first video). There’s only one other situation to worry about: namely, that the train makes a new cycle that intersects the first cycle, forming a “theta” (θ) shaped trajectory. In this case, there must be a Y-junction at the point where the new cycle bumps into the old cycle. Now, if the base of the Y isn’t part of the old cycle, then the train never could’ve made it all the way around the old cycle in the first place (it would’ve exited the old cycle at this Y-junction), contradiction. If the base of the Y is part of the old cycle, then the flap must have been initially set to let the train make it all the way around the old cycle; when the train then reenters the old cycle, the flap must be moved so that the train will never make it all the way around the old cycle again. So now the train is stuck in a new simple cycle (sharing some edges with the old cycle), and the trajectory has type IIc in the figure.

This completes the proof of the theorem.

---

We might wonder: why isn’t this model train set capable of universal computation, of AND, OR, and NOT gates—or at any rate, of some computation more interesting than repeatedly toggling one or two flaps? My answer might sound tautological: it’s simply that the logic of the Y-junctions is too limited. Yes, the flaps can get pushed out of the way—that’s a “bit flip”—but every time such a flip happens, it helps to set up a “groove” in which the train just wants to continue around and around forever, not flipping any additional bits, with only the minor complications of the lollipop and dumbbell structures to deal with. Even though my proof of the theorem might’ve seemed like a tedious case analysis, it had this as its unifying message.

It’s interesting to think about what gadgets would need to be added to the train set to make it computationally universal, or at least expressively richer—able, as turned out to be the case for the Digi-Comp II, to express some nontrivial complexity class falling short of P. So for example, what if we had degree-4 vertices, with little turnstile gadgets? Or multiple trains, which could be synchronized to the millisecond to control how they interacted with each other via the flaps, or which could even crash into each other? I look forward to reading your ideas in the comment section!

For the truth is this: quantum complexity classes, BosonSampling, closed timelike curves, circuit complexity in black holes and AdS/CFT, etc. etc.—all these topics are great, but the same models and problems do get stale after a while. I aspire for my research agenda to chug forward, full steam ahead, into new computational domains.

PS. Happy Easter to those who celebrate!

For years, I’d sometimes hear discussions about the ethics of quantum computing research. Quantum ethics!

When the debates weren’t purely semantic, over the propriety of terms like “quantum supremacy” or “ancilla qubit,” they were always about chin-strokers like “but what if cracking RSA encryption gives governments more power to surveil their citizens? or what if only a few big countries or companies get quantum computers, thereby widening the divide between haves and have-nots?” Which, OK, conceivably these will someday be issues. But, besides barely depending on any specific facts about quantum computing, these debates always struck me as oddly safe, because the moral dilemmas were so hypothetical and far removed from us in time.

I confess I may have even occasionally poked fun when asked to expound on quantum ethics. I may have commented that quantum computers probably won’t kill anyone unless a dilution refrigerator tips over onto their head. I may have asked forgiveness for feeding custom-designed oracles to BQP and QMA, without first consulting an ethics committee about the long-term effects on those complexity classes.

Now fate has punished me for my flippancy. These days, I really do feel like quantum computing research has become an ethical minefield—but not for any of the reasons mentioned previously. What’s new is that millions of dollars are now potentially available to quantum computing researchers, along with equity, stock options, and whatever else causes “ka-ching” sound effects and bulging eyes with dollar signs. And in many cases, to have a shot at such riches, all an expert needs to do is profess optimism that quantum computing will have revolutionary, world-changing applications and have them soon. Or at least, not object too strongly when others say that.

Some of today’s rhetoric will of course remind people of the D-Wave saga, which first brought this blog to prominence when it began in earnest in 2007. Quantum computers, we hear now as then, will soon leave the Earth’s fastest supercomputers in the dust. They’re going to harness superposition to try all the exponentially many possible solutions at once. They’ll crack the Traveling Salesman Problem, and will transform machine learning and AI beyond recognition. Meanwhile, simulations of quantum systems will be key to solving global warming and cancer.

Despite the parallels, though, this new gold rush doesn’t feel to me like the D-Wave one, which seems in retrospect like just a little dry run. If I had to articulate what’s new in one sentence, it’s that this time “the call is coming from inside the house.” Many of the companies making wildly overhyped claims are recognized leaders of the field. They have brilliant quantum computing theorists and experimentalists on their staff with impeccable research records. Some of those researchers are among my best friends. And even when I wince at the claims of near-term applications, in many cases (especially with quantum simulation) the claims aren’t obviously false—we won’t know for certain until we try it and see! It’s genuinely gotten harder to draw the line between defensible optimism and exaggerations verging on fraud.

Indeed, this time around virtually everyone in QC is “complicit” to a greater or lesser degree. I, too, have accepted compensation to consult on quantum computing topics, to give talks at hedge funds, and in a few cases to serve as a scientific adviser to quantum computing startups. I tell myself that, by 2021 standards, this stuff is all trivial chump change—a few thousands of dollars here or there, to expound on the same themes that I already discuss free of charge on this blog. I actually get paid to dispel hype, rather than propagate it! I tell myself that I’ve turned my back on the orders of magnitude more money available to those willing to hitch their scientific reputations to the aspirations of this or that specific QC company. (Yes, this blog, and my desire to preserve its intellectual independence and credibility, might well be costing me millions!)

But, OK, some would argue that accepting any money from QC companies or QC investors just puts you at the top of a slope with unabashed snake-oil salesmen at the bottom. With the commercialization of our field that started around 2015, there’s no bright line anymore marking the boundary between pure scientific curiosity and the pursuit of filthy lucre; it’s all just points along a continuum. I’m not sure that these people are wrong.

As some of you might’ve seen already, IonQ, the trapped-ion QC startup that originated from the University of Maryland, is poised to have the first-ever quantum computing IPO—a so-called “SPAC IPO,” which while I’m a financial ignoramus, apparently involves merging with a shell company and thereby bypassing the SEC’s normal IPO rules. Supposedly they’re seeking $650 million in new funding and a $2 billion market cap. If you want to see what IonQ is saying about QC to prospective investors, click here. Lacking any choice in the matter, I’ll probably say more about these developments in a future post.

Meanwhile, PsiQuantum, the Palo-Alto-based optical QC startup, has said that it’s soon going to leave “stealth mode.” And Amazon, Microsoft, Google, IBM, Honeywell, and other big players continue making large investments in QC—treating it, at least rhetorically, not at all like blue-sky basic research, but like a central part of their future business plans.

All of these companies have produced or funded excellent QC research. And of course, they’re all heterogeneous, composed of individuals who might vehemently disagree with each other about the near- or long-term prospects of QC. And yet all of them have, at various times, inspired reflections in me like the ones in this post.

I regret that this post has no clear conclusion. I’m still hashing things out, solicing thoughts from my readers and friends. Speaking of which: this coming Monday, March 22, at 8-10pm US Eastern time, I’ve decided to hold a discussion around these issues on Clubhouse—my “grand debut” on that app, and an opportunity to see whether I like it or not! My friend Adam Brown will moderate the discussion; other likely participants will be John Horgan, George Musser, Michael Nielsen, and Matjaž Leonardis. If you’re on Clubhouse, I hope to see you there!

Update (March 22): Read this comment by “FB” if you’d like to understand how we got to this point.

Many of you will have seen the happy news today that Avi Wigderson and László Lovász share this year’s Abel Prize (which now contends with the Fields Medal for the highest award in pure math). This is only the second time that the Abel Prize has been given wholly or partly for work in theoretical computer science, after Szemerédi in 2012. See also the articles in Quanta or the NYT, which actually say most of what I would’ve said for a lay audience about Wigderson’s and Lovász’s most famous research results and their importance (except, no, Avi hasn’t yet proved P=BPP, just taken some major steps toward it…).

On a personal note, Avi was both my and my wife Dana’s postdoctoral advisor at the Institute for Advanced Study in Princeton. He’s been an unbelievably important mentor to both of us, as he’s been for dozens of others in the CS theory community. Back in 2007, I also had the privilege of working closely with Avi for months on our Algebrization paper. Now would be a fine time to revisit Avi’s Permanent Impact on Me (or watch the YouTube video), which is the talk I gave at IAS in 2016 on the occasion of Avi’s 60th birthday.

Huge congratulations to both Avi and László!

Back at MIT, whenever I taught my graduate course on Quantum Complexity Theory (see here for lecture notes), I had a tradition of showcasing the student projects on this blog: see here (Fall 2010), here (Fall 2012), here (Fall 2014). I was incredibly proud that, each time I taught, at least some of the projects led to publishable original research—sometimes highly significant research, like Paul Christiano’s work on quantum money (which led to my later paper with him), Shelby Kimmel’s work on quantum query complexity, Jenny Barry’s work on quantum partially observable Markov decision processes (“QOMDPs”), or Matt Coudron and Henry Yuen’s work on randomness expansion (which led to their later breakthrough in the subject).

Alas, after I moved to UT Austin, for some reason I discontinued the tradition of these blog-showcases—and inexcusably, I did this even though the wonderful new research results continued! Now that I’m teaching Quantum Complexity Theory at UT for the third time (via Zoom, of course), I decided that it was finally time to remedy this. To keep things manageable, this time I’m going to limit myself to research projects that began their lives in my course and that are already public on the arXiv (or in one case, that will soon be).

So please enjoy the following smorgasbord, from 2016 and 2019 iterations of my course! And if you have any questions about any of the projects—well, I’ll try to get the students to answer in the comments section! Thanks so much and congratulations to the students for their work.

From the Fall 2016 iteration of the course

William Hoza (project turned into a joint paper with Cole Graham), Universal Bell Correlations Do Not Exist.

We prove that there is no finite-alphabet nonlocal box that generates exactly those correlations that can be generated using a maximally entangled pair of qubits. More generally, we prove that if some finite-alphabet nonlocal box is strong enough to simulate arbitrary local projective measurements of a maximally entangled pair of qubits, then that nonlocal box cannot itself be simulated using any finite amount of entanglement. We also give a quantitative version of this theorem for approximate simulations, along with a corresponding upper bound.

Patrick Rall, Signed quantum weight enumerators characterize qubit magic state distillation.

Many proposals for fault-tolerant quantum computation require injection of ‘magic states’ to achieve a universal set of operations. Some qubit states are above a threshold fidelity, allowing them to be converted into magic states via ‘magic state distillation’, a process based on stabilizer codes from quantum error correction.
We define quantum weight enumerators that take into account the sign of the stabilizer operators. These enumerators completely describe the magic state distillation behavior when distilling T-type magic states. While it is straightforward to calculate them directly by counting exponentially many operator weights, it is also an NP-hard problem to compute them in general. This suggests that finding a family of distillation schemes with desired threshold properties is at least as hard as finding the weight distributions of a family of classical codes.
Additionally, we develop search algorithms fast enough to analyze all useful 5 qubit codes and some 7 qubit codes, finding no codes that surpass the best known threshold.

From the Spring 2019 iteration of the course

Ying-Hao Chen, 2-Local Hamiltonian with Low Complexity is QCMA-complete.

We prove that 2-Local Hamiltonian (2-LH) with Low Complexity problem is QCMA-complete by combining the results from the QMA-completeness of 2-LH and QCMA-completeness of 3-LH with Low Complexity. The idea is straightforward. It has been known that 2-LH is QMA-complete. By putting a low complexity constraint on the input state, we make the problem QCMA. Finally, we use similar arguments as in [Kempe, Kitaev, Regev] to show that all QCMA problems can be reduced to our proposed problem.

Jeremy Cook, On the relationships between Z-, C-, and H-local unitaries.

Quantum walk algorithms can speed up search of physical regions of space in both the discrete-time [arXiv:quant-ph/0402107] and continuous-time setting [arXiv:quant-ph/0306054], where the physical region of space being searched is modeled as a connected graph. In such a model, Aaronson and Ambainis [arXiv:quant-ph/0303041] provide three different criteria for a unitary matrix to act locally with respect to a graph, called Z-local, C-local, and H-local unitaries, and left the open question of relating these three locality criteria. Using a correspondence between continuous- and discrete-time quantum walks by Childs [arXiv:0810.0312], we provide a way to approximate N×N H-local unitaries with error δ using O(1/√δ,√N) C-local unitaries, where the comma denotes the maximum of the two terms.

Joshua A. Cook, Approximating Unitary Preparations of Orthogonal Black Box States.

In this paper, I take a step toward answering the following question: for m different small circuits that compute m orthogonal n qubit states, is there a small circuit that will map m computational basis states to these m states without any input leaving any auxiliary bits changed. While this may seem simple, the constraint that auxiliary bits always be returned to 0 on any input (even ones besides the m we care about) led me to use sophisticated techniques. I give an approximation of such a unitary in the m = 2 case that has size polynomial in the approximation error, and the number of qubits n.

Sabee Grewal (project turned into a joint paper with me), Efficient Learning of Non-Interacting Fermion Distributions.

We give an efficient classical algorithm that recovers the distribution of a non-interacting fermion state over the computational basis. For a system of n non-interacting fermions and m modes, we show that O(m²n⁴log(m/δ)/ε⁴) samples and O(m⁴n⁴log(m/δ)/ε⁴) time are sufficient to learn the original distribution to total variation distance ε with probability 1−δ. Our algorithm empirically estimates the one- and two-mode correlations and uses them to reconstruct a succinct description of the entire distribution efficiently.

Sam Gunn and Niels Kornerup, Review of a Quantum Algorithm for Betti Numbers.

We looked into the algorithm for calculating Betti numbers presented by Lloyd, Garnerone, and Zanardi (LGZ). We present a new algorithm in the same spirit as LGZ with the intent of clarifying quantum algorithms for computing Betti numbers. Our algorithm is simpler and slightly more efficient than that presented by LGZ. We present a thorough analysis of our algorithm, pointing out reasons that both our algorithm and that presented by LGZ do not run in polynomial time for most inputs. However, the algorithms do run in polynomial time for calculating an approximation of the Betti number to polynomial multiplicative error, when applied to some class of graphs for which the Betti number is exponentially large.

William Kretschmer, Lower Bounding the AND-OR Tree via Symmetrization.

We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ~deg(ANDm∘ORn)=Ω(~√(mn)). To our knowledge, this is the first proof of this fact that relies on symmetrization exclusively; most other proofs involve the more complicated formulation of approximate degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].

Jiahui Liu and Ruizhe Zhang (project turned into a joint paper with me, Mark Zhandry, and Qipeng Liu),
New Approaches for Quantum Copy-Protection.

Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results:
– We show how to copy protect any program that cannot be learned from its input/output behavior, relative to a classical oracle. This improves on Aaronson [CCC’09], which achieves the same relative to a quantum oracle. By instantiating the oracle with post-quantum candidate obfuscation schemes, we obtain a heuristic construction of copy protection.
– We show, roughly, that any program which can be watermarked can be copy detected, a weaker version of copy protection that does not prevent copying, but guarantees that any copying can be detected. Our scheme relies on the security of the assumed watermarking, plus the assumed existence of public key quantum money. Our construction is general, applicable to many recent watermarking schemes.

John Kallaugher, Triangle Counting in the Quantum Streaming Model. Not yet available but coming soon to an arXiv near you!

We give a quantum algorithm for counting triangles in graph streams that uses less space than the best possible classical algorithm.

Many of you have surely already seen the news that the Kouwenhoven group in Delft—which in 2018 published a paper in Nature claiming to have detected Majorana particles, a type of nonabelian anyon—have retracted the paper and apologized for “insufficient scientific rigour.” This work was considered one of the linchpins of Microsoft’s experimental effort toward building topological quantum computers.

Like most quantum computing theorists, I guess, I’m thrilled if Majorana particles can be created using existing technology, I’m sad if they can’t be, but I don’t have any special investment in or knowledge of the topic, beyond what I read in the news or hear from colleagues. Certainly Majorana particles seem neither necessary nor sufficient for building a scalable quantum computer, although they’d be a step forward for the topological approach to QC.

The purpose of this post is to invite informed scientific discussion of the relevant issues—first and foremost so that I can learn something, and second so that my readers can! I’d be especially interested to understand:

1. Weren’t there, like, several other claims to have produced Majoranas? What of those then?
2. If, today, no one has convincingly demonstrated the existence of Majoranas, then do people think it more likely that they were produced but not detected, or that they weren’t even produced?
3. How credible are the explanations as to what went wrong?
4. Are there any broader implications for the prospects of topological QC, or Microsoft’s path to topological QC, or was this just an isolated mistake?

So there’s an interesting new paper on the arXiv by Feng Pan and Pan Zhang, entitled “Simulating the Sycamore supremacy circuits.” It’s about a new tensor contraction strategy for classically simulating Google’s 53-qubit quantum supremacy experiment from Fall 2019. Using their approach, and using just 60 GPUs running for a few days, the authors say they managed to generate a million correlated 53-bit strings—meaning, strings that all agree on a specific subset of 20 or so bits—that achieve a high linear cross-entropy score.

Alas, I haven’t had time this weekend to write a “proper” blog post about this, but several people have by now emailed to ask my opinion, so I thought I’d share the brief response I sent to a journalist.

This does look like a significant advance on simulating Sycamore-like random quantum circuits! Since it’s based on tensor networks, you don’t need the literally largest supercomputer on the planet filling up tens of petabytes of hard disk space with amplitudes, as in the brute-force strategy proposed by IBM. Pan and Zhang’s strategy seems most similar to the strategy previously proposed by Alibaba, with the key difference being that the new approach generates millions of correlated samples rather than just one.

I guess my main thoughts for now are:

1. Once you knew about this particular attack, you could evade it and get back to where we were before by switching to a more sophisticated verification test — namely, one where you not only computed a Linear XEB score for the observed samples, you also made sure that the samples didn’t share too many bits in common.  (Strangely, though, the paper never mentions this point.)
2. The other response, of course, would just be to redo random circuit sampling with a slightly bigger quantum computer, like the ~70-qubit devices that Google, IBM, and others are now building!

Anyway, very happy for thoughts from anyone who knows more.

As I lay bedridden this week, knocked out by my second dose of the Moderna vaccine, I decided I should blog some more half-baked ideas because what the hell? It feels therapeutic, I have tenure, and anyone who doesn’t like it can close their broswer tab.

So: although I’ve written tens of thousands of words, on this blog and elsewhere, about interpretations of quantum mechanics, again and again I’ve dodged the question of which interpretation (if any) I really believe myself. Today, at last, I’ll emerge from the shadows and tell you precisely where I stand.

I hold that all interpretations of QM are just crutches that are better or worse at helping you along to the Zen realization that QM is what it is and doesn’t need an interpretation.  As Sidney Coleman famously argued, what needs reinterpretation is not QM itself, but all our pre-quantum philosophical baggage—the baggage that leads us to demand, for example, that a wavefunction |ψ⟩ either be “real” like a stubbed toe or else “unreal” like a dream. Crucially, because this philosophical baggage differs somewhat from person to person, the “best” interpretation—meaning, the one that leads most quickly to the desired Zen state—can also differ from person to person. Meanwhile, though, thousands of physicists (and chemists, mathematicians, quantum computer scientists, etc.) have approached the Zen state merely by spending decades working with QM, never worrying much about interpretations at all. This is probably the truest path; it’s just that most people lack the inclination, ability, or time.

Greg Kuperberg, one of the smartest people I know, once told me that the problem with the Many-Worlds Interpretation is not that it says anything wrong, but only that it’s “melodramatic” and “overwritten.” Greg is far along the Zen path, probably further than me.

You shouldn’t confuse the Zen Anti-Interpretation with “Shut Up And Calculate.” The latter phrase, mistakenly attributed to Feynman but really due to David Mermin, is something one might say at the beginning of the path, when one is as a baby. I’m talking here only about the endpoint of the path, which one can approach but never reach—the endpoint where you intuitively understand exactly what a Many-Worlder, Copenhagenist, or Bohmian would say about any given issue, and also how they’d respond to each other, and how they’d respond to the responses, etc. but after years of study and effort you’ve returned to the situation of the baby, who just sees the thing for what it is.

I don’t mean to say that the interpretations are all interchangeable, or equally good or bad. If you had to, you could call even me a “Many-Worlder,” but only in the following limited sense: that in fifteen years of teaching quantum information, my experience has consistently been that for most students, Everett’s crutch is the best one currently on the market. At any rate, it’s the one that’s the most like a straightforward picture of the equations, and the least like a wobbly tower of words that might collapse if you utter any wrong ones.  Unlike Bohr, Everett will never make you feel stupid for asking the questions an inquisitive child would ask; he’ll simply give you answers that are as clear, logical, and internally consistent as they are metaphysically extravagant. That’s a start.

The Copenhagen Interpretation retains a place of honor as the first crutch, for decades the only crutch, and the one closest to the spirit of positivism. Unfortunately, wielding the Copenhagen crutch requires mad philosophical skillz—which parts of the universe should you temporarily regard as “classical”? which questions should be answered, and which deflected?—to the point where, if you’re capable of all that verbal footwork, then why do you even need a crutch in the first place? In the hands of amateurs—meaning, alas, nearly everyone—Copenhagen often leads away from rather than toward the Zen state, as one sees with the generations of New-Age bastardizations about “observations creating reality.”

As for deBroglie-Bohm—well, that’s a weird, interesting, baroque crutch, one whose actual details (the preferred basis and the guiding equation) are historically contingent and tied to specific physical systems. It’s probably the right crutch for someone—it gets eternal credit for having led Bell to discover the Bell inequality—but its quirks definitely need to be discarded along the way.

Note that, among those who approach the Zen state, many might still call themselves Many-Worlders or Copenhagenists or Bohmians or whatever—just as those far along in spiritual enlightenment might still call themselves Buddhists or Catholics or Muslims or Jews (or atheists or agnostics)—even though, by that point, they might have more in common with each other than they do with their supposed coreligionists or co-irreligionists.

Alright, but isn’t all this Zen stuff just a way to dodge the actual, substantive questions about QM, by cheaply claiming to have transcended them? If that’s your charge, then please help yourself to the following FAQ about the details of the Zen Anti-Interpretation.

1. What is a quantum state? It’s a unit vector of complex numbers (or if we’re talking about mixed states, then a trace-1, Hermitian, positive semidefinite matrix), which encodes everything there is to know about a physical system.
   
2. OK, but are the quantum states “ontic” (really out in the world), or “epistemic” (only in our heads)? Dude. Do “basketball games” really exist, or is that just a phrase we use to summarize our knowledge about certain large agglomerations of interacting quarks and leptons? Do even the “quarks” and “leptons” exist, or are those just words for excitations of the more fundamental fields? Does “jealousy” exist? Pretty much all our concepts are complicated grab bags of “ontic” and “epistemic,” so it shouldn’t surprise us if quantum states are too. Bad dichotomy.
   
3. Why are there probabilities in QM? Because QM is a (the?) generalization of probability theory to involve complex numbers, whose squared absolute values are probabilities. It includes probability as a special case.
   
4. But why do the probabilities obey the Born rule? Because, once the unitary part of QM has picked out the 2-norm as being special, for the probabilities also to be governed by the 2-norm is pretty much the only possibility that makes mathematical sense; there are many nice theorems formalizing that intuition under reasonable assumptions.
   
5. What is an “observer”? It’s exactly what modern decoherence theory says it is: a particular kind of quantum system that interacts with other quantum systems, becomes entangled with them, and thereby records information about them—reversibly in principle but irreversibly in practice.
   
6. Can observers be manipulated in coherent superposition, as in the Wigner’s Friend scenario? If so, they’d be radically unlike any physical system we’ve ever had direct experience with. So, are you asking whether such “observers” would be conscious, or if so what they’d be conscious of? Who the hell knows?
   
7. Do “other” branches of the wavefunction—ones, for example, where my life took a different course—exist in the same sense this one does? If you start with a quantum state for the early universe and then time-evolve it forward, then yes, you’ll get not only “our” branch but also a proliferation of other branches, in the overwhelming majority of which Donald Trump was never president and civilization didn’t grind to a halt because of a bat near Wuhan.  But how could we possibly know whether anything “breathes fire” into the other branches and makes them real, when we have no idea what breathes fire into this branch and makes it real? This is not a dodge—it’s just that a simple “yes” or “no” would fail to do justice to the enormity of such a question, which is above the pay grade of physics as it currently exists. 
   
8. Is this it? Have you brought me to the end of the path of understanding QM? No, I’ve just pointed the way toward the beginning of the path. The most fundamental tenet of the Zen Anti-Interpretation is that there’s no shortcut to actually working through the Bell inequality, quantum teleportation, Shor’s algorithm, the Kochen-Specker and PBR theorems, possibly even a … photon or a hydrogen atom, so you can see quantum probability in action and be enlightened. I’m further along the path than I was twenty years ago, but not as far along as some of my colleagues. Even the greatest quantum Zen masters will be able to get further when new quantum phenomena and protocols are discovered in the future. All the same, though—and this is another major teaching of the Zen Anti-Interpretation—there’s more to life than achieving greater and greater clarity about the foundations of QM. And on that note…

To those who asked me about Claus Peter Schnorr’s claim to have discovered a fast classical factoring algorithm, thereby “destroying” (in his words) the RSA cryptosystem, see (e.g.) this Twitter thread by Keegan Ryan, which explains what certainly looks like a fatal error in Schnorr’s paper.

A month ago, UT Austin changed its email policies—banning auto-forwarding from university accounts to Gmail accounts, apparently as a way to force the faculty and other employees to separate their work email from their personal email, and thereby comply with various government regulations. Ever since that change, the email part of my life has been a total, unmitigated disaster. I’ve missed (or been late to see) dozens of important work emails, with the only silver lining being that that’s arguably UT’s problem more than it is mine!

And yes, I’ve already gone to technical support; the only answer I’ve gotten is that (in so many words) there is no answer. Other UT faculty are somehow able to deal with this because they are them; I am unable to deal with it because I am me. As a mere PhD in computer science, I’m utterly unqualified to set up a technical fix for this sort of problem.

So the bottom line is: from now on, if you want me to see an email, send it to scott@scottaaronson.com. Really. If you try sending it to aaronson@cs.utexas.edu, it will land in a separate inbox that I can access only with great inconvenience. And if, God forbid, you try sending it to aaronson@utexas.edu, the email will bounce and I’ll never see it at all. Indeed, a central purpose of this post is just to have a place to point the people who contact me every day, shocked that their emails to me bounced.

This whole episode has given me immense sympathy for Hillary Clinton, and for the factors that led her to set up clintonemail.com from her house. It’s not merely that her private email server was a laughably trivial reason to end the United States’ 240-year run of democratic government. Rather it’s that, even on the narrow question of emails, I now feel certain that Hillary was 100% right. Bureaucracy that impedes communication is a cancer on human civilization.

Update: Thanks so much to commenter Avraham and to my colleague Etienne Vouga, who quickly gave me the crucial information that tech support would not, and thereby let me solve this problem. I can once again easily read emails sent to aaronson@cs.utexas.edu … well, at least for now! I’m now checking about aaronson@utexas.edu. Again, though, scott@scottaaronson.com to be safe.

This past week, I spent so much mental energy worrying about the fate of Scott Alexander that I almost forgot that right here in Texas, I’m surrounded by historic scenes of Third-World-style devastation: snowstorms and sub-freezing temperatures for which our infrastructure was completely unprepared; impassable roads; burst gas and water pipes; millions without electricity or heat or clean water; the UT campus a short walk from me converted into a giant refugee camp.

For all those who asked: my family and I are fine. While many we know were without power for days (or are still without power), we lucked out by living close to a hospital, which means that they can’t shut off the electricity to our block. We are now on a boil-water notice, like all of Austin, and we can’t take deliveries or easily go anywhere, and the university and schools and daycares are all closed (even for remote learning). Which means: we’re simply holed up in our house, eating through our stockpiled food, the kids running around being crazy, Dana and I watching them with one eye and our laptops with the other. Could be worse.

In some sense, it’s not surprising that the Texas infrastructure would buckle under weather stresses outside the envelope of anything it was designed for or saw for decades. The central problem is that our elected leaders have shown zero indication of understanding the urgent need, for Texas’ economic viability, to do whatever it takes to make sure nothing like this ever happens again. Ted Cruz, as everyone now knows, left for Cancun; the mayor of Colorado City angrily told everyone to fend for themselves (and then resigned); and Governor Abbott has been blaming frozen wind turbines, a tiny percentage of the problem (frozen gas pipes are a much bigger issue) but one that plays with the base. The bare minimum of a sane response might be, I dunno,

• acknowledging the reality that climate change means that “once-per-century” weather events will be every couple years from now on,
• building spare capacity (nuclear would be ideal … well, I can dream),
• winterizing what we have now, and
• connecting the Texas grid to the rest of the US.

If I were a Texas Democrat, I’d consider making Republican incompetence on infrastructure, utilities, and public health my only campaign issues.

Alright, now back to watching the Mars lander, which is apparently easier to build and deploy than a reliable electric grid.

Note: To get myself into the spirit of writing this post, tonight I watched the 2019 movie Mr. Jones, about the true story of the coverup of Stalin’s 1932-3 mass famine by New York Times journalist Walter Duranty. Recommended!

In my last post, I wrote that despite all my problems with Cade Metz’s New York Times hit piece on Scott Alexander, I’d continue talking to journalists—even Metz himself, I added, assuming he’d still talk to me after my public disparagement of his work. Over the past few days, though, the many counterarguments in my comments section and elsewhere gradually caused me to change my mind. I now feel like to work with Metz again, even just on some quantum computing piece, would be to reward—and to be seen as rewarding—journalistic practices that are making the world worse, and that this consideration overrides even my extreme commitment to openness.

At the least, before I could talk to Metz again, I’d need a better understanding of how the hit piece happened. What was the role of the editors? How did the original hook—namely, the rationalist community’s early rightness about covid-19—disappear entirely from the article? How did the piece manage to evince so little curiosity about such an unusual subculture and such a widely-admired writer? How did it fail so completely to engage with the rationalists’ ideas, instead jumping immediately to “six degrees of Peter Thiel” and other reductive games? How did an angry SneerClubber, David Gerard, end up (according to his own boast) basically dictating the NYT piece’s content?

It’s always ripping-off-a-bandage painful to admit when trust in another person was wildly misplaced—for then who else can we not trust? But sometimes that’s the truth of it.

I continue to believe passionately in the centrality of good journalism to a free society. I’ll continue to talk to journalists often, about quantum computing or whatever else. I also recognize that the NYT is a large, heterogeneous institution (I myself published in it twice); it’s not hard to imagine that many of its own staff take issue with the SSC piece.

But let’s be clear about the stakes here. In the discussion of my last post, I described the NYT as “still the main vessel of consensus reality in human civilization” [alright, alright, American civilization!]. What’s really at issue, beyond the treatment of a single blogger, is whether the NYT can continue serving that central role in a world reshaped by social media, resurgent fascism, and entitled wokery.

Sure, we all know that the NYT has been disastrously wrong before: it ridiculed Goddard’s dream of spaceflight, denied the Holodomor, relegated the Holocaust to the back pages while it was happening, published the fabricated justifications for the Iraq War. But the NYT and a few other publications were still the blockchain of reality, the engine of the consensus of all that is, the last bulwark against the conspiracists and the anti-vaxxers and the empowered fabulists and the horned insurrectionists storming the Capitol, because there was no ability to coordinate around any serious alternative. I’m still skeptical that there’s a serious alternative, but I now look more positively than I did just a few days ago on attempts to create one.

To all those who called me naïve or a coward for having cooperated with the NYT: believe me, I’m well aware that I wasn’t born with much backbone. (I am, after all, that guy on the Internet who famously once planned on a life of celibate asceticism, or more likely suicide, rather than asking women out and thereby risking eternal condemnation as a misogynistic sexual harasser by the normal, the popular, the socially adept, the … humanities grads and the journalists.) But whenever I need a pick-me-up, I tell myself that rather than being ashamed about my lack of a backbone, I can take pride in having occasionally managed to stand even without one.