Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates

• URL: http://arxiv.org/abs/2402.09117v3
• Date: Tue, 04 Feb 2025 12:17:30 GMT
• Title: Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates
• Authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter,
• Abstract summary: We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R,nlog n$ with the block length $n$. We show that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code.
• Score: 49.126395046088014
• License:
• Abstract: Following initial work by JaJa, Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by its output distributions as a subset in the probability simplex. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R\,n\log n$ with the block length $n$, and that the optimal rate $R$ is bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension $d$ of a certain algebraic transformation of the output set: $\frac14 d \leq R \leq \frac12 d$. Remarkably, both the lower and upper Minkowski dimensions play a role in this result. Along the way, we present a "Hypothesis Testing Lemma" showing that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits superactivation: there exist channels whose capacities individually are zero, but whose product has positive capacity. We also generalise these results to classical-quantum channels with finite-dimensional output quantum system, in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

Related papers

• Rate-reliability functions for deterministic identification [49.126395046088014]
  We find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We extend our results to classical-quantum channels and quantum channels with product input restriction.
  arXiv  Detail & Related papers  (2025-02-04T15:09:14Z)
• Resolvability of classical-quantum channels [54.825573549226924]
  We study the resolvability of classical-quantum channels in two settings, for the channel output generated from the worst input, and form the fixed independent and identically distributed (i.i.d.) input. For the fixed-input setting, while the direct part follows from the known quantum soft covering result, we exploit the recent alternative quantum Sanov theorem to solve the strong converse.
  arXiv  Detail & Related papers  (2024-10-22T05:18:43Z)
• General Communication Enhancement via the Quantum Switch [15.779145740528417]
  We conjecture that $mathcalP_n>0$ is both a necessary and sufficient condition for communication enhancement via the quantum $tt SWITCH$. We then formulate a communication protocol involving the quantum $tt SWITCH$ which enhances the private capacity of the BB84 channel.
  arXiv  Detail & Related papers  (2024-07-03T00:47:13Z)
• 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)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• Unital Qubit Queue-channels: Classical Capacity and Product Decoding [4.971638713979981]
  Quantum queue-channels arise naturally in the context of buffering in quantum networks. We show that the upper-bound on the capacity of an additive queue-channel has a simple expression, and is achievable for the erasure and depolarizing channels. Our results provide useful insights towards designing practical quantum communication networks.
  arXiv  Detail & Related papers  (2021-10-06T14:20:00Z)
• 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)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings. We then establish a connection between covert communication and deniability to propose DC-QKE. We present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
  arXiv  Detail & Related papers  (2020-03-25T22:20:47Z)

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.