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:1809.10149 · IEEE Transactions on Information Theory

A Quantum Multiparty Packing Lemma and the Relay Channel

Dawei Ding, Hrant Gharibyan, Patrick M. Hayden, Michael Walter

Published Dec 18, 2019• 12 citations
arXivHTMLPDF

Abstract

Optimally encoding classical information in a quantum system is one of the oldest and most fundamental challenges of quantum information theory. Holevo's bound places a hard upper limit on such encodings, while the Holevo-Schumacher-Westmoreland (HSW) theorem addresses the question of how many classical messages can be “packed” into a given quantum system. In this article, we use Sen's recent quantum joint typicality results to prove a one-shot multiparty quantum packing lemma generalizing the HSW theorem. The lemma is designed to be easily applicable in many network communication scenarios. As an illustration, we use it to straightforwardly obtain quantum generalizations of well-known classical coding schemes for the relay channel: multihop, coherent multihop, decode-forward, and partial decode-forward. We provide both finite blocklength and asymptotic results, the latter matching existing classical formulas. Given the key role of the classical packing lemma in network information theory, our packing lemma should help open the field to direct quantum generalization.

DOI
10.1109/tit.2019.2960500

Related papers

The Packing Lemma

Mark M. Wilde

The packing lemma is a general method for one party to “pack” or encode classical messages into a Hilbert space so that another party can distinguish the encoded messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors using which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive for many coding theorems. Examples of coding theorems that we can prove using the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for the transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 22 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel. As long as we can determine an ensemble and a set of projectors satisfying the conditions of the packing lemma, we can apply it in a straightforward way. For example, we prove the HSW coding theorem in Chapter 20 largely by relying on the properties of typical and conditionally typical subspaces that we proved in the previous chapter, and some of these properties are equivalent to the conditions of the packing lemma. The packing lemma is a “one-shot” lemma because it applies to a general scenario that is not limited only to i.i.d. uses of a quantum channel. This “oneshot” approach is part of the reason that we can apply it to a variety of situations. The technique of proving a “one-shot” result and applying it to the i.i.d.

Cambridge University Press eBooks•Nov 2, 2016•0 citations

The Packing Lemma

Mark M. Wilde

The packing lemma is a general method for one party to pack classical messages into a Hilbert space so that another party can distinguish the packed messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors from which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive in many coding theorems in quantum Shannon theory. Examples of coding theorems that we can prove with the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 21 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel.

Cambridge University Press eBooks•Apr 18, 2013•0 citations

Making Good Codes for Classical-Quantum Channel Coding via Quantum Hypothesis Testing

Tomohiro Ogawa, Hiroshi Nagaoka

In this correspondence, we give an alternative proof of the direct part of the classical-quantum channel coding theorem (the Holevo-Schumacher-Westmoreland (HSW) theorem), using ideas of quantum hypothesis testing. In order to show the existence of good codes, we invoke a limit theorem, relevant to the quantum Stein's lemma, in quantum hypothesis testing as the law of large numbers used in the classical case. We also apply a greedy construction of good codes using a packing procedure of noncommutative operators. Consequently we derive an upper bound on the coding error probability, which is used to give an alternative proof of the HSW theorem. This approach elucidates how the Holevo information applies to the classical-quantum channel coding problems

IEEE Transactions on Information Theory•Jun 1, 2007•104 citations

Partial decode-forward for quantum relay channels

Ivan Savov, Mark M. Wilde, Mai H. Vu

A relay channel is one in which a Source and Destination use an intermediate Relay station in order to improve communication rates. We propose the study of relay channels with classical inputs and quantum outputs and prove that a “partial decode and forward” strategy is achievable. We divide the channel uses into many blocks and build codes in a randomized, block-Markov manner within each block. The Relay performs a standard Holevo-Schumacher-Westmoreland quantum measurement on each block in order to decode part of the Source's message and then forwards this partial message in the next block. The Destination performs a novel “sliding-window” quantum measurement on two adjacent blocks in order to decode the Source's message. This strategy achieves non-trivial rates for classical communication over a quantum relay channel.

arXiv:1201.0011•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•16 citations

Quantum Information Theory: Classical Communication Over Quantum Channels

John A. Cortese

This thesis studies classical communication over quantum channels. Chapter 1 describes an algebraic technique which extends several previously known qubit channel capacity results to the qudit quantum channel case. Chapter 2 derives a formula for the relative entropy function of two qubit density matrices in terms of their Bloch vectors. The application of the Bloch vector relative entropy formula to the determination of Holevo-Schumacher-Westmoreland (HSW) capacities for qubit quantum channels is discussed. Chapter 3 outlines several numerical simulation results which support theoretical conclusions and conjectures discussed in Chapters 1 and 2. Chapter 4 closes the thesis with comments, examples and discussion on the additivity of Holevo Chi and the HSW channel capacity.

•Feb 18, 2004•4 citations

Relative Entropy and Single Qubit Holevo-Schumacher-Westmoreland Channel Capacity

John A. Cortese

