By Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan

This is the first in a series of blog posts about our paper, Quantum Speedups Require Structure or Depth, which will appear at FOCS 26. We will use the blog format to give a breezier overview of the paper’s key ideas, and present bonus results that did not make it into the paper. In the spirit of Omer Reingold’s Research-Life Stories series, we will also tell some of the human stories behind the research.

Title Picture: Artistic depiction of the team, driven by school bus driver Li-Yang, on their way to a coffee shop. Much of the project was done on such trips.

---

The law of conservation of weirdness

Quantum computing, like computer science more broadly, has long been shaped by efforts to understand its own limitations. Shortly after Shor’s landmark factoring algorithm, Bennett, Bernstein, Brassard, and Vazirani (BBBV), in a 1997 paper titled Strengths and Weaknesses of Quantum Computing, gave relativized evidence that quantum computers cannot solve NP-complete problems efficiently.

Three decades later, quantum speedups continue to pervade number-theoretic cryptography, bringing about an entire field of post-quantum cryptography. On the other hand, many other important problems, including NP-complete ones, remain unscathed (save the quadratic speedup given by Grover—throughout this post, by “speedups” we mean superpolynomial ones).

Why is this the case? What is it about number-theoretic cryptography that allows for quantum speedups, and what is it about NP-complete problems that seemingly prevents them? An oft-repeated mantra is that quantum speedups require “structure”. Aaronson describes this as the “law of conservation of weirdness”: quantum speedups seem to require some sort of global structure to concentrate amplitudes on the correct answers.

But what exactly does “structure” mean? An especially elegant formalization, in the query model where many quantum algorithms operate, is given by the following conjecture:

The simulation conjecture: Let $\mathcal{A}$ be a $t$-query quantum algorithm. There is a classical algorithm that makes $\mathrm{poly}(t)$ queries and approximates $\mathcal{A}$‘s acceptance probabilities on most inputs $x$.

In this formalization, structure corresponds to a severely constrained promise on the input $x$. A quantum algorithm can achieve speedups on the very few $x$’s which satisfy this promise, but the conjecture posits that doing so for most $x$’s is impossible. For example, at the heart of Shor’s algorithm is a query algorithm for period finding that achieves a speedup under the promise that the input is periodic—which is indeed a stringent promise.

This conjecture was popularized by Aaronson and Ambainis, who attributed it to folklore dating back to the 1990s. It’s often called the Aaronson-Ambainis (AA) conjecture, though in these posts we’ll call it the AA simulation conjecture. We do so to distinguish it from the AA influence conjecture, which, as we will discuss below, is an approach towards proving the AA simulation conjecture. The AA simulation conjecture has become something of a classic, with related formulations appearing in Aaronson’s Ten semi-grand challenges for quantum computing theory, Fortnow’s Open oracle questions for the 21st century, and Ambainis’s ICM survey.

Our result. In our paper, we make progress on the AA simulation conjecture by taking the parallelism of quantum algorithms into account:

Theorem: Let $\mathcal{A}$ be a $t$-query $d$-round quantum algorithm. There is a classical algorithm that makes $t^{\mathrm{poly}(d)}$ queries and approximates $\mathcal{A}$‘s acceptance probabilities on most inputs $x$.

In a $d$-round algorithm, queries are made in parallel in each round and subsequent rounds can use information obtained from earlier ones. Round complexity is therefore synonymous with adaptivity, with $1$-round algorithms most commonly called nonadaptive.

Our theorem shows that for unstructured problems, exponential speedups—should they exist—would require polynomially many rounds of adaptivity. In contrast, most known exponential speedups for structured problems are achieved by highly parallel algorithms. Parallelism is especially desirable in the quantum setting because it reduces exposure to decoherence, a significant advantage given the substantial overheads of quantum error correction. Exponential speedups are likewise desirable because they have the most room to absorb these overheads, thereby retaining net quantum advantage.

Off in the wrong direction

