Shtetl-Optimized

Daily Updates:
Saturday January 18 (introduction)
Sunday January 19 (Elton John and Greta Thunberg)
Monday January 20 (the $71,000-a-head ski resort conference for Equality)
Tuesday January 21 (Trump! Greta! QC panel!)
Wednesday January 22 (wherein I fail to introduce myself to Al Gore)
Thursday January 23 (wherein I attend the IBM QC panel and “drunkenly unload” at the Canada Reception)
Friday January 24 (second Al Gore session, and getting lost)

It would be great to know whether anyone’s actually reading the later updates, so I know whether to continue putting effort into them!

Saturday January 18

Today I’m headed to the 50th World Economic Forum in Davos, where on Tuesday I’ll participate in a panel discussion on “The Quantum Potential” with Jeremy O’Brien of the quantum computing startup PsiQuantum, and will also host an ask-me-anything session about quantum computational supremacy and Google’s claim to have achieved it.

I’m well aware that this will be unlike any other conference I’ve ever attended: STOC or FOCS it ain’t. As one example, also speaking on Tuesday—although not conflicting with my QC sessions—will be a real-estate swindler and reality-TV star who’s somehow (alas) the current President of the United States. Yes, even while his impeachment trial in the Senate gets underway. Also speaking on Tuesday, a mere hour and a half after him, will be TIME’s Person of the Year, 17-year-old climate activist Greta Thunberg.

In short, this Davos is shaping up to be an epic showdown between two diametrically opposed visions for the future of life on Earth. And your humble blogger will be right there in the middle of it, to … uhh … explain how quantum computers can sample probability distributions that are classically intractable unless the polynomial hierarchy collapses to the third level. I feel appropriately sheepish.

Since the experience will be so unusual for me, I’m planning to “live-blog Davos”: I’ll be updating this post, all week, with any strange new things that I see or learn. As a sign of my devotion to you, my loyal readers, I’ll even clothespin my nose and attend Trump’s speech so I can write about it.

And Greta: on the off chance that you happen to read Shtetl-Optimized, let me treat you to a vegan lunch or dinner! I’d like to try to persuade you of just how essential nuclear power will be to a carbon-free future. Oh, and if it’s not too much trouble, I’d also like a selfie with you for this blog. (Alas, a friend pointed out to me that it would probably be easier to meet Trump: unlike Greta, he won’t be swarmed with thousands of fans!)

Anyway, check back here throughout the week for updates. And if you’re in Davos and would like to meet, please shoot me an email. And please use the comment section to give me your advice, suggestions, well-wishes, requests, or important messages for me to fail to deliver to the “Davoisie” who run the world.

Sunday January 19

So I’ve arrived in Klosters, a village in the Swiss Alps close to Davos where I’ll be staying. (All the hotels in Davos itself were booked by the time I checked.)

I’d braced myself for the challenge of navigating three different trains through the Alps not knowing German. In reality, it was like a hundred times easier than public transportation at home. Every train arrived at the exact right second at the exact platform that was listed, bearing the exact right number, and there were clear visible signs strategically placed at exactly the places where anyone could get confused. I’d entered Bizarro Opposite World. I’m surely one of the more absentminded people on earth, as well as one of the more neurotic about being judged by bystanders if I ever admit to being lost, and it was nothing.

Snow! Once a regular part of my life, now the first I’d seen in several years. Partly because I now live in Texas, but also because even when we take the kids back to Pennsylvania for ChanuChrismaNewYears, it no longer snows like it did when I was a kid. If you show my 2-year-old, Daniel, a picture of snow-covered wilderness, he calls it a “beach.” Daniel’s soon-to-be 7-year-old sister still remembers snow from Boston, but the memory is rapidly fading. I wonder for how many of the children of the 21st century will snow just be a thing from old books and movies, like typewriters or rotary phones.

The World Economic Forum starts tomorrow afternoon. In the meantime, though, I thought I’d give an update not on the WEF itself, but on the inflight movie that I watched on my way here.

I watched Rocketman, the recent biopic/hagiography about Elton John, though as I watched I found that I kept making comparisons between Elton John and Greta Thunberg.

On the surface, these two might not seem to have a great deal of similarity.

But I gathered that they had this in common: while still teenagers, they saw a chance and they seized it. And doing so involved taking inner turmoil and then succesfully externalizing it to the whole planet. Making hundreds of millions of people feel the same emotions that they had felt. If I’m being painfully honest (how often am I not?), that’s something I’ve always wanted to achieve and haven’t.

Of course, when some of the most intense and distinctive emotions you’ve ever felt revolved around the discovery of quantum query complexity lower bounds … yeah, it might be tough to find more people than could fill a room to relive those emotional journeys with you. But a child’s joy at discovering numbers like Ackerman(100) (to say nothing of BB(100)), which are so incomprehensibly bigger than \( 9^{9^{9^{9^9}}} \) that I didn’t need to think twice about how many 9’s I put there? Or the exasperation at those who, yeah, totally get that quantum computers aren’t known to give exponential speedups for NP-complete problems, that’s a really important clarification coming from the theory side, but still, let’s continue to base our entire business or talk or article around the presupposition that quantum computers do give exponential speedups for NP-complete problems? Or even just the type of crush that comes with a ceaseless monologue about what an objectifying, misogynist pig you must be to experience it? Maybe I could someday make people vicariously experience and understand those emotions–if I could only find the right words.

My point is, this is precisely what Greta did for the burgeoning emotion of existential terror about the Anthropocene—another emotion that’s characterized my life since childhood. Not that I ever figured out anything to do about it, with the exception of Gore/Nader vote-swapping. By the standards of existential terrors, I consider this terror to be extraordinarily well-grounded. If Steven Weinberg is scared, who among us has the right to be calm?

The obvious objection to Greta—why should anyone care what a histrionic teenager thinks about a complicated scientific field that thousands of people get PhDs in?—calls for a substantive answer. So here’s mine. Like many concerned citizens, I try to absorb some of the research on ocean warming or the collapse of ice sheets and the melting permafrost leading to even more warming or the collapse of ecosystems due to changes in rainfall or bushfires or climate migrations or whatever. And whenever I do, I’m reminded of Richard Feynman’s remark, during the investigation of the Challenger disaster, that maybe it wasn’t all that interesting for the commission to spend its time reconstructing the exact details of which system caused which other system to malfunction at which millisecond, after the Space Shuttle had already started exploding. The thing was hosed at that point.

Still, even after the 80s and 90s, there remained deep open questions about the eventual shape of the climate crisis, and foremost among them was: how do you get people to stop talking about this crisis in the language of intellectual hypotheticals and meaningless virtue-signalling gestures and “those crazy scientists, who knows what they’ll say tomorrow”? How does one get people to revert to a more ancient language, the one that was used to win WWII for example, which speaks of courage and duty and heroism and defiance in the jaws of death?

Greta’s origin story—the one where the autistic girl spends months so depressed over climate inaction that she can’t eat or leave her room, until finally, no longer able to bear the psychic burden, she ditches school and carries a handmade protest sign to the front of the Swedish parliament—is not merely a prerequisite to a real contribution. It is Greta’s real contribution (so far anyway), and by that I don’t mean to diminish it. The idea was “trivial,” yes, but only in the sense that the wheel, Arabic numerals, or “personal computers will be important” were trivial ideas. Greta modeled for the rest of the world how they, too, would probably feel about climate change were they able to sync up their lizard brains with their higher brains … and crucially, a substantial segment of the world was already primed to agree with her. But it needed to see one successful example of a succesful sync between the science and the emotions appropriate to the science, as a crystal needs a seed.

The thesis of Rocketman is that Elton John’s great achievement was not only to invent a new character, but actually to become that character, since only by succesfully fusing the two could he touch the emotions of the masses. In a similar way, Greta Thunberg’s great accomplishment of her short life has been to make herself into the human race’s first Greta Thunberg.

Monday January 20

Happy 7th birthday to my daughter Lily!  (No, I didn’t miss her birthday party.  We did it on the 18th, right before I flew out.)

I think my goals for Davos have been downgraded from delivering a message of peace and nerd liberation to the world’s powerful, or even getting a selfie with Greta, to simply taking in a week in an environment that’s so alien to me.

Everything in Davos is based on a tiered system of badges, which determine which buildings you can get into to participate in the sessions.  I have a white badge, the highest tier, which would’ve set me back around $71,000 had WEF not thankfully waived its fees for academics.  I should mention that I’m also extremely underdressed compared to most of the people here, and that I spent much of my time today looking for free food.  It turns out that there’s pretty copious and excellent free food, although the sponsors sometimes ask you to leave your business card before you take any.  I don’t have a business card.

The above, for me, represents the true spirit of Davos: a conference at a Swiss ski resort that costs $71,000 to attend, held on behalf of the ideal of human equality.

But maybe I shouldn’t scoff.  I learned today about a war between Greece and Turkey that was averted only because the heads of the two countries talked it over at Davos, so that’s cool.  At the opening ceremony today, besides a beautiful orchestral rendition of “Ode to Joy,” there were a bunch of speeches about how Davos pioneered the entire concept of corporate social responsibility.  I suppose the critics might say instead that Davos pioneered the concept of corporate whitewashing—as with the wall-sized posters that I saw this afternoon, wherein a financial services corporation showcased a diverse cast of people each above their preferred pronouns (he/him, she/her, they/them).  Amazing how pronouns make everything woke and social-justicey!  I imagine that the truth is somewhere between these visions.  Just like the easiest way for NASA to fake a moon landing was actually to send humans to the moon, sometimes the easiest way to virtue-signal is actually to become more virtuous.

Tonight I went to a reception specifically for the academics at Davos.  There, for the first time since my arrival, I saw people who I knew (Shafi Goldwasser, Neha Narula…), and met someone who I’d known by reputation (Brian Schmidt, who shared the Nobel Prize in Physics for the discovery of dark energy).  But even the people who I didn’t know were clearly “my people,” with familiar nerdy mannerisms and interests, and in some cases even a thorough knowledge of SlateStarCodex references.  Imagine visiting a foreign country where no one spoke your language, then suddenly stumbling on the first ones who did.  I found it a hundred times easier than at the main conference to strike up conversations.

