In this note, we develop a bounded-error quantum algorithm that makes $\tilde O(n^{1/4}\varepsilon^{-1/2})$ queries to a Boolean function $f$, accepts a monotone function, and rejects a function that is $\varepsilon$-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all $\varepsilon = o(1)$. The improvement is cubic when $\varepsilon = 1/\sqrt{n}$.
In this note, we develop a bounded-error quantum algorithm that makes O~(n1/4ε−1/2) queries to a Boolean function f, accepts a monotone function, and rejects a function that is ε-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all ε=o(1). The improvement is cubic when ε=1/n.
Boolean function monotonicity testing requires (almost) n1/2 queries
We show that for any constant c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n1/2−c). This improves the Ω~(n1/3) lower bound of [CWX17] and almost matches the O~(n) upper bound of [KMS18].
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant k-junta testing with high precision can be solved using poly(k) quantum queries, whereas any classical algorithm requires at least kΩ(logk) queries.
The problem of tolerant k-junta testing is as follows: given parameters (k,ε1,ε2), with 0≤ε1<ε2≤1/2, and black-box access to a Boolean function f (defined on n variables), distinguish whether f is ε1-close to some k-junta or ε2-far from every k-junta.
We show the quantum advantage for a range of parameters close to 1/2, for example, ε1=1/2−1/k and ε2=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most ε1 to k-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick k out of n coordinates, and for each fixing of the k coordinates, the 2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to k-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making ko(logk) queries.
We consider the problem of deciding whether an n-qubit unitary (or n-bit Boolean function) is ε1-close to some k-junta or ε2-far from every k-junta, where k-junta unitaries act non-trivially on at most k qubits and as the identity on the rest, and k-junta Boolean functions depend on at most k variables. For constant numbers ε1,ε2 such that 0<ε1<ε2<1, we show the following.1.A non-adaptive O(klogk)-query tolerant (ε1,ε2)-tester for k-junta unitaries when 22ε1<ε2.2.A non-adaptive tolerant (ε1,ε2)-tester for k-junta Boolean functions with O(klogk) quantum queries when 4ε1<ε2.3.A 2O(k)-query tolerant (ε1,ε2)-tester for k-junta unitaries for any ε1,ε2.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.
Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is ε-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or ε-far (0<ε<21) from linear functions requires O(ε−32) many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to O(ε−21) by using the Deutsch-Jozsa and the Grover Algorithms.
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−ε)-approximation using only Oε(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/logn) 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−ε)-approximation using Oε(min{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−ε, the query complexity reduces to Oε,c(logn), yielding an exponential separation from the classical Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.