Search results for " Lower"
showing 10 items of 378 documents
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
2014
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (compl…
Time-Efficient Quantum Walks for 3-Distinctness
2013
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
2014
Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy [7], is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity.
A Polynomial Quantum Query Lower Bound for the Set Equality Problem
2004
The set equality problem is to tell whether two sets A and B are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorphism problem. It was an open problem to find any ω(1) query lower bound when sets A and B are given by quantum oracles. We will show that any error-bounded quantum query algorithm that solves the set equality problem must evaluate oracles \(\Omega(\sqrt[5]{\frac{n}{\ln n}})\) times, where n=|A|=|B|.
Symmetry-assisted adversaries for quantum state generation
2011
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the $backslash$sc Graph Isomorphism problem. We show that for the related problem of $backslash$sc Index Erasure our method leads to a lower bound of $backslash Omega(backslash sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is …
Nonmalleable encryption of quantum information
2008
We introduce the notion of "non-malleability" of a quantum state encryption scheme (in dimension d): in addition to the requirement that an adversary cannot learn information about the state, here we demand that no controlled modification of the encrypted state can be effected. We show that such a scheme is equivalent to a "unitary 2-design" [Dankert et al.], as opposed to normal encryption which is a unitary 1-design. Our other main results include a new proof of the lower bound of (d^2-1)^2+1 on the number of unitaries in a 2-design [Gross et al.], which lends itself to a generalization to approximate 2-design. Furthermore, while in prime power dimension there is a unitary 2-design with =…
On n–Fold Blocking Sets
1986
An n-fold blocking set is a set of n-disjoint blocking sets. We shall prove upper and lower bounds for the number of components in an n-fold blocking set in projective and affine spaces.
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
2017
We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…
Real Line Arrangements and Surfaces with Many Real Nodes
2008
A long standing question is if the maximum number μ(d) of nodes on a surface of degree d in P( ) can be achieved by a surface defined over the reals which has only real singularities. The currently best known asymptotic lower bound, μ(d) 5 12 d, is provided by Chmutov’s construction from 1992 which gives surfaces whose nodes have non-real coordinates. Using explicit constructions of certain real line arrangements we show that Chmutov’s construction can be adapted to give only real singularities. All currently best known constructions which exceed Chmutov’s lower bound (i.e., for d = 3, 4, . . . , 8, 10, 12) can also be realized with only real singularities. Thus, our result shows that, up t…