Oh yeah, quantum computing.  This afternoon I hosted three roundtable discussions about quantum computing, which were fun and stress-free — I spent much more of my mental energy today figuring out the shuttle buses.  If you’re a regular reader of this blog or my popular articles, or a watcher of my talks on YouTube, etc., then congratulations: you’ve gotten the same explanations of quantum computing for free that others may have paid $71,000 apiece to hear!  Tomorrow are my two “real” quantum computing sessions, as well as the speeches by both the Donald and the Greta (the latter being the much hotter ticket).  So it’s a big day, which I’ll tell you about after it’s happened. Stay tuned!

Tuesday January 21

PsiQuantum’s Jeremy O’Brien and I did the Davos quantum computing panel this morning (moderated by Jennifer Schenker). You can watch our 45-minute panel here. For regular readers of this blog, the territory will be familiar, but I dunno, I hope someone enjoys it anyway!

I’m now in the Congress Hall, in a seat near the front, waiting for Trump to arrive. I will listen to the President of the United States and not attract the Secret Service’s attention by loudly booing, but I have no intention to stand or applaud either.

Alas, getting a seat at Greta’s talk is looking like it will be difficult or impossible.

I was struck by the long runup to Trump’s address: the President of Switzerland gave a searing speech about the existential threats of climate change and ecosystem destruction, and “the politicians in many nations who appeal to fear and bigotry”—never mentioning Trump by name but making clear that she despised the entire ideology of the man people had come to hear. I thought it was a nice touch. Then some technicians spent 15 minutes adjusting Trump’s podium, then nothing happened for 20 minutes as we all waited for a tardy Trump, then some traditional Swiss singers did a performance on stage (!), and finally Klaus Schwab, director of the WEF, gave Trump a brief and coldly cordial introduction, joking about the weather in Davos.

And … now Trump is finally speaking. Once he starts, I suddenly realize that I have no idea what new insight I expected from this. He’s giving his standard stump speech, America has regained its footing after the disaster of the previous administration, winning like it’s never won before, unemployment is the lowest in recorded history, blah blah blah. I estimate that less than half of the audience applauded Trump’s entrance; the rest sat in stony silence. Meanwhile, some people were passing out flyers to the audience documenting all the egregious errors in Trump’s economic statistics.

Given the small and childish nature of the remarks (“we’re the best! ain’t no one gonna push us around!”), it feels somehow right to be looking down at my phone, blogging, rather than giving my undivided attention to the President of the United States speaking 75 feet in front of me.

Ok, I admit I just looked up, when Trump mentioned America’s commitment to developing new technologies like “5G and quantum computing” (he slowly drew out the word “quantum”).

His whole delivery is strangely lethargic, as if he didn’t sleep well last night (I didn’t either).

Trump announced that the US would be joining the WEF’s “1 trillion trees” environmental initiative, garnering the only applause in his speech. But he then immediately pivoted to a denunciation of the “doomsayers and pessimists and socialists who want to control our lives and take away our liberty” (he presumably meant people worried about climate change).

Now, I kid you not, Trump is expanding on his “optimism” theme by going on and on about the architectural achievements of Renaissance Florence.

You can watch Trump’s speech for yourself here.

While I wasn’t able to get in to see Greta Thunberg in person, you can watch her (along with others) here. I learned that her name is pronounced “toon-berg.”

Having now listened to Greta’s remarks, I confess that I disagree with the content of what she says.  She explicitly advocates a sort of purity-based carbon absolutism—demanding that companies and governments immediately implement, not merely net zero emissions (i.e. offsetting their emissions by paying to plant trees and so forth), but zero emissions period.  Since she can’t possibly mean literally zero, I’ll interpret her to mean close to zero.  Even so, it seems to me that the resulting economic upheavals would provoke a massive backlash against whoever tried to enforce such a policy.  Greta also dismisses the idea of technological solutions to climate change, saying that we don’t have time to invent such solutions.  But of course, some of the solutions already exist—a prime example being nuclear power.  And if we no longer have time to nuclearize the world, then to a great extent, that’s the fault of the antinuclear activists—an unbelievable moral and strategic failure that may have doomed our civilization, and for which there’s never been a reckoning.

Despite all my disagreements, if Greta’s strident, uncompromising rhetoric helps push the world toward cutting emissions, then she’ll have to be counted as one of the greatest people who ever lived. Of course, another possibility is the world’s leaders will applaud her and celebrate her moral courage, while not taking anything beyond token actions.

Wednesday January 22

Alas, I’ve come down with a nasty cold (is there any other kind?).  So I’m paring back my participation in the rest of Davos to the stuff that really interests me.  The good news is that my quantum computing sessions are already finished!

This morning, as I sat in the lobby of the Congress Centre checking my email and blowing my nose, I noticed some guy playing a cello nearby.  Dozens were gathered around him — so many that I could barely see the guy, only hear the music.  After he was finished, I worked up the courage to ask someone what the fuss was about.  Turns out that the guy was Yo-Yo Ma.

The Prince Regent of Liechtenstein was explaining to one of my quantum computing colleagues that Liechtenstein does not have much in the way of quantum.

Speaking of princes, I’m now at a cybersecurity session with Shafi Goldwasser and others, at which the attendance might be slightly depressed because it’s up against Prince Charles. That’s right: Davos is the conference where the heir apparent to the British throne speaks in a parallel session.

I’ve realized these past few days that I’m not very good at schmoozing with powerful people.  On the other hand, it’s possible that my being bad at it is a sort of mental defense mechanism.  The issue is that, the more I became a powerful “thought leader” who unironically used phrases like “Fourth Industrial Revolution” or “disruptive innovation,” the more I used business cards and LinkedIn to expand my network of contacts or checked my social media metrics … well, the less I’d be able to do the research that led to stuff like being invited here in the first place.  I imagine that many Davos regulars started out as nerds like me, and that today, coming to Davos to talk about “disruptive innovation” is a fun kind of semi-retirement.  If so, though, I’m not ready to retire just yet!  I still want to do things that are new enough that they don’t need to be described using multiple synonyms for newness.

Apparently one of the hottest tickets at Davos is a post-Forum Shabbat dinner, which used to be frequented by Shimon Peres, Elie Wiesel, etc.  Alas, not having known about it, I already planned my travel in a way that won’t let me attend it.  I feel a little like the guy in this Onion article.

I had signed up for a session entitled What’s At Stake: The Arctic, featuring Al Gore. As I waited for them to start letting people in, I suddenly realized that Al Gore was standing right next to me. However, he was engrossed in conversation with a young woman, and even though I assumed she was just some random fan like I was, I didn’t work up the courage to interrupt them. Only once the panel had started, with the woman on it two seats from Gore, did I realize that she was Sanna Marin, the new Prime Minister of Finland (and at 34, the world’s second-youngest head of state).

You can watch the panel here. Briefly, the Arctic has lost about half of its ice cover, not merely since preindustrial times but since a few decades ago. And this is not only a problem for polar bears. It’s increasing the earth’s absorption of sunlight and hence significantly accelerating global warming, and it’s also screwing up weather patterns all across the northern hemisphere. Of course, the Siberian permafrost is also thawing and releasing greenhouse gases that are even worse than CO2, further accelerating the wonderful feedback loop of doom.

I thought that Gore gave a masterful performance. He was in total command of the facts—discoursing clearly and at length on the relative roles of CO2, SO2, and methane in the permafrost as well as the economics of oil extraction, less in the manner of thundering (or ‘thunberging’?) prophet than in the manner of an academic savoring all the non-obvious twists as he explains something to a colleague—and his every response to the other panelists was completely on point.

In 2000, there was indeed a bifurcation of the universe, and we ended up in a freakishly horrible branch. Instead of something close to the best, most fact-driven US president one could conjure in one’s mind, we got something close to the worst, and then, after an 8-year interregnum just to lull us into complacency, we got something even worse than the worst.

The other panelists were good too. Gail Whiteman (the scientist) had the annoying tic of starting sentence after sentence with “the science says…,” but then did a good job of summarizing what the science does say about the melting of the Arctic and the permafrost.

Alas, rather than trying to talk to Gore, immediately after the session ended, I headed back to my hotel to go to sleep. Why? Partly because of my cold. But partly also because of incident immediately before the panel. I was sitting in the front row, next to an empty seat, when a woman who wanted to occupy that seat hissed at me that I was “manspreading.”

If, on these narrow seats packed so tightly together that they were basically a bench, my left leg had strayed an inch over the line, I would’ve addressed the situation differently: for example, “oh hello, may I sit here?” (At which point I would’ve immediately squeezed in.) Amazingly, the woman didn’t seem to didn’t care that a different woman, the one to my right, kept her pocketbook and other items on the seat next to her throughout the panel, preventing anyone else from using the seat in what was otherwise a packed house. (Is that “womanspreading”?)

Anyway, the effect of her comment was to transform the way I related to the panel. I looked around at the audience and thought: “these activists, who came to hear a panel on climate change, are fighting for a better world. And in their minds, one of the main ways that the world will be better is that it won’t contain sexist, entitled ‘manspreaders’ like me.”

In case any SneerClubbers are reading, I should clarify that I recognize an element of the irrational in these thoughts. I’m simply reporting, truthfully, that they’re what bubbled up outside the arena of conscious control. But furthermore, I feel like the fact that my brain works this way might give me some insight into the psychology of Trump support that few Democrats share—so much that I wonder if I could provide useful service as a Democratic political consultant!

I understand the mindset that howls: “better that every tree burn to the ground, every fish get trawled from the ocean, every coastal city get flooded out of existence, than that these sanctimonious hypocrites ‘on the right side of history,’ singing of their own universal compassion even as they build a utopia with no place for me in it, should get to enjoy even a second of smug self-satisfaction.” I hasten to add that I’ve learned how to override that mindset with a broader, better mindset: I can jump into the abyss, but I can also climb back out, and I can even look down at the abyss from above and report what’s there. It’s as if I’d captured some virulent strain of Ebola in a microbiology lab of the soul. And if nearly half of American voters (more in crucial swing states) have gotten infected with that Ebola strain, then maybe my lab work could have some broader interest.

