We consider a superdense coding based quantum communication system utilizing entangled qubits. These qubits are added to and retrieved from a pool of available entangled qubits. In this work, we examine the reliability of such a system with respect to probability of depletion of the entangled qubit budget. Furthermore, we analyze the latency ahead of resuming transmission. Our model and analysis includes specific effects, such as quantum decoherence. Additionally, we compare different approaches for transmission after exhaustion of the entangled qubit budget. Since reliability and latency are essential metrics for quantum communication systems, joint analysis of these in relation to the system parameters is of significant interest. The results presented in this work will help guide quantum communication system designers in making modifications to meet reliability and latency specifications.

We present an information-theoretic framework for secure storage and message identification utilizing fully quantum physically unclonable functions (QPUFs). Extending prior models rooted in classical and hybrid classical-quantum PUFs, we propose a fully quantum setting that enables robust identification protocols in the presence of a powerful quantum wiretapper holding correlated side information. We derive achievable second-order identification rates under stringent privacy leakage constraints and show that secure identification is feasible whenever a positive secret key rate can be extracted from the QPUF output—establishing a quantum analogue of the classical dichotomy theorem. Furthermore, we demonstrate that augmenting the system with an auxiliary public quantum source enhances identification capacity without increasing privacy leakage. Our results provide a rigorous theoretical foundation for quantum-secure identification and storage, with implications for next-generation communication systems and adversarial environments requiring low-latency, energy-efficient quantum-secure storage protocols.

Molecular communication (MC) enables information transfer via molecules, making it ideal for biomedical applications where traditional methods fall short. In many such scenarios, identifying specific events is more critical than decoding full messages, motivating the use of deterministic identification (DI). This paper investigates DI over discrete-time Poisson channels (DTPCs) with inter-symbol interference (ISI), a realistic setting due to channel memory effects. We consider memory scaling as K = 2κ log n, where κ represents the coding rate and n the code length. We improve the known upper bound on DI capacity under power constraints from $\frac{3}{2} + \kappa $ to $\frac{{1 + \kappa }}{2}$. Additionally, we present the first results on deterministic identification with feedback (DIF) in this context, providing a constructive lower bound. These findings enhance the theoretical understanding of MC and support more efficient, feedback-driven biomedical systems.

We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length$n$, controlled by reliability exponents$E_{1}, E_{2}>0$. We find that, in contrast to the case of slowly vanishing errors where the identifiable message length scales as$\Theta(n \log n)$, here linear scaling is restored, now as a function of the reliability exponents. We give upper and lower bounds on the ensuing ratereliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents$E_{1}, E_{2}>0$are bounded below and above in terms of the product of the Minkowski dimension and$\log \min \left\{E_{1}, E_{2}\right\}$. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms.

An information-theoretic analysis of secure authentication based on Quantum Physically Unclonable Functions (QPUF) is presented in this paper. The proposed model employs a secret key generated through QPUF to authenticate pre-enrolled user and device identities while maintaining secrecy and limiting privacy leakage. We analyze the system's robustness against an active adversary who exploits publicly available data to impersonate legitimate users with fraudulent inputs. Our analysis focuses on characterizing the capacity region of the adversary's false acceptance exponent alongside the privacy leakage under reliability conditions. We further demonstrate that the achievable capacity region in the quantum domain surpasses that of classical systems. Additionally, we derive an optimal trade-off among the false acceptance exponent, public storage rate, and privacy leakage rate, offering key insights into the system's asymptotic performance.

Physical Unclonable Functions (PUFs) have emerged as a powerful cryptographic tool for various applications due to their inherent physical uniqueness and unclonability. However, the advent of quantum computers has posed significant threats to classical PUFs. In response, Quantum PUFs (QPUFs), which exploit the principles of quantum mechanics, have been introduced as a robust alternative. This paper analyzes two key applications of QPUFs utilizing their distinctive output: secure storage and identification, from an information theoretic perspective. We establish achievability under different constraints and derive the secure storage capacity and a doubly exponential identification rate, even in the presence of an active adversary attempting to deceive the system by exploiting publicly stored data. We further demonstrate that within the quantum domain, we achieve higher rates compared to classical counterparts.

Many communication applications incorporate eventtriggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon's message transmission paradigm we achieved completely different capacity scaling for deterministic identification codes for all relevant fading channels.

This paper explores communication over a twosender, two-receiver classical interference channel, enhanced by the availability of entanglement resources between transmitters. The central contributions are an inner and outer bound on the capacity region for a general interference channel with entangled transmitters. It addresses the persistent challenge of the lack of a general capacity formula, even in the purely classical case, and highlights the striking similarities in achievable rate expressions when assessing quantum advantages. Through a concrete example, it is shown that entanglement can significantly boost performance in certain types of channels.

We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.

This work introduces a Quantum PUF (QPUF)-based approach to enhance cryptographic key generation and secure storage. An information-theoretic model is developed to analyze trade-offs between key generation, secure storage, and privacy leakage under unconditional and conditional secrecy constraints. Additionally, the use of shared private keys is explored to achieve zero privacy leakage. The results extend classical and classical-quantum findings to the fully quantum regime, to provide a pathway toward robust authentication and data security and offering a foundation for next-generation hardware security.

Stochastic network codes for consensus testing (CT) via a relay are proposed, where each of two or more parties knows a message and can find out if all these messages are equal, e.g. as an integrity check in a decentralized storage system or the control of mobile autonomous robots. The proposed codes achieve the CT capacity for memoryless uplinks channels when common randomness (CR) is available and no local randomness is used. With only local randomness at the edge nodes, upper and lower bounds for the capacity are given. The lower bound is achieved by CR generation via decode-and-forward transmission, and then using a common-randomness (CR)-assisted code. The upper bound is imposed by the CT over the uplink, when this consists of independent parallel channels to the relay. A recent derandomization result for encoders shows that, unlike deterministic encoding and CR shared between both encoders, the use of local randomness prevents the relay from successfully testing consensus. Therefore, in the proposed coding scheme, the relay recodes only to transmit random seeds and message hashes generated with these seeds. This scheme relies on an underlying CT code based on almost-universal hashing, where hashing is done with random seeds.

The understanding of achievable rates for quantum identification is far behind that of quantum transmission, as well as classical identification and transmission. Notably, in the classical case, common randomness shared between Alice and Bob before communication begins can greatly enhance the identification capacity. In the quantum regime, pre-shared entanglement may have an even more profound impact on the quantum identification (ID) capacity. This paper presents a regularized expression for the quantum ID capacity with entanglement assistance and demonstrates how it grows with the entanglement rate. Additionally, we provide deeper insights into the nature of quantum ID capacity. Interestingly, while the classical ID capacity becomes unbounded with unlimited common randomness, we find that the quantum ID capacity remains bounded even with unlimited entanglement assistance. Additionally, we find that entanglement plays the same role as an additional noiseless channel that is amortized, i.e., only used to make the rate positive.

