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

Quantum Physics [Submitted on 31 Mar 2026] From Promises to Totality: A Framework for Ruling Out Quantum Speedups Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky, Supartha Podder 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 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. Comments: 37 pages, 3 figures Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2603.29256 [quant-ph]   (or arXiv:2603.29256v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.29256 Focus to learn more Submission history From: Thomas Huffstutler [view email] [v1] Tue, 31 Mar 2026 04:29:00 UTC (57 KB) Access Paper: view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)