Archive for the ‘Announcements’ Category

Stop emailing my utexas address

Tuesday, February 23rd, 2021

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

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

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

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

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

Sufficiently amusing that I had no choice

Thursday, January 21st, 2021

A day to celebrate

Wednesday, January 20th, 2021

The reason I’m celebrating is presumably obvious to all: today is my daughter Lily’s 8th birthday! (She had a tiny Star Wars-themed party, dressed in her Rey costume.)

A second reason I’m celebrating yesterday: I began teaching (via Zoom, of course) the latest iteration of my graduate course on Quantum Complexity Theory!

A third reason: I’m now scheduled to get my first covid vaccine shot on Monday! (Texas is working through its “Phase 1b,” which includes both the over-65 and those with underlying conditions—in my case, mild type-2 diabetes.) I’d encourage everyone to do as I did: don’t lie to jump the line, but don’t sacrifice your place either. Just follow the stated rules and get vaccinated the first microsecond you can, and urge all your friends and loved ones to do the same. A crush of demand is actually good if it encourages the providers to expand their hours (they’re taking off weekends! they took off MLK Day!) and not to waste a single dose.

Anyway, people can use this thread to talk about whatever they like, but one thing that would interest me especially is readers’ experiences with vaccination: if you’ve gotten one by now, how hard did you have to look for an appointment, how orderly or chaotic was the process where you live, and what advice can you offer?

Incidentally, to the several commenters on this blog who expressed absolute certainty (as recently as yesterday) that Trump would reverse the election result and be inaugurated instead of Biden, and who confidently accused the rest of us of living in a manufactured media bubble that prevented them from seeing that: I respect that, whatever else is said about you, no one can ever again accuse you of being fair-weather friends!

Congratulations to the new President! There are difficult months ahead, but today the arc of the universe bent slightly toward sanity and goodness.

Update (Jan 21): WOOHOO! Yet another reason to celebrate: Scott Alexander is finally back in business, now blogging at Astral Codex Ten on Substack.

Happy Chanukah / Vaccine Approval Day!

Friday, December 11th, 2020
  1. Inspired by my survey article, John Pavlus has now published an article on Busy Beaver for Quanta magazine.
  2. This week, I flitted back and forth between two virtual conferences: the Institute for Advanced Study’s Online Workshop on Qubits and Black Holes (which I co-organized with Juan Maldacena and Mark Van Raamsdonk), and Q2B (Quantum 2 Business) 2020, organized by QC Ware, for which I did my now-annual Ask-Me-Anything session. It was an interesting experience, switching between Euclidean path integrals and replica wormholes that I barely understood, and corporate pitches for near-term quantum computing that I … well, did understand! Anyway, happy to discuss either conference in the comments.
  3. For anyone interested in the new Chinese quantum supremacy claim based on Gaussian BosonSampling—the story has developing rapidly all week, with multiple groups trying to understand the classical difficulty of simulating the experiment. I’ll plan to write a followup post soon!
  4. The Complexity Zoo has now officially moved from the University of Waterloo to complexityzoo.net, hosted by the LessWrong folks! Thanks so much to Oliver Habryka for setting this up. Update (Dec. 12): Alas, complexityzoo.com no longer works if you use https. I don’t know how to fix it—the Bluehost control panel provides no options—and I’m not at a point in life where I can deal again with Bluehost SSL certificate hell. (How does everyone else deal with this shit? That’s the one part I don’t understand.) So, for now, you’ll need to update your bookmarks to complexityzoo.net.
  5. In return for his help with Zoo, Oliver asked me to help publicize a handsome $29 five-book set, “A Map that Reflects the Territory,” containing a selection of the best essays from LessWrong, including multiple essays by the much-missed Scott Alexander, and an essay on common knowledge inspired by my own Common Knowledge and Aumann’s Agreement Theorem. (See also the FAQ.) If you know any LW fans, I can think of few better gifts to go under their Christmas tree or secular rationalist equivalent.

Quantum supremacy, now with BosonSampling

Thursday, December 3rd, 2020