We investigate the Han-Kobayashi rate region (HK-region) for a two-user interference channel (IC) in the presence of entangled transmitters. Our approach begins with an analysis of a three-user multiple access channel (MAC) where the transmitters share quantum entanglement. Building on these results, we extend our findings to the interference channel scenario. Our results demonstrate that sharing a maximally entangled state between the transmitters can significantly expand the Han-Kobayashi rate region.

This paper investigates secure communication over a broadcast channel in the presence of an unreliable cooperation link between the two decoders. Two messages are sent over the channel. One receiver aims to decode both messages while ensuring that the second message remains confidential from the other receiver. The second receiver is only interested in the first message, decoding either a part of it when the cooperation link fails or the entire message when the link is operational. A communication scheme is proposed that ensures reliability, confidentiality, and robustness against potential link failures. The capacity regions are characterized for both the discrete memoryless and the Gaussian version of the channel. Additionally, several notable special cases of the problem are examined.

In this paper, we derive the second-order coding rates for message identification via simple-dispersion discrete memoryless channels (DMCs) with noiseless feedback, both for deterministic and randomized encoding. Identification via channels, originally introduced by Ahlswede and Dueck, differs fundamentally from traditional message transmission: instead of decoding a specific message from multiple possibilities, the receiver seeks only to determine if a particular message was sent. Previous research established that feedback significantly enhances identification capacity, a stark contrast to the message transmission scenario. While second-order expansions are extensively studied for transmission, analogous results for identification remain largely unexplored. Our results generalize classical identification proofs by carefully modifying the standard two-phase codebook construction, previously reliant on typical sequences, thus making it suitable for second-order analysis. Additionally, we generalize the established converse argument and use martingale-based methods to obtain a tight second-order converse.

Physically Unclonable Functions (PUFs) have emerged as critical primitives for secure authentication and key generation. However, classical PUFs are increasingly vulnerable to machine learning and quantum-enabled attacks. Quantum PUFs, leveraging the principles of quantum mechanics, provide a promising alternative offering information-theoretic security. In this work, we present an information-theoretic framework for two key applications of QPUFs: secret key generation and secure data storage. We rigorously characterize the trade-offs between achievable key and storage rates under various privacy leakage constraints—unconditional, conditional, and zero-leakage—extending classical results into the quantum domain. We derive single-letter capacity expressions based on Holevo information and analyze the impact of shared private randomness on achieving zero privacy leakage. Our results establish fundamental performance limits for QPUF-based security systems and lay the foundation for cryptographic key generation and storage protocols in future quantum-resilient communication infrastructures.

We introduce the concept of locally homomorphic channels (LHCs) as a framework for analyzing the composition and decomposition of channels that simulate functions. We establish an equivalence between a specific class of LHCs and function computation codes for noisy channels. Further, we show for LHCs composed of multiple parts, e.g., an encoder, a noisy channel, and a decoder, that each component is independently locally homomorphic. A key implication is that stochastic decoding offers only very limited improvements in reliability. In scenarios where two messages from a large set are encoded independently, such as in K-identification, we prove that, in general, at most one of the encoders can compress the messages to logarithmic size. This result has significant consequences: for instance, it implies that consensus testing (CT) over discrete memoryless multiple-access channels becomes impossible when the message set has double-exponential size. In contrast, independent encoders can be reliable in such a setting, when the number of messages is only exponential. We demonstrate this for the example of deterministic consensus testing over a pair of binary symmetric channels.

We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length n, controlled by reliability exponents E1,E2≥ 0. In contrast to the regime of slowly vanishing errors, where the identifiable message length scales linearithmically as Θ(n log n), here we find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We give upper and lower bounds on the ensuing rate-reliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents E1,E2> 0 can be expanded in leading order as the product of the Minkowski dimension of a certain parametrisation the channel output set and log min{E1,E2}. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms. We also show that even if only one of the two errors is required to be exponentially small, the linearithmic scaling is lost. We further illustrate our results with a discussion of the case of dimension zero, and extend them to classical-quantum channels and quantum channels with tensor product input restriction.

Many communication applications incorporate event-triggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the slow and fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon’s message transmission paradigm we achieved completely different message set scaling for deterministic identification codes for all relevant fading channels.

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:$\frac {1}{4} d \leq R \leq \frac {1}{2} 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.

We investigate the problem of generating common randomness (CR) from a finite compound source aided by unidirectional communication over a rate-limited perfect channel. The two communicating parties observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with high probability for every possible state. Both parties know the set of source states as well as their statistics. However, they don’t know the actual state. We establish a single-letter formula for the compound CR capacity in the presence of communication over the channel and study key properties of the compound CR capacity: superadditivity, concavity, and continuity. We also consider the case where there is no communication between the terminals, and only the source outputs observed by the terminal at the receiving end of the perfect channel are state-dependent. In this setting, we establish single-letter bounds on the compound CR capacity. The single-letter lower bound is derived under the assumption that the source distributions are pairwise distinct for all states. Finally, within the same setting, we propose a CR generation scheme for a two-state binary source example. Notably, this scheme does not depend on the previously mentioned assumption.

Communication over a classical multiple-access channel (MAC) with entanglement resources is considered, whereby two transmitters share entanglement resources a priori before communication begins. Leditzky et al. (2020) presented an example of a classical MAC, defined in terms of a pseudo telepathy game, such that the sum rate with entangled transmitters is strictly higher than the best achievable sum rate without such resources. Here, we establish inner and outer bounds on the capacity region for the general MAC with entangled transmitters, and show that the previous result can be obtained as a special case. It has long been known that the capacity region of the classical MAC under a message-average error criterion can be strictly larger than with a maximal error criterion (Dueck, 1978). We observe that given entanglement resources, the regions coincide. Furthermore, we address the combined setting of entanglement resources and conferencing, where the transmitters can also communicate with each other over rate-limited links. Using superdense coding, entanglement can double the conferencing rate.

In this work, we present two new methods for Variational Quantum Circuit (VQC) Process Tomography onto n qubits systems: PT_VQC and U-VQSVD.Compared to the state of the art, PT_VQC halves in each run the required amount of qubits for process tomography and decreases the required seed states from 4nto 2n, ensuring high-fidelity reconstruction of the targeted unitary U. It is worth noting that, for a fixed reconstruction accuracy, PT_VQC achieves faster convergence per iteration compared to Quantum Deep Neural Network (QDNN) and tensor network schemes.U-VQSVD utilizes variational singular value decomposition to extract eigenvectors (up to a global phase) and their associated eigenvalues from an unknown unitary representing a general channel. We assess the performance of U-VQSVD by executing an attack on a non-unitary channel Quantum Physical Unclonable Function (QPUF), outperforming an uninformed impersonation attack by a factor of 2 to 5, depending on the qubit dimension.For the two presented methods, we propose a new approach to calculate the complexity of the displayed VQC, based on what we denote as optimal depth.

