# Lower bounds on $Q_{\epsilon}(IP)$

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.

• It would be very useful if you mentioned what $Q$ is. – Robin Kothari Jul 4 '12 at 6:12
• 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 Jul 5 '12 at 4:01
In Kremer's Thesis "Quantum Communication" he proves that $Q_{\epsilon}(IP)= \Omega(n)$.