Conclusive Identification Via Noisy Classical Channel: Superactivation and Quantum Advantage

• URL: http://arxiv.org/abs/2604.00089v1
• Date: Tue, 31 Mar 2026 18:02:13 GMT
• Title: Conclusive Identification Via Noisy Classical Channel: Superactivation and Quantum Advantage
• Abstract summary: We show that a noiseless quantum channel of dimension equal to the rank $(mathttS_N) (mathttS_N)$ suffices, yielding a strict quantum advantage whenever $(mathttS_N) (mathttS_N)$.
• Score: 0.5863360388454261
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility [0.0]
  We propose quantum algorithms for the exact simulation of a normalised correlated Gaussian random vector.<n>Motivated by financial applications, we provide an end-to-end resource analysis.
  arXiv  Detail & Related papers  (2026-04-24T11:29:09Z)
• Information storage and transmission under Markovian noise [11.745324895296465]
  We study the information transmission capacities of quantum Markov semigroups $(Psit)_tin mathbbN$ acting on $d-dimensional quantum systems.<n>We show that, in the limit of $tto infty$, the capacities can be efficiently computed in terms of the structure of the peripheral space of $Psi$.<n>We also establish convergence bounds to show that the infinite-time capacities are reached after time $tgtrsim d2ln (d)$.
  arXiv  Detail & Related papers  (2025-04-14T17:27:43Z)
• Quantum Channel Learning [0.0]
  It is shown that a quadratic on $mathcalU$ fidelity can be constructed by considering $sqrtrho(l) to sqrtvarrho(l)$ mapping, and on a quantum channel.<n>The approach can be applied to studying quantum inverse problems, variational quantum algorithms, quantum tomography, and more.
  arXiv  Detail & Related papers  (2024-07-05T10:43:24Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
  arXiv  Detail & Related papers  (2023-11-22T20:27:05Z)
• Monogamy of entanglement between cones [43.57338639836868]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones.<n>Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Dephasing superchannels [0.09545101073027092]
  We characterise a class of environmental noises that decrease coherent properties of quantum channels by introducing and analysing the properties of dephasing superchannels. These are defined as superchannels that affect only non-classical properties of a quantum channel $mathcalE$. We prove that such superchannels $Xi_C$ form a particular subclass of Schur-product supermaps that act on the Jamiolkowski state $J(mathcalE)$ of a channel $mathcalE$ via a Schur product, $J'=J
  arXiv  Detail & Related papers  (2021-07-14T10:10:46Z)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  A general attenuator $Phi_lambda, sigma$ is a bosonic quantum channel that acts by combining the input with a fixed environment state. We show that for any arbitrary value of $lambda>0$ there exists a suitable single-mode state $sigma(lambda)$. Our result holds even when we fix an energy constraint at the input of the channel, and implies that quantum communication at a constant rate is possible even in the limit of arbitrarily low transmissivity.
  arXiv  Detail & Related papers  (2020-03-19T16:50:11Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.