This paper introduces several techniques for minimal trellis construction for degenerate decoding of quantum stabilizer codes, specifically the minimal multi-goal trellis for the cosets of the stabilizer group S in the normalizer group N. The methods include a merging algorithm, a Shannon-product approach, and the BCJR-Wolf method. The study establishes the necessary properties of multi-goal trellises and bounds on the decoding complexity of the minimal multi-goal trellis using the sum-product Viterbi algorithm. The proposed multi-goal trellises decrease the decoding complexity by a factor O(n), where n is the code length.

In contrast to Shannon transmission codes, the size of identification (ID) codes for discrete memoryless channels (DMCs) experiences doubly exponential growth with the block length when randomized encoding is used. Additional enhancements within the ID paradigm can be realized through supplementary resources such as quantum entanglement, common randomness (CR), and feedback. Joint transmission and sensing demonstrate significant benefits over separation-based methods. Inspired by the significant impact of feedback on the ID capacity, our work delves into the realm of joint ID and sensing (JIDAS) for state-dependent multiple access channels (SD-MACs) with noiseless strictly casual feedback. Here, the senders aim to convey ID messages to the receiver while simultaneously sensing the channel states. We establish a lower bound on the capacity-distortion region of the SD-MACs. An example shows that JIDAS outperforms the separation-based approach.

Motivated by deterministic identification via channels, where the encoder cannot use randomisation, we revisit the problem of identification via quantum channels with the additional restriction that the message encoding must use pure quantum states, rather than general mixed states. Together with the previously considered distinction between simultaneous and general decoders, this suggests a two-dimensional spectrum of different identification capacities, whose behaviour could a priori be very different. We demonstrate two new main results: first, we show that all of the four combinations (pure/mixed encoder, simultaneous/general decoder) have a double-exponentially growing code size, and that indeed the corresponding identification capacities are lower bounded by the classical transmission capacity for a general quantum channel, which is given by the Holevo-Schumacher- Westmoreland theorem. Secondly, we show that the simultaneous identification capacity of a quantum channel equals the simultaneous identification capacity with pure state encodings, thus leaving three linearly ordered identification capacities. By considering some simple examples we finally show that these three are all different: general identification capacity can be larger than pure-state-encoded identification capacity which in turn can be larger than pure-state-encoded simultaneous identification capacity,

Following initial work by JaJa, and 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 (the closure of) the subset of its output distributions in the probability simplex. Our main findings are that the maximum number of messages thus identifiable scales super-exponentially as$2^{Rn\log n}$with the block length$n$, and that the optimal rate$R$is upper and lower bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension$d$of a certain algebraic transformation of the output set:$\frac{1}{4}d\leq R\leq\frac{1}{2}d$, Along the way, we present a Hypothesis Testing Lemma that shows 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 super-activation: there exist channels whose capacity is zero, but whose product has positive capacity. These results are then generalised to classical-quantum channels with finite-dimensional output quantum system (but arbitrary input alphabet), and in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.

Physical Unclonable Functions (PUFs) are hardware devices with the assumption of possessing inherent, non-clonable physical randomness which leads to unique pairs of inputs and outputs that provide a secure fingerprint for cryptographic protocols like Authentication. In the case of quantum PUFs (QPUFs), the input-output pairs consists of quantum states instead of classical bitstrings, offering advantages over classical PUFs (CPUFs) such as challenge reusability via public channels and non-reliance over any trusted party due to the no-cloning theorem. In recent literature, a generalized mathematical frame-work for studying QPUFs was developed, which paved the way for having QPUF models with provable security. It was proved that existential unforgeability against Quantum Polynomial Time (QPT) adversaries cannot be achieved by any random unitary QPUF. Since measurements are non-unitary quantum processes, we define a QPUF based on random von Neumann measurements. We prove that such a QPUF is existentially unforgeable. Thus, we introduce the first model in existing literature that depicts such a high level of provable security. We also prove that the Quantum Phase Estimation (QPE) protocol applied on a Haar random unitary serves as an approximate implementation for this kind of QPUF as it approximates a von Neumann measurement on the eigenbasis of the unitary.

An information-theoretic model is presented for a general quantum physically unclonable function (QPUF) that generates a bipartite classical-quantum output. We first define achievable secret key rate versus privacy leakage rate pairs featuring perfect secrecy and uniform distribution of the secret key. To analyze the secret key generation from this QPUF model, we focus on two cases: first, without any constraints on the storage of public information, i.e., the helper data, and second, with rate constraints on it. This, in turn, provides a solution for the case of privacy leakage constraint. We calculate the maximum secret key that a QPUF can generate and derive the capacity region corresponding to this definition of achievability.

Many communication applications are event-triggered, but current applications still use the Shannon communication model to transmit and decode messages. Due to the ever-growing number of users in communication networks, this leads to a weakening of performance. To counteract this, it makes sense to use post-Shannon methods such as deterministic identification (DI) codes. The information theory analysis carried out so far has shown how performance can be increased through DI codes. In this paper we provide a new constructive proof of the capacity of deterministic identification codes for discrete memoryless channels (DMC), while so far only existence proofs exist. Based on this idea, we implement DI codes of finite length and analyze their performance both analytically and experimentally. For the latter, we build a prototype using software-defined radios and a noise generator.

We investigate message identification over a K-sender Gaussian multiple access channel (K-GMAC). Unlike conventional Shannon transmission codes, the size of randomized identification (ID) codes experiences a doubly exponential growth in the code length. Improvements in the ID approach can be attained through additional resources such as quantum entanglement, common randomness (CR), and feedback. It has been demonstrated that an infinite capacity can be attained for a single-user Gaussian channel with noiseless feedback, irrespective of the chosen rate scaling. We establish the capacity region of both the K-sender Gaussian multiple access channel (K-GMAC) and the K-sender state-dependent Gaussian multiple access channel (K-SD-GMAC) when strictly causal noiseless feedback is available.

We investigate the problem of message transmission and the problem of common randomness (CR) generation over single-user multiple-input multiple-output (MIMO) slow fading channels with average input power constraint, additive white Gaussian noise (AWGN), arbitrary state distribution and with complete channel state information available at the receiver side (CSIR). We derive a lower and an upper bound on the outage transmission capacity of MIMO slow fading channels for arbitrary state distribution and show that the bounds coincide except possibly at points of discontinuity of the outage transmission capacity, of which there are, at most, countably many. Such discontinuity issues might occur because the channel state distribution is arbitrary. We also establish the capacity of a specific compound MIMO Gaussian channel in order to prove the lower bound on the outage transmission capacity. Furthermore, we define the outage CR capacity for a two-source model with unidirectional communication over a MIMO slow fading channel with arbitrary state distribution and establish a lower and an upper bound on it using our bounds on the outage transmission capacity of the MIMO slow fading channel.