The relative entropy description of Holevo-Schumacher-Westmoreland (HSW) classical channel capacity is applied to single qubit channels. A simple formula for the relative entropy of qubit density matrices in the Bloch sphere representation is derived. This formula is combined with the King-Ruskai-Szarek-Werner qubit channel ellipsoid picture to analyze several unital and non-unital qubit channels in detail. An alternate proof that the optimal HSW signalling states for single qubit unital channels are those states with the minimum channel output entropy is presented. The derivation is based on the symmetries of the qubit relative entropy formula and the King-Ruskai-Szarek-Werner qubit channel ellipsoid picture. A proof is given that the average output density matrix of any set of optimal HSW signalling states for a (qubit or non-qubit) quantum channel is unique.

arXiv:quant-ph/0207128•Jul 22, 2002•5 citations
Optimally encoding classical information in a quantum system is one of the oldest and most fundamental challenges of quantum information theory. Holevo's bound places a hard upper limit on such encodings, while the Holevo-Schumacher-Westmoreland (HSW) theorem addresses the question of how many classical messages can be “packed” into a given quantum system. In this article, we use Sen's recent quantum joint typicality results to prove a one-shot multiparty quantum packing lemma generalizing the HSW theorem. The lemma is designed to be easily applicable in many network communication scenarios. As an illustration, we use it to straightforwardly obtain quantum generalizations of well-known classical coding schemes for the relay channel: multihop, coherent multihop, decode-forward, and partial decode-forward. We provide both finite blocklength and asymptotic results, the latter matching existing classical formulas. Given the key role of the classical packing lemma in network information theory, our packing lemma should help open the field to direct quantum generalization.
The packing lemma is a general method for one party to “pack” or encode classical messages into a Hilbert space so that another party can distinguish the encoded messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors using which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive for many coding theorems. Examples of coding theorems that we can prove using the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for the transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 22 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel. As long as we can determine an ensemble and a set of projectors satisfying the conditions of the packing lemma, we can apply it in a straightforward way. For example, we prove the HSW coding theorem in Chapter 20 largely by relying on the properties of typical and conditionally typical subspaces that we proved in the previous chapter, and some of these properties are equivalent to the conditions of the packing lemma. The packing lemma is a “one-shot” lemma because it applies to a general scenario that is not limited only to i.i.d. uses of a quantum channel. This “oneshot” approach is part of the reason that we can apply it to a variety of situations. The technique of proving a “one-shot” result and applying it to the i.i.d.
The packing lemma is a general method for one party to pack classical messages into a Hilbert space so that another party can distinguish the packed messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors from which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive in many coding theorems in quantum Shannon theory. Examples of coding theorems that we can prove with the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 21 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel.
In this correspondence, we give an alternative proof of the direct part of the classical-quantum channel coding theorem (the Holevo-Schumacher-Westmoreland (HSW) theorem), using ideas of quantum hypothesis testing. In order to show the existence of good codes, we invoke a limit theorem, relevant to the quantum Stein's lemma, in quantum hypothesis testing as the law of large numbers used in the classical case. We also apply a greedy construction of good codes using a packing procedure of noncommutative operators. Consequently we derive an upper bound on the coding error probability, which is used to give an alternative proof of the HSW theorem. This approach elucidates how the Holevo information applies to the classical-quantum channel coding problems
A relay channel is one in which a Source and Destination use an intermediate Relay station in order to improve communication rates. We propose the study of relay channels with classical inputs and quantum outputs and prove that a “partial decode and forward” strategy is achievable. We divide the channel uses into many blocks and build codes in a randomized, block-Markov manner within each block. The Relay performs a standard Holevo-Schumacher-Westmoreland quantum measurement on each block in order to decode part of the Source's message and then forwards this partial message in the next block. The Destination performs a novel “sliding-window” quantum measurement on two adjacent blocks in order to decode the Source's message. This strategy achieves non-trivial rates for classical communication over a quantum relay channel.
This thesis studies classical communication over quantum channels. Chapter 1 describes an algebraic technique which extends several previously known qubit channel capacity results to the qudit quantum channel case. Chapter 2 derives a formula for the relative entropy function of two qubit density matrices in terms of their Bloch vectors. The application of the Bloch vector relative entropy formula to the determination of Holevo-Schumacher-Westmoreland (HSW) capacities for qubit quantum channels is discussed. Chapter 3 outlines several numerical simulation results which support theoretical conclusions and conjectures discussed in Chapters 1 and 2. Chapter 4 closes the thesis with comments, examples and discussion on the additivity of Holevo Chi and the HSW channel capacity.
The relative entropy description of Holevo-Schumacher-Westmoreland (HSW) classical channel capacity is applied to single qubit channels. A simple formula for the relative entropy of qubit density matrices in the Bloch sphere representation is derived. This formula is combined with the King-Ruskai-Szarek-Werner qubit channel ellipsoid picture to analyze several unital and non-unital qubit channels in detail. An alternate proof that the optimal HSW signalling states for single qubit unital channels are those states with the minimum channel output entropy is presented. The derivation is based on the symmetries of the qubit relative entropy formula and the King-Ruskai-Szarek-Werner qubit channel ellipsoid picture. A proof is given that the average output density matrix of any set of optimal HSW signalling states for a (qubit or non-qubit) quantum channel is unique.