A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is an $O(k/\sqrtε)$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of $Ω(2^{k/2})$, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity.
We then introduce and study the tolerant version of this problem. That is, determining whether a function is $αε$-close to having Fourier dimension at most $k$, or is $ε$-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a $\tilde{O}(k/ε)$ quantum tester, and a $\tilde{O}(2^{k/2}/ε)$ classical tester.
AI Summary
The paper studies the query complexity of testing whether a Boolean function has Fourier dimension at most $k$, meaning that its Fourier support spans a subspace of dimension at most $k$, versus being $\epsilon$-far from every such function. Equivalently, this tests whether the function is a linear $k$-junta.
For standard testing, it gives a one-sided quantum tester using $O(k/\sqrt{\epsilon})$ queries and proves an $\Omega(k)$ quantum lower bound for fixed $\epsilon<1/4$. Together with the existing classical lower bound $\Omega(2^{k/2})$, this establishes an exponential quantum–classical query separation. A classical tester uses $O(k2^{k/2}/\epsilon)$ queries, matching the exponential dependence of that lower bound up to polynomial factors in $k$.
The quantum algorithm uses Fourier sampling and amplitude amplification to grow the sampled span: an $\epsilon$-far function has at least $2\epsilon$ Fourier mass outside every subspace of dimension at most $k$. The lower bound reduces decision Simon’s problem through random Boolean masking. The classical algorithm detects birthday-scale collisions between tuples of values at randomly shifted inputs.
For tolerant testing—distinguishing distance at most $\alpha\epsilon$ from distance at least $\epsilon$, with fixed $\alpha<1/2$—the query bounds are $\tilde O(k/\epsilon)$ quantumly and $\tilde O(2^{k/2}/\epsilon)$ classically. The classical construction uses a random-linear-compression theorem preserving the minimum probability mass outside $k$-dimensional subspaces to additive accuracy. The tolerant testers require exhaustive subspace searches rather than efficient computation. Extending tolerance to $\alpha\geq1/2$, improving the tolerant quantum dependence on $\epsilon$, and removing its extra logarithmic factor remain open.
No sign of AI-generated textAI use disclosedPossible error
With brief back and forth discussion, the LLM pointed out that instead of using naive Fourier sampling, one could use amplitude amplification to improve the dependence on $\epsilon$ to $\sqrt{\epsilon}$.
Error found: The abstract omits the restriction α<1/2 on tolerant testing, although the paper explicitly leaves the remaining tolerance range open.
The abstract's tolerant query bounds omit polynomial dependence on 1/(1−2α) and therefore are not uniform as α approaches 1/2.
The tolerant quantum soundness proof chooses a Chernoff parameter that fails its required inequality, but halving that parameter repairs the argument without changing the query bound.
The appendix sampling-estimate proof reverses an empirical-minimum comparison, uses the wrong upper-tail threshold, and interchanges inside and outside counts, all repairable within its concentration argument.
The compression-theorem proof incorrectly subtracts an extra β/2 when equating empirical estimators, although correcting the arithmetic still gives the claimed β-error bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
38 pages; small fixes to existing sections, adding new sections on the tolerant version of the problem
A boolean function f has Fourier dimension k if its strings with nonzero Fourier coefficients span a subspace of dimension k. We first consider the property testing task of determining whether a function has Fourier dimension at most k, or is ε-far from being so. We show that there is an O(k/ε)-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of Ω(2k/2), this demonstrates an exponential quantum advantage for this task. We complement this result with a O~(2k/2/ε) classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity.
We then introduce and study the tolerant version of this problem. That is, determining whether a function is αε-close to having Fourier dimension at most k, or is ε-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a O~(k/ε) quantum tester, and a O~(2k/2/ε) classical tester.
The paper studies the query complexity of testing whether a Boolean function has Fourier dimension at most k, meaning that its Fourier support spans a subspace of dimension at most k, versus being ϵ-far from every such function. Equivalently, this tests whether the function is a linear k-junta.
For standard testing, it gives a one-sided quantum tester using O(k/ϵ) queries and proves an Ω(k) quantum lower bound for fixed ϵ<1/4. Together with the existing classical lower bound Ω(2k/2), this establishes an exponential quantum–classical query separation. A classical tester uses O(k2k/2/ϵ) queries, matching the exponential dependence of that lower bound up to polynomial factors in k.
The quantum algorithm uses Fourier sampling and amplitude amplification to grow the sampled span: an ϵ-far function has at least 2ϵ Fourier mass outside every subspace of dimension at most k. The lower bound reduces decision Simon’s problem through random Boolean masking. The classical algorithm detects birthday-scale collisions between tuples of values at randomly shifted inputs.
For tolerant testing—distinguishing distance at most αϵ from distance at least ϵ, with fixed α<1/2—the query bounds are O~(k/ϵ) quantumly and O~(2k/2/ϵ) classically. The classical construction uses a random-linear-compression theorem preserving the minimum probability mass outside k-dimensional subspaces to additive accuracy. The tolerant testers require exhaustive subspace searches rather than efficient computation. Extending tolerance to α≥1/2, improving the tolerant quantum dependence on ϵ, and removing its extra logarithmic factor remain open.
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.
In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}n→{0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O~(k/ε) and time complexity O~(nk/ε). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ε).
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.
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function f, of n variables, is identical with a given function g or is ε-far from g, where ε is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O(ε1). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ(ε1). Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f,g) denote the correlation of f and g. We propose an exact quantum algorithm for making distinction between ∣C(f,g)∣=ε and ∣C(f,g)∣=1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε-far balanced using O(ε1) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function f, of n variables, is identical with a given function g or is ε-far from g, where ε is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O(ε1). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ(ε1). Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f,g) denote the correlation of f and g. We propose an exact quantum algorithm for making distinction between ∣C(f,g)∣=ε and ∣C(f,g)∣=1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε-far balanced using O(ε1) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most k nonzero Fourier coefficients. We give a learner with near-optimal O(k) sample complexity independent of the input length n. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log2k) upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk) by combining known sparse-recovery and lower-bound results.