Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets

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 a noiseless qudit channel over a $\mathrm {poly} { \left ({n }\right) }$ size alphabet, our main result is a simulation method that fails with probability less than $2^{-\Theta (n\epsilon)}$ and uses a qudit channel over the same alphabet $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. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al. , SICOMP’19] for low $\epsilon $ .