I thought about Scott Minerd, the investor on the panel, who became a punching bag for the other panelists (except for Gore, a politician in a good sense, who went out of his way to find points of agreement). In his clumsy way, Minerd was making the same point that climate activists themselves correctly make: namely, that the oil companies need to be incentivized (for example, through a carbon tax) to leave reserves in the ground, that we can’t just trust them to do the noble thing and write off their own assets. But for some reason, Minerd presented himself as a greedy fat-cat, raining on the dreams of the hippies all around him for a carbon-free future, so then that’s how the other panelists duly treated him (except, again, for Gore).

But I looked at the audience, which was cheering attacks on Minerd, and the Ebola in my internal microbiology lab said: “the way these activists see Scott Minerd is not far from how they see Scott Aaronson. You’ll never be good enough for them. The people in this room might or might not succeed at saving the world, but in any case they don’t want your help.”

After all, what was the pinnacle of my contribution to saving the world? It was surely when I was 19, and created a website to defend the practice of NaderTrading (i.e., Ralph Nader supporters in swing states voting for Al Gore, while Gore supporters in safe states pledged to vote Nader on their behalf). Alas, we failed. We did help arrange a few thousand swaps, including a few hundred swaps in Florida, but it was 538 too few. We did too little, too late.

So what would I have talked to Gore about, anyway? Would I have reminded him of the central tragedy of his life, which was also a central tragedy of recent American history, just in order to babble, or brag, about a NaderTrading website that I made half a lifetime ago? Would I have made up a post-hoc rationalization for why I work on quantum computing, like that I hope it will lead to the discovery of new carbon-capture methods? Immediately after Gore’s eloquent brief for the survival of the Arctic and all life on earth, would I have asked him for an autograph or a selfie? No, better to just reflect on his words. At a crucial pivot point in history, Gore failed by a mere 538 votes, and I also failed to prevent the failure. But amazingly, Gore never gave up-–he just kept on fighting for what he knew civilization needed to do—and yesterday I sat a few feet away while he explained why the rest of us shouldn’t give up either. And he’s right about this—if not in the sense of the outlook being especially hopeful or encouraging right now, then surely in the sense of which attitude is the useful one to adopt. And my attitude, which you might call “Many-Worlds-inflected despair,” might be epistemically sound but it definitely wasn’t useful. What further clarifications did I need?

Thursday January 23

I attended a panel discussion on quantum computing hosted by IBM. The participants were Thomas Friedman (the New York Times columnist), Arvind Krishna (a senior Vice President at IBM), Raoul Klingner (director of a European research organization), and Alison Snyder (the managing editor of Axios magazine). There were about 100 people in the audience, more than at all of my Davos quantum computing sessions combined. I sat right in front, although I don’t think anyone on the panel recognized me.

Ginni Rometty, the CEO of IBM, gave an introduction. She said that quantum will change the world by speeding up supply-chain and other optimization problems. I assume she was talking about the Grover speedup? She also said that IBM is committed to delivering value for its customers, rather than “things you can do in two seconds that are not commercially valid” (I assume she meant Google’s supremacy experiment). She asked for a show of hands of who knows absolutely nothing about the science behind quantum computing. She then quipped, “well, that’s all of you!” She may have missed two hands that hadn’t gone up (both belonging to the same person).

I accepted an invitation to this session firstly for the free lunch (which turned out to be delicious), and secondly because I was truly, genuinely curious to hear what Thomas Friedman, many of whose columns I’ve liked, had to teach me about quantum computing. The answer turns out to be this: in his travels around the world over the past 6 years, Friedman has witnessed firsthand how the old dichotomy between right-wing parties and left-wing parties is breaking down everywhere (I assume he means, as both sides get taken over by populist movements?). And this is just like how a qubit breaks down the binary dichotomy between 0’s and 1’s! Also, the way a quantum computer can be in multiple states at once, is like how the US now has to be in multiple states at once in its relationship with China.

Friedman opened his remarks by joking about how he never took a single physics course, and had no idea why he was on a quantum computing panel at all. He quickly added, though, that he toured IBM’s QC labs, where he found IBM’s leaders to be wonderful explainers of what it all means.

I’ll note that Friedman, the politics and Middle East affairs writer — not the two panelists serving the role of quantum experts — was the only one who mentioned, even in passing, the idea that the advantage of QCs depends on something called “constructive interference.”

Krishna, the IBM Vice President, explained why IBM rejects the entire concept of “quantum supremacy”: because it’s an irrelevant curiosity, and creating value for customers in the marketplace (for example by solving their supply-chain optimization problems) is the only test that matters. No one on the panel expressed a contrary view.

Later, Krishna explained why quantum computers will never replace classical computers: because if you stored your bank balance on a quantum computer, one day you’d have $1, the next day $1000, the day after that $1 again, and so forth! He explained how, where current supercomputers use the same amount of energy needed to power all of Davos to train machine learning models, quantum computers would use less than the energy needed to power a single house. New algorithms do need to be designed to run neural networks quantumly, but fortunately that’s all being done as we speak.

I got the feeling that the businesspeople who came to this session felt like they got a lot more out of it than the businesspeople who came to my and Jeremy O’Brien’s session felt like they got out of ours. After all, this session got across some big real-world takeaways—e.g., that if you don’t quantum, your business will be left in the dust, stuck with a single value at a time rather than exploring all values in parallel, and IBM can help you rather than your competitors win the quantum race. It didn’t muddy the message with all the incomprehensible technicalities about how QCs only give exponential speedups for problems with special structure.

Later Update:

Tonight I went to a Davos reception hosted by the government of Canada (🇨🇦). I’m not sure why exactly they invited me, although I have of course enjoyed a couple years of life “up north” (well, in Waterloo, so actually further south than a decent chunk of the US … you see that I do have a tiny speck of a Canadian in me?).

I didn’t recognize a single person at the reception. So I just ate the food, drank beer, and answered emails. But then a few people did introduce themselves (two who recognized me, one who didn’t). As they gathered around, they started asking me questions about quantum computing: is it true that QCs could crack the classically impossible Traveling Salesman Problem? That they try all possible answers in parallel? Are they going to go commercial in 2-5 years, or have they already?

It might have been the beer, but for some reason I decided to launch an all-out assault of truth bombs, one after the next, with what they might have considered a somewhat emotional delivery.

OK fine, it wasn’t the beer. That’s just who I am.

And then, improbably, I was a sort of localized “life of the party” — although possibly for the amusement / novelty value of my rant more than for the manifest truth of my assertions. One person afterward told me that it was by far the most useful conversation he’d had at Davos.

And I replied: I’m flattered by your surely inflated praise, but in truth I should also thank you. You caught me at a moment when I’d been thinking to myself that, if only I could make one or two people’s eyes light up with comprehension about the fallacy of a QC simply trying all possible answers in parallel and then magically picking the best one, or about the central role of amplitudes and interference, or about the “merely” quadratic nature of the Grover speedup, or about the specialized nature of the most dramatic known applications for QCs, or about the gap between where the experimentalists are now and what’s needed for error correction and hence true scalability, or about the fact that “quantum supremacy” is obviously not a sufficient condition for a QC to be useful, but it’s equally obviously a necessary condition, or about the fact that doing something “practical” with a QC is of very little interest unless the task in question is actually harder for classical computers, which is a question of great subtlety … I say, if I could make only two or four eyes light up with comprehension of these things, then on that basis alone I could declare that the whole trip to Davos was worth it.

And then one of the people hugged me … and that was the coolest thing that happened to me today.

Friday January 24

I attended a second session with Al Gore, about the problem of the world filling up with plastic. I learned that the world’s plastic waste is set to double over the next 15-20 years, and that a superb solution—indeed, it seems like a crime that it hasn’t been implemented already—-would be to set up garbage booms at the mouths of a few major rivers from which something like 80% of the plastic waste in the ocean gets there.

Anyway, still didn’t introduce myself.

I wrote before about how surprisingly clear and logical the trains to Davos were, even with multiple changes. Unfortunately God’s mercy on me didn’t last. All week, I kept getting lost in warren-like buildings with dozens of “secret passageways” (often literally behind unmarked doors) and few signs—not even exit signs. In one case I missed a tram that was the only way out from somewhere because I arrived to the wrong side of the tram—and getting to the right side required entering a building and navigating another unmarked labyrinth, by which point the tram had already left. In another case, I wandered through a Davos hotel for almost an hour trying to find an exit, ricocheting like a pinball off person after person giving me conflicting directions. Only after I literally started ranting to a crowd: ”holy f-ck, is this place some psychological torture labyrinth designed by Franz Kafka? Am I the only one? Is it clear to all of you? Please, WHERE IS THE F-CKING EXIT???” until finally some local took pity and walked me through the maze. As I mentioned earlier, logistical issues like these made me about 5,000 times more anxious on this trip than the prospect of giving quantum computing talks to the world’s captains of industry. I don’t recall having had a nightmare about lecturing even once—but I’ve had never-ending nightmares about failing to show up to give a lecture because I’m wandering endlessly through an airport or a research center or whatever, always the only one who’s lost.

1. Two weeks ago, I blogged about the claim of Nathan Keller and Ohad Klein to have proven the Aaronson-Ambainis Conjecture. Alas, Keller and Klein tell me that they’ve now withdrawn their preprint (though it may take another day for that to show up on the arXiv), because of what looks for now like a fatal flaw, in Lemma 5.3, discovered by Paata Ivanishvili. (My own embarrassment over having missed this flaw is slightly mitigated by most of the experts in discrete Fourier analysis having missed it as well!) Keller and Klein are now working to fix the flaw, and I wholeheartedly wish them success.
2. In unrelated news, I was saddened to read that Virgil Griffith—cryptocurrency researcher, former Integrated Information Theory researcher, and onetime contributor to Shtetl-Optimized—was arrested at LAX for having traveled to North Korea to teach the DPRK about cryptocurrency, against the admonitions of the US State Department. I didn’t know Virgil well, but I did meet him in person at least once, and I liked his essays for this blog about how, after spending years studying IIT under Giulio Tononi himself, he became disillusioned with many aspects of it and evolved to a position not far from mine (though not identical either).
   Personally, I despise the North Korean regime for the obvious reasons—I regard it as not merely evil, but cartoonishly so—and I’m mystified by Virgil’s apparently sincere belief that he could bring peace between the North and South by traveling to North Korea to give a lecture about blockchain. Yet, however world-historically naïve he may have been, his intentions appear to have been good. More pointedly—and here I’m asking not in a legal sense but in a human one—if giving aid and comfort to the DPRK is treasonous, then isn’t the current occupant of the Oval Office a million times guiltier of that particular treason (to say nothing of others)? It’s like, what does “treason” even mean anymore? In any case, I hope some plea deal or other arrangement can be worked out that won’t end Virgil’s productive career.