Update (12/5): The Google team, along with Gil Kalai, have raised questions about whether the results of the new BosonSampling experiment might be easier to spoof classically than the USTC team thought they were, because of a crucial difference between BosonSampling and qubit-based random circuit sampling. Namely, with random circuit sampling, the marginal distribution over any k output qubits (for small k) is exponentially close to the uniform distribution. With BosonSampling, by contrast, the marginal distribution over k output modes is distinguishable from uniform, as Arkhipov and I noted in a 2013 followup paper. On the one hand, these easily-detected nonuniformities provide a quick, useful sanity check for whether BosonSampling is being done correctly. On the other hand, they might also give classical spoofing algorithms more of a toehold. The question is whether, by spoofing the k-mode marginals, a classical algorithm could also achieve scores on the relevant “HOG” (Heavy Output Generation) benchmark that are comparable to what the USTC team reported.

One way or the other, this question should be resolvable by looking at the data that’s already been collected, and we’re trying now to get to the bottom of it. And having failed to flag this potential issue when I reviewed the paper, I felt a moral obligation at least to let my readers know about it as soon as I did. If nothing else, this is an answer to those who claim this stuff is all obvious. Please pardon the science underway!


A group led by Jianwei Pan and Chao-Yang Lu, based mainly at USTC in Hefei, China, announced today that it achieved BosonSampling with 40-70 detected photons—up to and beyond the limit where a classical supercomputer could feasibly verify the results. (Technically, they achieved a variant called Gaussian BosonSampling: a generalization of what I called Scattershot BosonSampling in a 2013 post on this blog.)

For more, see also Emily Conover’s piece in Science News, or Daniel Garisto’s in Scientific American, both of which I consulted on. (Full disclosure: I was one of the reviewers for the Pan group’s Science paper, and will be writing the Perspective article to accompany it.)

The new result follows the announcement of 14-photon BosonSampling by the same group a year ago. It represents the second time quantum supremacy has been reported, following Google’s celebrated announcement from last year, and the first time it’s been done using photonics rather than superconducting qubits.

As the co-inventor of BosonSampling (with Alex Arkhipov), obviously I’m gratified about this.

For anyone who regards it as boring or obvious, here and here is Gil Kalai, on this blog, telling me why BosonSampling would never scale beyond 8-10 photons. (He wrote that, if aliens forced us to try, then much like with the Ramsey number R(6,6), our only hope would be to attack the aliens.) Here’s Kalai making a similar prediction, on the impossibility of quantum supremacy by BosonSampling or any other means, in his plenary address to the International Congress of Mathematicians two years ago.

Even if we set aside the quantum computing skeptics, many colleagues told me they thought experimental BosonSampling was a dead end, because of photon losses and the staggering difficulty of synchronizing 50-100 single-photon sources. They said that a convincing demonstration of quantum supremacy would have to await the arrival of quantum fault-tolerance—or at any rate, some hardware platform more robust than photonics. I always agreed that they might be right. Furthermore, even if 50-photon BosonSampling was possible, after Google reached the supremacy milestone first with superconducting qubits, it wasn’t clear if anyone would still bother. Even when I learned a year ago about the USTC group’s intention to go for it, I was skeptical, figuring I’d believe it when I saw it.

Obviously the new result isn’t dispositive. Nevertheless, as someone whose intellectual origins are close to pure math, it’s strange and exciting to find myself in a field where, once in a while, the world itself gets to weigh in on a theoretical disagreement.

Since excitement is best when paired with accurate understanding, please help yourself to the following FAQ, which I might add more to over the next couple days.

What is BosonSampling? You must be new here! Briefly, it’s a proposal for achieving quantum supremacy by simply passing identical, non-interacting photons through an array of beamsplitters, and then measuring where they end up. For more: in increasing order of difficulty, here’s an MIT News article from back in 2011, here’s the Wikipedia page, here are my PowerPoint slides, here are my lecture notes from Rio de Janeiro, and here’s my original paper with Arkhipov.

What is quantum supremacy? Roughly, the use of a programmable or configurable quantum computer to solve some well-defined computational problem much faster than we know how to solve it with any existing classical computer. “Quantum supremacy,” a term coined by John Preskill in 2012, does not mean useful QC, or scalable QC, or fault-tolerant QC, all of which remain outstanding challenges. For more, see my Supreme Quantum Supremacy FAQ, or (e.g.) my recent Lytle Lecture for the University of Washington.

If Google already announced quantum supremacy a year ago, what’s the point of this new experiment? To me, at least, quantum supremacy seems important enough to do at least twice! Also, as I said, this represents the first demonstration that quantum supremacy is possible via photonics. Finally, as the authors point out, the new experiment has one big technical advantage compared to Google’s: namely, many more possible output states (~1030 of them, rather than a mere ~9 quadrillion). This makes it infeasible to calculate the whole probability distribution over outputs and store it on a gigantic hard disk (after which one could easily generate as many samples as one wanted), which is what IBM proposed doing in its response to Google’s announcement.

