The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance $h$ between two strings of length $n$ is greater than $a$ or less than $b$, where the gap $g=|a-b|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $Ω( \sqrt{n/g})$ on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght $n$. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance h between two strings of length n is greater than a or less than b, where the gap g=∣a−b∣≥1 and a and b could depend on n. In this short note, we give a lower bound of Ω(n/g) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght n. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
Branching programs are quite popular for studying time-space lower bounds. Bera et al. recently introduced the model of generalized quantum branching program aka. GQBP that generalized two earlier models of quantum branching programs. In this work we study a restricted version of GQBP with the motivation of proving bounds on the query-space requirement of quantum-query circuits. We show the first explicit query-space lower bound for our restricted version. We prove that the well-studied ORn decision problem, given a promise that at most one position of an n-sized Boolean array is a 1, satisfies the bound Q2s=Ω(n2), where Q denotes the number of queries and s denotes the width of the GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance; this gives us query-space lower bounds on problems such as Parity and Majority. Our results produce an alternative proof of the Ω(n)-lower bound on the query complexity of any non-constant symmetric Boolean function.
Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDL,Un): Alice and Bob are given binary string of length n and they are guaranteed that Hamming distance between their inputs is either ≤L or ≥U for some L<U. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of GHDL,Un for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O((Us)31⋅nlogn) bits and has one-sided error probability e−s provided s≥U2(L+n10)3. Our second result is about deterministic communication complexity of GHD0,tn. Surprisingly, it can be computed with logarithmic precision: D(GHD0,tn)=n−log2V2(n,⌊2t⌋)+O(logn), where V2(n,r) denotes the size of Hamming ball of radius r. As an application of this result for every c<2 we prove a Ω(pn(2−c)2) lower bound on the space complexity of any c-approximate deterministic p-pass streaming algorithm for computing the number of distinct elements in a data stream of length n with tokens drawn from the universe U={1,2,…,n}. Previously that lower bound was known for c<23 and for c<2 but with larger ∣U∣.
We study the problem of computing the Hamming weight of an n-bit string modulo m, for any positive integer m≤n whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is ⌈n(1−1/m)⌉. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli m) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given n-bit input has Hamming weight 0 modulo m, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For m>2 our lower bound exceeds n/2, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-n input is k or it is l. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of (nk,nl) and sufficiently large n, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of (nk,nl) with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.