Capacity Approaching Codes for Low Noise Interactive Quantum Communication

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