The Classical Channel

« first day (994 days earlier) ← previous day next day → last day (1233 days later) »

9:49 AM

Hi @Mithrandir24601

10:05 AM

@Mithrandir24601 If you have a chance could you advise on the following. In the [following paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4791) titled "Exponential Separation of Quantum and Classical Communication
Complexity" it states:

> The quantum communication complexity is $\mathcal{O}(\log m)$ and the
> classical communication complexity is $\Omega(m^{1/4}/\log m)$ we hence
> get an exponential gap for the standard communication.

Do you know how *the exponential gap* is defined/shown in this context?

Mithrandir24601

11:03 AM

@JohnDoe Looks like it's the comparison between the log and the $m^{1/4}$ term

Yeah, must be that

if you let $n=\log(m)$, you're comparing $n$ with $e^{n/4}/n$

A bit of plugging stuff into wolfram alpha suggests this is one of those cases where it really only is true in the limit

John Doe

11:46 AM

@Mithrandir24601 Thanks for your response. So since I am working in base $2$ we are comparing $n = \log_2(m)$ to $\frac{2^{\frac{\log_2(m)}{4}}}{\log(m)}$, but if you plug this into wolfram or desmos it shows that in the asymptotic limit $\log_2(m) \geq \frac{2^{\frac{\log_2(m)}{4}}}{\log(m)}$. How does it follow then that there is an exponential gap between the classical and quantum cases?

Mithrandir24601

I'm finding that it's less for $m> 1.3\times 10^{13}$ or so

John Doe

12:08 PM

@Mithrandir24601 I think you might be right, if I plug $m = 2 \times 10^{13}$ into a calculator I also get that $\log_2(m) = 44.185 \leq \frac{2^{\frac{\log_2(m)}{4}}}{\log(m)} = 47.86$. I think desmos probably not good for asymptotic limits.

@Mithrandir24601 Thanks for your assistance, much appreciated.

Mithrandir24601

Yeah, it's just one of these things - it's a theoretically true statement, but practically, when am I going to be transmitting >10^13 bits?

No problem!

« first day (994 days earlier) ← previous day next day → last day (1233 days later) »

all rooms