Shtetl-Optimized

Like many academics, I’ve now been regularly “attending” conferences and giving talks via Zoom for four months. Naturally, I’ve learned a lot about how to use this platform—one that, despite numerous quirks and flaws, actually works well enough that it could probably replace at least 2/3 of in-person talks and meetings after the covid crisis is over. But one particular lesson is so important that I thought I’d make a public service announcement of it. So without further ado:

Email the link.

You know, the thing like

https://us02web.zoom.us/jblahblah

that you actually click to get to the actual conversation. Definitely email the link to the speaker (!). But also email it to whomever said they plan to attend. Resend the link between a day and an hour in advance, so that it doesn’t get buried, but turns up right away when people search their inboxes. If possible, put the link in every single email about the meeting or lecture. Even if you already sent the link for previous iterations of the meeting and it hasn’t changed, send it again. Don’t assume people will find the link on the web. Don’t make them click through five other links or open an attached PDF for it. Don’t send ten emails that explain every possible detail of the meeting except how to get to it. Just email the link. That’s all. Thanks!

Follow

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

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

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

Scott’s foreword: Today I’m honored to host another guest post by friend-of-the-blog Steve Ebin, who not only published a beautiful essay here a month ago (the one that I titled “First it came from Wuhan”), but also posted an extremely informative timeline of what he understood when about the severity of the covid crisis, from early January until March 31st. By the latter date, Steve had quit his job, having made a hefty sum shorting airline stocks, and was devoting his full time to a new nonprofit to manufacture low-cost ventilators, called AirToAll. A couple weeks ago, Steve was kind enough to include me in one of AirToAll’s regular Zoom meetings; I learned more about pistons than I had in my entire previous life (admittedly, still not much). Which brings me to what Steve wants to talk about today: what he and others are doing and how you can help.

Without further ado, Steve’s guest post:

In my last essay on Coronavirus, I argued that Coronavirus will radically change society. In this blog post, I’d like to propose a structure for how we can organize to fight the virus. I will also make a call to action for readers of this blog to help a non-profit I co-founded, AirToAll, build safe, low-cost ventilators and other medical devices and distribute them across the world at scale.

There are four ways we can help fight coronavirus:

1. Reduce exposure to the virus. Examples: learn where the virus is through better testing; attempt to be where the virus isn’t through social distancing, quarantining, and other means.
2. Reduce the chance of exposure leading to infection. Examples: Wash your hands; avoid touching your face; wear personal protective equipment.
3. Reduce the chance of infection leading to serious illness. Examples: improve your aerobic and pulmonary health; make it more difficult for coronavirus’s spike protein to bind to ACE-2 receptors; scale antibody therapies; consume adequate vitamin D; get more sleep; develop a vaccine.
4. Reduce the chance of serious illness leading to death. Examples: ramp up the production and distribution of certain drugs; develop better drugs; build more ventilators; help healthcare workers.

Obviously, not every example I listed is practical, advisable, or will work, and some options, like producing a vaccine, may be better solutions than others. But we must pursue all approaches.

I’ve been devoting my own time to pursuing the fourth approach, reducing the chance that the illness will lead to death. Specifically, along with Neil Thanedar, I co-founded AirToAll, a nonprofit that helps bring low-cost, reliable, and clinically tested ventilators to market. I know lots of groups are working on this problem, so I thought I’d talk about it briefly.

First, like many groups, we’re designing our own ventilators. Although designing ventilators and bringing them to market at scale poses unique challenges, particularly in an environment where supply chains are strained, this is much easier than it must have been to build iron lungs in the early part of the 20th century, when Zoom conferencing wasn’t yet invented. When it comes to the ventilators we’re producing, we’re focused on safety and clinical validation rather than speed to market. We are not the farthest along here, but we’ve made good progress.

Second, our nonprofit is helping other groups produce safe and reliable ventilators by doing direct consultations with them and also by producing whitepapers to help them think through the issues at hand (h/t to Harvey Hawes, Abdullah Saleh, and our friends at ICChange).

Third, we’re working to increase the manufacturing capacity for currently approved ventilators.

The current shortage of ventilators is a symptom of a greater underlying problem: namely, the world is not good at recognizing healthcare crises early and responding to them quickly. While our nonprofit helps bring more ventilators to market, we are also trying to solve this greater underlying problem. I look at our work in ventilator-land as a first step towards our ultimate goal of making medical devices cheaper and more available through an open-source nonprofit model.

I am writing this post as a call to action to you, dear Shtetl-Optimized reader, to get involved.

You don’t have to be an engineer, pulmonologist, virologist, or epidemiologist to help us, although those skillsets are of course helpful and if you are we’d love to have you. If you have experience in data science and modeling, supply chain and manufacturing, public health, finance, operations, community management, or anything else a rapidly scaling organization needs, you can help us too. 

We are a group of 700+ volunteers and growing rapidly. If you’d like to help, we’d love to have you. If you might be interested in volunteering, click here. Donors click here. Everyone else, please email me at steven@airtoall.org and include a clear subject line so I can direct you to the right person.

Follow

Today, as the world braces for the possibility of losing millions of lives to the new coronavirus—to the hunger for pangolin meat, of all things (combined with the evisceration of competent public health agencies like the CDC)—we also mourn the loss of two incredibly special lives, those of Freeman Dyson (age 96) and Boris Tsirelson (age 69).

Freeman Dyson was sufficiently legendary, both within and beyond the worlds of math and physics, that there’s very little I can add to what’s been said. It seemed like he was immortal, although I’d heard from mutual friends that his health was failing over the past year. When I spent a year as a postdoc at the Institute for Advanced Study, in 2004-5, I often sat across from Dyson in the common room, while he drank tea and read the news. That I never once struck up a conversation with him is a regret that I’ll now carry with me forever.

