Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-335 | 16th November 2026 16:41

Two-Way Quantum Codes with Optimal Erasure Resilience

RSS-Feed




TR26-335
Authors: Klim Efremenko, Gillat Kol, Sergey Komech, Raghuvansh Saxena, Zhijun Zhang
Publication: 22nd November 2026 15:37
Downloads: 17
Keywords: 


Abstract:

The no-cloning theorem imposes a fundamental limit on quantum error correction. It implies that no code is resilient to a half fraction of adversarial erasures: otherwise, we can clone by decoding from two disjoint halves of the encoding. This argument works because the encoding does not depend on the receiver, allowing the two halves to be decoded by different decoders.

We initiate the study of two-way quantum codes, codes in which the receiver participates in the now-interactive encoding process, and show that interaction substantially improves resilience. Our main result shows that this improvement is achievable even when the receiver’s return channel is purely classical and controlled by the same adversary as the sender’s quantum channel. For this quantum–classical channel, we prove a sharp 3/5 resilience threshold: we design an efficient, constant-rate code over a constant-size alphabet achieving this resilience, and prove that higher resilience is impossible.

We then ask how much more can be gained when the receiver’s return channel is quantum rather than classical. We show that in the quantum–quantum channel, the maximum resilience increases to 2/3. For the more general task of interactive coding, we prove that the optimal erasure resilience is 1/2.



ISSN 1433-8092 | Imprint