Testing Boolean Functions Properties

• URL: http://arxiv.org/abs/2109.06763v2
• Date: Tue, 9 Nov 2021 13:05:28 GMT
• Title: Testing Boolean Functions Properties
• Authors: Zhengwei Xie, Daowen Qiu, Guangya Cai, Jozef Gruska, Paulo Mateus
• Abstract summary: 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 $varepsilon$-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.
• Score: 1.5924410290166868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\varepsilon$-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 $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. 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)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ 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/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.

Related papers

• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-order but smooth objective functions is a computational problem. We show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.
  arXiv  Detail & Related papers  (2023-10-13T14:52:46Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. It takes a $poly(n,frac1epsilonlogfrac1delta)$ time to output the vectors $w$ with Walsh coefficients $S(w)geqepsilon$ with probability at least $1-delta$. In this paper, a quantum algorithm for this problem is given with query complexity $O(fraclogfrac1deltaepsilon4)$, which is independent of $n$.
  arXiv  Detail & Related papers  (2019-12-31T14:52:36Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs. For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
  arXiv  Detail & Related papers  (2019-12-29T01:42:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.