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?

  • 7
    $\begingroup$ It would be very useful if you mentioned what $Q$ is. $\endgroup$ – Robin Kothari Jul 4 '12 at 6:12
  • $\begingroup$ I guess he is talking about the bound for quantum random access codes. $\endgroup$ – Joe Fitzsimons Jul 4 '12 at 6:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev Jul 5 '12 at 4:01

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=

page 38.


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.