Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Queries

Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell

Published Jun 9, 2026• 2 citations
Publisher
DOI
10.1145/3798129.3800775

Related papers

Approximating the influence of monotone boolean functions in O(√n) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques•Aug 17, 2011•3 citations

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

Lecture notes in computer science•Jan 1, 2011•4 citations

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries

Chen, Mark, Xi Chen, Hao Xuan Cui +2 more

We show that for any constant $c>0$, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity $Ω(n^{1/2-c})$. This improves the $\tildeΩ(n^{1/3})$ lower bound of [CWX17] and almost matches the $\tilde{O}(\sqrt{n})$ upper bound of [KMS18].

arXiv:2511.04558•Nov 6, 2025•2 citations

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

Xi Chen, Rocco A. Servedio, Li-Yang Tan +1 more

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

arXiv:1706.05556•Leibniz international proceedings in informatics•Jan 1, 2017•1 citation

Testing Classical Properties from Quantum Data

Matthias C. Caro, Naik, Preksha, Joseph Slote

Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.

arXiv:2411.12730•Leibniz international proceedings in informatics•Nov 19, 2024•7 citations

Query Complexity of Boolean Functions on the Middle Slice of the Cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4 more

•Jan 1, 2023•0 citations
Approximating the Influence of Monotone Boolean Functions in O(n)O(\sqrt{n})O(n​) Query Complexity
Boolean function monotonicity testing requires (almost) n1/2n^{1/2}n1/2 queries
We show that for any constant c>0c>0c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n1/2−c)Ω(n^{1/2-c})Ω(n1/2−c). This improves the Ω~(n1/3)\tildeΩ(n^{1/3})Ω~(n1/3) lower bound of [CWX17] and almost matches the O~(n)\tilde{O}(\sqrt{n})O~(n​) upper bound of [KMS18].
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.