A Framework for Ruling Out Quantum Speedups

arXiv:2603.29256 · quant-ph · Submitted 2026-03-31 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "A Framework for Ruling Out Quantum Speedups".

Mira: This paper introduces a general framework for ruling out superpolynomial quantum query speedups by analyzing partial Boolean functions through two complementary lenses: promise-aware complexity measures and function completions.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: We've established that the paper, "A Framework for Ruling Out Quantum Speedups," provides a systematic way to rule out superpolynomial quantum query speedups by using two main approaches: promise-aware complexity measures and function completions. The authors argue that if these specific measures collapse, then the deterministic and quantum query complexities are polynomially related.

Mira: That's a concise summary of the paper's main contribution; they are essentially building a general mechanism to prove when exponential quantum speedups aren't possible by focusing on structural properties of Boolean functions rather than just brute-force algorithm design.

Lev: It sounds like this framework is less about proving an exponential speedup exists and more about providing a necessary condition for ruling one out, which is important for practical complexity analysis where we often need to know what's achievable with existing models.

Kai: Precisely, Lev. They move the focus onto the intrinsic properties of the function—like its sensitivity measures—to determine if it falls into a class where polynomial relationships must hold.

Mira: And they go further by characterizing specific structured functions, like symmetric partial functions and those defined on Hamming slices, giving us very precise formulas in terms of parameters like GAP(f) that quantify their complexity limits.

Lev: Having those concrete characterizations means we can potentially map real-world problems onto these known classes to immediately get a bound on the deterministic versus quantum query cost without having to run a full, intractable quantum simulation.

Kai: That’s the practical application I see; it allows us to use this paper's findings proactively in designing algorithms or understanding why certain problems might be inherently limited in terms of query access.

The paper's summary: Mira: To elaborate on the summary, the authors introduce promise versions of standard combinatorial measures and then prove that if those specific promise and completion measures "collapse," then D(f) equals poly Q(f). This means determinism and quantum query complexity are polynomially related under those collapse conditions.

Kai: So, it's not just a theoretical statement; they provide the specific conditions—like critical block sensitivity being polynomially related to promised block sensitivity or critical certificate complexity—that trigger this polynomial relationship. That's the actionable part for us on the experimental side.

Lev: I wonder if those relationships between cbs(f) and bs'(f) are robust enough to survive the noise and finite-size effects we encounter when trying to implement these functions on actual physical qubits?

Mira: That’s a fair concern, Lev, but the paper focuses on establishing these theoretical requirements for superpolynomial speedup based on these measures, which sets the theoretical bar we have to clear. They establish that if either of those specific relationships holds, then D(f) equals poly Q(f).

Kai: And they connect this to completion complexity by showing that "completability of a measure captures the possibility of superpolynomial quantum speedups," which is a very elegant way to link the function's structure directly to the existence of an advantage.

Lev: That connection between structure and completion complexity is interesting; it suggests that if we can't find a way to extend or complete these measures in a certain way, then we can rule out speedup.

The paper's improvements: Kai: The paper suggests several improvements, primarily by formalizing how to analyze structured families of promises, leading to sharp characterizations for symmetric functions and k-slice domains using gap parameters and refined bounds.

Mira: Those structural characterizations are the main improvement here because they move the discussion from abstract complexity measures to concrete formulas like D(f) ≤ 3n min

k, n−k: C(f) bs(f) for functions defined on a k-slice. That's much more tangible for understanding how complexity scales with the domain size and shape.

Lev: Those bounds are helpful because they give us an upper limit; if we know this bound, we can immediately set a practical performance target for any quantum algorithm we try to implement or simulate for that function class.

Kai: Furthermore, they formalize "natural completions," analyzing whether an approximate polynomial representation satisfies smoothness conditions based on Lipschitz continuity and constraints on influence and sparsity. This is important because it directly relates the mathematical structure to the possibility of a degree blow-up during completion.

Mira: That analysis of natural versus naïve completions is crucial because it tells us if we can actually achieve a manageable degree without incurring an exponential penalty, which directly informs whether quantum speedups via domain extension are viable.

Lev: If the AI system we mentioned earlier can automatically verify those smoothness conditions on an approximate polynomial, it could serve as a powerful tool for verifying the tractability of function completions in practice.

Conclusion: Kai: So, to wrap up, the paper "A Framework for Ruling Out Quantum Speedups" shows that structured domains cannot attain a speedup and provides tight bounds for other classes where the polynomial method is tight. It also presents Conjecture sixty-four which characterizes when a partial function admits the natural completion without a degree blow-up in terms of perturbations.

Mira: Overall, this work solidifies the idea that we have robust criteria to rule out speedups based on these structural properties and completion analysis, giving us tools to analyze functions more rigorously. It gives us a better map for where quantum advantages are likely not found.

Lev: I think the main implication for error correction is that we now have clearer theoretical boundaries on what kinds of functions can realistically be tackled with current or near-future hardware constraints when we look at complexity.

Kai: Exactly, Lev. And this whole framework helps us steer our experimental efforts away from problems that are theoretically destined to require exponentially powerful quantum resources for query access alone.

