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.html