Just like I did last year, and the year before, I’m putting up a post to let y’all know about opportunities in our growing Quantum Information Center at UT Austin.

I’m proud to report that we’re building something pretty good here. This fall Shyam Shankar joined our Electrical and Computer Engineering (ECE) faculty to do experimental superconducting qubits, while (as I blogged in the summer) the quantum complexity theorist John Wright will join me on the CS faculty in Fall 2020. Meanwhile, Drew Potter, an expert on topological qubits, rejoined our physics faculty after a brief leave. Our weekly quantum information group meeting now regularly attracts around 30 participants—from the turnout, you wouldn’t know it’s not MIT or Caltech or Waterloo. My own group now has five postdocs and six PhD students—as well as some amazing undergrads striving to meet the bar set by Ewin Tang. Course offerings in quantum information currently include Brian La Cour’s Freshman Research Initiative, my own undergrad Intro to Quantum Information Science honors class, and graduate classes on quantum complexity theory, experimental realizations of QC, and topological matter (with more to come). We’ll also be starting an undergraduate Quantum Information Science concentration next fall.

So without further ado:

(1) If you’re interested in pursuing a PhD focused on quantum computing and information (and/or classical theoretical computer science) at UT Austin: please apply! If you want to work with me or John Wright on quantum algorithms and complexity, apply to CS (I can also supervise physics students in rare cases). Also apply to CS, of course, if you want to work with our other CS theory faculty: David Zuckerman, Dana Moshkovitz, Adam Klivans, Anna Gal, Eric Price, Brent Waters, Vijaya Ramachandran, or Greg Plaxton. If you want to work with Drew Potter on nonabelian anyons or suchlike, or with Allan MacDonald, Linda Reichl, Elaine Li, or others on many-body quantum theory, apply to physics. If you want to work with Shyam Shankar on superconducting qubits, apply to ECE. Note that the deadline for CS and physics is December 1, while the deadline for ECE is December 15.

You don’t need to ask me whether I’m on the lookout for great students: I always am! If you say on your application that you want to work with me, I’ll be sure to see it. Emailing individual faculty members is not how it works and won’t help. Admissions are extremely competitive, so I strongly encourage you to apply broadly to maximize your options.

(2) If you’re interested in a postdoc in my group, I’ll have approximately two openings starting in Fall 2020. To apply, just send me an email by January 1, 2020 with the following info:
– Your CV
– 2 or 3 of your best papers (links or PDF attachments)
– The names of two recommenders (who should email me their letters separately)

(3) If you’re on the faculty job market in quantum computing and information—well, please give me a heads-up if you’re potentially interested in Austin! Our CS, physics, and ECE departments are all open to considering additional candidates in quantum information, both junior and senior. I can’t take credit for this—it surely has to do with developments beyond my control, both at UT and beyond—but I’m happy to relay that, in the three years since I arrived in Texas, the appetite for strengthening UT’s presence in quantum information has undergone jaw-dropping growth at every level of the university.

Also, Austin-Bergstrom International Airport now has direct flights to London, Frankfurt, and (soon) Amsterdam and Paris.

Hook ’em Hadamards!

Here it is.

I’d like to offer special thanks to the editor in charge, Eleanor Barkhorn, who commissioned this piece and then went way, way beyond the call of duty to get it right—including relaxing the usual length limit to let me squeeze in amplitudes and interference, and working late into the night to fix last-minute problems. Obviously I take sole responsibility for whatever errors remain.

Of course a lot of material still ended up on the cutting room floor, including a little riff about Andrew Yang’s tweet that because of quantum supremacy, now “no code is uncrackable,” as well as Ivanka Trump’s tweet giving credit for Google’s experiment (one that Google was working toward since 2015) partly to her father’s administration.

While I’m posting: those of a more technical bent might want to check out my new short preprint with UT undergraduate Sam Gunn, where we directly study the complexity-theoretic hardness of spoofing Google’s linear cross-entropy benchmark using a classical computer. Enjoy!

Links:
Google paper in Nature
New York Times article
IBM paper and blog post responding to Google’s announcement
Boaz Barak’s new post: “Boaz’s inferior classical inferiority FAQ”
Lipton and Regan’s post
My quantum supremacy interview with the BBC (featuring some of my fewest “uhms” and “ahs” ever!)
NEW: My preprint with Sam Gunn, On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
My interview on NPR affiliate WOSU (starts around 16:30)

When Google’s quantum supremacy paper leaked a month ago—not through Google’s error, but through NASA’s—I had a hard time figuring out how to cover the news here. I had to say something; on the other hand, I wanted to avoid any detailed technical analysis of the leaked paper, because I was acutely aware that my colleagues at Google were still barred by Nature‘s embargo rules from publicly responding to anything I or others said. (I was also one of the reviewers for the Nature paper, which put additional obligations on me.)

I ended up with Scott’s Supreme Quantum Supremacy FAQ, which tried to toe this impossible line by “answering general questions about quantum supremacy, and the consequences of its still-hypothetical achievement, in light of the leak.” It wasn’t an ideal solution—for one thing, because while I still regard Google’s sampling experiment as a historic milestone for our whole field, there are some technical issues, aspects that subsequent experiments (hopefully coming soon) will need to improve. Alas, the ground rules of my FAQ forced me to avoid such issues, which caused some readers to conclude mistakenly that I didn’t think there were any.

Now, though, the Google paper has come out as Nature‘s cover story, at the same time as there have been new technical developments—most obviously, the paper from IBM (see also their blog post) saying that they could simulate the Google experiment in 2.5 days, rather than the 10,000 years that Google had estimated.

(Yesterday I was deluged by emails asking me “whether I’d seen” IBM’s paper. As a science blogger, I try to respond to stuff pretty quickly when necessary, but I don’t—can’t—respond in Twitter time.)

So now the gloves are off. No more embargo. Time to address the technical stuff under the hood—which is the purpose of this post.

I’m going to assume, from this point on, that you already understand the basics of sampling-based quantum supremacy experiments, and that I don’t need to correct beginner-level misconceptions about what the term “quantum supremacy” does and doesn’t mean (no, it doesn’t mean scalability, fault-tolerance, useful applications, breaking public-key crypto, etc. etc.). If this is not the case, you could start (e.g.) with my FAQ, or with John Preskill’s excellent Quanta commentary.

Without further ado:

(1) So what about that IBM thing? Are random quantum circuits easy to simulate classically?

OK, so let’s carefully spell out what the IBM paper says. They argue that, by commandeering the full attention of Summit at Oak Ridge National Lab, the most powerful supercomputer that currently exists on Earth—one that fills the area of two basketball courts, and that (crucially) has 250 petabytes of hard disk space—one could just barely store the entire quantum state vector of Google’s 53-qubit Sycamore chip in hard disk.  And once one had done that, one could simulate the chip in ~2.5 days, more-or-less just by updating the entire state vector by brute force, rather than the 10,000 years that Google had estimated on the basis of my and Lijie Chen’s “Schrödinger-Feynman algorithm” (which can get by with less memory).

The IBM group understandably hasn’t actually done this yet—even though IBM set it up, the world’s #1 supercomputer isn’t just sitting around waiting for jobs! But I see little reason to doubt that their analysis is basically right. I don’t know why the Google team didn’t consider how such near-astronomical hard disk space would change their calculations; probably they wish they had.

I find this to be much, much better than IBM’s initial reaction to the Google leak, which was simply to dismiss the importance of quantum supremacy as a milestone. Designing better classical simulations is precisely how IBM and others should respond to Google’s announcement, and how I said a month ago that I hoped they would respond. If we set aside the pass-the-popcorn PR war (or even if we don’t), this is how science progresses.

But does IBM’s analysis mean that “quantum supremacy” hasn’t been achieved? No, it doesn’t—at least, not under any definition of “quantum supremacy” that I’ve ever used. The Sycamore chip took about 3 minutes to generate the ~5 million samples that were needed to pass the “linear cross-entropy benchmark”—the statistical test that Google applies to the outputs of its device.

(Technical note added: Google’s samples are extremely noisy—the actual distribution being sampled from is something like 0.998U+0.002D, where U is the uniform distribution and D is the hard distribution that you want. What this means, in practice, is that you need to take a number of samples that’s large compared to 1/0.002², in order to extract a signal corresponding to D. But the good news is that Google can take that many samples in just a few minutes, since once the circuit has been loaded onto the chip, generating each sample takes only about 40 microseconds. And once you’ve done this, what hardness results we have for passing the linear cross-entropy test—to be discussed later in this post—apply basically just as well as if you’d taken a single noiseless sample.)

Anyway, you might notice that three minutes versus 2.5 days is still a quantum speedup by a factor of 1200. But even more relevant, I think, is to compare the number of “elementary operations.” Let’s generously count a FLOP (floating-point operation) as the equivalent of a quantum gate. Then by my estimate, we’re comparing ~5×10⁹ quantum gates against ~2×10²⁰ FLOPs—a quantum speedup by a factor of ~40 billion.

For me, though, the broader point is that neither party here—certainly not IBM—denies that the top-supercomputers-on-the-planet-level difficulty of classically simulating Google’s 53-qubit programmable chip really is coming from the exponential character of the quantum states in that chip, and nothing else. That’s what makes this back-and-forth fundamentally different from the previous one between D-Wave and the people who sought to simulate its devices classically. The skeptics, like me, didn’t much care what speedup over classical benchmarks there was or wasn’t today: we cared about the increase in the speedup as D-Wave upgraded its hardware, and the trouble was that we never saw a convincing case that there would be one. I’m a theoretical computer scientist, and this is what I believe: that after the constant factors have come and gone, what remains are asymptotic growth rates.