Mira: It’s a very useful piece of theoretical machinery for anyone working in complexity theory, providing tools to analyze the inherent limitations of quantum query models versus deterministic ones through these completion and measure collapse criteria.

Lev: I just think this paper sets a solid foundation for connecting the abstract measures to concrete computational limits, which is exactly what we need when we're trying to design scalable quantum systems.

Stony Brook University, USA · University of Ottawa, Canada

quant-ph

Submitted: 2026-03-31

Updated: 2026-09-30

Comments: 40 pages, 3 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: This paper introduces a general framework for ruling out superpolynomial quantum query speedups by analyzing partial Boolean functions through two complementary lenses: promise-aware complexity

Key concepts

Promise Measures: These are modified versions of standard combinatorial measures used to study functions. By examining how these promise and completion measures relate to each other, the authors establish conditions under which a superpolynomial quantum speedup is impossible.
Function Completions: This concept involves finding a way to complete a partial function (filling in the undefined parts) using different methods like naïve or natural completions. The ability to find an efficient completion determines whether quantum speedups are possible.
Critical Block Sensitivity (cbs(f)): This is a specific complexity measure used to analyze the structure of partial functions, particularly those with high symmetry. Relating this measure to others, like promised block sensitivity or certificate complexity, provides criteria for ruling out quantum speedups.
Polynomial Relation D(f) = poly Q(f): This means that the deterministic query complexity (D(f)) is bounded by a polynomial in the quantum query complexity (Q(f)). Establishing this polynomial relationship is a key outcome, indicating that no superpolynomial quantum speedup is possible for the function.

Terminology

Query Complexity — 39× in this paper · explained in 2 episodes
Sparsity — 9× in this paper · explained in 4 episodes
Generalization — 2× in this paper · explained in 13 episodes
Linear Margin Avoidance — 2× in this paper
Perturbation Finding — 2× in this paper
Core — 1× in this paper · explained in 2 episodes
Optimal Transport — 1× in this paper · explained in 5 episodes

Summary

This paper introduces a general framework for ruling out superpolynomial quantum query speedups by analyzing partial Boolean functions through two complementary lenses: promise-aware complexity measures and function completions. It establishes that if certain relevant complexity measures collapse, then deterministic and quantum query complexities are necessarily polynomially related, i.e., D(f) = poly(Q(f)). This framework provides broad non-speedup criteria for specific classes of functions, such as those with low maximum influence or efficiently identifiable domains.

Promise Measures and Complexity Relations

The authors introduce promise versions of standard combinatorial measures, including block sensitivity and related variants, to study when quantum speedups are possible. They prove that if the relevant promise and completion measures “collapse,” then deterministic and quantum query complexities are polynomially related. Specifically, they show that if either (i) critical block sensitivity cbs(f) is polynomially related to promised block sensitivity bs'(f), or (ii) critical block sensitivity is polynomially related to critical certificate complexity Ccri(f), then D(f) = poly Q(f). This result establishes the requirements for superpolynomial quantum speedup based on these measures.

Characterization of Symmetric and Slice Functions

The framework provides sharp characterizations for functions exhibiting high symmetry, such as fully symmetric partial functions (where the value depends only on Hamming weight) and functions defined on a single slice of the Boolean cube. For symmetric partial functions, they characterize several query complexity measures in terms of a single gap parameter GAP(f), which captures the minimal Hamming-weight separation between any two inputs on which the function differs. They derive results such as:

For any partial symmetric function f, deg(g f) = poly Q(f) = poly R(f) = poly n − GAP(f).
For functions defined on a k-slice, they establish a bound D(f) ≤ 3n min[k, n−k] C(f) bs(f), which implies D(f) = O n min[k,n−k] Q(f).

Quantum Speedups through Completions

The authors formalize completion complexity as the minimum of a measure over total completions of a partial function. They show that completability of a measure captures the possibility of superpolynomial quantum speedups. A key result states that for any partial function f, deterministic query complexity D(f) is polynomially related to M(f) if and only if the measure M is extendable, meaning D(f) = poly M(f) if and only if M(f) = poly M(f). This allows them to derive quantum non-speedup criteria. For instance, they show that superpolynomial quantum speedups exist only when the complexity of identifying the domain is superpolynomial with respect to the approximate degree.

Characterizing Naïve and Natural Completions

The paper analyzes two types of completions: the naïve completion (setting undefined inputs to 0 or 1) and the natural completion (based on the sign of an approximating polynomial). They show that if an efficient algorithm can decide whether an input is in the domain, then the approximate degree of F0 satisfies deg(g F0) ≤ poly(d, q), leading to quantum non-speedup. Furthermore, they establish conditions under which a partial function admits a natural completion without a degree blow-up, relying on Lipschitz continuity properties and constraints on the influence and sparsity of approximating polynomials.

Hardness Results for Perturbing Polynomials

