<p>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 <a href="http://arxiv.org/abs/1101.0523" rel="nofollow">this paper</a> by Klauck for the definition of QCMA communication.</p>

<p>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 <a href="http://arxiv.org/pdf/0911.4007v1.pdf" rel="nofollow">this paper</a>. This will also hold for certain types of entanglement.</p>

CC BY-SA 3.0
2014-03-02T16:21:15.620Z
Thank you.  I had not heard of this aspect.
Dan Stahlke
CC BY-SA 3.0
2014-03-02T20:08:19.910Z
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.)
Robin Kothari
CC BY-SA 3.0
2014-03-03T04:16:17.557Z
@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.
Marcos Villagra
CC BY-SA 3.0
2014-03-03T04:17:20.617Z
or maybe they are the same?
Marcos Villagra
CC BY-SA 3.0
2014-03-25T17:45:07.787Z
@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?
Robin Kothari
CC BY-SA 3.0
2014-06-05T22:05:41.303Z
QCMA should be QMA here, right?
Aram Harrow
CC BY-SA 3.0
2014-03-02T03:44:35.710Z
2014-03-03T04:16:27.710Z
2014-03-03T04:16:27.710Z
Marcos Villagra
<p>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?</p>

<p>The factorization norm bound (also called the $\gamma_2$ bound) I speak of is Theorem 13 of <a href="http://onlinelibrary.wiley.com/doi/10.1002/rsa.20232/abstract">Linial, Shraibman 2008</a>.  In fact, this bound follows from a reduction from quantum communication complexity to the bias in a 2-player XOR game <a href="http://arxiv.org/abs/0804.4859">Degorre, et al. 2008</a>.  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 <a href="http://www.research.rutgers.edu/~troyjlee/grothtalk.pdf">some slides by Troy Lee</a>.</p>

<p>The introduction text of <a href="http://arxiv.org/abs/0910.4266">Jain, Klauck 2010</a> 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.</p>

CC BY-SA 3.0
2014-03-01T19:19:26.490Z
for completeness, can you provide a link to the result ?
Suresh Venkat
CC BY-SA 3.0
2014-03-01T19:57:13.803Z
@SureshVenkat: I've added some links and context.
Dan Stahlke
CC BY-SA 3.0
2014-03-02T16:23:30.707Z
+1. This is exactly the kind of question I wouldn't know where to ask if CSTheory didn't exist.
Robin Kothari
<quantum-information><communication-complexity><norms>
Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?
Dan Stahlke
# Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

(Asked by: username_0 on 2014-03-01)

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](http://onlinelibrary.wiley.com/doi/10.1002/rsa.20232/abstract). 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](http://arxiv.org/abs/0804.4859). 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](http://www.research.rutgers.edu/~troyjlee/grothtalk.pdf).

The introduction text of [Jain, Klauck 2010](http://arxiv.org/abs/0910.4266) 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.

**Tags:** quantum-information, communication-complexity, norms
> **Comments:**
> **username_1**: for completeness, can you provide a link to the result ?  
> **username_0**: @SureshVenkat: I've added some links and context.  
> **username_2**: +1. This is exactly the kind of question I wouldn't know where to ask if CSTheory didn't exist.  

---

## 1 answers

### Answer by username_3 on 2014-03-02. Score: 6 | Accepted answer

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](http://arxiv.org/abs/1101.0523) 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](http://arxiv.org/pdf/0911.4007v1.pdf). This will also hold for certain types of entanglement.

> **Comments:**
> **username_0**: Thank you.  I had not heard of this aspect.  
> **username_2**: 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.)  
> **username_3**: @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.  
> **username_3**: or maybe they are the same?  
> **username_2**: @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?  
> **username_4**: QCMA should be QMA here, right?  

---