Deterministic K-Identification (DKI) for the binary symmetric channel (BSC) is developed. A full characterization of the DKI capacity for such a channel, with and without the Hamming weight constraint, is established. As a key finding, we find that for deterministic encoding the number of identifiable messages$K$may grow exponentially with the codeword length$n$, i.e.,$K\ =\ 2^{\kappa n}$, where$\kappa$is the target identification rate. Furthermore, the eligible region for$\kappa$as a function of the channel statistics, i.e., the crossover probability, is determined.

Nearest-neighbour clustering is a powerful set of heuristic algorithms that find natural application in the decoding of signals transmitted using the$M$-Quadrature Amplitude Modulation ($M$-QAM) protocol. Lloyd et al. proposed a quantum version of the algorithm that promised an exponential speedup. We analyse the performance of this algorithm by simulating the use of a hybrid quantum-classical implementation of it upon 16-QAM and experimental 64-QAM data. We then benchmark the implementation against the classical k-means clustering algorithm. The choice of quantum encoding of the classical data plays a significant role in the performance, as it would for the hybrid quantum-classical implementation of any quantum machine learning algorithm. In this work, we use the popular angle embedding method for data embedding and the swap test for overlap estimation. The algorithm is emulated in software using Qiskit and tested on simulated and real-world experimental data. The discrepancy in accuracy from the perspective of the induced metric of the angle embedding method is discussed, and a thorough analysis regarding the angle embedding method in the context of distance estimation is provided. We detail an experimental optic fibre setup as well, from which we collect 64-QAM data. This is the dataset upon which the algorithms are benchmarked. Finally, some promising current and future directions for further research are discussed.

Communication over a classical multiple-access channel (MAC) with quantum entanglement resources is considered, whereby two transmitters share entanglement resources a priori. Leditzky et al. (2020) presented an example, defined in terms of a pseudo telepathy game, such that the sum rate with entangled transmitters is strictly higher than the best achievable sum rate without such resources. Here, we establish inner and outer bounds on the capacity region for the general MAC with entangled transmitters, and show that the previous result can be obtained as a special case. It has long been known that the capacity region of the classical MAC under a message-average error criterion can be strictly larger than with a maximal error criterion (Dueck, 1978). We observe that given entanglement resources, the regions coincide.

We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.

Several applications of molecular communications (MC) feature an alarm-prompt behavior for which the prevalent Shannon capacity may not be the appropriate performance metric. The identification capacity as an alternative measure for such systems has been motivated and established in the literature. In this paper, we study deterministic identification (DI) for the discrete-time Poisson channel (DTPC) with intersymbol interference (ISI) where the transmitter is restricted to an average and a peak molecule release rate constraint. Such a channel serves as a model for diffusive MC systems featuring long channel impulse responses and employing molecule counting receivers. We derive lower and upper bounds on the DI capacity of the DTPC with ISI when the number of ISI channel taps$K$may grow with the codeword length$n$(e.g., due to increasing symbol rate). As a key finding, we establish that for deterministic encoding, the codebook size scales as$2^{(n\log n)R}$assuming that the number of ISI channel taps scales as$K=2^{\kappa\log n}$, where$R$is the coding rate and$\kappa$is the ISI rate. Moreover, we show that optimizing$\kappa$leads to an effective identification rate [bits/s] that scales linearly with$n$, which is in contrast to the typical transmission rate [bits/s] that is independent of$n$.

We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].

In the identification (ID) scheme proposed by Ahlswede and Dueck, the receiver only checks whether a message of special interest to him has been sent or not. In contrast to Shannon transmission codes, the size of ID codes for a Discrete Memoryless Channel (DMC) grows doubly exponentially fast with the blocklength, if randomized encoding is used. This groundbreaking result makes the ID paradigm more efficient than the classical Shannon transmission in terms of necessary energy and hardware components. Further gains can be achieved by taking advantage of additional resources such as feedback. We study the problem of joint ID and channel state estimation over a DMC with independent and identically distributed (i.i.d.) state sequences. The sender simultaneously sends an ID message over the DMC with a random state and estimates the channel state via a strictly causal channel output. The random channel state is available to neither the sender nor the receiver. For the proposed system model, we establish a lower bound on the ID capacity-distortion function.

An upper bound to the identification capacity of discrete memoryless wiretap channels is derived under the requirement of semantic effective secrecy, combining semantic secrecy and stealth constraints. A previously established lower bound is improved by applying it to a prefix channel, formed by concatenating an auxiliary channel and the actual channel. The bounds are tight if the legitimate channel is more capable than the eavesdropper’s channel. An illustrative example is provided for a wiretap channel that is composed of a point-to-point channel, and a parallel, reversely degraded wiretap channel. A comparison with results for message transmission and for identification with only secrecy constraint is provided.

Deterministic identification over K-input multiple-access channels with average input cost constraints is considered. The capacity region for deterministic identification is determined for an average-error criterion, where arbitrarily large codes are achievable. For a maximal-error criterion, upper and lower bounds on the capacity region are derived. The bounds coincide if all average partial point-to-point channels are injective under the input constraint, i.e. all inputs at one terminal are mapped to distinct output distributions, if averaged over the inputs at all other terminals. The achievability is proved by treating the MAC as an arbitrarily varying channel with average state constraints. For injective average channels, the capacity region is a hyperrectangle. The modulo-2 and modulo-3 binary adder MAC are presented as examples of channels which are injective under suitable input constraints. The binary multiplier MAC is presented as an example of a non-injective channel, where the achievable identification rate region still includes the Shannon capacity region.

The Binomial channel serves as a fundamental model for molecular communication (MC) systems employing molecule-counting receivers. Here, deterministic identification (DI) is addressed for the discrete-time Binomial channels (DTBC), subject to an average and a peak constraint on the molecule release rate. We establish that the number of different messages that can be reliably identified for the DTBC scales as 2(n log n)R, where n and R are the codeword length and coding rate, respectively. Lower and upper bounds on the DI capacity of the DTBC are developed.

Deterministic K-identification (DKI) is addressed for Gaussian channels with slow fading (GSF), where the transmitter is restricted to an average power constraint and channel side information is available at the decoder. We derive lower and upper bounds on the DKI capacity when the number of identifiable messages K may grow sub-linearly with the codeword length n. As a key finding, we establish that for deterministic encoding, assuming that the number of identifiable messages K = 2κ log nwith κ ∈ [0, 1) being the identification target rate, the codebook size scales as 2(n log n)R, where R is the coding rate.

