Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.
Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.
Most coding theorems in quantum Shannon theory can be proven using the decoupling technique. To send data through a channel, one guarantees that the environment gets no information about it. Uhlmann's theorem then ensures that the receiver must be able to decode. While a wide range of problems can be solved this way, one of the most basic coding problems remains impervious to a direct application of this method, sending classical information through a quantum channel. We will show that this problem can, in fact, be solved using decoupling ideas, specifically by proving a dequantizing theorem, which ensures that the environment is only classically correlated with the sent data. Our techniques naturally yield a generalization of the Holevo-Schumacher-Westmoreland theorem to the one-shot scenario, where a quantum channel can be applied only once.
One of the fundamental tasks in classical information theory is the compression of information. Given access to many uses of a noiseless classical channel, what is the best that a sender and receiver can make of this resource for compressed data transmission? Shannon's compression theorem demonstrates that the Shannon entropy is the fundamental limit for the compression rate in the IID setting (recall the development in Section 13.4). That is, if one compresses at a rate above the Shannon entropy, then it is possible to recover the compressed data perfectly in the asymptotic limit, and otherwise, it is not possible to do so. This theorem establishes the prominent role of the entropy in Shannon's theory of information. In the quantum world, it very well could be that one day a sender and a receiver would have many uses of a noiseless quantum channel available, and the sender could use this resource to transmit compressed quantum information. But what exactly does this mean in the quantum setting? A simple model of a quantum information source is an ensemble of quantum states { pX(x) , ∣ψ x ⟩}, i.e., the source outputs the state ∣ψ x ⟩ with probability pX(x) , and the states {∣ψ x ⟩} do not necessarily have to form an orthonormal basis. Let us suppose for the moment that the classical data x is available as well, even though this might not necessarily be the case in practice. A naive strategy for compressing this quantum information source would be to ignore the quantum states coming out, handle the classical data instead, and exploit Shannon's compression protocol from Section 13.4.
The quantum capacity theorem is one of the most important theorems in quantum Shannon theory. It is a fundamentally “quantum” theorem in that it demonstrates that a fundamentally quantum information quantity, the coherent information, is an achievable rate for quantum communication over a quantum channel. The fact that the coherent information does not have a strong analog in classical Shannon theory truly separates the quantum and classical theories of information. The no-cloning theorem (Section 3.5.4) provides the intuition behind the quantum capacity theorem. The goal of any quantum communication protocol is for Alice to establish quantum correlations with the receiver Bob. We know well now that every quantum channel has an isometric extension, so that we can think of another receiver, the environment Eve, who is at a second output port of a larger unitary evolution. Were Eve able to learn anything about the quantum information that Alice is attempting to transmit to Bob, then Bob could not be retrieving this information—otherwise, they would violate the no-cloning theorem. Thus, Alice should figure out some subspace of the channel input where she can place her quantum information such that only Bob has access to it, while Eve does not. That the dimensionality of this subspace is exponential in the coherent information is perhaps then unsurprising in light of the above no-cloning reasoning. The coherent information is an entropy difference H ( B ) -H ( E )—a measure of the amount of quantum correlations that Alice can establish with Bob less the amount that Eve can gain. We proved achievability of the coherent information for quantum data transmission in Corollary 22.2.1, but the roundabout path that we followed to prove achievability there perhaps does not give much insight into the structure of a quantum code that achieves the coherent information. Our approach in this chapter is different and should shed more light on this structure. Specifically, we show how to make coherent versions of the private classical codes from the previous chapter.
In this Thesis, several results in quantum information theory are collected, most of which use entropy as the main mathematical tool. *While a direct generalization of the Shannon entropy to density matrices, the von Neumann entropy behaves differently. A long-standing open question is, whether there are quantum analogues of unconstrained non-Shannon type inequalities. Here, a new constrained non-von-Neumann type inequality is proven, a step towards a conjectured unconstrained inequality by Linden and Winter. *IID quantum state merging can be optimally achieved using the decoupling technique. The one-shot results by Berta et al. and Anshu at al., however, had to bring in additional mathematical machinery. We introduce a natural generalized decoupling paradigm, catalytic decoupling, that can reproduce the aforementioned results when used analogously to the application of standard decoupling in the asymptotic case. *Port based teleportation, a variant of standard quantum teleportation protocol, cannot be implemented perfectly. We prove several lower bounds on the necessary number of output ports N to achieve port based teleportation for given error and input dimension, showing that N diverges uniformly in the dimension of the teleported quantum system, for vanishing error. As a byproduct, a new lower bound for the size of the program register for an approximate universal programmable quantum processor is derived. *In the last part, we give a new definition for information-theoretic quantum non-malleability, strengthening the previous definition by Ambainis et al. We show that quantum non-malleability implies secrecy, analogous to quantum authentication. Furthermore, non-malleable encryption schemes can be used as a primitive to build authenticating encryption schemes. We also show that the strong notion of authentication recently proposed by Garg et al. can be fulfilled using 2-designs.
A central question in classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and i.i.d. compression rate of the Shannon entropy of the source. In this work, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated to the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Further, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation.
This thesis establishes a number of connections between foundational issues in quantum theory, and some quantum information applications. It starts with a review of quantum contextuality and non-locality, multipartite entanglement characterisation, and of a few quantum information protocols. Quantum non-locality and contextuality are shown to be essential for different implementations of quantum information protocols known as quantum random access codes and quantum communication complexity protocols. I derive sufficient experimental conditions for tests of these quantum properties. I also discuss how the distribution of quantum information through quantum cloning processes can be useful in quantum computing. Regarding entanglement characterisation, some results are obtained relating two problems, that of additivity of the relative entropy of entanglement, and that of identifying different types of tripartite entanglement in the asymptotic regime of manipulations of many copies of a given state. The thesis ends with a description of an information processing task in which a single qubit substitutes for an arbitrarily large amount of classical communication. This result is interpreted in different ways: as a gap between quantum and classical computation space complexity; as a bound on the amount of classical communication necessary to simulate entanglement; and as a basic result on hidden-variable theories for quantum mechanics. I also show that the advantage of quantum over classical communication can be established in a feasible experiment.