<p>Ok I believe i found what I was looking for.</p>

<p>In Kremer's Thesis "Quantum Communication" he proves that $Q_{\epsilon}(IP)= \Omega(n)$.</p>

<p>here: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.6636" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.6636</a></p>

<p>page 38.</p>

CC BY-SA 3.0
2012-07-04T06:02:49.553Z
2012-07-04T06:02:49.553Z
MathematicalPhysicist
<p>I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product.</p>

<p>I have Nayak's lower bound, but I am not sure how to use it in the above.</p>

<p>I have that for some encoding $p:n\rightarrow m$ $m\geq n(1-H(p))$, I feel that I need to use this bound here, but I am not sure how.</p>

<p>Any advice?</p>

CC BY-SA 3.0
2012-07-04T06:12:00.243Z
It would be very useful if you mentioned what $Q$ is.
Robin Kothari
CC BY-SA 3.0
2012-07-04T06:20:16.380Z
I guess he is talking about the bound for quantum random access codes.
Joe Fitzsimons
CC BY-SA 3.0
2012-07-05T04:01:13.983Z
I agree with @RobinKothari that it is not clear if you are talking about query-complexity or communication-complexity. You should clarify this in your question and re-tag appropriately. You already found a self-answer for the case of communication complexity. If you are happy with asymptotic statements, then the $\Omega(n)$ lower bound for query-complexity follows trivially from parity.
Artem Kaznatcheev
<quantum-computing><lower-bounds><quantum-information>
Lower bounds on $Q_{\epsilon}(IP)$
MathematicalPhysicist
# Lower bounds on $Q_{\epsilon}(IP)$

(Asked by: username_0 on 2012-07-04)

I want to show that $Q\_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product.

I have Nayak's lower bound, but I am not sure how to use it in the above.

I have that for some encoding $p:n\rightarrow m$ $m\geq n(1-H(p))$, I feel that I need to use this bound here, but I am not sure how.

Any advice?

**Tags:** quantum-computing, lower-bounds, quantum-information
> **Comments:**
> **username_1**: It would be very useful if you mentioned what $Q$ is.  
> **username_2**: I guess he is talking about the bound for quantum random access codes.  
> **username_3**: I agree with @RobinKothari that it is not clear if you are talking about query-complexity or communication-complexity. You should clarify this in your question and re-tag appropriately. You already found a self-answer for the case of communication complexity. If you are happy with asymptotic statements, then the $\Omega(n)$ lower bound for query-complexity follows trivially from parity.  

---

## 1 answers

### Answer by username_0 on 2012-07-04. Score: 0 | Accepted answer

Ok I believe i found what I was looking for.

In Kremer's Thesis "Quantum Communication" he proves that $Q\_{\epsilon}(IP)= \Omega(n)$.

here: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.6636>

page 38.


---

