CS Paper Radar

Exact Quantum Algorithms for Composed Boolean Functions

Gagan Chiruvella, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

cs.CC quant-ph ·submitted 2026-11-12 07:24 UTC · v1
theory

Abstract

We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\sqrt2)^{k(1+o(1))}$ queries asymptotically. More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}$ and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with $s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\ldots$. A second construction gives $R \ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. We also allow different inner functions and give analogous quantitative separations in quantum communication.

Closest papers

Nearest neighbours by meaning across the whole index.

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.73
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

Noisy Quantum Query Complexity via Fractional Block Sensitivity

cs.CC quant-ph ·2026-09-30 ·Mehil Agarwal, Shravas Rao, Fang Song
theory similarity 0.71
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

A General Composition Theorem for Approximate Degree

cs.CC quant-ph ·2026-09-24 ·Samruddhi Pednekar, Supartha Podder
theoryhot direction similarity 0.70
Abstract · Added a counterexample to multiplicative composition for exact quantum query complexity

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

0.54

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

cs.CC quant-ph ·2026-10-17 ·Guoliang Xu, Haoran Zhang, Mengfan Wu, Songyao Xue, Mingke Liu
theory similarity 0.70
Abstract

Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

0.06

Separations Between Randomized and Exact Quantum Query Complexity for Boolean Functions

cs.CC quant-ph ·2026-11-16 ·Zekun Ye
similarity 0.70
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

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.69
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

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.69
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

Certification complexity of Boolean functions

cs.CC ·2026-09-22 ·Chandrima Kayal, Sophie Laplante, Émile Larroque, Krišjānis Prūsis, Jevgēnijs Vihrovs
publishedtheory similarity 0.68
Abstract

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

0.28