arXiv:1307.6738 · ACM-SIAM Symposium on Discrete Algorithms (SODA)

Efficient quantum protocols for XOR functions

Shengyu Zhang

Published Dec 18, 2013• 17 citations

Abstract

We show that for any Boolean function f : {0,1}n → {0,1}, the bounded-error quantum communication complexity Q∊(f ○ ⊕) of XOR functions f(x ⊕ y) satisfies that where d = deg2(f) is the ℱ2-degree of f, and ‖ ‖1,∊ = ming:‖f–g‖∞≤∊ ‖ĝ‖1. This implies that the previous lower bound Q∊(f ○ ⊕) = Ω(log ‖ ‖1,∊) by Lee and Shraibman [LS09] is tight for f with low 2-degree. The result also confirms the quantum version of the Log-rank Conjecture for low-degree XOR functions. In addition, we show that the exact quantum communication complexity satisfies where ‖ ‖0 is the number of nonzero Fourier coefficients of f. This matches the previous lower bound QE(f(x, y)) = Ω(logrank(Mf)) by Buhrman and de Wolf [BdW01] for low-degree XOR functions.

DOI: 10.1137/1.9781611973402.136

Related papers

The one-way communication complexity of the Boolean Hidden Matching Problem

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].

arXiv:quant-ph/0607173Jul 25, 20069 citations

On the communication complexity of XOR functions

Ashley Montanaro, Tobias Osborne

An XOR function is a function of the form g(x,y) = f(x + y), for some boolean function f on n bits. We study the quantum and classical communication complexity of XOR functions. In the case of exact protocols, we completely characterise one-way communication complexity for all f. We also show that, when f is monotone, g's quantum and classical complexities are quadratically related, and that when f is a linear threshold function, g's quantum complexity is Theta(n). More generally, we make a structural conjecture about the Fourier spectra of boolean functions which, if true, would imply that the quantum and classical exact communication complexities of all XOR functions are asymptotically equivalent. We give two randomised classical protocols for general XOR functions which are efficient for certain functions, and a third protocol for linear threshold functions with high margin. These protocols operate in the symmetric message passing model with shared randomness.

arXiv:0909.3392Sep 18, 200944 citations

Lower bounds for quantum communication complexity

Hartmut Klauck

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that \sqrt{\bar{s}(f)/\log n}, for the average sensitivity \bar{s}(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f(x AND y XOR z), where x is a Boolean word held by Alice and y,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(\log n).

arXiv:quant-ph/0106160Jun 28, 200144 citations

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande +1 more

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f:{-1,1}ⁿ → {-1,1} and •:{-1,1}² → {-1,1} the two-party bounded-error quantum communication complexity of (f ∘ •) 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 ∘ •) 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. Razborov (IZV MATH'03) showed that the bounded-error quantum communication complexity of Set-Disjointness is Ω(√n). The BCW simulation yields an upper bound of O(√n log n). Høyer and de Wolf (STACS'02) showed that this can be reduced to c^(log^* n) for some constant c, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is NOR_n ∘ ∧) is O(Q(NOR_n)). Perhaps somewhat surprisingly, we show that when • = ⊕, then the extra log n factor in the BCW simulation is unavoidable. In other words, we exhibit a total function F:{-1,1}ⁿ → {-1,1} such that Q^{cc}(F ∘ ⊕) = Θ(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 •, such that Q^{cc}(F ∘ •) = ω(Q(F)).

arXiv:1909.10428Leibniz international proceedings in informaticsSep 23, 20193 citations

Communication complexity lower bounds by polynomials

Harry Buhrman, Ronald de Wolf

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

arXiv:cs/9910010IEEE Conference on Computational Complexity (CCC)Nov 13, 2002127 citations

Lower bounds for quantum communication complexity

Hartmut Klauck

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by R. Raz (1995) to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other Fourier based lower bound methods, notably showing that /spl radic/(s~(f)/log n) n, for the average sensitivity s~(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f (x/spl and/y/spl oplus/yz), where x is a Boolean word held by Alice and y, z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, only the previously applied general lower bound method based on discrepancy yields bounds that are O(log n).

Annual Symposium on Foundations of Computer ScienceJan 1, 200130 citations