My only exchange with Dyson came when he gave a lecture at UC Berkeley, about how life might persist infinitely far into the future, even after the last stars had burnt out, by feeding off steadily dimishing negentropy flows in the nearly-thermal radiation. During the Q&A, I challenged Dyson that his proposal seemed to assume an analog model of computation. But, I asked, once we took on board the quantum-gravity insights of Jacob Bekenstein and others, suggesting that nature behaves like a (quantum) digital computer at the Planck scale, with at most ~10⁴³ operations per second and ~10⁶⁹ qubits per square meter and so forth, wasn’t this sort of proposal ruled out? “I’m not going to argue with you,” was Dyson’s response. Yes, he’d assumed an analog computational model; if computation was digital then that surely changed the picture.

Sometimes—and not just with his climate skepticism, but also (e.g.) with his idea that general relativity and quantum mechanics didn’t need to be reconciled, that it was totally fine for the deepest layer of reality to be a patchwork of inconsistent theories—Dyson’s views struck me as not merely contrarian but as a high-level form of trolling. Even so, Dyson’s book Disturbing the Universe had had a major impact on me as a teenager, for the sparkling prose as much as for the ideas.

With Dyson’s passing, the scientific world has lost one of its last direct links to a heroic era, of Einstein and Oppenheimer and von Neumann and a young Richard Feynman, when theoretical physics stood at the helm of civilization like never before or since. Dyson, who apparently remained not only lucid but mathematically powerful (!) well into his last year, clearly remembered when the Golden Age of science fiction looked like simply sober forecasting; when the smartest young people, rather than denouncing each other on Twitter, dreamed of scouting the solar system in thermonuclear-explosion-powered spacecraft and seriously worked to make that happen.

Boris Tsirelson (homepage, Wikipedia), who emigrated from the Soviet Union and then worked at Tel Aviv University (where my wife Dana attended his math lectures), wasn’t nearly as well known as Dyson to the wider world, but was equally beloved within the quantum computing and information community. Tsirelson’s bound, which he proved in the 1980s, showed that even quantum mechanics could only violate the Bell inequality by so much and by no more, could only let Alice and Bob win the CHSH game with probability cos²(π/8). This seminal result anticipated many of the questions that would only be asked decades later with the rise of quantum information. Tsirelson’s investigations of quantum nonlocality also led him to pose the famous Tsirelson’s problem: loosely speaking, can all sets of quantum correlations that can arise from an infinite amount of entanglement, be arbitrarily well approximated using finite amounts of entanglement? The spectacular answer—no—was only announced one month ago, as a corollary of the MIP*=RE breakthrough, something that Tsirelson happily lived to see although I don’t know what his reaction was (update: I’m told that he indeed learned of it in his final weeks, and was happy about it). Sadly, for some reason, I never met Tsirelson in person, although I did have lively email exchanges with him 10-15 years ago about his problem and other topics. This amusing interview with Tsirelson gives some sense for his personality (hat tip to Gil Kalai, who knew Tsirelson well).

Please share any memories of Dyson or Tsirelson in the comments section.

Follow

Here it is (about 90 minutes; I recommend the 1.5x speed)

I had buried this as an addendum to my previous post on the quantum supremacy lecture tour, but then decided that a steely-eyed assessment of what’s likely to have more or less interest for this blog’s readers probably militated in favor of a separate post.

Thanks so much to Lex for arranging the interview and for his questions!

Follow

(At a few people’s request, I’ve changed the title so that it no longer refers to a specific person. I try always to be accurate, amusing, and appropriate, but sometimes I only hit 1 or 2 of the 3.)

As part of my speaking tour, in the last month I’ve already given talks at the following fine places:

World Economic Forum at Davos
University of Waterloo
Perimeter Institute
UC Berkeley
Harvard
MIT
Princeton
University of Houston

And I’ll be giving talks at the following places over the next couple of months:

Louisiana State University
Pittsburgh Quantum Institute
Fermilab
Yale

For anyone who’s interested, I’ll add links and dates to this post later (if you want that to happen any faster, feel free to hunt them down for me!).

In the meantime, there are also interviews! See, for example, this 5-minute one on Texas Standard (an NPR affiliate), where I’m asked about the current state of quantum computing in the US, in light of the Trump administration’s recent proposal to give a big boost to quantum computing and AI research, even while slashing and burning basic science more broadly. I made some critical comments—for example, about the need to support the whole basic research ecosystem (I pointed out that “quantum computing can’t thrive in isolation”), and also about the urgent need to make it feasible for the best researchers from around the world to get US visas and green cards. Unfortunately, those parts seem to have been edited out, in favor of my explanations of basic points about quantum computing.

More Updates:

There was a discussion on Twitter of the ethics of the “Quantum Bullshit Detector” Twitter feed—which dishes out vigilante justice, like some dark and troubled comic-book hero, by rendering anonymous, unexplained, unaccountable, very often correct albeit not infallible verdicts of “Bullshit” or “Not Bullshit” on claimed quantum information advances. As part of that discussion, Christopher Savoie wrote:

[Criticizing] is what we do in science. [But not calling] “bullshit” anonymously and without any accountability. Look at Scott Aaronson’s blog. He takes strong positions. But as Scott. I respect that.

What do people think: should “He takes strong positions. But as Scott.” be added onto the Shtetl-Optimized header bar?

In other news, I was amused by the following headline, for a Vice story about the MIP*=RE breakthrough: Mathematicians Are Studying Planet-Sized Supercomputers With God-Like Powers. (If I’m going to quibble about accuracy: only planet-sized???)

Follow