A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We 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 a $Θ(k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω(2^{k/2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.
A boolean function f has Fourier dimension k if its nonzero Fourier coefficients span a subspace of dimension k. We 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 a Θ(k) quantum property tester for this problem. With Gopalan \etal's classical lower bound of Ω(2k/2) for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a O~(2k/2/ε) classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.
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 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.
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 present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[m] is the fraction of its domain that f maps to j. We give quantum algorithms for testing whether two such distributions are identical or ε-far in L1-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly m quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about m queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.