Over the past decades, the problem of communication over finite-state Markov channels (FSMCs) has been investigated in many works and the capacity of FSMCs has been studied in closed form under the assumption of the availability of partial/complete channel state information at the sender and/or the receiver. In our work, we focus on infinite-state Markov channels by investigating the problem of message transmission over time-varying single-user multiple-input multiple-output (MIMO) Gauss-Markov Rayleigh fading channels, as an example of MIMO ergodic Rayleigh fading channels, with average power constraint and with complete channel state information available at the receiver side (CSIR). We prove a single-letter formula for the channel capacity and in particular the formula pointed out by Telatar for the channel capacity of MIMO ergodic Rayleigh fading channels for the case when the Gaussian noise is uncorrelated across antennas.

Entanglement resources can increase transmission rates substantially. Unfortunately, entanglement is a fragile resource that is quickly degraded by decoherence effects. In order to generate entanglement for optical communication, the transmitter and the receiver first prepare entangled spin-photon pairs locally, and then the photon at the transmitter is sent to the receiver through an optical fiber or free space. Without feedback, the transmitter does not know whether the entangled photon has reached the receiver. The present work introduces a new model of unreliable entanglement assistance, whereby the communication system operates whether entanglement assistance is present or not. While the sender is ignorant, the receiver knows whether the entanglement generation was successful. In the case of a failure, the receiver decodes less information. In this manner, the effective transmission rate is adapted according to the assistance status. Regularized formulas are derived for the classical and quantum capacity regions with unreliable entanglement assistance, characterizing the tradeoff between the unassisted rate and the excess rate that can be obtained from entanglement assistance. It is further established that time division between entanglement-assisted and unassisted coding strategies is optimal for the noiseless qubit channel, but can be strictly suboptimal for a noisy channel.

The identification capacity region of the compound broadcast channel is determined under an average error criterion, where the sender has no channel state information. We give single-letter identification capacity formulas for discrete channels and multiple-input multiple-output Gaussian channels under an average input constraint. The capacity theorems apply to general discrete memoryless broadcast channels. This is in contrast to the transmission setting, where the capacity is only known for special cases, notably the degraded broadcast channel and the multipleinput multiple-output broadcast channel with private messages. Furthermore, the identification capacity region of the compound multiple-input multiple-output broadcast channel can be larger than the transmission capacity region. This is a departure from the single-user behavior of identification, since the identification capacity of a single-user channel equals the transmission capacity.

We analyze deterministic message identification via channels with non-discrete additive white noise and with a noiseless feedback link under both average power and peak power constraints. The identification task is part of Post Shannon Theory. The consideration of communication systems beyond Shannon’s approach is useful in order to increase the efficiency of information transmission for certain applications. We propose a coding scheme that first generates infinite common randomness between the sender and the receiver. If the channel has a positive message transmission feedback capacity, for given error thresholds and sufficiently large blocklength this common randomness is then used to construct arbitrarily large deterministic identification codes. In particular, the deterministic identification feedback capacity is infinite regardless of the scaling (exponential, doubly exponential, etc.) chosen for the capacity definition. Clearly, if randomized encoding is allowed in addition to the use of feedback, these results continue to hold.

We consider a decision problem associated to the task of estimating the state of a dynamic plant remotely via a noisy communication channel: given the characteristics of some unstable linear time-invariant (LTI) plant and some discrete memoryless channel (DMC), does there exist an encoder/decoder pair that allows for the remote tracking of the plant’s state with bounded error? Questions of this kind are becoming increasingly important in communication technologies, since future communication networks are expected to incorporate distributed control and decision-making. Analytically, this problem has been shown to involve the zero-error capacity of the DMC. Starting from this result, we approach the problem from the view of theoretical computer science, with an explicit treatment of the underlying machine Model. In particular, we prove that for every pair of a finite channel input alphabet and a finite channel output alphabet, there exists a Blum-Shub-Smale (BSS) algorithm that computes the zero-error capacity in dependence of the channel matrix. Based on this, we devise a BSS algorithm that solves the above decision problem given the plant’s and DMC’s characteristics. BSS machines are a promising candidate for a universal model of real number processing hardware, comparable to the Turing machine in the digital domain. Recently, we observe an increased interest in research and development towards real number and/or analog computing hardware, usually referred to by the term "neuromorphic computing".

The identification (ID) capacity region of the compound broadcast channel is determined under an average error criterion, where the sender has no channel state information. We give single-letter ID capacity formulas for discrete channels and MIMO Gaussian channels, under an average input constraint. The capacity theorems apply to general broadcast channels. This is in contrast to the transmission setting, where the capacity is only known for special cases, notably the degraded broadcast channel and the MIMO broadcast channel with private messages. Furthermore, the ID capacity region of the compound MIMO broadcast channel is in general larger than the transmission capacity region. This is a departure from the single-user behavior of ID, since the ID capacity of a single-user channel equals the transmission capacity.

The channel reliability function is an important tool that characterizes the reliable transmission of messages over communication channels. For many channels, only upper and lower bounds of the function are known. We analyze the computability of the reliability function and its related functions. We show that the reliability function is not a Turing computable performance function. The same also applies to the functions of the sphere packing bound and the expurgation bound. Furthermore, we show that the R∞function is not Banach Mazur computable and additive.

We investigate the problem of message transmission over time-varying single-user multiple-input multiple-output (MIMO) Rayleigh fading channels with average power constraint and with complete channel state information available at the receiver side (CSIR). To describe the channel variations over the time, we consider a first-order Gauss-Markov model. We completely solve the problem by giving a single-letter characterization of the channel capacity in closed form and by providing a rigorous proof of it.

We study the problem of common randomness (CR) generation in the basic two-party communication setting in which the sender and the receiver aim to agree on a common random variable with high probability by observing independent and identically distributed (i.i.d.) samples of correlated Gaussian sources and while communicating as little as possible over a noisy memoryless channel. We completely solve the problem by giving a single-letter characterization of the CR capacity for the proposed model and by providing rigorous proof of it We prove that the CR capacity is infinite when the Gaussian sources are perfectly correlated.

Communication over a quantum multiple-access channel (MAC) with cribbing encoders is considered, whereby Transmitter 2 performs a measurement on a system that is entangled with Transmitter 1. Based on the no-cloning theorem, perfect cribbing is impossible. This leads to the introduction of a MAC model with noisy cribbing. In the causal and non-causal cribbing scenarios, Transmitter 2 performs the measurement before the input of Transmitter 1 is sent through the channel. Hence, Transmitter 2’s cribbing may inflict a "state collapse" for Transmitter 1. Achievable regions are derived for each setting. Furthermore, a regularized capacity characterization is established for robust cribbing, i.e. when the cribbing system contains all the information of the channel input, and a partial decode-forward region for non-robust cribbing. For the classical-quantum (c-q) MAC with cribbing encoders, the capacity region is determined with perfect cribbing of the classical input, and a cutset region is derived for noisy cribbing.

