Search results for "Bounds"
showing 10 items of 298 documents
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…
Rank structured approximation method for quasi--periodic elliptic problems
2016
We consider an iteration method for solving an elliptic type boundary value problem $\mathcal{A} u=f$, where a positive definite operator $\mathcal{A}$ is generated by a quasi--periodic structure with rapidly changing coefficients (typical period is characterized by a small parameter $\epsilon$) . The method is based on using a simpler operator $\mathcal{A}_0$ (inversion of $\mathcal{A}_0$ is much simpler than inversion of $\mathcal{A}$), which can be viewed as a preconditioner for $\mathcal{A}$. We prove contraction of the iteration method and establish explicit estimates of the contraction factor $q$. Certainly the value of $q$ depends on the difference between $\mathcal{A}$ and $\mathcal…
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.
Conditional Random Quantities and Compounds of Conditionals
2013
In this paper we consider finite conditional random quantities and conditional previsions assessments in the setting of coherence. We use a suitable representation for conditional random quantities; in particular the indicator of a conditional event $E|H$ is looked at as a three-valued quantity with values 1, or 0, or $p$, where $p$ is the probability of $E|H$. We introduce a notion of iterated conditional random quantity of the form $(X|H)|K$ defined as a suitable conditional random quantity, which coincides with $X|HK$ when $H \subseteq K$. Based on a recent paper by S. Kaufmann, we introduce a notion of conjunction of two conditional events and then we analyze it in the setting of cohere…
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…