Is BosonSampling a form of universal quantum computing? No, we don’t even think it can simulate universal classical computing! It’s designed for exactly one task: namely, demonstrating quantum supremacy and refuting Gil Kalai. It might have some other applications besides that, but if so, they’ll be icing on the cake. This is in contrast to Google’s Sycamore processor, which in principle is a universal quantum computer, just with a severe limit on the number of qubits (53) and how many layers of gates one can apply to them (about 20).

Is BosonSampling at least a step toward universal quantum computing? I think so! In 2000, Knill, Laflamme, and Milburn (KLM) famously showed that pure, non-interacting photons, passing through a network of beamsplitters, are capable of universal QC, provided we assume one extra thing: namely, the ability to measure the photons at intermediate times, and change which beamsplitters to apply to the remaining photons depending on the outcome. In other words, “BosonSampling plus adaptive measurements equals universality.” Basically, KLM is the holy grail that experimental optics groups around the world have been working toward for 20 years, with BosonSampling just a more achievable pit stop along the way.

Are there any applications of BosonSampling? We don’t know yet. There are proposals in the literature to apply BosonSampling to vibronic spectra in quantum chemistry, finding dense subgraphs, and other problems, but I’m not yet sure whether these proposals will yield real speedups over the best we can do with classical computers, for a task of practical interest that involves estimating specific numbers (as opposed to sampling tasks, where BosonSampling almost certainly does yield exponential speedups, but which are rarely the thing practitioners directly care about). [See this comment for further discussion of the issues regarding dense subgraphs.] In a completely different direction, one could try to use BosonSampling to generate cryptographically certified random bits, along the lines of my proposal from 2018, much like one could with qubit-based quantum circuits.

How hard is it to simulate BosonSampling on a classical computer? As far as we know today, the difficulty of simulating a “generic” BosonSampling experiment increases roughly like 2n, where n is the number of detected photons. It might be easier than that, particularly when noise and imperfections are taken into account; and at any rate it might be easier to spoof the statistical tests that one applies to verify the outputs. I and others managed to give some theoretical evidence against those possibilities, but just like with Google’s experiment, it’s conceivable that some future breakthrough will change the outlook and remove the case for quantum supremacy.

Do you have any amusing stories? When I refereed the Science paper, I asked why the authors directly verified the results of their experiment only for up to 26-30 photons, relying on plausible extrapolations beyond that. While directly verifying the results of n-photon BosonSampling takes ~2n time for any known classical algorithm, I said, surely it should be possible with existing computers to go up to n=40 or n=50? A couple weeks later, the authors responded, saying that they’d now verified their results up to n=40, but it burned $400,000 worth of supercomputer time so they decided to stop there. This was by far the most expensive referee report I ever wrote!

Also: when Covid first started, and facemasks were plentiful in China but almost impossible to get in the US, Chao-Yang Lu, one of the leaders of the new work and my sometime correspondent on the theory of BosonSampling, decided to mail me a box of 200 masks (I didn’t ask for it). I don’t think that influenced my later review, but it was appreciated nonetheless.

Huge congratulations to the whole team for their accomplishment!

Happy Thanksgiving Y’All!

Wednesday, November 25th, 2020

While a lot of pain is still ahead, this year I’m thankful that a dark chapter in American history might be finally drawing to a close. I’m thankful that the mRNA vaccines actually work. I’m thankful that my family has remained safe, and I’m thankful for all the essential workers who’ve kept our civilization running.

A few things:

  1. Friend-of-the-blog Jelani Nelson asked me to advertise an important questionnaire for theoretical computer scientists, about what the future of STOC and FOCS should look like (for example, should they become all virtual?). It only takes 2 or 3 minutes to fill out (I just did).
  2. Here’s a podcast that I recently did with UT Austin undergraduate Dwarkesh Patel. (As usual, I recommend 2x speed to compensate for my verbal tics.)
  3. Feel free to use the comments on this post to talk about recent progress in quantum computing or computational complexity! Like, I dunno, a (sub)exponential black-box speedup for the adiabatic algorithm, or anti-concentration for log-depth random quantum circuits, or an improved shadow tomography procedure, or a quantum algorithm for nonlinear differential equations, or a barrier to proving strong 3-party parallel repetition, or equivalence of one-way functions and time-bounded Kolmogorov complexity, or turning any hard-on-average NP problem into one that’s guaranteed to have solutions.
  4. It’s funny how quantum computing, P vs. NP, and so forth can come to feel like just an utterly mundane day job, not something anyone outside a small circle could possibly want to talk about while the fate of civilization hangs in the balance. Sometimes it takes my readers to remind me that not only are these topics what brought most of you here in the first place, they’re also awesome! So, I’ll mark that down as one more thing to be thankful for.

