The Aaronson-Ambainis Conjecture (2008-2019)
Update: Sadly, Nathan Keller and Ohad Klein tell me that they’ve retracted their preprint, because of what currently looks like a fatal flaw in Lemma 5.3, uncovered by Paata Ivanishvili. I wish them the best of luck in fixing the problem. In the meantime, I’m leaving up this post for “historical” reasons.
Around 1999, one of the first things I ever did in quantum computing theory was to work on a problem that Fortnow and Rogers suggested in a paper: is it possible to separate P from BQP relative to a random oracle? (That is, without first needing to separate P from PSPACE or whatever in the real world?) Or to the contrary: suppose that a quantum algorithm Q makes T queries to a Boolean input string X. Is there then a classical simulation algorithm that makes poly(T) queries to X, and that approximates Q’s acceptance probability for most values of X? Such a classical simulation, were it possible, would still be consistent with the existence of quantum algorithms like Simon’s and Shor’s, which are able to achieve exponential (and even greater) speedups in the black-box setting. It would simply demonstrate the importance, for Simon’s and Shor’s algorithms, of global structure that makes the string X extremely non-random: for example, encoding a periodic function (in the case of Shor’s algorithm), or encoding a function that hides a secret string s (in the case of Simon’s). It would underscore that superpolynomial quantum speedups depend on structure.
I never managed to solve this problem. Around 2008, though, I noticed that a solution would follow from a perhaps-not-obviously-related conjecture, about influences in low-degree polynomials. Namely, let p:Rn→R be a degree-d real polynomial in n variables, and suppose p(x)∈[0,1] for all x∈{0,1}n. Define the variance of p to be
Var(p):=Ex,y[|p(x)-p(y)|],
and define the influence of the ith variable to be
Infi(p):=Ex[|p(x)-p(xi)|].
Here the expectations are over strings in {0,1}n, and xi means x with its ith bit flipped between 0 and 1. Then the conjecture is this: there must be some variable i such that Infi(p) ≥ poly(Var(p)/d) (in other words, that “explains” a non-negligible fraction of the variance of the entire polynomial).
Why would this conjecture imply the statement about quantum algorithms? Basically, because of the seminal result of Beals et al. from 1998: that if a quantum algorithm makes T queries to a Boolean input X, then its acceptance probability can be written as a real polynomial over the bits of X, of degree at most 2T. Given that result, if you wanted to classically simulate a quantum algorithm Q on most inputs—and if you only cared about query complexity, not computation time—you’d simply need to do the following:
(1) Find the polynomial p that represents Q’s acceptance probability.
(2) Find a variable i that explains at least a 1/poly(T) fraction of the total remaining variance in p, and query that i.
(3) Keep repeating step (2), until p has been restricted to a polynomial with not much variance left—i.e., to nearly a constant function p(X)=c. Whenever that happens, halt and output the constant c.
The key is that by hypothesis, this algorithm will halt, with high probability over X, after only poly(T) steps.
Anyway, around the same time, Andris Ambainis had a major break on a different problem that I’d told him about: namely, whether randomized and quantum query complexities are polynomially related for all partial functions with permutation symmetry (like the collision and the element distinctness functions). Andris and I decided to write up the two directions jointly. The result was our 2011 paper entitled The Need for Structure in Quantum Speedups.
Of the two contributions in the “Need for Structure” paper, the one about random oracles and influences in low-degree polynomials was clearly the weaker and less satisfying one. As the reviewers pointed out, that part of the paper didn’t solve anything: it just reduced one unsolved problem to a new, slightly different problem that was also unsolved. Nevertheless, that part of the paper acquired a life of its own over the ensuing decade, as the world’s experts in analysis of Boolean functions and polynomials began referring to the “Aaronson-Ambainis Conjecture.” Ryan O’Donnell, Guy Kindler, and many others had a stab. I even got Terry Tao to spend an hour or two on the problem when I visited UCLA.
Now, at long last, Nathan Keller and Ohad Klein say they’ve proven the Aaronson-Ambainis Conjecture, in a preprint whose title is a riff on ours: “Quantum Speedups Need Structure.”
Their paper hasn’t yet been peer-reviewed, and I haven’t yet carefully studied it, but I could and should: at 19 pages, it looks very approachable and clear, if not as radically short as (say) Huang’s proof of the Sensitivity Conjecture. Keller and Klein’s argument subsumes all the earlier results that I knew would need to be subsumed, and involves all the concepts (like a real analogue of block sensitivity) that I knew would need to be involved somehow.
My plan had been as follows:
(1) Read their paper in detail. Understand every step of their proof.
(2) Write a blog post that reflects my detailed understanding.
Unfortunately, this plan did not sufficiently grapple with the fact that I now have two kids. It got snagged for a week at step (1). So I’m now executing an alternative plan, which is to jump immediately to the blog post.
Assuming Keller and Klein’s result holds up—as I expect it will—by combining it with the observations in my and Andris’s paper, one immediately gets an explanation for why no one has managed to separate P from BQP relative to a random oracle, but only relative to non-random oracles. This complements the work of Kahn, Saks, and Smyth, who around 2000 gave a precisely analogous explanation for the difficulty of separating P from NP∩coNP relative to a random oracle.
Unfortunately, the polynomial blowup is quite enormous: from a quantum algorithm making T queries, Keller and Klein apparently get a classical algorithm making O(T18) queries. But such things can almost always be massively improved.
Feel free to use the comments to ask any questions about this result or its broader context. I’ll either do my best to answer from the limited amount I know, or else I’ll pass the questions along to Nathan and Ohad themselves. Maybe, at some point, I’ll even be forced to understand the new proof.
Congratulations to Nathan and Ohad!
Update (Nov. 20): Tonight I finally did what I should’ve done two weeks ago, and worked through the paper from start to finish. Modulo some facts about noise operators, hypercontractivity, etc. that I took on faith, I now have a reasonable (albeit imperfect) understanding of the proof. It’s great!
In case it’s helpful to anybody, here’s my one-paragraph summary of how it works. First, you hit your bounded degree-d function f with a random restriction to attenuate its higher-degree Fourier coefficients (reminiscent of Linial-Mansour-Nisan). Next, in that attenuated function, you find a small “coalition” of influential variables—by which we mean, a set of variables for which there’s some assignment that substantially biases f. You keep iterating—finding influential coalitions in subfunctions on n/4, n/8, etc. variables. All the while, you keep track of the norm of the vector of all the block-sensitivities of all the inputs (the authors don’t clearly explain this in the intro, but they reveal it near the end). Every time you find another influential coalition, that norm goes down by a little, but by approximation theory, it can only go down O(d2) times until it hits rock bottom and your function is nearly constant. By the end, you’ll have approximated f itself by a decision tree of depth poly(d, 1/ε, log(n)). Finally, you get rid of the log(n) term by using the fact that f essentially depended on at most exp(O(d)) variables anyway.
Anyway, I’m not sure how helpful it is to write more: the paper itself is about 95% as clear as it could possibly be, and even where it isn’t, you’d probably need to read it first (and, uh, know something about influences, block sensitivity, random restrictions, etc.) before any further clarifying remarks would be of use. But happy to discuss more in the comments, if anyone else is reading it.
Follow
Comment #1 November 17th, 2019 at 6:27 pm
Should x∈{0,1}^2 be x∈{0,1}^n in the statement of the conjecture in the second paragraph?
Comment #2 November 17th, 2019 at 7:49 pm
Basic question: What’s the classical analogue of this? The paper mentions that there is one but I’m having some trouble finding it.
Comment #3 November 17th, 2019 at 8:23 pm
Abhijit #1: Yes, thanks, fixed!
Comment #4 November 17th, 2019 at 8:25 pm
Sniffnoy #2: Classically, you get the same statement as you do quantumly (any T-query algorithm gives rise to a degree-T real polynomial), and in that case without even the factor of 2. It’s just that it’s much more interesting in the quantum case, since it typically yields a tighter bound there (and also, since quantumly we have fewer alternative lower bound techniques).
Comment #5 November 17th, 2019 at 8:52 pm
Scott #4: I see, thanks!
Comment #6 November 17th, 2019 at 11:26 pm
[…] by Nathan Keller, Ohad Klein, resolving the Aaronson-Ambainis Conjecture. (Update: here is a blog post on the Shtetl-Optimized.) Congrats to Nathan and […]
Comment #7 November 18th, 2019 at 9:38 am
[…] The Aaronson-Ambainis Conjecture (2008-2019) 3 by weinzierl | 0 comments on Hacker News. […]
Comment #8 November 18th, 2019 at 12:05 pm
Hey Scott,
sorry for being offtopic, but do you have any thoughts on that recent eigenvalues -> eigenvectors “discovery” (by Tao and co)?
Is that affecting QC in any way?
Comment #9 November 18th, 2019 at 1:37 pm
fred #8: I read about the eigenvectors from eigenvalues thing on Terry Tao’s blog post a while ago. It’s super-cool! We just heard about it in our Austin quantum group meeting this morning. And of course it was first (re-)noticed by physicists working on neutrino oscillations. Having said that, no, I don’t know of any implications that it has for QC (although it’s not out of the question that there could be something).
Comment #10 November 18th, 2019 at 2:22 pm
The eigenvectors from eigenvalues identity turns out to have been known in folklore, though obscure. Props are still due to the rediscoverers for finding this useful identity again, and bringing it into the light. See the more recent flurry of comments on Tao’s blog thread:
https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/#comments-meta
Comment #11 November 20th, 2019 at 10:24 am
Structure is required but not sufficient right. How much structure is needed?
Does it have to be as constrained as Simon’s problem and period finding?
I’ve noticed that Graph Isomorphism doesn’t seem to have the same type of structure.
For example, you can get interference between each pair of orderings x1 and x2 that yield the same graph when applied to two isomorphic graphs g1 and g2, but the result doesn’t reveal much since each pair can be so varied.
It’s like sampling from a large set of double-slit experiments with misaligned interference patterns. The combined result just looks like a single slit.
Does it have to be as constrained as x1=x2+s for it to work? What’s the most complex structure we know of that still produces a quantum speedup?
Comment #12 November 20th, 2019 at 11:02 am
Job #11: Welcome to quantum algorithms research! Those are the questions we’ve been studying for the last 25 years. 🙂
One place where exponential quantum speedups are traditionally considered to have made their “last stand,” in the quest for greater and greater generality, is the nonabelian hidden subgroup problem. There, Ettinger, Hoyer, and Knill showed in 1997 that the quantum query complexity is always only polylogarithmic in the group order. But alas, 22 years later we still know algorithms that are computationally efficient for only a tiny sliver of nonabelian groups. Famously, graph isomorphism and breaking lattice-based cryptography both reduce to the hidden subgroup problem over nonabelian groups that we don’t know how to handle efficiently (the symmetric and dihedral groups respectively).
If starting from the HSP, you take away the group structure, and just ask (for example) to distinguish 1-to-1 from 2-to-1 functions, then the collision lower bound that I proved in 2002 showed that there’s not even a quantum algorithm that’s efficient in terms of query complexity.
There are various other ways to formalize the notion of “structured” versus “unstructured,” even just within query complexity (including the way relevant to Keller and Klein’s dramatic advance last week), but hopefully that gives you a taste!
Comment #13 November 22nd, 2019 at 1:32 pm
I figured that wasn’t known to be possible, otherwise there would be a quantum algorithm for GI, but it actually seemed like an easier problem than period-finding. I was wondering about it.
Also, i’m wondering what the output for a problem like GI would look like when rendered as an image, relative to what we get for Simon’s problem.
I imagine it will have no identifiable pattern across different instances, but it might still look cool. Period finding should also look interesting.
I actually think quantum simulators should render the output samples as an image, it’s alot easier to visualize the resulting probability distribution that way. Definitely easier than looking at pairs of bit strings and probabilities.
Plus i like the analogy of a QC as an imaging device, like a telescope.
With the supremacy experiment, we used such a high magnification we could only statistically identify what we were looking at. Maybe next time we could just take really good pictures of Pluto.
Comment #14 November 22nd, 2019 at 3:03 pm
Job #13: Period-finding is actually a special case of the collision problem—namely, the special case where the k-to-1 function for which you want collisions is known to be periodic. It’s a special case that’s quantumly much easier than the general case, although classically their difficulties are essentially the same.
Your questions about “what things look like when rendered as images” are ill-defined. An n-qubit state represents a huge amount of data, and there are many different images you could make to help visualize that data, depending on what you care about. Or you could just write down a formula. 🙂
Comment #15 November 22nd, 2019 at 3:25 pm
It’s not like simulators can handle a large quantum state anyway.
And I couldn’t possibly write a formula for the interference between node-ordering pairs for a GI instance. I would be impressed if you could, and you’re an actual mathematician.
Not only is it not my domain or language, it’s not really the most adequate tool. I’m not trying to start a big discussion, but it’s too formal, i don’t need the elegance of a formula during experimentation and discovery.
It’s easier to write code, render the result, observe patterns and investigate. How else are you going find what you’re not looking for?
Comment #16 December 2nd, 2019 at 9:31 am
[…] weeks ago, I blogged about the claim of Ohad Keller and Nathan Klein to have proven the Aaronson-Ambainis Conjecture. Alas, […]