Entanglement resources can increase transmission rates substantially. Unfortunately, entanglement is a fragile resource that is quickly degraded by decoherence effects. The present work introduces a new model of unreliable entanglement assistance, whereby the communication system operates whether entanglement assistance is present or not. While the sender is ignorant, the receiver knows whether the entanglement generation was successful. In the case of a failure, the receiver decodes less information. In this manner, the effective transmission rate is adapted according to the assistance status. Regularized formulas are derived for the classical and quantum capacity regions with unreliable entanglement assistance, characterizing the tradeoff between the unassisted rate and the excess rate that can be obtained from entanglement assistance.

In the identification problem, as opposed to the information transmission task, the decoder only identifies whether a message of his choosing was sent or not. This relaxation allows for a double-exponential code size. An achievable identification region is derived for a quantum broadcast channel, and a full characterization for the class of classical-quantum broadcast channels. The results are demonstrated for a depolarizing broadcast channel. Furthermore, the identification capacity region of the single-mode pure-loss bosonic broadcast channel is obtained as a consequence. In contrast to the single-user case, the capacity region for identification can be significantly larger than for transmission.

We generalize the uniform common randomness capacity formula, initially established by Ahslwede and Csiszár for a two-source model for common randomness generation from independent and identically distributed (i.i.d.) discrete sources with unidirectional communication over rate-limited discrete noiseless channels to the case when the one-way communication is over arbitrary single-user channels. In our proof, we will make use of the transmission capacity formula established by Verdú and Han for arbitrary point-to-point channels.

Communication over a quantum multiple-access channel (MAC) with cribbing encoders is considered, whereby Transmitter 2 performs a measurement on a system that is entangled with Transmitter 1. Based on the no-cloning theorem, perfect cribbing is impossible. This leads to the introduction of a MAC model with noisy cribbing. In the causal and non-causal cribbing scenarios, Transmitter 2 performs the measurement before the input of Transmitter 1 is sent through the channel. Hence, Transmitter 2's cribbing may inflict a "state collapse" for Transmitter 1. Achievable regions are derived for each setting. Furthermore, a regularized capacity characterization is established for robust cribbing, i.e. when the cribbing system contains all the information of the channel input. Building on the analogy between the noisy cribbing model and the relay channel, a partial decode-forward region is derived for a quantum MAC with non-robust cribbing. For the classical-quantum MAC with cribbing encoders, the capacity region is determined with perfect cribbing of the classical input, and a cutset region is derived for noisy cribbing. In the special case of a classical-quantum MAC with a deterministic cribbing channel, the inner and outer bounds coincide.

The deterministic identification (DI) capacity is developed in multiple settings of channels with power constraints. A full characterization is established for the DI capacity of the discrete memoryless channel (DMC) with and without input constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness at the encoder, resulting in a double exponential number of messages in the block length $n$ . In the deterministic setup, the number of messages scales exponentially, as in Shannon's transmission paradigm, but the achievable identification rates are higher. An explicit proof was not provided for the deterministic setting. In this paper, a detailed proof is presented for the DMC. Furthermore, Gaussian channels with fast and slow fading are considered, when channel side information is available at the decoder. A new phenomenon is observed as we establish that the number of messages scales as $2^{n\log (n)R}$ by deriving lower and upper bounds on the DI capacity on this scale. Consequently, the DI capacity of the Gaussian channel is infinite in the exponential scale and zero in the double exponential scale, regardless of the channel noise.

Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.

This paper analyzes the problem of common randomness (CR) generation from correlated discrete sources aided by unidirectional communication over Single-Input Single-Output (SISO) slow fading channels with additive white Gaussian noise (AWGN) and arbitrary state distribution. Slow fading channels are practically relevant in many situations in wireless communications. We completely solve the SISO slow fading case by establishing its corresponding outage CR capacity using our characterization of its channel outage capacity. The generated CR could be exploited to improve the performance gain in the identification scheme. The latter is known to be more efficient than the classical transmission scheme in many new applications, which demand ultra-reliable low latency communication.

We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitions $\frac{1}{n}\log M$ (as defined by Shannon for transmission) and $\frac{1}{n}\ \log \log\ M$ — (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].

Koopman introduced in 1946 a two-sided search model. In this search model, the searched object is active and can move one step after each test at most. In this paper we analyze the model of a combinatorial two-sided search by allowing more moves of the searched object after each test. We give search strategies and show that these strategies are optimal. We consider adaptive and non-adaptive strategies. We show the surprising result that with the combinatorial two-sided search on a path graph the optimal non-adaptive search needs the same number of questions as the corresponding adaptive search strategy does. The strategy obtained can also be used to transmit the position of a moving element through a channel. Furthermore, the strategy is a generalization of a group testing strategy to a moving searched element.

Communication over a quantum broadcast channel with cooperation between the receivers is considered. The first form of cooperation addressed is classical conferencing. Another cooperation setting involves quantum conferencing, where Receiver 1 can teleport a quantum state to Receiver 2. The conferencing setting is intimately related to quantum repeaters, as the sender, Receiver 1, and Receiver 2 can be viewed as the transmitter, the repeater, and the destination receiver, respectively. We develop lower and upper bounds on the capacity region in each setting. At last, we show that as opposed to the MAC with entangled encoders, entanglement between decoders does not increase the classical communication rates for the broadcast dual.

Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede’s characterization of the zero-errorcapacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

We investigate the problem of common randomness (CR) generation from discrete correlated sources aided by one-way communication over single-user multiple-input multiple-output (MIMO) slow fading channels with additive white Gaussian noise (AWGN), arbitrary state distribution and with channel state information available at the receiver side (CSIR). We completely solve the problem by first characterizing the channel outage capacity of MIMO slow fading channels for arbitrary state distribution. For this purpose, we also provide an achievable rate for a specific compound MIMO Gaussian channel. Second, we define the outage CR capacity of the MIMO slow fading channel and establish a single-letter characterization of it using our result on its outage transmission capacity.

We study the problem of identification over a DMC wiretap channel under effective secrecy. In identification, due to the fact that single messages are compared to each other, all conditions are inherently semantic, and thus we are forced to consider semantic effective secrecy. We show that even effective secrecy “comes for free” by giving an achievability theorem for stealth identification. We use two concatenated transmission codes, the first one is a resolvability transmission code. The second code is an effective-secrecy transmission code. An achievable rate is derived for the problem.

Communication over a quantum channel that depends on a quantum state is considered when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region with a maximally correlated channel state, and a regularized formula is given for the quantum capacity-leakage function without assistance. For Hadamard channels without assistance, we derive single-letter inner and outer bounds, which coincide in the standard case of a channel that does not depend on a state.

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction$\tau \ge 1/4$vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with$n$transmissions that achieves a positive rate for any fraction of errors$\tau < 1$and$n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes.

