اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTesting Boolean Functions Properties
115
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis, and shows that van Dams oracle interrogation is essentially
optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.
The relationship between quantum physics and discrete mathematics is reviewed in this article. The Boolean functions unitary representation is considered. The relationship between Zhegalkin polynomial, which defines the algebraic normal form of Boole
an function, and quantum logic circuits is described. It is shown that quantum information approach provides simple algorithm to construct Zhegalkin polynomial using truth table. Developed methods and algorithms have arbitrary Boolean function generalization with multibit input and multibit output. Such generalization allows us to use many-valued logic (k-valued logic, where k is a prime number). Developed methods and algorithms can significantly improve quantum technology realization. The presented approach is the baseline for transition from classical machine logic to quantum hardware.
We study the volatility of the output of a Boolean function when the input bits undergo a natural dynamics. For $n = 1,2,ldots$, let $f_n:{0,1}^{m_n} ra {0,1}$ be a Boolean function and $X^{(n)}(t)=(X_1(t),ldots,X_{m_n}(t))_{t in [0,infty)}$ be a vec
tor of i.i.d. stationary continuous time Markov chains on ${0,1}$ that jump from $0$ to $1$ with rate $p_n in [0,1]$ and from $1$ to $0$ with rate $q_n=1-p_n$. Our object of study will be $C_n$ which is the number of state changes of $f_n(X^{(n)}(t))$ as a function of $t$ during $[0,1]$. We say that the family ${f_n}_{nge 1}$ is volatile if $C_n ra iy$ in distribution as $ntoinfty$ and say that ${f_n}_{nge 1}$ is tame if ${C_n}_{nge 1}$ is tight. We study these concepts in and of themselves as well as investigate their relationship with the recent notions of noise sensitivity and noise stability. In addition, we study the question of lameness which means that $Pro(C_n =0)ra 1$ as $ntoinfty$. Finally, we investigate these properties for a number of standard Boolean functions such as the majority function, iterated 3-majority, the AND/OR function on the binary tree and percolation on certain trees at various levels of the parameter $p_n$.
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : {0,1}^n to {0,1}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic o
bject of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a highlight showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the books chapters.
Boolean networks are discrete dynamical systems for modeling regulation and signaling in living cells. We investigate a particular class of Boolean functions with inhibiting inputs exerting a veto (forced zero) on the output. We give analytical expre
ssions for the sensitivity of these functions and provide evidence for their role in natural systems. In an intracellular signal transduction network [Helikar et al., PNAS (2008)], the functions with veto are over-represented by a factor exceeding the over-representation of threshold functions and canalyzing functions in the same system. In Boolean networks for control of the yeast cell cycle [Fangting Li et al., PNAS (2004), Davidich et al., PLoS One (2009)], none or minimal changes to the wiring diagrams are necessary to formulate their dynamics in terms of the veto functions introduced here.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
