As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). Is there any evidence against this bound being tight?

The factorization norm bound (also called the $\gamma_2$ bound) I speak of is Theorem 13 of Linial, Shraibman 2008. In fact, this bound follows from a reduction from quantum communication complexity to the bias in a 2-player XOR game Degorre, et al. 2008. For this reason it could be expected to be a lousy bound since the XOR game doesn't even have anything to do with communication. For the impatient, a brief overview is given in some slides by Troy Lee.

The introduction text of Jain, Klauck 2010 says that information theoretic techniques may offer some competition but it is not known whether these beat the $\gamma_2$ bound. So it would seem that, at least as of a few years ago, $\gamma_2$ was the best technique. But I would like to know if there is even a specific example of a function that is believed to have quantum communication complexity much greater than the $\gamma_2$ bound.

  • $\begingroup$ for completeness, can you provide a link to the result ? $\endgroup$ Mar 1 '14 at 19:19
  • 1
    $\begingroup$ @SureshVenkat: I've added some links and context. $\endgroup$ Mar 1 '14 at 19:57
  • 2
    $\begingroup$ +1. This is exactly the kind of question I wouldn't know where to ask if CSTheory didn't exist. $\endgroup$ Mar 2 '14 at 16:23

I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication.

To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can use the same reduction to an XOR game as in the proof of Theorem 14 of this paper. This will also hold for certain types of entanglement.

  • $\begingroup$ Thank you. I had not heard of this aspect. $\endgroup$ Mar 2 '14 at 16:21
  • $\begingroup$ If the $\gamma_2$ bound lower bounds both quantum communication complexity and QCMA communication complexity, does that mean there's no known separation between the two? (I assume QCMA in communication complexity means Merlin sends Alice a classical proof, and then Alice and Bob can communicate quantumly to decide the answer.) $\endgroup$ Mar 2 '14 at 20:08
  • $\begingroup$ @RobinKothari, yes, that's right. Because QCMA communication cost is lower that BQP communication, we need a QCMA upper bound and a (more tighter) BQP lower bound. $\endgroup$ Mar 3 '14 at 4:16
  • $\begingroup$ or maybe they are the same? $\endgroup$ Mar 3 '14 at 4:17
  • 2
    $\begingroup$ @MarcosVillagra: I don't understand. The complement of Disjointness is in NP, and therefore in QCMA. However, Disjointness (or its complement) has a strong exponential lower bound in quantum communication complexity. Doesn't that separate BQP and QCMA? $\endgroup$ Mar 25 '14 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.