Common randomness (CR), as a resource, is not commonly used in existing practical communication systems. In the common randomness framework, both sender and receiver, often described as terminals, aim to generate a common random variable observable to both, perhaps with low error probability. The knowledge of this CR allows to implement correlated random protocols that could lead to faster and more efficient algorithms. We characterize CR over Gaussian channels for their practical relevance in many communication situations by deriving the CR capacity for both Gaussian Single-Input Single-Output (SISO) and Multiple-Input Multiple-Output (MIMO) cases. Furthermore, CR plays a key role in the identification scheme. In many new applications such as several machine-to-machine and human-to-machine systems and the tactile internet, which demand ultra-reliable low latency, the identification or also called post-Shannon scheme is proved to be more efficient than the classical transmission. It has been proved that through CR generation, the post-Shannon communication task allows to achieve an enormous performance gain. We consider a correlation-assisted secure identification scheme over Gaussian wiretap channels (GWC) and develop a lower bound on the corresponding secure identification capacity.

New applications in modern communications are demanding robust and ultra-reliable low latency information exchange such as machine-to-machine and human-to-machine communications. For many of these applications, the identification approach of Ahlswede and Dueck is much more efficient than the classical transmission scheme proposed by Shannon. Previous studies concentrate mainly on identification over discrete channels. We focus on Gaussian channels for their known practical relevance. We deal with secure identification over Gaussian channels. In particular, we provide a suitable coding scheme for the Gaussian wiretap channel (GWC) and determine the corresponding secure identification capacity.

We determine the semantic security capacity for quantum wiretap channels. We extend methods for classical channels to quantum channels to demonstrate that a strongly secure code guarantees a semantically secure code with the same secrecy rate. Furthermore, we show how to transform a non-secure code into a semantically secure code by means of biregular irreducible functions (BRI functions). We analyze semantic security for classical-quantum channels and for quantum channels.

The zero-error capacity of a discrete classical channel was first defined by Shannon as the least upper bound of rates for which one transmits information with zero probability of error. The problem of finding the zero-error capacity C0, which assigns a capacity to each channel as a function, was reformulated in terms of graph theory as a function Θ, which assigns a value to each simple graph. This paper studies the computability of the zero-error capacity. For the computability, the concept of a Turing machine and a Kolmogorov oracle is used. It is unknown if the zero-error capacity is computable in general. We show that in general the zero-error capacity is semi-computable with the help of a Kolmogorov Oracle. Furthermore, we show that C0and Θ are computable functions if and only if there is a computable sequence of computable functions of upper bounds, i.e. the converse exist in the sense of information theory, which point-wise converges to C0or Θ. Finally, we examine Zuiddam's characterization of C0and Θ in terms of algorithmic computability.

Fekete's lemma is a well known assertion that states the existence of limit values of superadditive sequences. In information theory, superadditivity of rate functions occurs in a variety of channel models, making Fekete's lemma essential to the corresponding capacity problems. We analyze Fekete's lemma with respect to effective convergence and computability and show that Fekete's lemma exhibits no constructive derivation. In particular, we devise a superadditive, computable sequence of rational numbers so that the associated limit value in the sense of Fekete's lemma is not a computable number. We further characterize the requirements for effective convergence and investigate the speed of convergence, as proposed by Rudolf Ahlswede in his 2006 Shannon lecture.

Communication over a quantum channel that depends on a quantum state is considered, when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region, and a regularized formula is given for the quantum capacity-leakage function without assistance. For Hadamard channels without assistance, we derive single-letter inner and outer bounds, which coincide in the standard case of a channel that does not depend on a state.

Deterministic identification (DI) is addressed for Gaussian channels with fast and slow fading, where channel side information is available at the decoder. In particular, it is established that the number of messages scales as 2nlog(n)R, where n is the block length and R is the coding rate. Lower and upper bounds on the DI capacity are developed in this scale for fast and slow fading. Consequently, the DI capacity is infinite in the exponential scale and zero in the double-exponential scale, regardless of the channel noise.

Berlekamp and Zigangirov completely determined the capacity error function for binary error correcting codes with noiseless feedback. It is still an unsolved problem if the upper bound for the capacity error function in the non-binary case of Ahlswede, Lebedev, and Deppe is sharp. We consider channels with limited magnitude and feedback. For several classes of these channels we completely determine the capacity error function. All our algorithms do not use all the feedback immediately. Furthermore, a special case of the problem is equivalent to Shannons zero-error problem.

Ahlswede and Dueck introduced identification via channels as a new paradigm in information theory. They showed that the number of messages that can reliably be identified over a noisy channel grows doubly exponentially with the block length. In this paper, we also consider identification, but we assume that messages are stored on a database such that they can be identified. In addition, the legitimate users have access to the output of a source. This source allows us to store messages securely. It is also used to increase the number of messages that can be stored securely on the database and identified reliably. We define a protocol for secure storage for identification such that the number of stored messages that can be identified grows doubly exponentially with the number of symbols read from the source and the number of storage cells available, respectively. We also consider the privacy leakage of the protocols used for identification. So, it makes sense to consider two sources. We assume one source is public, whereas the other source is available only to the legitimate users. The public source is used to increase the number of messages that can be identified, while the second source is used to guarantee secrecy. Using the public source does not increase the privacy leakage. So, we can possibly achieve a higher number of messages that can be identified, while the privacy leakage does not increase using two sources. As a by-product, we also get new results on common randomness generation.

In next-generation connectivity systems, which rely on robust and low-latency information exchange, there exists communication tasks in which the Ahlswede/Dueck identification scheme is much more efficient than Shannon's transmission scheme. We concentrate on the arbitrarily varying wiretap channel (AVWC) that models jamming attacks. We provide a coding scheme for secure identification and determine the secrecy capacity of the AVWC. Furthermore, we analyze important properties of this capacity function, e.g., continuity and super-additivity. These properties are important for the design of robust secure communication design and for the optimization of the medium access control.

We study the identification capacity of classical-quantum channels (“cq-channels”) under channel uncertainty and privacy constraints. To be precise, we first consider compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper by considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then the secrecy identification capacity is also zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC) with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.

We consider a model of communication via a fully quantum jammer channel with quantum jammer, quantum sender and quantum receiver, which we dub quantum arbitrarily varying channel (QAVC). Restricting to finite dimensional user and jammer systems, we show, using permutation symmetry and a de Finetti reduction, how the random coding capacity (classical and quantum) of the QAVC is reduced to the capacity of a naturally associated compound channel, which is obtained by restricting the jammer to i.i.d. input states. Furthermore, we demonstrate that the shared randomness required is at most logarithmic in the block length, via a quantum version of the “elimination of of correlation” using a random matrix tail bound. This implies a dichotomy theorem: either the classical capacity of the QAVC is zero, and then also the quantum capacity is zero, or each capacity equals its random coding variant.

