Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
86
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.
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 randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newmans theorem [Inf. Proc. Let.91] in the dependence on the error parameter. 2) Using this we obtain a $(log(n/epsilon^2)+4)$-cost private-coin communication protocol that computes the $n$-bit Equality function, to error $epsilon$. This improves upon the $log(n/epsilon^3)+O(1)$ upper bound implied by Newmans theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.09], up to an additive $loglog(1/epsilon)+O(1)$. In the quantum model, 1) we exhibit a one-way protocol of cost $log(n/epsilon)+4$, that uses only pure states and computes the $n$-bit Equality function to error $epsilon$. This bound was implicitly already shown by Nayak [PhD thesis99]. 2) We show that any $epsilon$-error one-way protocol for $n$-bit Equality that uses only pure states communicates at least $log(n/epsilon)-loglog(1/epsilon)-O(1)$ qubits. 3) We exhibit a one-way protocol of cost $log(sqrt{n}/epsilon)+3$, that uses mixed states and computes the $n$-bit Equality function to error $epsilon$. This is also tight up to an additive $loglog(1/epsilon)+O(1)$, which follows from Alons result. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix. This also implies improved upper bounds on these measures for the distributed SINK function, which was recently used to refute the randomized and quant
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 shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ``unknown shift problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.
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. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
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})$ queries suffice, with a $tilde{O}$ term depending on $k$. We prove a lower bound of $Omega(c^k sqrt{n})$, showing that the complexity of this problem increases exponentially in $k$. This is interesting as a representative example of star-free languages for which a surprising $tilde{O}(sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Second, we consider connectivity problems on directed/undirected grid in 2 dimensions, if some of the edges of the grid may be missing. By embedding the balanced parentheses problem into the grid, we show a lower bound of $Omega(n^{1.5-epsilon})$ for the directed 2D grid and $Omega(n^{2-epsilon})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