The authors prove hardness results for finding well-behaved perturbations that allow for defining completions. They define the Perturbation Finding (PF) problem, which asks whether there exists a vector ∆ such that a perturbed polynomial remains above an error threshold while staying within a bounded norm. They show that PF is NP-complete by reducing Linear Margin Avoidance (LMA) to it, demonstrating the difficulty of finding such perturbations in general. This hardness implies that finding well-behaved completions is computationally hard.

Conclusion and Open Problems

The paper concludes by showing that Theorem 33 implies that structured domains cannot attain a speedup, and for other classes, the polynomial method is tight. They also present Conjecture 64, which characterizes when a partial function admits the natural completion without a degree blow-up in terms of perturbations. The work opens several open problems regarding the relationship between quantum and randomized query complexity and the intrinsic properties of polynomials that determine whether they admit such completions.

Key Results Summary:

**)&Result 1: For any partial Boolean function f, if either (i) critical block sensitivity cbs(f) is polynomially related to promised block sensitivity bs'(f), or (ii) critical block sensitivity is polynomially related to critical certificate complexity Ccri(f), then D(f) = poly Q(f).

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, A Framework for Ruling Out Quantum Speedups, which establishes powerful connections between classical and quantum query complexities by introducing concepts like promise measures and completion complexity.

The core value of this framework is providing rigorous criteria to determine when superpolynomial quantum speedups are impossible (i.e., when deterministic and quantum complexities are polynomially related).

Here are the specific improvements for AI systems that can be derived from this research, categorized by the capability they enable:

)

]

Enhanced Robustness in Quantum Algorithm Design (Speedup Avoidance):

As the framework provides a precise set of conditions (Theorem 33) under which superpolynomial quantum speedups are ruled out, AI systems can be used to proactively search for speedup-resistant problem instances.

An AI system can analyze the structure of a given Boolean function (or problem instance) and calculate its critical measures: critical block sensitivity (cbs), promised block sensitivity (bs'), and certificate complexity (Ccri).
The system can then immediately output a definitive answer regarding query complexity relationships: if it finds that either cbs(f) = poly bs'(f) or cbs(f) = poly Ccri(f), the system can conclude with high confidence that the deterministic and quantum query complexities are polynomially related, thus ruling out an exponential quantum speedup.
This prevents researchers and developers from wasting time designing potentially exponential-speedup algorithms for problems known to be classically hard in terms of query complexity.

Optimized Query Complexity Lower Bounds (D(f) vs Q(f)):

The paper provides sharp bounds relating deterministic complexity, quantum complexity, and approximate degree:

For symmetric functions, it establishes the tight relationship: D(f) = poly n - GAP(f).
For general partial functions on a slice, it provides a refined bound: D(f) ≤ O(n min[k, n−k] Q(f) 6).

AI can leverage these derived structural relationships to establish stronger, more practical lower bounds for specific AI tasks:

If an AI task (e.g., a specific type of pattern recognition or classification problem) is modeled as a partial function with known symmetry (like those characterized by GAP), the system can use the provided formulas to set tighter, theoretically grounded lower bounds on both deterministic and quantum query complexity, guiding algorithm design toward the most efficient possible solution space.

Automated Completion Analysis for Verification (Natural Completion):

The framework formalizes natural completions based on approximating polynomials and Lipschitz continuity (Lemma 52, Lemma 55).

An AI system can take an approximate polynomial representation of a partial function and test whether it satisfies the necessary smoothness conditions (e.g., low influence/sparsity bounds) required for the natural completion to have a manageable degree blow-up.
This allows the AI to automatically verify if a proposed approximation is well-behaved enough to allow for an efficient total function completion, which is crucial for understanding whether quantum speedups are achievable through domain extension.

Hardness Verification in Perturbation Problems (PF Problem):

The paper proves the NP-completeness of the Perturbation Finding (PF) problem, which seeks a perturbation vector that maintains a polynomial relationship between complexity measures.

AI systems can be used to solve complex optimization or search problems that map onto this structure. For example, if an AI is trying to find a good parameter set (the perturbation vector), it can use the hardness result of PF to determine whether finding such a set is computationally intractable (NP-hard). This informs the AI on whether its search strategy should be exhaustive or heuristic.

)

Abstract

We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two complementary lenses: promise-aware complexity measures and function completions. First, we introduce promise versions of standard combinatorial measures (including block sensitivity and related variants) and prove that if the relevant promise and completion measures ``collapse'', then deterministic and quantum query complexities are necessarily polynomially related, i.e. D(f) = poly(Q(f)). We then analyze structured families of promises, including symmetric partial functions and promises supported on Hamming slices, obtaining sharp (up to polynomial factors) characterizations in terms of a single gap parameter for the symmetric case and refined slice-dependent bounds for k-slice domains. Next, we formalize completion complexity as the minimum of a measure over total completions of a partial function, and show that completability of a measure captures the possibility of superpolynomial quantum speedups. Finally, we apply this viewpoint to derive broad non-speedup criteria for some classes of functions admitting well-behaved completions, such as functions defined on a single slice or a union of slices, functions with low maximum influence on both the standard and p-biased hypercubes and functions with efficiently identifiable domains, and then show some hardness results for general completion techniques.