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

Abstract

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}(n)$ 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\left(1+\Theta \left(\sqrt{\epsilon }\right)\right)$ 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., FOCS'14] for low $\epsilon$.

arXiv comment94 pages, 7 figures

References in corpus (8)

• Mixed State Entanglement and Quantum Error Correction
• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Good Quantum Error-Correcting Codes Exist
• The capacity of the noisy quantum channel
• Superadditivity of communication capacity using entangled inputs
• Quantum Channel Capacity of Very Noisy Channels
• Improved Quantum Communication Complexity Bounds for Disjointness and Equality
• Interaction in Quantum Communication