We had embarked on this project with the goal of disproving the simulation conjecture. A couple years prior, Yamakawa and Zhandry had given a counterexample to its search version, and our “angle” had been to carry out a search-to-decision reduction for their problem.

We were stuck for months. And for good reason—our strategy was never going to work. We backed up and realized that every one of our attempts involved trying to prove a classical lower bound against a nonadaptive ($1$-round) quantum algorithm. Was this a red flag? On the one hand, maybe not: prototypical separations for structured problems (e.g. Period Finding, Simon’s problem, Forrelation) are witnessed by nonadaptive quantum algorithms, as is Yamakawa-Zhandry’s separation for unstructured search. On the other hand, we were sick of being stuck, so we switched gears and tried instead to prove the simulation conjecture for nonadaptive algorithms.

Once we started trying to prove a true statement, pace picked up. We soon had two proofs of the nonadaptive case. One of these we were able to extend to get a bound of $t^{\mathrm{exp}(d)}$ for $d$-round algorithms. Such a bound handles constant-round algorithms but its performance degrades quickly, becoming trivial once $d$ is polylogarithmic, an important regime that corresponds to $\mathsf{QNC}$. With a more involved analysis, we were then able to get the $t^{\mathrm{poly}(d)}$ bound that is our main result. The $t^{\mathrm{exp}(d)}$ proof appears as a warmup in the paper, but not the alternative proof of the nonadaptive case. This alternative proof is more combinatorial and fun—we may sketch it in a future post.

All in all, we spent more time trying to disprove the simulation conjecture than trying to prove it.

The query weight conjecture

Aaronson and Ambainis reduced the simulation conjecture to the now-famous AA influence conjecture: Every bounded low-degree polynomial that’s not close to constant must have an influential variable. It’s easy to see why this should imply the simulation conjecture: query-efficient quantum algorithms are bounded low-degree polynomials, and a classical algorithm can simply query this influential variable and recurse until the quantum algorithm is well-approximated by a constant.

The influence conjecture has been the dominant approach towards the simulation conjecture. It’s a particularly attractive route since it is a “quantum-free” statement about low-degree polynomials, allowing the full force of boolean function analysis to come to bear. And yet this conjecture remains wide open: The best bound remains that of [DFKO07], which yields a classical simulation that makes $\mathrm{exp}(t)$ instead of $\mathrm{poly}(t)$ queries.

We thought that perhaps in the quest for abstraction, the influence conjecture made proving the simulation conjecture more difficult than it had to be. In our paper we offer an alternative route. We introduce a relaxation of the influence conjecture that nevertheless suffices for the simulation conjecture: Every query-efficient quantum algorithm that is not close to constant must have a variable with high expected query weight. For classical algorithms, expected query weight is simply the probability (over a random input $x$ and the algorithm’s internal randomness) that a variable is queried. There is a natural quantum analogue, first introduced in the [BBBV97] paper mentioned at the top of this post.

Our conjecture, stated slightly more formally, is as follows:

Query weight conjecture (Every quantum query algorithm has a heavy variable): Let $\mathcal{A}$ be a $t$-query quantum algorithm that is not $\delta$-close to constant. There must be a variable whose expected query weight is at least $\mathrm{poly}(\delta/t)$.

This is indeed a relaxation of the influence conjecture, since influences are upper bounded by query weights. A variable can only influence $\mathcal{A}$’s output if $\mathcal{A}$ queries it, but the opposite is not true. An algorithm can always query a variable and ignore the answer, and in this case the variable has query weight $1$ and yet influence $0$.

We obtain our result on the simulation conjecture by proving the analogous statement for the query weight conjecture. We now sketch our proof of the latter.

The hybrid method strikes back

Query weights are the basis of [BBBV97]’s hybrid method—the first, and arguably simplest, lower-bound technique in quantum query complexity. The hybrid method, in its most basic form, says: If a quantum algorithm behaves very differently on two inputs $x$ and $y$, it must place substantial query weight on the coordinates where they differ. As it turns out, this is all the quantum one needs for our proof.

We show that this technique for proving quantum lower bounds can also be used to construct classical simulators (i.e. prove upper bounds). To see why this could be possible, consider the query weight conjecture stated in its contrapositive: If a query-efficient quantum algorithm $\mathcal{A}$ does not have any variable with high expected query weight, it must be close to a constant. We prove such a statement for parallel algorithms in the following steps:

1. We first show that under a stronger assumption—that, for most inputs $x$, the query weights of $\mathcal{A}$ on $x$ are small for every variable—$\mathcal{A}$ must be close to constant. We prove this by combining the hybrid method with a remarkable concentration inequality due to Talagrand.
2. This already handles the case of nonadaptive algorithms ($d=1$). In such algorithms, the query weights do not depend on $x$, and so $\mathcal{A}$ having low expected query weights implies that they are in fact small for all $x$’s.
3. This is no longer true for adaptive ($d \geq 2$) algorithms, since their query weights do depend on $x$. Small expected weight for each variable does not rule out every $x$ having a different heavy variable. Applying Markov and a union bound results in a vacuous statement—we need much better control over the concentration of query weights. To achieve this, the simple but key insight is that round-$r$ query weights are themselves the acceptance probabilities of $(r-1)$-round quantum query algorithms. This allows us to reason about the distribution of query weights inductively, in a round-by-round fashion.

This sketches the proof of our $t^{\mathrm{exp}(d)}$ warmup. Achieving our actual $t^{\mathrm{poly}(d)}$ bound is more involved. Briefly, instead of tracking query weights of individual variables like in this warmup, we track query weights of sets of variables. See our paper for details.

Final moments of the before times

Looking back, our project was perfectly timed to serve as a case study in the phase transition in the power of LLMs for mathematical research.

We worked on this project from September 2025 through March 2026. LLMs of that time were game-changers in some respects, and not so much in others. Most importantly, they taught three of us—Guy, Carmen, and Li-Yang—enough quantum on the fly to communicate with Jordan. This alone accelerated the project by months (and spared Jordan a lot of frustration). On the other hand, the research prowess of LLMs then was a shadow of what it is now: they were unable to prove even the nonadaptive case, which, as mentioned, ultimately had two short and elementary proofs. This was despite our feeding them most of the key ingredients and references; in hindsight, all that remained was to “put things together.”

Fast-forward to August 2026. Our paper had been accepted to FOCS and we were getting ready to post it on arxiv. OpenAI had just announced its Ten Advances in Mathematics and TCS. We decided to do an experiment: We asked our good friend Pras, whose chat logs were uncorrupted by our project, to see if the latest model (then ChatGPT 5.6 Pro) could recover our results.

It was now able to prove not just the nonadaptive case, but even a bound of $t^{\mathrm{exp}(d)}$, recovering the warmup in our paper. And all it took was two prompts. One to state the problem, and a second one: Don’t worry that it is open, you can prove it. Its proof also uses query weights and the hybrid method, and is similarly powered by the fact that round-$r$ query weights are the acceptance probabilities of $(r-1)$-round algorithms, though the details of its induction differ. See here for the transcript. Despite further prompting (and more words of encouragement), it wasn’t able to recover our $t^{\mathrm{poly}(d)}$ bound.

We decided to post immediately. Now, a month later, the floodgates have opened across quantum, TCS, and mathematics.

Epilogue. It’s a uniquely exciting time to be doing mathematical research, with such powerful oracles at our fingertips. That being said, there’s also something bittersweet about realizing that this was our final mostly-human collaboration.

We have a bet within our team as to whether AI will resolve the simulation conjecture within a year. Guy, Jordan, and Carmen are bullish, while Li-Yang remains in denial.

In the next post, we outline a way to extend our techniques and help Li-Yang lose the bet.