Search results for "Complexity"
showing 10 items of 1094 documents
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…
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
2007
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
2006
In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.
Span programs for functions with constant-sized 1-certificates
2012
Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…
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).
Enlarging the gap between quantum and classical query complexity of multifunctions
2013
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: Q UD (M′) ≤ N versus C UD (M′) ≥ 3N,…
Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
2001
We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a…
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…
On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.