Dave Touchette:Exponential separation quantum communication & classical information complexity

Опубликовано 1 февраля 2017, 1:46

"We show an exponentially large separation between {\em quantum communication
complexity} and {\em classical information complexity} by exhibiting a Boolean
function with such a property. By the link between information and amortized communication, this implies the existence of a task for which the amortized classical communication complexity is exponentially \emph{smaller} than
the quantum communication complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [KLL+12], hence our work implies that these two notions are incomparable.

The function we use to present such a separation is the \textsf{Symmetric $k$-ary Pointer Jumping} function due to Rao and Sinha [RS15b], who used it to show an exponential separation between classical communication complexity and classical information complexity.In this paper, we show that the quantum communication complexity of this problem is polynomially equivalent to the classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence
of round-elimination arguments.

As classical information complexity is an upper bound on {\em quantum information complexity}, which in turn is equal to {\em amortized quantum communication complexity} (Touchette [Tou15]), our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold.

As another application of the techniques that we develop, a simple
proof for an optimal trade-off between Alice's and Bob's communication is given,
even when allowing for pre-shared entanglement, while computing the
related GREATER THAN function on $n$ bits: say Bob communicates at
most $b$ bits, then Alice must send $\frac{n}{2^{O (b)}}$ bits to Bob.
We also present a \emph{classical} protocol achieving this bound."