In the present case, while increasing the circuit depth won’t evade IBM’s “store everything to hard disk” strategy, increasing the number of qubits will. If Google, or someone else, upgraded from 53 to 55 qubits, that would apparently already be enough to exceed Summit’s 250-petabyte storage capacity. At 60 qubits, you’d need 33 Summits. At 70 qubits, enough Summits to fill a city … you get the idea.

From the beginning, it was clear that quantum supremacy would not be a milestone like the moon landing—something that’s achieved in a moment, and is then clear to everyone for all time. It would be more like eradicating measles: it could be achieved, then temporarily unachieved, then re-achieved. For by definition, quantum supremacy all about beating something—namely, classical computation—and the latter can, at least for a while, fight back.

As Boaz Barak put it to me, the current contest between IBM and Google is analogous to Kasparov versus Deep Blue—except with the world-historic irony that IBM is playing the role of Kasparov! In other words, Kasparov can put up a heroic struggle, during a “transitional period” that lasts a year or two, but the fundamentals of the situation are that he’s toast. If Kasparov had narrowly beaten Deep Blue in 1997, rather than narrowly losing, the whole public narrative would likely have been different (“humanity triumphs over computers after all!”). Yet as Kasparov himself well knew, the very fact that the contest was close meant that, either way, human dominance would soon end for good.

Let me leave the last word on this to friend-of-the-blog Greg Kuperberg, who graciously gave me permission to quote his comments about the IBM paper.

I’m not entirely sure how embarrassed Google should feel that they overlooked this.   I’m sure that they would have been happier to anticipate it, and happier still if they had put more qubits on their chip to defeat it.   However, it doesn’t change their real achievement.

I respect the IBM paper, even if the press along with it seems more grouchy than necessary.   I tend to believe them that the Google team did not explore all avenues when they said that their 53 qubits aren’t classically simulable.   But if this is the best rebuttal, then you should still consider how much Google and IBM still agree on this as a proof-of-concept of QC.   This is still quantum David vs classical Goliath, in the extreme.   53 qubits is in some ways still just 53 bits, only enhanced with quantum randomness.  To answer those 53 qubits, IBM would still need entire days of computer time with the world’s fastest supercomputer, a 200-petaflop machine with hundreds of thousands of processing cores and trillions of high-speed transistors.   If we can confirm that the Google chip actually meets spec, but we need this much computer power to do it, then to me that’s about as convincing as a larger quantum supremacy demonstration that humanity can no longer confirm at all.

Honestly, I’m happy to give both Google and IBM credit for helping the field of QC, even if it is the result of a strange dispute.

I should mention that, even before IBM’s announcement, Johnnie Gray, a postdoc at Imperial College, gave a talk (abstract here) at Caltech’s Institute for Quantum Information with a proposal for a different faster way to classically simulate quantum circuits like Google’s—in this case, by doing tensor network contraction more cleverly. Unlike both IBM’s proposed brute-force simulation, and the Schrödinger-Feynman algorithm that Google implemented, Gray’s algorithm (as far as we know now) would need to be repeated k times if you wanted k independent samples from the hard distribution. Partly because of this issue, Gray’s approach doesn’t currently look competitive for simulating thousands or millions of samples, but we’ll need to watch it and see what happens.

(2) Direct versus indirect verification.

The discussion of IBM’s proposed simulation brings us to a curious aspect of the Google paper—one that was already apparent when Nature sent me the paper for review back in August. Namely, Google took its supremacy experiments well past the point where even they themselves knew how to verify the results, by any classical computation that they knew how to perform feasibly (say, in less than 10,000 years).

So you might reasonably ask: if they couldn’t even verify the results, then how did they get to claim quantum speedups from those experiments? Well, they resorted to various gambits, which basically involved estimating the fidelity on quantum circuits that looked almost the same as the hard circuits, but happened to be easier to simulate classically, and then making the (totally plausible) assumption that that fidelity would be maintained on the hard circuits. Interestingly, they also cached their outputs and put them online (as part of the supplementary material to their Nature paper), in case it became feasible to verify them in the future.

Maybe you can now see where this is going. From Google’s perspective, IBM’s rainstorm comes with a big silver lining. Namely, by using Summit, hopefully it will now be possible to verify Google’s hardest (53-qubit and depth-20) sampling computations directly! This should provide an excellent test, since not even the Google group themselves would’ve known how to cheat and bias the results had they wanted to.

This whole episode has demonstrated the importance, when doing a sampling-based quantum supremacy experiment, of going deep into the regime where you can no longer classically verify the outputs, as weird as that sounds. Namely, you need to leave yourself a margin, in the likely event that the classical algorithms improve!

Having said that, I don’t mind revealing at this point that the lack of direct verification of the outputs, for the largest reported speedups, was my single biggest complaint when I reviewed Google’s Nature submission. It was because of my review that they added a paragraph explicitly pointing out that they did do direct verification for a smaller quantum speedup:

The largest circuits for which the fidelity can still be directly verified have 53 qubits and a simplified gate arrangement. Performing random circuit sampling on these at 0.8% fidelity takes one million cores 130 seconds, corresponding to a million-fold speedup of the quantum processor relative to a single core.

(An earlier version of this post misstated the numbers involved.)

(3) The asymptotic hardness of spoofing Google’s benchmark.

OK, but if Google thought that spoofing its test would take 10,000 years, using the best known classical algorithms running on the world’s top supercomputers, and it turns out instead that it could probably be done in more like 2.5 days, then how much else could’ve been missed? Will we find out next that Google’s benchmark can be classically spoofed in mere milliseconds?

Well, no one can rule that out, but we do have some reasons to think that it’s unlikely—and crucially, that even if it turned out to be true, one would just have to add 10 or 20 or 30 more qubits to make it no longer true. (We can’t be more definitive than that? Aye, such are the perils of life at a technological inflection point—and of computational complexity itself.)

The key point to understand here is that we really are talking about simulating a random quantum circuit, with no particular structure whatsoever. While such problems might have a theoretically efficient classical algorithm—i.e., one that runs in time polynomial in the number of qubits—I’d personally be much less surprised if you told me there was a polynomial-time classical algorithm for factoring. In the universe where amplitudes of random quantum circuits turn out to be efficiently computable—well, you might as well just tell me that P=PSPACE and be done with it.

Crucially, if you look at IBM’s approach to simulating quantum circuits classically, and Johnnie Gray’s approach, and Google’s approach, they could all be described as different flavors of “brute force.” That is, they all use extremely clever tricks to parallelize, shave off constant factors, make the best use of available memory, etc., but none involves any deep new mathematical insight that could roust BPP and BQP and the other complexity gods from their heavenly slumber. More concretely, none of these approaches seem to have any hope of “breaching the 2ⁿ barrier,” where n is the number of qubits in the quantum circuit to be simulated (assuming that the circuit depth is reasonably large). Mostly, they’re just trying to get down to that barrier, while taking the maximum advantage of whatever storage and connectivity and parallelism are there.

Ah, but at the end of the day, we only believe that Google’s Sycamore chip is solving a classically hard problem because of the statistical test that Google applies to its outputs: the so-called “Linear Cross-Entropy Benchmark,” which I described in Q3 of my FAQ. And even if we grant that calculating the output probabilities for a random quantum circuit is almost certainly classically hard, and sampling the output distribution of a random quantum circuit is almost certainly classically hard—still, couldn’t spoofing Google’s benchmark be classically easy?

This last question is where complexity theory can contribute something to the story. A couple weeks ago, UT undergraduate Sam Gunn and I adapted the hardness analysis from my and Lijie Chen’s 2017 paper “Complexity-Theoretic Foundations of Quantum Supremacy Experiments,” to talk directly about the classical hardness of spoofing the Linear Cross-Entropy benchmark. Our short paper about this should be on the arXiv later this week (or early next week, given that there are no arXiv updates on Friday or Saturday nights) here it is.

Briefly, Sam and I show that if you had a sub-2ⁿ classical algorithm to spoof the Linear Cross-Entropy benchmark, then you’d also have a sub-2ⁿ classical algorithm that, given as input a random quantum circuit, could estimate a specific output probability (for example, that of the all-0 string) with variance at least slightly (say, Ω(2^-3n)) better than that of the trivial estimator that just always guesses 2^-n. Or in other words: we show that spoofing Google’s benchmark is no easier than the general problem of nontrivially estimating amplitudes in random quantum circuits. Furthermore, this result automatically generalizes to the case of noisy circuits: all that the noise affects is the threshold for the Linear Cross-Entropy benchmark, and thus (indirectly) the number of samples one needs to take with the QC. Our result helps to explain why, indeed, neither IBM nor Johnnie Gray nor anyone else suggested any attack that’s specific to Google’s Linear Cross-Entropy benchmark: they all simply attack the general problem of calculating the final amplitudes.

(4) Why use Linear Cross-Entropy at all?

In the comments of my FAQ, some people wondered why Google chose the Linear Cross-Entropy benchmark specifically—especially since they’d used a different benchmark (multiplicative cross-entropy, which unlike the linear version actually is a cross-entropy) in their earlier papers. I asked John Martinis this question, and his answer was simply that linear cross-entropy had the lowest variance of any estimator they tried. Since I also like linear cross-entropy—it turns out, for example, to be convenient for the analysis of my certified randomness protocol—I’m 100% happy with their choice. Having said that, there are many other choices of benchmark that would’ve also worked fine, and with roughly the same level of theoretical justification.

(5) Controlled-Z versus iSWAP gates.

Another interesting detail from the Google paper is that, in their previous hardware, they could implement a particular 2-qubit gate called the Controlled-Z. For their quantum supremacy demonstration, on the other hand, they modified their hardware to implement a different 2-qubit gate called the iSWAP some weird combination of iSWAP and Controlled-Z; see the comments section for more. Now, this other gate has no known advantages over the Controlled-Z, for any applications like quantum simulation or Shor’s algorithm or Grover search. Why then did Google make the switch? Simply because, with certain classical simulation methods that they’d been considering, the simulation’s running time grows like 4 to the power of the number of these other gates, but only like 2 to the power of the number of Controlled-Z gates! In other words, they made this engineering choice purely and entirely to make a classical simulation of their device sweat more. This seems totally fine and entirely within the rules to me. (Alas, this choice has no effect on a proposed simulation method like IBM’s.)

(6) Gil Kalai’s objections.

