{"id":7972,"date":"2024-05-10T08:24:49","date_gmt":"2024-05-10T13:24:49","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=7972"},"modified":"2024-05-10T21:37:40","modified_gmt":"2024-05-11T02:37:40","slug":"umeshfest","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=7972","title":{"rendered":"UmeshFest"},"content":{"rendered":"\n

Unrelated Announcements:<\/mark><\/strong> See here<\/a> for a long interview with me in The Texas Orator<\/em>, covering the usual stuff (quantum computing, complexity theory, AI safety). And see here<\/a> for a podcast with me and Spencer Greenberg about a similar mix of topics.<\/p>\n\n\n\n

\n\n\n\n

A couple weeks ago, I helped organize UmeshFest: Don’t Miss This Flight<\/a>, a workshop at UC Berkeley’s Simons Institute to celebrate the 26<\/sup>th birthday of my former PhD adviser Umesh Vazirani<\/a>. Peter Shor, John Preskill, Manuel Blum, Madhu Sudan, Sanjeev Arora, and dozens of other luminaries of quantum and classical computation were on hand to help tell the story of quantum computing theory and Umesh’s central role in it. There was also constant roasting of Umesh—of his life lessons from the squash court, his last-minute organizational changes and phone calls at random hours. I was delighted to find that my old coinage of “Umeshisms”<\/a> was simply standard usage among the attendees.<\/p>\n\n\n\n

\n\n\n\n

At Berkeley, many things were as I remembered them—my favorite Thai eatery, the bubble tea, the Campanile—but not everything<\/em> was the same. Here I am in front of Berkeley’s Gaza encampment, a.k.a. its “Anti Zionism Zone” or what was formerly Sproul Plaza (zoom into the chalk):<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

I felt a need to walk through the Anti Zionism Zone day after day (albeit unassumingly, neither draped in an Israeli flag nor looking to start an argument with anyone), for more-or-less the same reasons why the US regularly sends aircraft carriers through the Strait of Taiwan.<\/p>\n\n\n\n

\n\n\n\n

Back in the more sheltered environment of the Simons Institute, it was great to be among friends, some of whom I hadn’t seen since before Covid. Andris Ambainis<\/a> and I worked together for a bit on an open problem in quantum query complexity, for old times’ sake (we haven’t solved it yet).<\/p>\n\n\n\n

And then there were talks! I thought I’d share my own talk, which was entitled The Story of BQP<\/a> (Bounded-Error Quantum Polynomial-Time). Here<\/a> are the PowerPoint slides, but I’ll also share screen-grabs for those of you who constantly complain that you can’t open PPTX files.<\/p>\n\n\n\n

I was particularly proud of the design of my title slide:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Moving on:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The class BQP\/qpoly<\/a>, I should explain, is all about an advisor who’s all-wise and perfectly benevolent, but who doesn’t have a lot of time to meet with his students, so he simply doles out the same generic advice to all of them, regardless of their thesis problem x.<\/p>\n\n\n\n

I then displayed my infamous “Umeshisms” blog post<\/a> from 2005—one of the first posts in the history of this blog: <\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

As I explained, now that I hang out with the rationalist and AI safety communities, which are also<\/em> headquartered in Berkeley, I’ve learned that my “Umeshisms” post somehow took on a life of its own. Once, when dining at one of the rationalists’ polyamorous Berkeley group houses, I said this has been lovely but I’ll now need to leave, to visit my PhD former adviser Umesh Vazirani. “You mean the<\/em> Umesh?!” the rationalists excitedly exclaimed. “Of Umeshisms? If you’ve never missed a flight?”<\/p>\n\n\n\n

But moving on:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

(Note that by “QBPP,” Bethiaume and Brassard meant what we now call BQP.)<\/p>\n\n\n\n

Feynman and Deutsch asked exactly the right question—does simulating quantum mechanics on a classical computer inherently produce an exponential slowdown, or not?—but they lacked most of the tools to start formally investigating the question. A factor-of-two quantum speedup for the XOR function could be dismissed as unimpressive, while a much greater quantum speedup for the “constant vs. balanced” problem could be dismissed as a win against only deterministic<\/em> classical algorithms, rather than randomized algorithms. Deutsch-Jozsa<\/a> may have been the first time that an apparent quantum speedup faltered in an honest comparison against classical algorithms. It certainly wasn’t the last!<\/p>\n\n\n\n

Ah, but this is where Bernstein and Vazirani<\/a> enter the scene.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Bernstein and Vazirani didn’t merely define BQP<\/a>, which remains the central object of study in quantum complexity theory. They also established its most basic properties:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

And, at least in the black-box model, Bernstein and Vazirani gave the first impressive quantum speedup for a classical problem that survived in a fair comparison against the best classical algorithm:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

The Recursive Bernstein-Vazirani problem, also called Recursive Fourier Sampling, is constructed as a “tree” of instances of the Bernstein-Vazirani problem, where to query the Boolean function at any given level, you need to solve a Bernstein-Vazirani problem for a Boolean function at the level below it, and then run the secret string s through a fixed Boolean function g. For more, see my old paper Quantum Lower Bound for Recursive Fourier Sampling<\/a>.<\/p>\n\n\n\n

Each Bernstein-Vazirani instance has classical query complexity n and quantum query complexity 1. So, if the tree of instances has depth d, then overall the classical query complexity is nd<\/sup>, while the quantum query complexity is only 2d<\/sup>. Where did the 2 come from? From the need to uncompute<\/em> the secret strings s at each level, to enable quantum interference at the next level up—thereby forcing us to run the algorithm twice. A key insight.<\/p>\n\n\n\n

The Recursive Fourier Sampling separation set the stage for Simon’s algorithm<\/a>, which gave a more impressive speedup in the black-box model, and thence for the famous Shor’s algorithm<\/a> for factoring and discrete log:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

But Umesh wasn’t done establishing the most fundamental properties of BQP! There’s also the seminal 1994 paper by Bennett, Bernstein, Brassard, and Vazirani<\/a>:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

In light of the BV and BBBV papers, let’s see how BQP seems to fit with classical complexity classes—an understanding that’s remained largely stable for the past 30 years:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

We can state a large fraction of the research agenda of the whole field, to this day, as questions about BQP:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

I won’t have time to discuss all of these questions, but let me at least drill down on the first few.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Many people hoped the list of known problems in BQP would now be longer than it is. So it goes: we don’t decide the truth, we only discover it.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

As a 17-year-old just learning about quantum computing in 1998 by reading the Bernstein-Vazirani paper, I was thrilled when I managed to improve their containment BQP \u2286 P#P<\/sup> to BQP \u2286 PP. I thought that would be my big debut in quantum complexity theory. I was then crushed when I learned that Adleman, DeMarrais, and Huang had proved the same thing a year prior. OK, but at least it wasn’t, like, 50 years prior! Maybe if I kept at it, I’d reach the frontier soon enough.<\/p>\n\n\n\n

Umesh, from the very beginning, raised the profound question of BQP’s relation to the polynomial hierarchy. Could we at least construct an oracle<\/em> relative to which BQP\u2284PH—or, closely related, relative to which P=NP\u2260BQP? Recursive Fourier Sampling was a already candidate for such a separation. I spent months trying to prove that candidate wasn’t in PH, but failed. That led me eventually to propose a very different problem, Forrelation, which seemed like a stronger candidate, although I couldn’t prove that either. Finally, in 2018, after four years of effort, Ran Raz and Avishay Tal proved that<\/a> my Forrelation problem was not in PH, thereby resolving Umesh’s question after a quarter century.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

We now know three different ways by which a quantum computer can not merely solve any BQP problem efficiently, but prove its answer to a classical skeptic via an interactive protocol! Using quantum communication, using two entangled (but non-communicating) quantum computers, or using cryptography (this last a breakthrough<\/a> of Umesh’s PhD student Urmila Mahadev). It remains a great open problem, first posed to my knowledge by Daniel Gottesman, whether one can do it with none of these things.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

To see many of the advantages of quantum computation over classical, we’ve learned that we need to broaden our vision beyond BQP (which is a class of languages), to promise problems<\/em> (like estimating the expectation values of observables), sampling problems (like BosonSampling<\/a> and Random Circuit Sampling), and relational problems (like the Yamakawa-Zhandry problem<\/a>, subject of a recent breakthrough). It’s conceivable that quantum advantage could remain for such problems even if it turned out that P=BQP.<\/p>\n\n\n\n

A much broader question is whether BQP captures all languages that can be efficiently decided using “reasonable physical resources.” What about chiral quantum field theories, like the Standard Model of elementary particles? What about quantum theories of gravity? Good questions!<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Since it was Passover during the talk, I literally said “Dayenu”<\/a> to Umesh: “if you had only given us BQP, that would’ve been enough! but you didn’t, you gave us so much more!”<\/p>\n\n\n\n

Happy birthday Umesh!! We look forward to celebrating again on all your subsequent power-of-2 birthdays.<\/p>\n","protected":false},"excerpt":{"rendered":"

Unrelated Announcements: See here for a long interview with me in The Texas Orator, covering the usual stuff (quantum computing, complexity theory, AI safety). And see here for a podcast with me and Spencer Greenberg about a similar mix of topics. A couple weeks ago, I helped organize UmeshFest: Don’t Miss This Flight, a workshop […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[10,5,4],"tags":[],"class_list":["post-7972","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/7972","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7972"}],"version-history":[{"count":11,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/7972\/revisions"}],"predecessor-version":[{"id":7995,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/7972\/revisions\/7995"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7972"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7972"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7972"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}