Conclusive Identification Via Noisy Classical Channel: Superactivation and Quantum Advantage
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911558594985984 |
|---|---|
| author | Chattopadhyay, Anushko Ambuj Das, Rakesh Patra, Smritikana Roychowdhury, Chitrak Banik, Manik Mukherjee, Amit |
| author_facet | Chattopadhyay, Anushko Ambuj Das, Rakesh Patra, Smritikana Roychowdhury, Chitrak Banik, Manik Mukherjee, Amit |
| contents | We introduce conclusive identification task for classical channels: a receiver identifies transmitted inputs without error when possible, and responds inconclusively when outputs are ambiguous. For a symmetric not-fully-corrupted channel $N : X \to X$, the single-shot conclusive identification index $\mathrm{ci}_\circ(N)$ counts the maximum number of conclusively identifiable inputs. We show $\mathrm{ci}_\circ(N)$ exhibits a striking superactivation phenomenon: a channel with $\mathrm{ci}_\circ(N) = 0$ achieves $\mathrm{ci}_\circ(N \otimes \mathrm{id}^c_β) = |X|$ when assisted by a perfect classical channel of dimension $β< |X|$. The minimum classical assistance required equals the chromatic number $χ(\mathtt{S}_N)$ of the channel's support graph $\mathtt{S}_N$. We provide channel families where the superactivation gap $\mathrm{ci}_\circ(N \otimes \mathrm{id}^c_β) - \mathrm{ci}_\circ(\mathrm{id}^c_β)$ can be made arbitrarily large. A noiseless quantum channel of dimension equal to the orthogonal rank $ξ(\mathtt{S}_N)$ suffices, yielding a strict quantum advantage whenever $ξ(\mathtt{S}_N) < χ(\mathtt{S}_N)$. This advantage is demonstrated through three explicit constructions motivated by combinatorial and algebraic state-independent, and state-dependent proofs of Kochen-Specker contextuality. Via the co-normal product of graphs, we analyze the scaling of the quantum advantage ratio $χ_f(\mathtt{S}_N)/ξ(\mathtt{S}_N)$, and present a channel for which quantum assistance is exponentially more efficient than classical. Our results establish $\mathtt{S}_N$, rather than the confusability graph $\mathtt{G}_N$, as the natural combinatorial object for conclusive identification, revealing that channels deemed useless under Shannon's zero-error framework can exhibit rich superactivation and quantum advantage, with deep connections to quantum contextuality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_00089 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Conclusive Identification Via Noisy Classical Channel: Superactivation and Quantum Advantage Chattopadhyay, Anushko Ambuj Das, Rakesh Patra, Smritikana Roychowdhury, Chitrak Banik, Manik Mukherjee, Amit Quantum Physics Information Theory We introduce conclusive identification task for classical channels: a receiver identifies transmitted inputs without error when possible, and responds inconclusively when outputs are ambiguous. For a symmetric not-fully-corrupted channel $N : X \to X$, the single-shot conclusive identification index $\mathrm{ci}_\circ(N)$ counts the maximum number of conclusively identifiable inputs. We show $\mathrm{ci}_\circ(N)$ exhibits a striking superactivation phenomenon: a channel with $\mathrm{ci}_\circ(N) = 0$ achieves $\mathrm{ci}_\circ(N \otimes \mathrm{id}^c_β) = |X|$ when assisted by a perfect classical channel of dimension $β< |X|$. The minimum classical assistance required equals the chromatic number $χ(\mathtt{S}_N)$ of the channel's support graph $\mathtt{S}_N$. We provide channel families where the superactivation gap $\mathrm{ci}_\circ(N \otimes \mathrm{id}^c_β) - \mathrm{ci}_\circ(\mathrm{id}^c_β)$ can be made arbitrarily large. A noiseless quantum channel of dimension equal to the orthogonal rank $ξ(\mathtt{S}_N)$ suffices, yielding a strict quantum advantage whenever $ξ(\mathtt{S}_N) < χ(\mathtt{S}_N)$. This advantage is demonstrated through three explicit constructions motivated by combinatorial and algebraic state-independent, and state-dependent proofs of Kochen-Specker contextuality. Via the co-normal product of graphs, we analyze the scaling of the quantum advantage ratio $χ_f(\mathtt{S}_N)/ξ(\mathtt{S}_N)$, and present a channel for which quantum assistance is exponentially more efficient than classical. Our results establish $\mathtt{S}_N$, rather than the confusability graph $\mathtt{G}_N$, as the natural combinatorial object for conclusive identification, revealing that channels deemed useless under Shannon's zero-error framework can exhibit rich superactivation and quantum advantage, with deep connections to quantum contextuality. |
| title | Conclusive Identification Via Noisy Classical Channel: Superactivation and Quantum Advantage |
| topic | Quantum Physics Information Theory |
| url | https://arxiv.org/abs/2604.00089 |