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.
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.
A central question in the 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 independent identically distributed (i.i.d.) compression rate of the Shannon entropy of the source. In this paper, 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 with 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 the quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Furthermore, 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.
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.
Let H be a finite dimensional Hilbert space and ρ, σ ∈ D(H) be quantum states in H \nsuch that S(ρ||σ) is finite. In this thesis, we consider the following communication task involving two parties Alice and Bob. Suppose that Alice is given a classical description of the states ρ and σ. Given an unlimited number of copies of an entangled state whose marginal on Bob’s side is σ, Alice’s goal is to help Bob output a single copy of the state ρ by sending a single message to Bob in a one-way LOCC (short for local operation and classical communication) protocol. We propose a class of one-way LOCC protocols for this task which we refer to as quantum rejection sampling protocols. Inspired by the classical rejection sampling protocol of Harsha, Jain, McAllester, and Radhakrishnan [25] for a similar classical communication task, we introduce the Greedy Quantum Rejection Sampler. We characterize the expected communication cost of the protocol in terms of max-relative entropy of ρ with respect to σ, in the case where the state ρ is a pure state and prove that the Greedy Quantum Rejection Sampler is an optimal quantum rejection sampling protocol in this case. We describe an optimal quantum rejection sampling protocol in terms of a semidefinite program and we find general lower bounds and upper bounds on the expected communication cost of the optimal protocol. We propose an LOCC compression protocol based on the Greedy Quantum Rejection Sampler protocol, for lossless compression of an arbitrary pure state quantum source in the visible compression model and we show an upper bound on the average length of this encoding. The upper bound is always less than or equal to the Shannon entropy of the quantum source and the gap between the two quantities can be arbitrary large. Finally, we introduce a high-entanglement deterministic exact protocol for remote preparation of an arbitrary ensemble of quantum states. Our protocol is based on a quantum rejection sampling protocol which uses a prefix-free encoding for communication of the messages. We establish an upper bound on the expected communication cost of this protocol for the worst case choice of the target state in terms of the max-information in Bob’s output register at the end of the protocol about Alice’s classical input register. Furthermore, this protocol can be used as a non-oblivious universal protocol for exact remote preparation of an arbitrary d-dimensional state at an expected communication cost of at most lg(d) +O (lg(lg(d))).
We revisit the task of quantum state redistribution in the one-shot setting, and design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to operationally connect quantum state redistribution and quantum Markov chains, and can be interpreted as an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. Thus, our work takes a step towards an optimal characterization of the resources required for one-shot quantum state redistribution, an important open problem in quantum Shannon theory.
This thesis consists of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. \n \nWe first study the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially higher communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed. We show that an ensemble given by Jain, Radhakrishnan, and Sen (ICALP'03) cannot be compressed by more than a constant number of qubits without shared entanglement, while in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. \n \nNext, we study the task of quantum state redistribution, the most general version of compression of quantum states. We design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to connect quantum state redistribution and Markov chains and gives an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. \n \nIn the last part, we focus on quantum algorithms for learning Boolean functions using quantum examples. We consider two commonly studied models of learning, namely, quantum PAC learning and quantum agnostic learning. We reproduce the optimal lower bounds by Arunachalam and de Wolf (JMLR’18) for the sample complexity of either of these models using information theory and spectral analysis. Our proofs are simpler than the previous ones and the techniques can be possibly extended to similar scenarios.
We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.