Capacity approaching coding for low noise interactive quantum communication

Publication Type:
Conference Proceeding
Citation:
Proceedings of the Annual ACM Symposium on Theory of Computing, 2018, pp. 926 - 939
Issue Date:
2018-06-20
Filename Description Size
stoc18main-p294-p.pdfPublished version1.63 MB
Adobe PDF
Full metadata record
© 2018 Copyright held by the owner/author(s). 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 (where d is arbitrary), our main result is a simulation method that fails with probability less than 2 −Θ (nϵ) and uses a qudit channel n 1 + Θ times, of which an 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 term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O log log ϵ1 in the corresponding 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 et al., FOCS’14] for low .
Please use this identifier to cite or link to this item: