CS Paper Radar

Quantum Query Advantage Requires Space

Minbo Gao, Zhengfeng Ji, Ziyi Xie

cs.CC quant-ph ·submitted 2026-09-04 13:04 UTC · v2
publishedtheory

Abstract

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

Comment
21 pages, update introduction and fix grammar mistakes

Closest papers

Nearest neighbours by meaning across the whole index.

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

cs.CC quant-ph ·2026-09-30 ·Paul Beame, Blake Holman, Niels Kornerup
theoryhot direction similarity 0.76
Abstract · 46 pages, submitted to QIP 2027. New version fixes the displayed abstract and makes some minor corrections to fix the parameters used in res…

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

0.27

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

cs.CC quant-ph ·2026-11-06 ·Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni +2 more
similarity 0.74
Abstract · 57 pages, 2 figures

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

0.27

Quantum Submodular Maximization

cs.CC quant-phcs.DS ·2026-10-03 ·Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang +1 more
theory similarity 0.72
Abstract · 62 pages; abstract shortened for arXiv

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

0.24

Randomized query complexity can beat certificate complexity

cs.CC quant-ph ·2026-09-14 ·Shalev Ben-David, Robin Kothari
similarity 0.71
Abstract · 6 pages

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

0.32

Noisy Quantum Query Complexity via Fractional Block Sensitivity

cs.CC quant-ph ·2026-09-30 ·Mehil Agarwal, Shravas Rao, Fang Song
theory similarity 0.70
Abstract · 34 pages, LaTex, fixed typos, updated acknowledgement, fixed mathjax in abstract

We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

0.26

Quantum Query Complexity Beyond the Worst Case

cs.CC quant-ph ·2026-09-28 ·Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani
hot direction similarity 0.70
Abstract

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

0.22

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

cs.CC quant-phcs.CRcs.DS ·2026-09-09 ·Frédéric Magniez, Sebastian Zur
theory similarity 0.69
Abstract · Addition of an example of an application to algorithms with intermediate measurements, together with minor edits

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

0.43

Separations Between Randomized and Exact Quantum Query Complexity for Boolean Functions

cs.CC quant-ph ·2026-11-16 ·Zekun Ye
similarity 0.68
Abstract

We construct a family of total Boolean functions $F_{\mathrm{tot}}$ whose randomized and exact quantum query complexities satisfy $R(F_{\mathrm{tot}}) \ge Q_E(F_{\mathrm{tot}})^{2-o(1)}$. Chiruvella, Kayal, Mittal, Paraashar, and Saurabh (2026) also obtained a nearly quadratic separation for total functions in the query model by a different method. For every fixed $\varepsilon \in (0,1)$, we construct a family of partial Boolean functions $F_{\mathrm{par}}$ on $n$ bits satisfying $Q_E(F_{\mathrm{par}})=O_\varepsilon(1)$ and $R(F_{\mathrm{par}})=Ω_\varepsilon(n^{1-\varepsilon})$. This matches the asymptotic separation previously obtained with bounded error (STOC 2021; SICOMP 2023). Lifting yields a family of partial communication functions $G_{\mathrm{par}}$ with $Q_E^{\mathrm{cc}}(G_{\mathrm{par}})=O_\varepsilon(\log n)$ and $R^{\mathrm{pub,cc}}(G_{\mathrm{par}})=Ω_\varepsilon(n^{1-\varepsilon})$, where $n$ is the total number of input bits held by the two parties.

0.13