We study the identification capacity of classical-quantum channels (“cq-channels”), under channel uncertainty and privacy constraints. To be precise, we consider first compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper, considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then also the secrecy identification capacity is zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC), with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.

We determine the secrecy capacities of AVQCs (arbitrarily varying quantum channels). Both secrecy capacity with average error probability and with maximal error probability are derived. Both derivations are based on one common code construction. The code we construct fulfills a stringent secrecy requirement, which is called the strong code concept. We determine when the secrecy capacity is a continuous function of the system parameters and completely characterize its discontinuity points both for average error criterion and for maximal error criterion. Furthermore, we prove the phenomenon “super-activation” for secrecy capacities of AVQCs, i.e., two quantum channels both with zero secrecy capacity, which, if used together, allow secure transmission with positive capacity. We also discuss the relations between the entanglement distillation capacity, the entanglement generating capacity, and the strong subspace transmission capacity for AVQCs.

We determine the identification capacity of compound channels in the presence of a wiretapper. It turns out that the secure identification capacity formula fulfills a dichotomy theorem: It is positive and equals the identification capacity of the channel if its message transmission secrecy capacity is positive. Otherwise, the secure identification capacity is zero. Thus, we show in the case that the secure identification capacity is greater than zero we do not pay a price for secure identification, i.e., the secure identification capacity is equal to the identification capacity. This is in strong contrast to the transmission capacity of the compound wiretap channel. We then use this characterization to investigate the analytic behavior of the secure identification capacity. In particular, it is practically relevant to investigate its continuity behavior as a function of the channels. We completely characterize this continuity behavior. We analyze the (dis-) continuity and (super-) additivity of the capacities. In 1998, N. Alon gave a conjecture about maximal violation for the additivity of capacity functions in graphs. We show that this maximal violation as well holds for the secure identification capacity of compound wiretap channels. This is the first example of a capacity function exhibiting this behavior.

We analyze arbitrarily varying classical-quantum wiretap channels. These channels are subject to two attacks at the same time: one passive (eavesdropping), and one active (jamming). We progress on previous works [5] and [6] by introducing a reduced class of allowed codes that fulfills a more stringent secrecy requirement than earlier definitions. In addition, we prove that non-symmetrizability of the legal link is sufficient for equality of the deterministic and the common randomness assisted secrecy capacities. At last, we focus on analytic properties of both secrecy capacities: We completely characterize their discontinuity points, and their super-activation properties.

We determine the identification capacity of compound channels with and without wiretapper. It turned out, that the secure capacity formula fulfill a dichotomy theorem. It is positive if its secure capacity is positive and equals the transmission capacity of the channel. Otherwise the capacity is zero. We analyze the (dis-)continuity and (super-)additivity of the capacities, which we determined. Alon gave in [6] a conjecture about maximal violation for the additivity for capacity functions. We show that this maximal violation holds for the secure identification capacity. This is the first example of a capacity function, which has this behavior.

We determine the secrecy capacities under common randomness assisted coding of arbitrarily varying classical-quantum wiretap channels. Furthermore, we determine the secrecy capacity of a mixed channel model which is compound from the sender to the legal receiver and varies arbitrarily from the sender to the eavesdropper. As an application we examine when the secrecy capacity is a continuous function of the system parameters and show that resources, i.e., having access to a perfect copy of the outcome of a random experiment, are helpful for channel stability.

We establish the Ahlswede Dichotomy for arbitrarily varying classical-quantum wiretap channels, i.e., either the deterministic secrecy capacity of an arbitrarily varying classical-quantum wiretap channel is zero, or it equals its randomness assisted secrecy capacity. We analyze the secrecy capacity of arbitrarily varying classical-quantum wiretap channels when the sender and the receiver use various resources. It turns out that having randomness, common randomness, and correlation as resources are very helpful for achieving a positive deterministic secrecy capacity of arbitrarily varying classical-quantum wiretap channels. We prove the phenomenon “super-activation” for arbitrarily varying classical-quantum wiretap channels, i.e., two arbitrarily varying classical-quantum wiretap channels, both with zero deterministic secrecy capacity, if used together allow perfect secure transmission.

We determine the capacity of the classical compound quantum wiretapper channel with channel state information at the transmitter. Moreover we derive a lower bound on the capacity of this channel without channel state information and determine the capacity of the classical quantum compound wiretap channel with channel state information at the transmitter.

We consider two generalizations of group testing: threshold group testing (introduced by Damaschke [8]) and majority group testing (a further generalization, including threshold group testing and a model introduced by Lebedev [15]). We show that each separating code gives a nonadaptive strategy for threshold group testing for some parameters. This is a generalization of a results on "guessing secrets", introduce. We introduce threshold codes and show that each threshold code gives a nonadaptive strategy for threshold group testing. We show that there exist threshold codes such that we can improve the lower bound for the rate of threshold group testing. We consider majority group testing if the number of defective elements is unknown (otherwise it reduces to threshold group testing). We show that cover-free codes and separating codes give strategies for majority group testing. We give a lower bound for the rate of majority group testing.

We consider a generalization of group testing, which gets together majority group testing and group testing with density tests. In contrast to the classical goal of group testing we want to find m defective elements of D defective elements. We examine four different test functions. We give adaptive strategies and lower bounds for the number of tests. We treat the cases if the number of defectives are known and if the number of defectives are bounded or unknown.

We consider the problem of searching for an unknown number in the search space U ={0,...,M-1}. q-ary questions can be asked and some of the answers may be wrong. An arbitrary integer weighted bipartite graph Gamma is given, stipulating the cost Gamma(i,j) of each answer jnei when the correct answer is i, i.e., the cost of a wrong answer. Correct answers are supposed to be cost-less. It is assumed that a maximum cost e for the sum of the cost of all wrong answers can be afforded by the responder during the whole search. We provide tight upper and lower bounds for the largest size M = M(q,e,Gamma,n) for which it is possible to find an unknown number x*isinU with n q-ary questions and maximum lie cost e. Our results improve the bounds of Cicalese et al. (2004) and Ahlswede et al. (2008). The questions in our strategies can be asked in two batches of nonadaptive questions. Finally, we remark that our results can be further generalized to a wider class of error models including also unidirectional errors.

The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors

We treat here the question, whether there exists a q-ary fix-free code for a given sequence of codeword lengths. We focus mostly on results which establish the 3/4-conjecture of Ahlswede/Balkenhol/Khachatrian for special classes of lengths sequences. We construct fix-free codes with directed deBrujin graphs. We improve and generalize work of Kukorelly/Zeger and of Yekhanin

This paper describes Nowak's model for language evolution and settle a conjecture. The human language is used to store and transmit information. Therefore there is significant interest in the mathematical models of language development. These models explains the natural selection that can lead to the gradual emergence of human language.