Annual post: Come join UT Austin’s Quantum Information Center!

Wednesday, November 18th, 2020

Hook ’em Hadamards!

If you’re a prospective PhD student: Apply here for the CS department (the deadline this year is December 15th), here for the physics department (the deadline is December 1st), or here for the ECE department (the deadline is 15th). GREs are not required this year because of covid. If you apply to CS and specify that you want to work with me, I’ll be sure to see your application. If you apply to physics or ECE, I won’t see your application, but once you arrive, I can sometimes supervise or co-supervise PhD students in other departments (or, of course, serve on their committees). In any case, everyone in the UT community is extremely welcome at our quantum information group meetings (which are now on Zoom, naturally, but depending on vaccine distribution, hopefully won’t be by the time you arrive!). Emailing me won’t make a difference. Admissions are very competitive, so apply broadly to maximize your chances.

If you’re a prospective postdoctoral fellow: By January 1, 2021, please email me a cover letter, your CV, and two or three of your best papers (links or attachments). Please also ask two recommenders to email me their letters by January 1. While my own work tends toward computational complexity, I’m open to all parts of theoretical quantum computing and information.

If you’re a prospective faculty member: Yes, faculty searches are still happening despite covid! Go here to apply for an opening in the CS department (which, in quantum computing, currently includes me and MIP*=RE superstar John Wright), or here to apply to the physics department (which, in quantum computing, currently includes Drew Potter, along with a world-class condensed matter group).

The Complexity Zoo needs a new home

Thursday, November 12th, 2020

Update (Nov. 14): I now have a deluge of serious hosting offers—thank you so much, everyone! No need for more.


Since I’m now feeling better that the first authoritarian coup attempt in US history will probably sort itself out OK, here’s a real problem:

Nearly a score years ago, I created the Complexity Zoo, a procrastination project turned encyclopedia of complexity classes. Nearly half a score years ago, the Zoo moved to my former employer, the Institute for Quantum Computing in Waterloo, Canada, which graciously hosted it ever since. Alas, IQC has decided that it can no longer do so. The reason is new regulations in Ontario about the accessibility of websites, which the Zoo might be out of compliance with. My students and I were willing to look into what was needed—like, does the polynomial hierarchy need ramps between its levels or something? The best would be if we heard from actual blind or other disabled complexity enthusiasts about how we could improve their experience, rather than trying to parse bureaucratese from the Ontario government. But IQC informed us that in any case, they can’t deal with the potential liability and their decision is final. I thank them for hosting the Zoo for eight years.

Now I’m looking for a volunteer for a new host. The Zoo runs on the MediaWiki platform, which doesn’t work with my own hosting provider (Bluehost) but is apparently easy to set up if you, unlike me, are the kind of person who can do such things. The IQC folks kindly offered to help with the transfer; I and my students can help as well. It’s a small site with modest traffic. The main things I need are just assurances that you can host the site for a long time (“forever” or thereabouts), and that you or someone else in your organization will be reachable if the site goes down or if there are other problems. I own the complexityzoo.com domain and can redirect from there.

In return, you’ll get the immense prestige of hosting such a storied resource for theoretical computer science … plus free publicity for your cause or organization on Shtetl-Optimized, and the eternal gratitude of thousands of my readers.

Of course, if you’re into complexity theory, and you want to update or improve the Zoo while you’re at it, then so much the awesomer! It could use some updates, badly. But you don’t even need to know P from NP.

If you’re interested, leave a comment or shoot me an email. Thanks!!

Unrelated Announcement: I’ll once again be doing an Ask-Me-Anything session at the Q2B (“Quantum to Business”) conference, December 8-10. Other speakers include Umesh Vazirani, John Preskill, Jennifer Ouellette, Eric Schmidt, and many others. Since the conference will of course be virtual this year, registration is a lot cheaper than in previous years. Check it out! (Full disclosure: Q2B is organized by QC Ware, Inc., for which I’m a scientific advisor.)