Over the past month, Shtetl-Optimized regular and noted quantum computing skeptic Gil Kalai has been posting one objection to the Google experiment after another on his blog. Unlike the IBM group and many of Google’s other critics, Gil completely accepts the centrality of quantum supremacy as a goal. Indeed, he’s firmly predicted for years that quantum supremacy could never be achieved for fundamental reasons—and he agrees that the Google result, if upheld, would refute his worldview. Gil also has no dispute with the exponential classical hardness of the problem that Google is solving.

Instead, Gil—if we’re talking not about “steelmanning” his beliefs, but about what he himself actually said—has taken the position that the Google experiment must’ve been done wrong and will need to be retracted. He’s offered varying grounds for this. First he said that Google never computed the full histogram of probabilities with a smaller number of qubits (for which such an experiment is feasible), which would be an important sanity check. Except, it turns out they did do that, and it’s in their 2018 Science paper. Next he said that the experiment is invalid because the qubits have to be calibrated in a way that depends on the specific circuit to be applied. Except, this too turns out to be false: John Martinis explicitly confirmed for me that once the qubits are calibrated, you can run any circuit on them that you want. In summary, unlike the objections of the IBM group, so far I’ve found Gil’s objections to be devoid of scientific interest or merit.

Update #1: Alas, I’ll have limited availability today for answering comments, since we’ll be grading the midterm exam for my Intro to Quantum Information Science course! I’ll try to handle the backlog tomorrow (Thursday).

Update #2: Aaannd … timed to coincide with the Google paper, last night the group of Jianwei Pan and Chaoyang Lu put up a preprint on the arXiv reporting a BosonSampling experiment with 20 photons 14 photons observed out of 20 generated (the previous record had been 6 photons). At this stage of the quantum supremacy race, many had of course written off BosonSampling—or said that its importance was mostly historical, in that it inspired Google’s random circuit sampling effort.  I’m thrilled to see BosonSampling itself take such a leap; hopefully, this will eventually lead to a demonstration that BosonSampling was (is) a viable pathway to quantum supremacy as well.  And right now, with fault-tolerance still having been demonstrated in zero platforms, we need all the viable pathways we can get.  What an exciting day for the field.

You’ve seen the stories—in the Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, or elsewhere—saying that a group at Google has now achieved quantum computational supremacy with a 53-qubit superconducting device. While these stories are easy to find, I’m not going to link to them here, for the simple reason that none of them were supposed to exist yet.

As the world now knows, Google is indeed preparing a big announcement about quantum supremacy, to coincide with the publication of its research paper in a high-profile journal (which journal? you can probably narrow it down to two). This will hopefully happen within a month.

Meanwhile, though, NASA, which has some contributors to the work, inadvertently posted an outdated version of the Google paper on a public website. It was there only briefly, but long enough to make it to the Financial Times, my inbox, and millions of other places. Fact-free pontificating about what it means has predictably proliferated.

The world, it seems, is going to be denied its clean “moon landing” moment, wherein the Extended Church-Turing Thesis gets experimentally obliterated within the space of a press conference. This is going to be more like the Wright Brothers’ flight—about which rumors and half-truths leaked out in dribs and drabs between 1903 and 1908, the year Will and Orville finally agreed to do public demonstration flights. (This time around, though, it thankfully won’t take that long to clear everything up!)

I’ve known about what was in the works for a couple months now; it was excruciating not being able to blog about it. Though sworn to secrecy, I couldn’t resist dropping some hints here and there (did you catch any?)—for example, in my recent Bernays Lectures in Zürich, a lecture series whose entire structure built up to the brink of this moment.

This post is not an official announcement or confirmation of anything. Though the lightning may already be visible, the thunder belongs to the group at Google, at a time and place of its choosing.

Rather, because so much misinformation is swirling around, what I thought I’d do here, in my role as blogger and “public intellectual,” is offer Scott’s Supreme Quantum Supremacy FAQ. You know, just in case you were randomly curious about the topic of quantum supremacy, or wanted to know what the implications would be if some search engine company based in Mountain View or wherever were hypothetically to claim to have achieved quantum supremacy.

Without further ado, then:

Q1. What is quantum computational supremacy?

Often abbreviated to just “quantum supremacy,” the term refers to the use of a quantum computer to solve some well-defined set of problems that would take orders of magnitude longer to solve with any currently known algorithms running on existing classical computers—and not for incidental reasons, but for reasons of asymptotic quantum complexity. The emphasis here is on being as sure as possible that the problem really was solved quantumly and really is classically intractable, and ideally achieving the speedup soon (with the noisy, non-universal QCs of the present or very near future). If the problem is also useful for something, then so much the better, but that’s not at all necessary. The Wright Flyer and the Fermi pile weren’t useful in themselves.

Q2. If Google has indeed achieved quantum supremacy, does that mean that now “no code is uncrackable”, as Democratic presidential candidate Andrew Yang recently tweeted?

No, it doesn’t. (But I still like Yang’s candidacy.)

There are two issues here. First, the devices currently being built by Google, IBM, and others have 50-100 qubits and no error-correction. Running Shor’s algorithm to break the RSA cryptosystem would require several thousand logical qubits. With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today. I don’t think anyone is close to that, and we have no idea how long it will take.

But the second issue is that, even in a hypothetical future with scalable, error-corrected QCs, on our current understanding they’ll only be able to crack some codes, not all of them. By an unfortunate coincidence, the public-key codes that they can crack include most of what we currently use to secure the Internet: RSA, Diffie-Hellman, elliptic curve crypto, etc. But symmetric-key crypto should only be minimally affected. And there are even candidates for public-key cryptosystems (for example, based on lattices) that no one knows how to break quantumly after 20+ years of trying, and some efforts underway now to start migrating to those systems. For more, see for example my letter to Rebecca Goldstein.

Q3. What calculation is Google planning to do, or has it already done, that’s believed to be classically hard?

So, I can tell you, but I’ll feel slightly sheepish doing so. The calculation is: a “challenger” generates a random quantum circuit C (i.e., a random sequence of 1-qubit and nearest-neighbor 2-qubit gates, of depth perhaps 20, acting on a 2D grid of n = 50 to 60 qubits). The challenger then sends C to the quantum computer, and asks it apply C to the all-0 initial state, measure the result in the {0,1} basis, send back whatever n-bit string was observed, and repeat some thousands or millions of times. Finally, using its knowledge of C, the classical challenger applies a statistical test to check whether the outputs are consistent with the QC having done this.

So, this is not a problem like factoring with a single right answer. The circuit C gives rise to some probability distribution, call it D_C, over n-bit strings, and the problem is to output samples from that distribution. In fact, there will typically be 2ⁿ strings in the support of D_C—so many that, if the QC is working as expected, the same output will never be observed twice. A crucial point, though, is that the distribution D_C is not uniform. Some strings enjoy constructive interference of amplitudes and therefore have larger probabilities, while others suffer destructive interference and have smaller probabilities. And even though we’ll only see a number of samples that’s tiny compared to 2ⁿ, we can check whether the samples preferentially cluster among the strings that are predicted to be likelier, and thereby build up our confidence that something classically intractable is being done.

So, tl;dr, the quantum computer is simply asked to apply a random (but known) sequence of quantum operations—not because we intrinsically care about the result, but because we’re trying to prove that it can beat a classical computer at some well-defined task.

Q4. But if the quantum computer is just executing some random garbage circuit, whose only purpose is to be hard to simulate classically, then who cares? Isn’t this a big overhyped nothingburger?

No. As I put it the other day, it’s not an everythingburger, but it’s certainly at least a somethingburger!

It’s like, have a little respect for the immensity of what we’re talking about here, and for the terrifying engineering that’s needed to make it reality. Before quantum supremacy, by definition, the QC skeptics can all laugh to each other that, for all the billions of dollars spent over 20+ years, still no quantum computer has even once been used to solve any problem faster than your laptop could solve it, or at least not in any way that depended on its being a quantum computer. In a post-quantum-supremacy world, that’s no longer the case. A superposition involving 2⁵⁰ or 2⁶⁰ complex numbers has been computationally harnessed, using time and space resources that are minuscule compared to 2⁵⁰ or 2⁶⁰.

I keep bringing up the Wright Flyer only because the chasm between what we’re talking about, and the dismissiveness I’m seeing in some corners of the Internet, is kind of breathtaking to me. It’s like, if you believed that useful air travel was fundamentally impossible, then seeing a dinky wooden propeller plane keep itself aloft wouldn’t refute your belief … but it sure as hell shouldn’t reassure you either.

Was I right to worry, years ago, that the constant drumbeat of hype about much less significant QC milestones would wear out people’s patience, so that they’d no longer care when something newsworthy finally did happen?

Q5. Years ago, you scolded the masses for being super-excited about D-Wave, and its claims to get huge quantum speedups for optimization problems via quantum annealing. Today you scold the masses for not being super-excited about quantum supremacy. Why can’t you stay consistent?

Because my goal is not to move the “excitement level” in some uniformly preferred direction, it’s to be right! With hindsight, would you say that I was mostly right about D-Wave, even when raining on that particular parade made me unpopular in some circles? Well, I’m trying to be right about quantum supremacy too.

Q6. If quantum supremacy calculations just involve sampling from probability distributions, how do you check that they were done correctly?

Glad you asked! This is the subject of a fair amount of theory that I and others developed over the last decade. I already gave you the short version in my answer to Q3: you check by doing statistics on the samples that the QC returned, to verify that they’re preferentially clustered in the “peaks” of the chaotic probability distribution D_C. One convenient way of doing this, which Google calls the “linear cross-entropy test,” is simply to sum up Pr[C outputs s_i] over all the samples s₁,…,s_k that the QC returned, and then to declare the test a “success” if and only if the sum exceeds some threshold—say, bk/2ⁿ, for some constant b strictly between 1 and 2.

Admittedly, in order to apply this test, you need to calculate the probabilities Pr[C outputs s_i] on your classical computer—and the only known ways to calculate them require brute force and take ~2ⁿ time. Is that a showstopper? No, not if n is 50, and you’re Google and are able to handle numbers like 2⁵⁰ (although not 2¹⁰⁰⁰, which exceeds a googol, har har). By running a huge cluster of classical cores for (say) a month, you can eventually verify the outputs that your QC produced in a few seconds—while also seeing that the QC was many orders of magnitude faster. However, this does mean that sampling-based quantum supremacy experiments are almost specifically designed for ~50-qubit devices like the ones being built right now. Even with 100 qubits, we wouldn’t know how to verify the results using all the classical computing power available on earth.

