11
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ for completeness, can you provide a link to the result ? $\endgroup$
    – Suresh Venkat
    Commented Mar 1, 2014 at 19:19
  • 1
    $\begingroup$ @SureshVenkat: I've added some links and context. $\endgroup$
    – Dan Stahlke
    Commented Mar 1, 2014 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$
    – Robin Kothari
    Commented Mar 2, 2014 at 16:23

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you. I had not heard of this aspect. $\endgroup$
    – Dan Stahlke
    Commented Mar 2, 2014 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$
    – Robin Kothari
    Commented Mar 2, 2014 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$
    – Marcos Villagra
    Commented Mar 3, 2014 at 4:16
  • $\begingroup$ or maybe they are the same? $\endgroup$
    – Marcos Villagra
    Commented Mar 3, 2014 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$
    – Robin Kothari
    Commented Mar 25, 2014 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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