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:1410.3031 · Physical Review Letters

Quantum Communication Using Coherent Rejection Sampling

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain

Published Sep 21, 2017• 86 citations
arXivHTMLPDF

Abstract

Compression of a message up to the information it carries is key to many tasks involved in classical and quantum information theory. Schumacher [B. Schumacher, Phys. Rev. A 51, 2738 (1995)PLRAAN1050-294710.1103/PhysRevA.51.2738] provided one of the first quantum compression schemes and several more general schemes have been developed ever since [M. Horodecki, J. Oppenheim, and A. Winter, Commun. Math. Phys. 269, 107 (2007); CMPHAY0010-361610.1007/s00220-006-0118-xI. Devetak and J. Yard, Phys. Rev. Lett. 100, 230501 (2008); PRLTAO0031-900710.1103/PhysRevLett.100.230501A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter, Proc. R. Soc. A 465, 2537 (2009)PRLAAZ1364-502110.1098/rspa.2009.0202]. However, the one-shot characterization of these quantum tasks is still under development, and often lacks a direct connection with analogous classical tasks. Here we show a new technique for the compression of quantum messages with the aid of entanglement. We devise a new tool that we call the convex split lemma, which is a coherent quantum analogue of the widely used rejection sampling procedure in classical communication protocols. As a consequence, we exhibit new explicit protocols with tight communication cost for quantum state merging, quantum state splitting, and quantum state redistribution (up to a certain optimization in the latter case). We also present a port-based teleportation scheme which uses a fewer number of ports in the presence of information about input.

DOI
10.1103/physrevlett.119.120506

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

Near optimal bounds on quantum communication complexity of single-shot quantum state redistribution

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain

We show near optimal bounds on the worst case quantum communication of single-shot entanglement-assisted one-way quantum communication protocols for the {\em quantum state redistribution} task and for the sub-tasks {\em quantum state splitting} and {\em quantum state merging}. Our bounds are tighter than previously known best bounds for the latter two sub-tasks. A key technical tool that we use is a {\em convex-split} lemma which may be of independent interest.

•Oct 11, 2014•10 citations

Efficient methods for one-shot quantum communication

Anurag Anshu, Rahul Jain

Abstract We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two methods for this; the first constructs a resource-efficient convex-split lemma and the second adapts the technique of classical correlated sampling in computer science literature. These lead to the following consequences in one-shot quantum information theory. First concerns the task of quantum decoupling, achieved in many previous works with the aid of a random or pseudo-random unitary. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner; furthermore our unitary performs addition and multiplication modulo a prime. As the second consequence, we construct near-optimal communication protocol for quantum channel coding that uses exponentially smaller entanglement than the previous near-optimal protocol.

arXiv:1809.07056•npj Quantum Information•Aug 20, 2022•12 citations

Efficient methods for one-shot quantum communication

Anurag Anshu

We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two new methods to achieve this, the first method involving two new versions of the convex-split lemma that use much smaller amount of additional resource (in comparison to previous version) and the second method being inspired by the technique of classical correlated sampling in computer science literature. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(nlog n) and depth poly(log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. Furthermore, the number of qubits of pre-shared entanglement is exponentially smaller than that used in the previous protocol that was near-optimal in communication. We also achieve similar results for the one-shot quantum state redistribution. Joint work with Rahul Jain. https://arxiv.org/abs/1809.07056

•Jan 1, 2020•4 citations

Expected Communication Cost of Distributed Quantum Tasks

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

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 citations

Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.

arXiv:1703.02342•IEEE Transactions on Information Theory•May 8, 2019•23 citations
Compression of a message up to the information it carries is key to many tasks involved in classical and quantum information theory. Schumacher [B. Schumacher, Phys. Rev. A 51, 2738 (1995)PLRAAN1050-294710.1103/PhysRevA.51.2738] provided one of the first quantum compression schemes and several more general schemes have been developed ever since [M. Horodecki, J. Oppenheim, and A. Winter, Commun. Math. Phys. 269, 107 (2007); CMPHAY0010-361610.1007/s00220-006-0118-xI. Devetak and J. Yard, Phys. Rev. Lett. 100, 230501 (2008); PRLTAO0031-900710.1103/PhysRevLett.100.230501A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter, Proc. R. Soc. A 465, 2537 (2009)PRLAAZ1364-502110.1098/rspa.2009.0202]. However, the one-shot characterization of these quantum tasks is still under development, and often lacks a direct connection with analogous classical tasks. Here we show a new technique for the compression of quantum messages with the aid of entanglement. We devise a new tool that we call the convex split lemma, which is a coherent quantum analogue of the widely used rejection sampling procedure in classical communication protocols. As a consequence, we exhibit new explicit protocols with tight communication cost for quantum state merging, quantum state splitting, and quantum state redistribution (up to a certain optimization in the latter case). We also present a port-based teleportation scheme which uses a fewer number of ports in the presence of information about input.
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))).
Abstract We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two methods for this; the first constructs a resource-efficient convex-split lemma and the second adapts the technique of classical correlated sampling in computer science literature. These lead to the following consequences in one-shot quantum information theory. First concerns the task of quantum decoupling, achieved in many previous works with the aid of a random or pseudo-random unitary. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner; furthermore our unitary performs addition and multiplication modulo a prime. As the second consequence, we construct near-optimal communication protocol for quantum channel coding that uses exponentially smaller entanglement than the previous near-optimal protocol.
We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two new methods to achieve this, the first method involving two new versions of the convex-split lemma that use much smaller amount of additional resource (in comparison to previous version) and the second method being inspired by the technique of classical correlated sampling in computer science literature. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(nlog n) and depth poly(log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. Furthermore, the number of qubits of pre-shared entanglement is exponentially smaller than that used in the previous protocol that was near-optimal in communication. We also achieve similar results for the one-shot quantum state redistribution. Joint work with Rahul Jain. https://arxiv.org/abs/1809.07056
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 paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.