On the removal of a hideous growth

Friday, November 6th, 2020

The title of this post is not an allegory.

At 10am this morning, I had a previously-scheduled appointment with an oral surgeon to remove a large, hideous, occasionally painful growth on the inside of my lower lip. (I’d delayed getting it looked at for several months because of covid, but I no longer could.)

So right now I’m laying in bed at home, with gauze on my lips, dazed, hopped up on painkillers. I regret that things ever got to the point where this was needed. I believe, intellectually, that the surgeon executed about as competently as anyone could ask. But I still wish, if we’re being honest, that there hadn’t been quite this much pain in the surgery or in the recovery from it.

Again intellectually, I know that there’s still lots more pain in the days ahead. I’m not sure that whatever it was won’t just quickly grow back. And yet, I couldn’t be feeling more joy through my whole body with every one of these words that I write. At last I can honestly tell myself: the growth is gone.

In a world like this one, take every ally you can get

Wednesday, September 16th, 2020

Update (Sep. 17): Several people, here and elsewhere, wrote to tell me that while they completely agreed with my strategic and moral stance in this post, they think that it’s the ads of Republican Voters Against Trump, rather than the Lincoln Project, that have been most effective in changing Trump supporters’ minds. So please consider donating to RVAT instead or in addition! In fact, what the hell, I’ll match donations to RVAT up to $1000.


For the past few months, I’ve alternated between periods of debilitating depression and (thankfully) longer stretches when I’m more-or-less able to work. Triggers for my depressive episodes include reading social media, watching my 7-year daughter struggle with prolonged isolation, and (especially) contemplating the ongoing apocalypse in the American West, the hundreds of thousands of pointless covid deaths, and an election in 48 days that if I didn’t know such things were impossible in America would seem likely to produce a terrifying standoff as a despot and millions of his armed loyalists refuse to cede control. Meanwhile, catalysts for my relatively functional periods have included teaching my undergrad quantum information class, Zoom calls with my students, life on Venus?!? (my guess is no, but almost entirely due to priors), learning new math (fulfilling a decades-old goal, I’m finally working my way through Paul Cohen’s celebrated proof of the independence of the Continuum Hypothesis—more about that later!).

Of course, when you feel crushed by the weight of the world’s horribleness, it improves your mood to be able even just to prick the horribleness with a pin. So I was gratified that, in response to a previous post, Shtetl-Optimized readers contributed at least $3,000, the first $2,000 of which I matched, mostly to the Biden-Harris campaign but a little to the Lincoln Project.

Alas, a commenter was unhappy with the latter:

Lincoln Project? Really? … Pushing the Overton window rightward during a worldwide fascist dawn isn’t good. I have trouble understanding why even extremely smart people have trouble with this sort of thing.

Since this is actually important, I’d like to spend the rest of this post responding to it.

For me it’s simple.

What’s the goal right now? To defeat Trump. In the US right now, that’s the prerequisite to every other sane political goal.

What will it take to achieve that goal? Turnout, energizing the base, defending the election process … but also, if possible, persuading a sliver of Trump supporters in swing states to switch sides, or at least vote third party or abstain.

Who is actually effective at that goal? Well, no one knows for sure. But while I thought the Biden campaign had some semi-decent ads, the Lincoln Project’s best stuff seems better to me, just savagely good.

Why are they effective? The answer seems obvious: for the same reason why a jilted ex is a more dangerous foe than a stranger. If anyone understood how to deprogram a Republican from the Trump cult, who would it be: Alexandria Ocasio-Cortez, or a fellow Republican who successfully broke from the cult?

Do I agree with the Lincoln Republicans about most of the “normal” issues that Americans once argued about? Not at all. Do I hold them, in part, morally responsible for creating the preconditions to the current nightmare? Certainly.

And should any of that cause me to boycott them? Not in my moral universe. If Churchill and FDR could team up with Stalin, then surely we in the Resistance can temporarily ally ourselves with the rare Republicans who chose their stated principles over power when tested—their very rarity attesting to the nontriviality of their choice.

To my mind, turning one’s back on would-be allies, in a conflict whose stakes obviously overshadow what’s bad about those allies, is simultaneously one of the dumbest and the ugliest things that human beings can do. It abandons reason for moral purity and ends up achieving neither.