UmeshFest
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 at UC Berkeley’s Simons Institute to celebrate the 26th birthday of my former PhD adviser Umesh Vazirani. 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” was simply standard usage among the attendees.
At Berkeley, many things were as I remembered them—my favorite Thai eatery, the bubble tea, the Campanile—but not everything 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):
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.
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 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).
And then there were talks! I thought I’d share my own talk, which was entitled The Story of BQP (Bounded-Error Quantum Polynomial-Time). Here 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.
I was particularly proud of the design of my title slide:
Moving on:
The class BQP/qpoly, 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.
I then displayed my infamous “Umeshisms” blog post from 2005—one of the first posts in the history of this blog:
As I explained, now that I hang out with the rationalist and AI safety communities, which are also 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 Umesh?!” the rationalists excitedly exclaimed. “Of Umeshisms? If you’ve never missed a flight?”
But moving on:
(Note that by “QBPP,” Bethiaume and Brassard meant what we now call BQP.)
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 classical algorithms, rather than randomized algorithms. Deutsch-Jozsa 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!
Ah, but this is where Bernstein and Vazirani enter the scene.
Bernstein and Vazirani didn’t merely define BQP, which remains the central object of study in quantum complexity theory. They also established its most basic properties:
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:
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.
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, while the quantum query complexity is only 2d. Where did the 2 come from? From the need to uncompute 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.
The Recursive Fourier Sampling separation set the stage for Simon’s algorithm, which gave a more impressive speedup in the black-box model, and thence for the famous Shor’s algorithm for factoring and discrete log:
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:
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:
We can state a large fraction of the research agenda of the whole field, to this day, as questions about BQP:
I won’t have time to discuss all of these questions, but let me at least drill down on the first few.
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.
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 ⊆ P#P to BQP ⊆ 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.
Umesh, from the very beginning, raised the profound question of BQP’s relation to the polynomial hierarchy. Could we at least construct an oracle relative to which BQP⊄PH—or, closely related, relative to which P=NP≠BQP? 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 my Forrelation problem was not in PH, thereby resolving Umesh’s question after a quarter century.
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 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.
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 (like estimating the expectation values of observables), sampling problems (like BosonSampling and Random Circuit Sampling), and relational problems (like the Yamakawa-Zhandry problem, subject of a recent breakthrough). It’s conceivable that quantum advantage could remain for such problems even if it turned out that P=BQP.
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!
Since it was Passover during the talk, I literally said “Dayenu” to Umesh: “if you had only given us BQP, that would’ve been enough! but you didn’t, you gave us so much more!”
Happy birthday Umesh!! We look forward to celebrating again on all your subsequent power-of-2 birthdays.
Follow
Comment #1 May 10th, 2024 at 8:41 am
a workshop at UC Berkeley’s Simons Institute to celebrate the 26th birthday of my former PhD adviser Umesh Vazirani
What about finding the fountain of youth?
Comment #2 May 10th, 2024 at 9:28 am
Doh #1: NoOoOoOoO!!!
I promised myself that I’d remember to put in all the superscripts before I posted … and then I was in a rush this morning, and didn’t.
I suppose this means that forever after, I have to forgive every popular science writer who writes 10500 when they mean 10500.
Comment #3 May 10th, 2024 at 9:44 am
Are the videos from the workshop going to be made available?
Comment #4 May 10th, 2024 at 10:05 am
I’m reminded of the ancient saying, “Heaven is in the low-order bits.” Of course, the counter-saying is that “the Devil is in the low-order bits.”
Comment #5 May 10th, 2024 at 10:36 am
They had boba in Berkeley in the old days? Now every other shop is boba it seems like but back in the 2010s I knew of only one place somewhere near Durant or Bancroft or something like that. Also what’s the thai place? There was Thai Basil but I think that was more for us lowly undergrads, though I also rather enjoyed Thai Noodle (or was it Thai Noodle II?).
Comment #6 May 10th, 2024 at 10:51 am
Amy #5: Thai Basil is the one! And I still go there to get my cashew chicken, surrounded by undergrads. 😀
Yes, Berkeley was (I think) one of the first places in North America to get boba, in 2000 or 2001 or so … which was when I got hooked on it.
Comment #7 May 10th, 2024 at 10:52 am
CC #3: Sorry! I believe that by Umesh’s preference, there’s no video for most of it.
Comment #8 May 10th, 2024 at 1:27 pm
Ignoring the low-order qubits will make your wave function not cancel where it was supposed to.
Comment #9 May 10th, 2024 at 8:53 pm
From the chalk, it looks like it was the “Anti-Zionism Zone” rather than the “Anti-Zionist Zone”.
Comment #10 May 10th, 2024 at 9:38 pm
D #9: Fixed.
Comment #11 May 11th, 2024 at 11:48 am
Regarding the hunt for elusive white whales of efficient quantum algorithms admitting an exponential speedup for problems with polynomially-verifiable certificates, the issues seems to be (1) whether the problem is a decision problem in NP, in which case a lot of structure such as what was exploited by Shor appears to be required, or (2) whether the problem itself is not a decision problem per se, in which case neat algorithms like Yamakawa-Zhandry might exist.
On the second note and inspired by various proofs-of-quantumness, consider the following: Let f be a random, two-to-one function from n bits to n bits that, apart from being two-to-one, satisfies no other structure (no Simon promise or trap-door or…) We wish to find a constant number of pairs (d,y) of n-bit strings d and y with d not equal to 0 and with y in the range of f, such that of the two preimages x1 and x2 satisfying f(x1)=f(x2)=y, when x1 and x2 are XOR’ed together and AND’ed with d, the parity of the 1’s count of \(d \land (x_1 \oplus x_2)\) is even.
I claim that there is a quick quantum algorithm for this, by, e.g., evaluating \(\frac{1}{\sqrt{2^n}}|x\rangle|f(x)\rangle\) in superposition, measuring the second register in the computational basis to get y, and measuring the first register in the Hadamard basis to get d. I claim also that this problem has an NP certificate – namely, the pairs (x1, x2) which can be used to determine (d,y). I further claim that, as an oracle problem, the best we could do classically is via birthday searching to find colliding x1 and x2 and reporting on y=f(x1)=f(x2), and then reporting a non-zero string d satisfying the Boolean equation relative to x1 XOR x2.
But this problem is not an NP-decision problem, because we aren’t asking for any specific properties of d or y (and if we did, we’d probably run up against the Aaronson-Ambainis conjecture). It’s not even a quantum approach to an NP-search problem, as we are asking for the pairs (d,y) and not for the pairs (x1,x2) (and if we did, we could use BHT but otherwise we’d probably run up against the collision lower bound).
What kind of problem is it to find pairs (d,y)? It avoids Aaronson-Ambainis, it has an efficient quantum algorithm without a lot of structure and has an NP-certificate, but it’s not an NP decision problem, nor is it an NP-search problem…
Comment #12 May 12th, 2024 at 1:11 pm
Please remove the photo of the Gaza encampment, or at least blur the faces. They did not give you permission to take photographs, and you are not a registered journalist. Furthermore, pro-Palestine students are being attacked across America, and you’re risking these students being doxxed. You’re actively making them unsafe. What if one of your Zionist readers at Berkeley recognizes one of these students and goes to attack them?
Comment #13 May 12th, 2024 at 2:16 pm
Now House #12: You’ve got to be kidding! They are there to try to intimidate me, and anyone is allowed to take photos in a public place, which Sproul Plaza most certainly still is. Any further comments about this will go straight to the trash.
Comment #14 May 12th, 2024 at 9:38 pm
What is the nature of the promise in quantum simulation problems? Is it some kind of “physical reasonableness” assumption, like translational invariance or locality of the Hamiltonian to be simulated?
Comment #15 May 13th, 2024 at 7:33 am
Ted #14: No, more basic than that! If you’re asking a yes-or-no question about the expectation value of some observable — of the form, “is it greater or less than C?” — then you need a promise that the true value isn’t ridiculously close to C, requiring an estimate with inordinate precision.
Comment #16 May 13th, 2024 at 10:02 am
Scott,
Your sunglasses make you look like a Mossad agent, which may have caused some students in the zone to feel unsafe.
Comment #17 May 13th, 2024 at 10:14 am
I remember that you wrote a letter opposing changes to tenure. My view is that a terrible ideological virus has infected university faculties in the US. It is readily apparent at this moment due to the visible antisemitism but the attacks on empiricism and the total focus on particular ideology has been ongoing for decades. How would you address the situation without removing the protection of tenure? It is a difficult situation to remedy in a liberal society but to my view it must be addressed.
There is societal pressure to attend university and that education for many is simply indoctrination so the opposite of what a liberal education should be.
Comment #18 May 13th, 2024 at 10:45 am
Craig #16: LOL! I confess that I did present a pretty terrifying appearance, what with my slacks, button-down shirt and soft OpenAI hoodie.
Comment #19 May 13th, 2024 at 10:55 am
OhMyGoodness #17: I’ve emphatically never asked even for tenured professors with repulsive ideologies (say, who celebrated Oct 7) to be fired. If such power existed, I expect it wouldn’t be long before it was turned against me, or people I agreed with.
Without venturing a full solution to everything wrong with American academia, I think we could improve the situation by just enforcing already-existing rules in a viewpoint-neutral way, for the purpose of ensuring universities remain places for seeking common ground through the use of reason, rather than intimidating through the chanting of slogans. So for example, if someone can declare part of a campus lawn a place where “no Zionists are allowed,” then someone else can declare another part a place where “no feminists are allowed,” etc. Or if we don’t like the implications of that, then all campus common areas should remain open to everyone.
Comment #20 May 13th, 2024 at 11:37 am
Scott #15: Gotcha, thanks! If I understand correctly, the ultimate root reason why quantum simulation problems are in PromiseBQP (rather than standard BQP) is that the quantities of interest (expectation values) are most naturally formulated as continuous real numbers rather than discrete natural numbers.
Comment #21 May 13th, 2024 at 11:45 am
I agree that in theory tenure was intended to protect diversity of thought but now in practice it actually protects a sad uniformity of thought. These pro-Gaza encampments are the most visible indications of a failure of US higher education but also the least important. Antisemitism is most importantly a belief that resides in minds and not the justification for an exclusion area on a commons.
Hopefully it will change now with stronger enforcement of existing regulations (you know those regulations much better than I do) but I expect it will be full speed forward down the same path.
Comment #22 May 13th, 2024 at 2:20 pm
Ted #20: Basically, yes. A problem only gets to be in BQP if it has a poly time quantum algorithm that, for all inputs, either outputs “yes” with high probability or “no” with high probability. “Does this number have a prime factor ending in 3?” is an example, because of Shor’s algorithm. But when you turn a problem of estimating a continuous quantity into a decision problem, it generally becomes a promise problem.
Comment #23 May 17th, 2024 at 7:07 am
In a prior post, you asked for exotic physics ideas that may prevent qc. I don’t have a reference, but I am sure someone has proposed that phases between quantum states are discrete, with some minimum positive phase difference (0 diff is allowed). If this min was say 10^(-18), would that be falsified by experiment? Would it prevent qc advantage? Is this obviously false?
Comment #24 May 17th, 2024 at 9:14 am
Johnny D #23: It’s impossible to answer your question without knowing more about the theory that enforces this discreteness in the phases. Almost all sets of quantum gates that you can write down will generate a dense subset of the unitary group. So, what prevents me from applying unitaries that would violate this discreetness? Depending on the answer, it’s conceivable that QC would be killed, but it’s also conceivable that we’d get even more power than QC … even efficient solution of NP-complete problems!
In any case, the usual comment applies: if the effort to build QCs led instead to the discovery of this new discrete structure underlying QM, that would be a scientific revolution, indeed a much greater success for the field than a mere success in building QCs would’ve been.
Comment #25 May 17th, 2024 at 9:24 am
Any thoughts on Sutskever having left OpenAI?
I doubt you’ll say much considering you’re working there, but while I’m not surprised, I personally do think that it’s way more significant to the future of (Open)AI than (e.g.) whether Altman is involved or not.
Of course, I could be wrong, there’s more to technology than engineering, but I just don’t see Altman being a driving force like Steve Jobs was (as a business guy).
Comment #26 May 17th, 2024 at 1:57 pm
fred #25: I don’t mind saying that I think it’s sad, and that I wish a way had been found for both Ilya and Jan Leike (who were my “bosses”) to continue their great work at OpenAI.
Comment #27 May 20th, 2024 at 8:10 am
Thanks Scott!