Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1603.05238 · IEEE Transactions on Information Theory

A Universal Coding Scheme for Remote Generation of Continuous Random Variables

Cheuk Ting Li, Abbas El Gamal

Published Sep 1, 2016• 8 citations
arXivHTMLPDF

Abstract

Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.

DOI
10.1109/tit.2018.2803752

Related papers

Quantum Rejection Sampling

Ala Shayeghi

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))).

•Jan 21, 2015•0 citations

A Lower and Upper Bound on the Epsilon-Uniform Common Randomness Capacity

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

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].

arXiv:2305.05524•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•5 citations

Faithful Simulation of Distributed Quantum Measurement with Coding for Computing

Anders Høst-Madsen

This paper considers a two-terminal problem in which Alice and Bob aim to perform a joint measurement on a bipartite quantum system $ρ^{AB}$. Alice transmits the results of her measurements to Bob over a classical channel, and the two share common randomness. The central question is: what is the minimum amount of communication and common randomness required to faithfully simulate the measurement? This paper derives an achievable rate region.

arXiv:2501.12271•Jan 21, 2025•1 citation

Lower bound on expected communication cost of quantum Huffman coding

Anurag Anshu, Ankit Garg, Aram W. Harrow +1 more

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.

arXiv:1605.04601•May 15, 2016•2 citations

Lower Bound on Expected Communication Cost of Quantum Huffman Coding

Anurag Anshu, Ankit Garg, Aram W. Harrow +1 more

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.

Leibniz international proceedings in informatics•Jan 1, 2016•1 citation

Common Randomness Generation From Finite Compound Sources Aided by One-Way Communication

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

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.

IEEE Transactions on Information Theory•Aug 4, 2025•0 citations
Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.
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 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].
This paper considers a two-terminal problem in which Alice and Bob aim to perform a joint measurement on a bipartite quantum system ρABρ^{AB}ρAB. Alice transmits the results of her measurements to Bob over a classical channel, and the two share common randomness. The central question is: what is the minimum amount of communication and common randomness required to faithfully simulate the measurement? This paper derives an achievable rate region.
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.
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.
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.