(Let me stress that this issue is specific to sampling experiments like the ones that are currently being done. If Shor’s algorithm factored a 2000-digit number, it would be easy to check the result by simply multiplying the claimed factors and running a primality test on them. Likewise, if a QC were used to simulate some complicated biomolecule, you could check its results by comparing them to experiment.)

Q7. Wait. If classical computers can only check the results of a quantum supremacy experiment, in a regime where the classical computers can still simulate the experiment (albeit extremely slowly), then how do you get to claim “quantum supremacy”?

Come on. With a 53-qubit chip, it’s perfectly feasible to see a speedup by a factor of many millions, in a regime where you can still directly verify the outputs, and also to see that the speedup is growing exponentially with the number of qubits, exactly as asymptotic analysis would predict. This isn’t marginal.

Q8. Is there a mathematical proof that no fast classical algorithm could possibly spoof the results of a sampling-based quantum supremacy experiment?

Not at present. But that’s not quantum supremacy researchers’ fault! As long as theoretical computer scientists can’t even prove basic conjectures like P≠NP or P≠PSPACE, there’s no hope of ruling out a fast classical simulation unconditionally. The best we can hope for are conditional hardness results. And we have indeed managed to prove some such results—see for example the BosonSampling paper, or the Bouland et al. paper on average-case #P-hardness of calculating amplitudes in random circuits, or my paper with Lijie Chen (“Complexity-Theoretic Foundations of Quantum Supremacy Experiments”). The biggest theoretical open problem in this area, in my opinion, is to prove better conditional hardness results.

Q9. Does sampling-based quantum supremacy have any applications in itself?

When people were first thinking about this subject, it seemed pretty obvious that the answer was “no”! (I know because I was one of the people.) Recently, however, the situation has changed—for example, because of my certified randomness protocol, which shows how a sampling-based quantum supremacy experiment could almost immediately be repurposed to generate bits that can be proven to be random to a skeptical third party (under computational assumptions). This, in turn, has possible applications to proof-of-stake cryptocurrencies and other cryptographic protocols. I’m hopeful that more such applications will be discovered in the near future.

Q10. If the quantum supremacy experiments are just generating random bits, isn’t that uninteresting? Isn’t it trivial to convert qubits into random bits, just by measuring them?

The key is that a quantum supremacy experiment doesn’t generate uniform random bits. Instead, it samples from some complicated, correlated probability distribution over 50- or 60-bit strings. In my certified randomness protocol, the deviations from uniformity play a central role in how the QC convinces a classical skeptic that it really was sampling the bits randomly, rather than in some secretly deterministic way (e.g., using a pseudorandom generator).

Q11. Haven’t decades of quantum-mechanical experiments–for example, the ones that violated the Bell inequality–already demonstrated quantum supremacy?

This is purely a confusion over words. Those other experiments demonstrated other forms of “quantum supremacy”: for example, in the case of Bell inequality violations, what you could call “quantum correlational supremacy.” They did not demonstrate quantum computational supremacy, meaning doing something that’s infeasible to simulate using a classical computer (where the classical simulation has no restrictions of spatial locality or anything else of that kind). Today, when people use the phrase “quantum supremacy,” it’s generally short for quantum computational supremacy.

Q12. Even so, there are countless examples of materials and chemical reactions that are hard to classically simulate, as well as special-purpose quantum simulators (like those of Lukin’s group at Harvard). Why don’t these already count as quantum computational supremacy?

Under some people’s definitions of “quantum computational supremacy,” they do! The key difference with Google’s effort is that they have a fully programmable device—one that you can program with an arbitrary sequence of nearest-neighbor 2-qubit gates, just by sending the appropriate signals from your classical computer.

In other words, it’s no longer open to the QC skeptics to sneer that, sure, there are quantum systems that are hard to simulate classically, but that’s just because nature is hard to simulate, and you don’t get to arbitrarily redefine whatever random chemical you find in the wild to be a “computer for simulating itself.” Under any sane definition, the superconducting devices that Google, IBM, and others are now building are indeed “computers.”

Q13. Did you (Scott Aaronson) invent the concept of quantum supremacy?

No. I did play some role in developing it, which led to Sabine Hossenfelder among others generously overcrediting me for the whole idea. The term “quantum supremacy” was coined by John Preskill in 2012, though in some sense the core concept goes back to the beginnings of quantum computing itself in the early 1980s. In 1993, Bernstein and Vazirani explicitly pointed out the severe apparent tension between quantum mechanics and the Extended Church-Turing Thesis of classical computer science. Then, in 1994, the use of Shor’s algorithm to factor a huge number became the quantum supremacy experiment par excellence—albeit, one that’s still (in 2019) much too hard to perform.

The key idea of instead demonstrating quantum supremacy using a sampling problem was, as far as I know, first suggested by Barbara Terhal and David DiVincenzo, in a farsighted paper from 2002. The “modern” push for sampling-based supremacy experiments started around 2011, when Alex Arkhipov and I published our paper on BosonSampling, and (independently of us) Bremner, Jozsa, and Shepherd published their paper on the commuting Hamiltonians model. These papers showed, not only that “simple,” non-universal quantum systems can solve apparently-hard sampling problems, but also that an efficient classical algorithm for the same sampling problems would imply a collapse of the polynomial hierarchy. Arkhipov and I also made a start toward arguing that even the approximate versions of quantum sampling problems can be classically hard.

As far as I know, the idea of “Random Circuit Sampling”—that is, generating your hard sampling problem by just picking a random sequence of 2-qubit gates in (say) a superconducting architecture—originated in an email thread that I started in December 2015, which also included John Martinis, Hartmut Neven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg, and others. The thread was entitled “Hard sampling problems with 40 qubits,” and my email began “Sorry for the spam.” I then discussed some advantages and disadvantages of three options for demonstrating sampling-based quantum supremacy: (1) random circuits, (2) commuting Hamiltonians, and (3) BosonSampling. After Greg Kuperberg chimed in to support option (1), a consensus quickly formed among the participants that (1) was indeed the best option from an engineering standpoint—and that, if the theoretical analysis wasn’t yet satisfactory for (1), then that was something we could remedy.

[Update: Sergio Boixo tells me that, internally, the Google group had been considering the idea of random circuit sampling since February 2015, even before my email thread. This doesn’t surprise me: while there are lots of details that had to be worked out, the idea itself is an extremely natural one.]

After that, the Google group did a huge amount of analysis of random circuit sampling, both theoretical and numerical, while Lijie Chen and I and Bouland et al. supplied different forms of complexity-theoretic evidence for the problem’s classical hardness.

Q14. If quantum supremacy was achieved, what would it mean for the QC skeptics?

I wouldn’t want to be them right now! They could retreat to the position that of course quantum supremacy is possible (who ever claimed that it wasn’t? surely not them!), that the real issue has always been quantum error-correction. And indeed, some of them have consistently maintained that position all along. But others, including my good friend Gil Kalai, are on record, right here on this blog predicting that even quantum supremacy can never be achieved for fundamental reasons. I won’t let them wiggle out of it now.

[Update: As many of you will have seen, Gil Kalai has taken the position that the Google result won’t stand and will need to be retracted. He asked for more data: specifically, a complete histogram of the output probabilities for a smaller number of qubits. This turns out to be already available, in a Science paper from 2018.]

Q15. What’s next?

If it’s achieved quantum supremacy, then I think the Google group already has the requisite hardware to demonstrate my protocol for generating certified random bits. And that’s indeed one of the very next things they’re planning to do.

[Addendum: Also, of course, the evidence for quantum supremacy itself can be made stronger and various loopholes closed—for example, by improving the fidelity so that fewer samples need to be taken (something that Umesh Vazirani tells me he’d like to see), by having the circuit C be generated and the outputs verified by a skeptic external to Google. and simply by letting more time pass, so outsiders can have a crack at simulating the results classically. My personal guess is that the basic picture is going to stand, but just like with the first experiments that claimed to violate the Bell inequality, there’s still plenty of room to force the skeptics into a tinier corner.]

Beyond that, one obvious next milestone would be to use a programmable QC, with (say) 50-100 qubits, to do some useful quantum simulation (say, of a condensed-matter system) much faster than any known classical method could do it. A second obvious milestone would be to demonstrate the use of quantum error-correction, to keep an encoded qubit alive for longer than the underlying physical qubits remain alive. There’s no doubt that Google, IBM, and the other players will now be racing toward both of these milestones.

[Update: Steve Girvin reminds me that the Yale group has already achieved quantum error-correction “beyond the break-even point,” albeit in a bosonic system rather than superconducting qubits. So perhaps a better way to phrase the next milestone would be: achieve quantum computational supremacy and useful quantum error-correction in the same system.]

Another update: I thought this IEEE Spectrum piece gave a really nice overview of the issues.

Last update: John Preskill’s Quanta column about quantum supremacy is predictably excellent (and possibly a bit more accessible than this FAQ).

My vision is blurry right now, because yesterday I had a procedure called corneal cross-linking, intended to prevent further deterioration of my eyes as I get older. But I can see clearly enough to tap out a post with random thoughts about the world.

I’m happy that the Netanyahu era might finally be ending in Israel, after which Netanyahu will hopefully face some long-delayed justice for his eye-popping corruption. If only there were a realistic prospect of Trump facing similar justice. I wish Benny Gantz success in putting together a coalition.

I’m happy that my two least favorite candidates, Bill de Blasio and Kirsten Gillibrand, have now both dropped out of the Democratic primary. Biden, Booker, Warren, Yang—I could enthusiastically support pretty much any of them, if they looked like they had a good chance to defeat Twitler. Let’s hope.

Most importantly, I wish to register my full-throated support for the climate strikes taking place today all over the world, including here in Austin. My daughter Lily, age 6, is old enough to understand the basics of what’s happening and to worry about her future. I urge the climate strikers to keep their eyes on things that will actually make a difference (building new nuclear plants, carbon taxes, geoengineering) and ignore what won’t (banning plastic straws).

