In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.
In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most pn errors (symbol changes) and pn erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.
Transmitting quantum information across quantum channels is an important task. However quantum information is delicate, and is easily corrupted. We address the task of protecting quantum information from an information theoretic perspective -- we encode some message qudits into a quantum code, send the encoded quantum information across the noisy quantum channel, then recover the message qudits by decoding. In this dissertation, we discuss the coding problem from several perspectives.} \n \nThe noisy quantum channel is one of the central aspects of the quantum coding problem, and hence quantifying the noisy quantum channel from the physical model is an important problem. \nWe work with an explicit physical model -- a pair of initially decoupled quantum harmonic oscillators interacting with a spring-like coupling, where the bath oscillator is initially in a thermal-like state. In particular, we treat the completely positive and trace preserving map on the system as a quantum channel, and study the truncation of the channel by truncating its Kraus set. We thereby derive the matrix elements of the Choi-Jamiolkowski operator of the corresponding truncated channel, which are truncated transition amplitudes. Finally, we give a computable approximation for these truncated transition amplitudes with explicit error bounds, and perform a case study of the oscillators in the off-resonant and weakly-coupled regime numerically. \n \nIn the context of truncated noisy channels, we revisit the notion of approximate error correction of finite dimension codes. We derive a computationally simple lower bound on the worst case entanglement fidelity of a quantum code, when the truncated recovery map of Leung et. al. is rescaled. As an application, we apply our bound to construct a family of multi-error correcting amplitude damping codes that are permutation-invariant. This demonstrates an explicit example where the specific structure of the noisy channel allows code design out of the stabilizer formalism via purely algebraic means. \n \nWe study lower bounds on the quantum capacity of adversarial channels, where we restrict the selection of quantum codes to the set of concatenated quantum codes. \nThe adversarial channel is a quantum channel where an adversary corrupts a fixed fraction of qudits sent across a quantum channel in the most malicious way possible. The best known rates of communicating over adversarial channels are given by the quantum Gilbert-Varshamov (GV) bound, that is known to be attainable with random quantum codes. We generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region. \n \nWe next study upper bounds on the quantum capacity of some low dimension quantum channels. \nThe quantum capacity of a quantum channel is the maximum rate at which quantum information can be transmitted reliably across it, given arbitrarily many uses of it. While it is known that random quantum codes can be used to attain the quantum capacity, the quantum capacity of many classes of channels is undetermined, even for channels of low input and output dimension. For example, depolarizing channels are \n important quantum channels, but do not have tight numerical bounds. \nWe obtain upper bounds on the quantum capacity of some unital and non-unital channels \n -- two-qubit Pauli channels, two-qubit depolarizing channels, two-qubit locally symmetric channels, \n shifted qubit depolarizing channels, and shifted two-qubit Pauli channels -- \n using the coherent information of some degradable channels. We use the notion \n of twirling quantum channels, and Smith and Smolin's method of constructing \n degradable extensions of quantum channels extensively. The degradable channels we \n introduce, study and use are two-qubit amplitude damping channels. Exploiting the \n notion of covariant quantum channels, we give sufficient conditions for the quantum \n capacity of a degradable channel to be the optimal value of a concave program with \n linear constraints, and show that our two-qubit degradable amplitude damping channels have this property.
The optimal quantum communication cost of computing a classical sum of distributed sources is studied over a quantum erasure multiple access channel (QEMAC).Kclassical messages comprised of finite-field symbols are distributed acrossSservers, who also share quantum entanglement in advance. Each servers∈ [S] manipulates its quantum subsystemQsaccording to its own available classical messages and sendsQsto the receiver who then computes the sum of the messages based on a joint quantum measurement. The download cost from Servers∈ [S] is the logarithm of the dimension ofQs. The rateRis defined as the number of instances of the sum computed at the receiver, divided by the total download cost from all the servers. The main focus is on the symmetric setting withK= (Sα) messages where each message is replicated among a unique subset of α servers, and the answers from any β servers may be erased. If no entanglement is initially available to the receiver, then we show that the capacity (maximal rate) is preciselyC= max { min { 2(α−β)/S,S−2β/S}, α−β/S}. The capacity with arbitrary levels of prior entanglement (Δ0) between theSdata-servers and the receiver is also characterized, by including an auxiliary server (Server 0) that has no classical data, so that the communication cost from Server 0 is a proxy for the amount of receiver-side entanglement that is available in advance. The challenge on the converse side resides in the optimal application of the weak monotonicity property, while the achievability combines ideas from classical network coding and treating qudits as classical dits, as well as new constructions based on the N-sum box abstraction that rely on absolutely maximally entangled quantum states.
Introduction Error-correcting codes were introduced in the 1940s in order to implement a theorem of Shannon's [260] which guaranteed that virtually error-free communication could be obtained even over a noisy channel. The message to be communicated is first “encoded”, i.e. turned into a codeword, by adding "redundancy". The codeword is then sent through the channel and the received message is “decoded” by the receiver into a message resembling, as closely as possible, the original message. The degree of resemblance will depend on how good the code is in relation to the channel. The usual pictorial representation of this communication link is shown in the schematic diagram Figure 2.1. Here a message is first given by the source to the encoder that turns the message into a codeword, i.e. a string of letters from some alphabet, chosen according to the code used; the encoded message is then sent through the channel, where it may be subjected to noise and hence altered; this possibly-altered message, when it arrives at the decoder belonging to the receiver, is, first of all, equated with the most likely codeword, i.e. the one (should that exist) that, in a probabilistic sense depending on the channel, was probably sent; finally this “most likely” codeword is decoded and the message is passed on to the receiver. Example 2.1.1 Suppose we use an alphabet of just two symbols, 0 and 1, and we have only two messages, for example “no” corresponding to 0, and "yes” corresponding to 1. We wish to send the message “no”, and we add redundancy by simply repeating the message five times. Thus we encode the message as the codeword (00000). The channel interferes, perhaps, with the message and could, for example, change it to (01100). The decoder assesses the message and decides that of the two possible codewords, i.e. (00000) and (11111), the former is the more likely, and hence the message is decoded, correctly, as “no”. Notice that we have made several assumptions here: for example we have assumed that the probability of an error at any position in the word is less than, that each codeword is equally likely to be sent, and that the receiver is aware of the code used.
We study the error detection problem in q-ary asymmetric channels, wherein every input symbol xiis mapped to an output symbol yisatisfying yi≥xi. A general setting is assumed, where the noise vectors are (potentially) restricted in: 1) the amplitude, yi-xi≤a, 2) the Hamming weight, Σi=1n1{yi≠xi}≤ h, and 3) the total weight, Σi=1n(yi-xi)≤t. Optimal codes detecting these types of errors are described for certain sets of parameters a, h, t, both in the standard and in the cyclic (mod q) version of the problem. It is also demonstrated that these codes are optimal in the large alphabet limit for every a, h, t and every block-length n.
In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via n parallel two-way channels, and Alice holds an 𝓁 symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls t of the channels, where n = 2t+1. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice’s secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice’s secret, regardless of Eve’s corruptions; and (b) private, i.e., Eve may not learn anything about Alice’s secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob. In this work we provide upper and lower bounds for the PSMT model when the length of the communicated secret 𝓁 is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an 𝓁 symbol secret to Bob by transmitting at most 2(1+o_{𝓁→∞}(1))n𝓁 symbols. Under a reasonable assumption (which is satisfied by all known efficient two-round PSMT protocols), we complement this with a lower bound showing that 2n𝓁 symbols are necessary for Alice to privately and reliably communicate her secret. This provides strong evidence that our construction is optimal (even up to the leading constant).