05095nas a2200169 4500008004100000245007900041210006900120260001500189520455700204100001804761700001804779700001804797700002004815700001704835700001604852856005704868 2018 eng d00aCapacity Approaching Codes for Low Noise Interactive Quantum Communication0 aCapacity Approaching Codes for Low Noise Interactive Quantum Com c2018/01/013 a
We consider the problem of implementing two-party interactive quantum
communication over noisy channels, a necessary endeavor if we wish to
fully reap quantum advantages for communication.  
 
For an arbitrary protocol with n messages, designed for
noiseless qudit channels, our main result is a simulation method that fails with probability less than
$2^{-\Theta(n\epsilon)}$ and uses a qudit channel $n(1 + \Theta
(\sqrt{\epsilon}))$ times, of which an $\epsilon$ fraction can be
corrupted adversarially.
 
The simulation is thus capacity achieving to leading order, and
we conjecture that it is optimal up to a constant factor in 
the $\sqrt{\epsilon}$ term.  
 
Furthermore, the simulation is in a model that does not require
pre-shared resources such as randomness or entanglement between the
communicating parties.
 
Surprisingly, this outperforms the best-known overhead of $1 +
O(\sqrt{\epsilon \log \log 1/\epsilon})$ in the corresponding
\emph{classical} model, which is also conjectured to be optimal
     [Haeupler, FOCS'14].
 
Our work also improves over the best previously known quantum result
where the overhead is a non-explicit large constant [Brassard \emph{et
    al.}, FOCS'14] for low $\epsilon$.
1 aLeung, Debbie1 aNayak, Ashwin1 aShayeghi, Ala1 aTouchette, Dave1 aYao, Penghui1 aYu, Nengkun uhttp://acm-stoc.org/stoc2018/STOC-2018-Accepted.html02567nas a2200145 4500008004100000245007800041210006900119260001500188520211000203100001802313700002002331700001702351700001602368856003702384 2016 eng d00aExponential Separation of Quantum Communication and Classical Information0 aExponential Separation of Quantum Communication and Classical In c2016/11/283 a
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its 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, allowing us to simplify further the approach of Rao and Sinha. 
As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
 
 
1 aAnshu, Anurag1 aTouchette, Dave1 aYao, Penghui1 aYu, Nengkun uhttps://arxiv.org/abs/1611.08946