From Promises to Totality: A Framework for Ruling Out Quantum Speedups

1. Problem Statement

The central problem addressed is identifying which partial Boolean functions admit superpolynomial quantum query speedups (where $Q(f) \ll D(f)$) and which do not.

• Context: While total Boolean functions ($f: \{0,1\}^n \to \{0,1\}$) are known to have polynomially related deterministic ($D$) and quantum ($Q$) query complexities, partial functions (defined on a subset $Dom(f) \subset \{0,1\}^n$) can exhibit exponential separations (e.g., Simon's problem, Period finding).
• Gap: Existing literature has characterized specific structured cases (e.g., symmetric functions, functions on slices) or used "sculpting" (removing inputs from total functions) to find speedups. However, there is no unified framework to systematically rule out speedups for general partial functions or to understand the structural properties that prevent them.
• Goal: Develop general frameworks to prove that $D(f) = \text{poly}(Q(f))$ for broad classes of partial functions, thereby ruling out superpolynomial speedups.

2. Methodology

The authors propose two complementary frameworks to analyze the relationship between $D(f)$ and $Q(f)$:

A. Promise-Aware Complexity Measures

The authors extend standard combinatorial complexity measures (Block Sensitivity, Certificate Complexity) to the partial function setting by explicitly accounting for the "promise" (the domain $Dom(f)$).

• Standard Measures: For total functions, measures like block sensitivity ($bs$) and certificate complexity ($C$) are polynomially related to $D$ and $Q$.
• Promise-Aware Measures: For partial functions, flipping a bit might take an input out of the domain (undefined, $\ast$). The authors define:
  • Promised Block Sensitivity ($bs'$): Counts blocks where flipping leads to either a flipped output or leaving the domain.
  • Promised Certificate Complexity ($C'$): Certificates that ensure the input stays within the domain or outputs a specific value.
  • Critical Measures ($cbs, C_{cri}$): Defined via the "best" total completion of the partial function.
• Logic: The authors prove that if these promise-aware measures "collapse" (i.e., are polynomially related to each other), then $D(f)$ and $Q(f)$ must also be polynomially related.

B. Completion Complexity

The authors introduce the concept of Completion Complexity.

• Definition: A total function $F$ is a completion of a partial function $f$ if $F(x) = f(x)$ for all $x \in Dom(f)$. The completion complexity $M(f)$ is the minimum value of a measure $M$ over all possible completions $F$.
• Core Theorem: A partial function $f$ admits a superpolynomial quantum speedup over deterministic algorithms if and only if its complexity measure (specifically approximate degree $\widetilde{\deg}$) cannot be extended to a total function without a superpolynomial blow-up.
• Technique: They analyze whether an approximating polynomial $p(x)$ for $f$ can be "completed" to a polynomial $P(x)$ over the entire hypercube such that $P(x)$ remains bounded away from 0 outside the domain (allowing for sign-based boosting).

3. Key Contributions and Results

Result 1: Conditions for Ruling Out Speedups via Promise Measures

The authors prove that if specific relationships hold between promise-aware measures, no superpolynomial speedup exists.

• Theorem: If $cbs(f) = \text{poly}(bs'(f))$ or $cbs(f) = \text{poly}(C_{cri}(f))$, then $D(f) = \text{poly}(Q(f))$.
• Implication: This provides a local obstruction to speedups. If the domain is "well-connected" such that flipping bits rarely leaves the promise without changing the output, speedups are impossible.

Result 2: Characterization of Symmetric Functions

The paper provides a tight characterization for partial symmetric functions (where $f(x)$ depends only on Hamming weight $wt(x)$).

• Parameter: They define a Gap parameter $GAP(f) = \min |wt(x) - wt(y)|$ for inputs $x, y$ where $f(x) \neq f(y)$.
• Characterization:
  • $Q(f) = \Theta(n / GAP(f))$
  • $D(f) = \Theta(n - GAP(f))$
  • $\widetilde{\deg}(f) = \Theta(n / GAP(f))$
• Conclusion: For symmetric functions, the polynomial method is tight ($Q \approx \widetilde{\deg}$). Speedups are only possible when $GAP(f)$ is large (inputs with different outputs are far apart in Hamming weight), but even then, the separation is bounded by the gap.

Result 3: Characterization of Functions on Slices

For functions defined on a single $k$-slice (inputs with fixed Hamming weight $k$):

• They derive a new bound: $D(f) \leq \frac{3n}{\min(k, n-k)} C(f) bs(f)$.
• This implies $D(f) = O(\frac{n}{\min(k, n-k)} Q(f)^6)$.
• This bound is tighter than previous results for slices near the middle ($k \approx n/2$) and shows that speedups are limited by the geometry of the slice.

Result 4: Completion Complexity and Domain Identification

The authors formalize the link between domain identification and speedups.

• Theorem: If the domain $Dom(f)$ can be identified (membership checked) by a classical algorithm in $T$ queries, and the approximate degree $\widetilde{\deg}(f) = \Omega(\text{poly}(T))$, then $D(f) = \text{poly}(\widetilde{\deg}(f))$.
• Mechanism: If the domain is easy to identify, one can construct a "naïve completion" (setting undefined inputs to 0) using the product of the approximating polynomial and the domain indicator polynomial. This completion preserves the degree up to polynomial factors, ruling out speedups.

Result 5: Smoothness and Low Influence

Using Lipschitz continuity and Fourier analysis, they show that functions with low influence and low sparsity admit natural completions.

• Theorem: If an approximating polynomial $p(x)$ has low influence ($\text{Inf}_i$) and low sparsity ($\text{spar}_i$), it satisfies a global Lipschitz condition. This ensures $|p(x)|$ is bounded away from 0 outside the domain, allowing for a "natural completion" (sign of $p(x)$) without degree blow-up.
• Generalization: These results extend to the $p$-biased hypercube, covering a broader class of functions relevant to random graph models and noise stability.

Result 6: Hardness of General Perturbation

The authors investigate the algorithmic difficulty of finding a perturbation vector $\Delta$ to an approximating polynomial to force it away from zero outside the domain.

• Problem: Given polynomials $p, q_1, \dots, q_n$, find $\Delta$ such that $|p(x) + \sum \Delta_j q_j(x)| \geq \epsilon$ for all $x$.
• Result: This Perturbation Finding (PF) problem is NP-complete (reduced from 3-SAT).
• Significance: This suggests that while completions exist for many functions, finding the specific perturbation that enables a low-degree completion is computationally hard, explaining why general speedup criteria are difficult to derive.

4. Significance

• Unified Framework: The paper moves beyond ad-hoc proofs for specific problems (like Simon's or Period finding) to provide a general toolkit (Promise Measures and Completion Complexity) for analyzing quantum speedups.
• Ruling Out Speedups: It provides rigorous criteria to prove that a vast class of partial functions (symmetric, slice-based, low-influence, efficiently verifiable domains) cannot exhibit superpolynomial quantum speedups.
• Structural Insight: It highlights that the "structure" preventing speedups is often related to the connectivity of the domain and the smoothness of the approximating polynomial. If the domain is "dense" or the polynomial is "smooth" enough to extend naturally, quantum advantage is limited to polynomial factors.
• Hardness Connection: By linking the existence of completions to NP-complete problems, the paper suggests that the boundary between functions with and without speedups is computationally hard to navigate, offering a new perspective on the limits of quantum algorithms.

In summary, the paper establishes that superpolynomial quantum speedups are rare and require specific, "hard-to-complete" structural properties in the function's domain and its approximating polynomials. For most "well-behaved" partial functions, classical and quantum complexities remain polynomially related.