Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Query-to-Communication Lifting for Adversary Bounds
167
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain honest-but-curious model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
rate research
Read More
Buhrman, Cleve and Wigderson (STOC98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) < 2 R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC20) exhibited a total function for which the log n overhead in the BCW simulation is required. We improve upon their result in several ways. We show that the log n overhead is not required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing05). This upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. To prove this, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. In view of our first result, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
Buhrman, Cleve and Wigderson (STOC98) observed that for every Boolean function $f : {-1, 1}^n to {-1, 1}$ and $bullet : {-1, 1}^2 to {-1, 1}$ the two-party bounded-error quantum communication complexity of $(f circ bullet)$ is $O(Q(f) log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. Note that the bounded-error randomized communication complexity of $(f circ bullet)$ is bounded by $O(R(f))$, where $R(f)$ denotes the bounded-error randomized query complexity of $f$. Thus, the BCW simulation has an extra $O(log n)$ factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. H{o}yer and de Wolf (STACS02) showed that for the Set-Disjointness function, this can be reduced to $c^{log^* n}$ for some constant $c$, and subsequently Aaronson and Ambainis (FOCS03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is $mathsf{NOR}_n circ wedge$) is $O(Q(mathsf{NOR}_n))$. Perhaps somewhat surprisingly, we show that when $ bullet = oplus$, then the extra $log n$ factor in the BCW simulation is unavoidable. In other words, we exhibit a total function $F : {-1, 1}^n to {-1, 1}$ such that $Q^{cc}(F circ oplus) = Theta(Q(F) log n)$. To the best of our knowledge, it was not even known prior to this work whether there existed a total function $F$ and 2-bit function $bullet$, such that $Q^{cc}(F circ bullet) = omega(Q(F))$.
Lifting theorems are theorems that relate the query complexity of a function $f:{0,1}^{n}to{0,1}$ to the communication complexity of the composed function $f circ g^{n}$, for some gadget $g:{0,1}^{b}times{0,1}^{b}to{0,1}$. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget $g$. We prove a new lifting theorem that works for all gadgets $g$ that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we significantly increase the range of gadgets for which such lifting theorems hold. Our result has two main motivations: First, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy.
Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity $B(f)$. We investigate its relationship with the usual quantum query complexity $Q(f)$, and show that $B(f)=Theta(Q(f)^2)$. This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on $Q(f)=Theta(sqrt{B(f)})$. We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with $O(n^{1.5})$ quantum query complexity, improving the best known algorithm of $O(n^{1.5}sqrt{log n})$ [arXiv:quant-ph/0606127]. Applying this method to the maximum bipartite matching problem gives an $O(n^{1.75})$ algorithm, improving the best known trivial $O(n^2)$ upper bound.
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many equivalent formulations, and has natural connections to classical lower bounds. A further nice property of the adversary method is that it behaves very well with respect to composition of functions. We generalize the adversary method to include costs--each bit of the input can be given an arbitrary positive cost representing the difficulty of querying that bit. We use this generalization to exactly capture the adversary bound of a composite function in terms of the adversary bounds of its component functions. Our results generalize and unify previously known composition properties of adversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of Barnum and Saks on the quantum query complexity of read-once functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