As for Greta Thunberg: she is, or is trying to be, the real-life version of the Comet King from Unsong. You can make fun of her, ask what standing or expertise she has as some random 16-year-old to lead a worldwide movement. But I suspect that this is always what it looks like when someone takes something that’s known to (almost) all, and then makes it common knowledge. If civilization makes it to the 22nd century at all, then in whatever form it still exists, I can easily imagine that it will have more statues of Greta than of MLK or Gandhi.

On a completely unrelated and much less important note, John Horgan has a post about “pluralism in math” that includes some comments by me.

Oh, and on the quantum supremacy front—I foresee some big news very soon. You know which blog to watch for more.

Last week, I had the honor of giving the annual Paul Bernays Lectures at ETH Zürich. My opening line: “as I look at the list of previous Bernays Lecturers—many of them Nobel physics laureates, Fields Medalists, etc.—I think to myself, how badly did you have to screw up this year in order to end up with me?”

Paul Bernays was the primary assistant to David Hilbert, before Bernays (being Jewish by birth) was forced out of Göttingen by the Nazis in 1933. He spent most of the rest of his career at ETH. He’s perhaps best known for the von Neumann-Bernays-Gödel set theory, and for writing (in a volume by “Hilbert and Bernays,” but actually just Bernays) arguably the first full proof of Gödel’s Second Incompleteness Theorem.

Anyway, the idea of the Paul Bernays Lectures is to rotate between Bernays’s different interests in his long, distinguished career—interests that included math, philosophy, logic, and the foundations of physics. I mentioned that, if there’s any benefit to carting me out to Switzerland for these lectures, it’s that quantum computing theory combines all of these interests. And this happens to be the moment in history right before we start finding out, directly from experiments, whether quantum computers can indeed solve certain special problems much faster.

The general theme for my three lectures was “Quantum Computing and the Fundamental Limits of Computation.” The attendance was a few hundred. My idea was to take the audience from Church and Turing in the 1930s, all the way to the quantum computational supremacy experiments that Google and others are doing now—as part of a single narrative.

If you’re interested, streaming video of the lectures is available as of today (though I haven’t watched it—let me know if the quality is OK!), as well as of course my slides. Here you go:

Lecture 1: The Church-Turing Thesis and Physics (watch streaming / PowerPoint slides) (with an intro in German by Giovanni Sommaruga, who knew Bernays, and a second intro in English by Renato Renner, who appeared on this blog here)

Abstract: Is nature computable?  What should we even mean in formulating such a question?  For generations, the identification of “computable” with “computable by a Turing machine” has been seen as either an arbitrary mathematical definition, or a philosophical or psychological claim. The rise of quantum computing and information, however, has brought a fruitful new way to look at the Church-Turing Thesis: namely, as a falsifiable empirical claim about the physical universe.  This talk seeks to examine the computability of the laws of physics from a modern standpoint—one that fully incorporates the insights of quantum mechanics, quantum field theory, quantum gravity, and cosmology.  We’ll critically assess ‘hypercomputing’ proposals involving (for example) relativistic time dilation, black holes, closed timelike curves, and exotic cosmologies, and will make a 21st-century case for the physical Church-Turing Thesis.

Lecture 2: The Limits of Efficient Computation (watch streaming / PowerPoint slides)

Abstract: Computer scientists care about what’s computable not only in principle, but within the resource constraints of the physical universe.  Closely related, which types of problems are solvable using a number of steps that scales reasonably (say, polynomially) with the problem size?  This lecture will examine whether the notorious NP-complete problems, like the Traveling Salesman Problem, are efficiently solvable using the resources of the physical world.  We’ll start with P=?NP problem of classical computer science—its meaning, history, and current status.  We’ll then discuss quantum computers: how they work, how they can sometimes yield exponential speedups over classical computers, and why many believe that not even they will do so for the NP-complete problems.  Finally, we’ll critically assess proposals that would use exotic physics to go even beyond quantum computers, in terms of what they would render computable in polynomial time.

Lecture 3: The Quest for Quantum Computational Supremacy (watch streaming / PowerPoint slides)

Abstract: Can useful quantum computers be built in our world?  This talk will discuss the current status of the large efforts currently underway at Google, IBM, and many other places to build noisy quantum devices, with 50-100 qubits, that can clearly outperform classical computers at least on some specialized tasks — a milestone that’s been given the unfortunate name of “quantum supremacy.”  We’ll survey recent theoretical work (on BosonSampling, random circuit sampling, and more) that aims to tell us: which problems should we give these devices, that we’re as confident as possible are hard for classical computers? And how should we check whether the devices indeed solved them?  We’ll end by discussing a new protocol, for generating certified random bits, that can be implemented almost as soon as quantum supremacy itself is achieved, and which might therefore become the first application of quantum computing to be realized.

Finally, thanks so much to Giovanni Sommaruga and everyone else at ETH for arranging a fantastic visit.

For those who haven’t yet seen it, Erica Klarreich has a wonderful article in Quanta on Hao Huang’s proof of the Sensitivity Conjecture. This is how good popular writing about math can be.

Klarreich quotes my line from this blog, “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.” However, even if God doesn’t know a simpler proof, that of course doesn’t rule out the possibility that Don Knuth does! And indeed, a couple days ago Knuth posted his own variant of Huang’s proof on his homepage—in Knuth’s words, fleshing out the argument that Shalev Ben-David previously posted on this blog—and then left a comment about it here, the first comment by Knuth that I know about on this blog or any other blog. I’m honored—although as for whether the variants that avoid the Cauchy Interlacing Theorem are actually “simpler,” I guess I’ll leave that between Huang, Ben-David, Knuth, and God.

In Communications of the ACM, Samuel Greengard has a good, detailed article on Ewin Tang and her dequantization of the quantum recommendation systems algorithm. One warning (with thanks to commenter Ted): the sentence “The only known provable separation theorem between quantum and classical is sqrt(n) vs. n” is mistaken, though it gestures in the direction of a truth. In the black-box setting, we can rigorously prove all sorts of separations: sqrt(n) vs. n (for Grover search), exponential (for period-finding), and more. In the non-black-box setting, we can’t prove any such separations at all.

Last week I returned to the US from the FQXi meeting in the Tuscan countryside. This year’s theme was “Mind Matters: Intelligence and Agency in the Physical World.” I gave a talk entitled “The Search for Physical Correlates of Consciousness: Lessons from the Failure of Integrated Information Theory” (PowerPoint slides here), which reprised my blog posts critical of IIT from five years ago. There were thought-provoking talks by many others who might be known to readers of this blog, including Sean Carroll, David Chalmers, Max Tegmark, Seth Lloyd, Carlo Rovelli, Karl Friston … you can see the full schedule here. Apparently video of the talks is not available yet but will be soon.

Let me close this post by sharing two important new insights about quantum mechanics that emerged from my conversations at the FQXi meeting:

(1) In Hilbert space, no one can hear you scream. Unless, that is, you scream the exact same way everywhere, or unless you split into separate copies, one for each different way of screaming.

(2) It’s true that, as a matter of logic, the Schrödinger equation does not imply the Born Rule. Having said that, if the Schrödinger equation were leading a rally, and the crowd started a chant of “BORN RULE! BORN RULE! BORN RULE!”—the Schrödinger equation would just smile and wait 13 seconds for the chant to die down before continuing.

I’m delighted to announce that quantum computing theorist John Wright will be joining the computer science faculty at UT Austin in Fall 2020, after he finishes a one-year postdoc at Caltech.

John made an appearance on this blog a few months ago, when I wrote about the new breakthrough by him and Anand Natarajan: namely, that MIP* (multi-prover interactive proofs with entangled provers) contains NEEXP (nondeterministic double-exponential time). Previously, MIP* had only been known to contain NEXP (nondeterministic single exponential time). So, this is an exponential expansion in the power of entangled provers over what was previously known and believed, and the first proof that entanglement actually increases the power of multi-prover protocols, rather than decreasing it (as it could’ve done a priori). Even more strikingly, there seems to be no natural stopping point: MIP* might soon swallow up arbitrary towers of exponentials or even the halting problem (!). For more, see for example this Quanta article, or this post by Thomas Vidick, or this short story [sic] by Henry Yuen.

John grew up in Texas, so he’s no stranger to BBQ brisket or scorching weather. He did his undergrad in computer science at UT Austin—my colleagues remember him as a star—and then completed his PhD with Ryan O’Donnell at Carnegie Mellon, followed by a postdoc at MIT. Besides the work on MIP*, John is also well-known for his 2015 work with O’Donnell pinning down the sample complexity of quantum state tomography. Their important result, a version of which was independently obtained by Haah et al., says that if you want to learn an unknown d-dimensional quantum mixed state ρ to a reasonable precision, then ~d² copies of ρ are both necessary and sufficient. This solved a problem that had personally interested me, and already plays a role in, e.g., my work on shadow tomography and gentle measurements.

Our little quantum information center at UT Austin is growing rapidly. Shyam Shankar, a superconducting qubits guy who previously worked in Michel Devoret’s group at Yale, will also be joining UT’s Electrical and Computer Engineering department this fall. I’ll have two new postdocs—Andrea Rocchetto and Yosi Atia—as well as new PhD students. We’ll continue recruiting this coming year, with potential opportunities for students, postdocs, faculty, and research scientists across the CS, physics, and ECE departments as well as the Texas Advanced Computing Center (TACC). I hope you’ll consider applying to join us.

With no evaluative judgment attached, I can honestly say that this is an unprecedented time for quantum computing as a field. Where once faculty applicants struggled to make a case for quantum computing (physics departments: “but isn’t this really CS?” / CS departments: “isn’t it really physics?” / everyone: “couldn’t this whole QC thing, like, all blow over in a year?”), today departments are vying with each other and with industry players and startups to recruit talented people. In such an environment, we’re fortunate to be doing as well as we are. We hope to continue to expand.

Meanwhile, this was an unprecedented year for CS hiring at UT Austin more generally. John Wright is one of at least four new faculty (probably more) who will be joining us. It’s a good time to be in CS.

A huge welcome to John, and hook ’em Hadamards!

(And for US readers: have a great 4^th! Though how could any fireworks match the proof of the Sensitivity Conjecture?)