ﻻ يوجد ملخص باللغة العربية
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum problems. The 3-shift-sum problem is as follows: given a table of $3times n$ elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of $Omega(n^{1/3})$ and $Omega(sqrt n)$, respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant.
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $epsilon$, getting the optimal constant factors in the leading terms in a number of different models. In the ran
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shif
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. pro
We show quantum lower bounds for two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. It has been known that, for any $k$, $tilde{O}(sqrt{n})$