Search results for "Boolean function"
showing 10 items of 38 documents
Precīzie kvantu algoritmi, izmantojot 1-kvantu-vaicājuma izsaukumus
2018
Darbā ir analizēti zināmi unikāli precīzie kvantu algoritmi, kuru īpašības ir atšķirīgas no citiem literatūrā atrodamiem algoritmiem, un uzsākts pētīt iespējas vispārināt šajos algoritmos esošos paņēmienus. Darbā ir noformulēts jauns skaitļošanas modelis, kas ir saistīts ar precīzo kvantu vaicājumu modeli. Veikti skaitliski aprēķini, lai palīdzētu saprast jaunā modeļa iespējas un ierobežojumus. Izteiktas hipotēzes un virzieni, kādos turpināt analīzi un pētījumu.
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory
2007
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…
Quantum Query Complexity of Boolean Functions with Small On-Sets
2008
The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x|f(x) = 1}| or the size of f's on-set. We prove that: (i) For $poly(N)\le M\le 2^{N^d}$ for some constant 0 < d < 1, the upper bound of Q(f) is $O(\sqrt{N\log M / \log N})$. This bound is tight, namely there is a Boolean function f such that $Q(f) = \Omega(\sqrt{N\log M / \log N})$. (ii) For the same range of M, the (also tight) lower bound of Q(f) is $\Omega(\sqrt{N})$. (iii) The average value of Q(f) is bounded from above and below by $Q(f) = O(\log M +\sqrt{N})$ and $Q(f) = \Omega (\log M/\log N+ \sqrt{N…
Complexity of decision trees for boolean functions
2004
For every positive integer k we present an example of a Boolean function f/sub k/ of n = (/sub k//sup 2k/) + 2k variables, an optimal deterministic tree T/sub k/' for f/sub k/ of complexity 2k + 1 as well as a nondeterministic decision tree T/sub k/ computing f/sub k/. with complexity k + 2; thus of complexity about 1/2 of the optimal deterministic decision tree. Certain leaves of T/sub k/ are called priority leaves. For every input a /spl isin/ {0, 1}/sup n/ if any of the parallel computation reaches a priority leaves then its label is f/sub k/ (a). If the priority leaves are not reached at all then the label on any of the remaining leaves reached by the computation is f/sub k/. (a).
Quantum Queries on Permutations with a Promise
2009
This paper studies quantum query complexities for deciding (exactly or with probability 1.0) the parity of permutations of n numbers, 0 through n *** 1. Our results show quantum mechanism is quite strong for this non-Boolean problem as it is for several Boolean problems: (i) For n = 3, we need a single query in the quantum case whereas we obviously need two queries deterministically. (ii) For even n , n /2 quantum queries are sufficient whereas we need n *** 1 queries deterministically. (iii) Our third result is for the problem deciding whether the given permutation is the identical one. For this problem, we show that there is a nontrivial promise such that if we impose that promise to the …
Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
2015
We study the structure of sets \(S\subseteq \{0, 1\}^n\) with small sensitivity. The well-known Simon’s lemma says that any \(S\subseteq \{0, 1\}^n\) of sensitivity \(s\) must be of size at least \(2^{n-s}\). This result has been useful for proving lower bounds on the sensitivity of Boolean functions, with applications to the theory of parallel computing and the “sensitivity vs. block sensitivity” conjecture.
Quantum Identification of Boolean Oracles
2004
The oracle identification problem (OIP) is, given a set S of M Boolean oracles out of 2 N ones, to determine which oracle in S is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to S. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is \(O(\sqrt{N {\rm log} M {\rm log} N}{\rm log log} M)\) for anyS such that M = |S| > N, which is better than the obvious bound N if M \(< 2^{N/log^3 N}\). (ii) It is \…
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.