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:1109.0802

Achieving the Han-Kobayashi inner bound for the quantum interference channel by sequential decoding

Sen, Pranab

Published Sep 5, 2011• 39 citations
arXivHTMLPDF

Abstract

In this paper, we study the power of sequential decoding strategies for several channels with classical input and quantum output. In our sequential decoding strategies, the receiver loops through all candidate messages trying to project the received state onto a `typical' subspace for the candidate message under consideration, stopping if the projection succeeds for a message, which is then declared as the guess of the receiver for the sent message. We show that even such a conceptually simple strategy can be used to achieve rates up to the mutual information for a single sender single receiver channel called cq-channel henceforth, as well as the standard inner bound for a two sender single receiver multiple access channel, called ccq-MAC in this paper. Our decoding scheme for the ccq-MAC uses a new kind of conditionally typical projector which is constructed using a geometric result about how two subspaces interact structurally. As the main application of our methods, we construct an encoding and decoding scheme achieving the Chong-Motani-Garg inner bound for a two sender two receiver interference channel with classical input and quantum output, called ccqq-IC henceforth. This matches the best known inner bound for the interference channel in the classical setting. Achieving the Chong-Motani-Garg inner bound, which is known to be equivalent to the Han-Kobayashi inner bound, answers an open question raised recently by Fawzi et al. (arxiv:1102.2624). Our encoding scheme is the same as that of Chong-Motani-Garg, and our decoding scheme is sequential.

DOI
10.48550/arxiv.1109.0802

Related papers

Achieving the Han-Kobayashi inner bound for the quantum interference channel

Pranab Sen

We construct an encoding and decoding scheme achieving the Chong-Motani-Garg inner bound [1] for a two sender two receiver interference channel with classical input and quantum output. This automatically gives a similar inner bound for sending classical information through an interference channel with quantum inputs and outputs without entanglement assistance. Our result matches the best known inner bound for the interference channel in the classical setting. Achieving the Chong-Motani-Garg inner bound, which is known to be equivalent to the Han-Kobayashi inner bound [3], answers an open question raised recently by Fawzi et al. [4]. Our encoding strategy is the standard random encoding strategy. Our decoding strategy is a sequential strategy where a receiver loops through all candidate messages trying to project the received state onto a `typical' subspace for the candidate message under consideration, stopping if the projection succeeds for a message, which is then declared as the guess of the receiver for the sent message. On the way to our main result, we show that random encoding and sequential decoding strategies suffice to achieve rates up to the mutual information for a single sender single receiver channel, and the standard inner bound for a two sender single receiver multiple access channel, for channels with classical input and quantum output. Besides conceptual simplicity, a sequential decoding strategy is space efficient, and may have additional efficiency advantages in some settings. We prove our inner bounds using two new technical tools - a non-commutative union bound to analyse the decoding error probability, and a geometric notion of approximate interesection of two conditionally typical subspaces.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•36 citations

Classical Communication Over a Quantum Interference Channel

Omar Fawzi, Patrick M. Hayden, Ivan Savov +2 more

Calculating the capacity of interference channels is a notorious open problem in classical information theory. Such channels have two senders and two receivers, and each sender would like to communicate with a partner receiver. The capacity of such channels is known exactly in the settings of “very strong” and “strong” interference, while the Han-Kobayashi coding strategy gives the best known achievable rate region in the general case. Here, we introduce and study the quantum interference channel, a natural generalization of the interference channel to the setting of quantum information theory. We restrict ourselves for the most part to channels with two classical inputs and two quantum outputs in order to simplify the presentation of our results (though generalizations of our results to channels with quantum inputs are straightforward). We are able to determine the exact classical capacity of this channel in the settings of “very strong” and “strong” interference, by exploiting Winter's successive decoding strategy and a novel two-sender quantum simultaneous decoder, respectively. We provide a proof that a Han-Kobayashi strategy is achievable with Holevo information rates, up to a conjecture regarding the existence of a three-sender quantum simultaneous decoder. This conjecture holds for a special class of quantum multiple-access channels with average output states that commute, and we discuss some other variations of the conjecture that hold. Finally, we detail a connection between the quantum interference channel and prior work on the capacity of bipartite unitary gates.

arXiv:1102.2624•IEEE Transactions on Information Theory•Feb 22, 2012•36 citations

Classical communication over a quantum interference channel

Omar Fawzi, Patrick M. Hayden, Ivan Savov +2 more

Calculating the capacity of interference channels is a notorious open problem in classical information theory. Such channels have two senders and two receivers, and each sender would like to communicate with a partner receiver. The capacity of such channels is known exactly in the settings of "very strong" and "strong" interference, while the Han-Kobayashi coding strategy gives the best known achievable rate region in the general case. Here, we introduce and study the quantum interference channel, a natural generalization of the interference channel to the setting of quantum information theory. We restrict ourselves for the most part to channels with two classical inputs and two quantum outputs in order to simplify the presentation of our results (though generalizations of our results to channels with quantum inputs are straightforward). We are able to determine the exact classical capacity of this channel in the settings of "very strong" and "strong" interference, by exploiting Winter's successive decoding strategy and a novel two-sender quantum simultaneous decoder, respectively. We provide a proof that a Han-Kobayashi strategy is achievable with Holevo information rates, up to a conjecture regarding the existence of a three-sender quantum simultaneous decoder. This conjecture holds for a special class of quantum multiple-access channels with average output states that commute, and we discuss some other variations of the conjecture that hold. Finally, we detail a connection between the quantum interference channel and prior work on the capacity of bipartite unitary gates. © 2012 IEEE.

Civil War Book Review•May 29, 2012•30 citations

Quantum interference channels

Omar Fawzi, Patrick M. Hayden, Ivan Savov +2 more

The discrete memoryless interference channel is modelled as a conditional probability distribution with two outputs depending on two inputs and has widespread applications in practical communication scenarios. In this paper, we introduce and study the quantum interference channel, a generalization of a two-input, two-output memoryless channel to the setting of quantum Shannon theory. We discuss three different coding strategies and obtain corresponding achievable rate regions for quantum interference channels. We calculate the capacity regions in the special cases of "very strong" and "strong" interference. The achievability proof in the case of "strong" interference exploits a novel quantum simultaneous decoder for two-sender quantum multiple access channels. We formulate a conjecture regarding the existence of a quantum simultaneous decoder in the three-sender case and use it to state the rates achievable by a quantum Han-Kobayashi strategy.

arXiv:1102.2955•Allerton Conference on Communication, Control, and Computing•Sep 1, 2011•8 citations

Cooperation for the classical-quantum multiple access channel

Holger Boche, Janis Nötzel

We prove coding theorems for two scenarios of cooperating encoders for the multiple access channel with two classical inputs and one quantum output. In the first scenario (ccq-MAC with common message), the two senders each have their private messages, but would also like to transmit common messages. In the second scenario (ccq-MAC with conferencing encoders), each sender has its own set of messages, but they are allowed to use a limited amount of noiseless classical communication amongst each other prior to encoding their messages. This conferencing protocol may depend on each individual message they intend to send. The two scenarios are related to each other not only in spirit - the existence of a capacity-achieving construction scheme for codes for the ccq-MAC with common messages is used for proving the existence of another such scheme for the ccq-MAC with conferencing encoders.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•1 citation

One-shot inner bounds for quantum multiple-access one-time pad

CHENG Feiran, LIU Xiaoming, Zhengjun Xi

We consider the one-shot coding of multiple access channels one-time pad. Suppose that the senders and the receiver share an entangled state in the multi-party systems. Using the position-based coding, each sender encodes the classical messages on their systems, then they transmit their systems over the ideal quantum channels. The receiver applies a decoding operator to all the systems in order to figure out which message was transmitted with respect to the quantum joint typicality lemma. We provide the upper bound of the information leakage by the convex split lemma. Combining quantum max-information with quantum hypothesis testing mutual information, we give the inner bound of the achievable rate.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Feb 27, 2025•0 citations
In this paper, we study the power of sequential decoding strategies for several channels with classical input and quantum output. In our sequential decoding strategies, the receiver loops through all candidate messages trying to project the received state onto a `typical' subspace for the candidate message under consideration, stopping if the projection succeeds for a message, which is then declared as the guess of the receiver for the sent message. We show that even such a conceptually simple strategy can be used to achieve rates up to the mutual information for a single sender single receiver channel called cq-channel henceforth, as well as the standard inner bound for a two sender single receiver multiple access channel, called ccq-MAC in this paper. Our decoding scheme for the ccq-MAC uses a new kind of conditionally typical projector which is constructed using a geometric result about how two subspaces interact structurally. As the main application of our methods, we construct an encoding and decoding scheme achieving the Chong-Motani-Garg inner bound for a two sender two receiver interference channel with classical input and quantum output, called ccqq-IC henceforth. This matches the best known inner bound for the interference channel in the classical setting. Achieving the Chong-Motani-Garg inner bound, which is known to be equivalent to the Han-Kobayashi inner bound, answers an open question raised recently by Fawzi et al. (arxiv:1102.2624). Our encoding scheme is the same as that of Chong-Motani-Garg, and our decoding scheme is sequential.
We construct an encoding and decoding scheme achieving the Chong-Motani-Garg inner bound [1] for a two sender two receiver interference channel with classical input and quantum output. This automatically gives a similar inner bound for sending classical information through an interference channel with quantum inputs and outputs without entanglement assistance. Our result matches the best known inner bound for the interference channel in the classical setting. Achieving the Chong-Motani-Garg inner bound, which is known to be equivalent to the Han-Kobayashi inner bound [3], answers an open question raised recently by Fawzi et al. [4]. Our encoding strategy is the standard random encoding strategy. Our decoding strategy is a sequential strategy where a receiver loops through all candidate messages trying to project the received state onto a `typical' subspace for the candidate message under consideration, stopping if the projection succeeds for a message, which is then declared as the guess of the receiver for the sent message. On the way to our main result, we show that random encoding and sequential decoding strategies suffice to achieve rates up to the mutual information for a single sender single receiver channel, and the standard inner bound for a two sender single receiver multiple access channel, for channels with classical input and quantum output. Besides conceptual simplicity, a sequential decoding strategy is space efficient, and may have additional efficiency advantages in some settings. We prove our inner bounds using two new technical tools - a non-commutative union bound to analyse the decoding error probability, and a geometric notion of approximate interesection of two conditionally typical subspaces.
Calculating the capacity of interference channels is a notorious open problem in classical information theory. Such channels have two senders and two receivers, and each sender would like to communicate with a partner receiver. The capacity of such channels is known exactly in the settings of “very strong” and “strong” interference, while the Han-Kobayashi coding strategy gives the best known achievable rate region in the general case. Here, we introduce and study the quantum interference channel, a natural generalization of the interference channel to the setting of quantum information theory. We restrict ourselves for the most part to channels with two classical inputs and two quantum outputs in order to simplify the presentation of our results (though generalizations of our results to channels with quantum inputs are straightforward). We are able to determine the exact classical capacity of this channel in the settings of “very strong” and “strong” interference, by exploiting Winter's successive decoding strategy and a novel two-sender quantum simultaneous decoder, respectively. We provide a proof that a Han-Kobayashi strategy is achievable with Holevo information rates, up to a conjecture regarding the existence of a three-sender quantum simultaneous decoder. This conjecture holds for a special class of quantum multiple-access channels with average output states that commute, and we discuss some other variations of the conjecture that hold. Finally, we detail a connection between the quantum interference channel and prior work on the capacity of bipartite unitary gates.
Calculating the capacity of interference channels is a notorious open problem in classical information theory. Such channels have two senders and two receivers, and each sender would like to communicate with a partner receiver. The capacity of such channels is known exactly in the settings of "very strong" and "strong" interference, while the Han-Kobayashi coding strategy gives the best known achievable rate region in the general case. Here, we introduce and study the quantum interference channel, a natural generalization of the interference channel to the setting of quantum information theory. We restrict ourselves for the most part to channels with two classical inputs and two quantum outputs in order to simplify the presentation of our results (though generalizations of our results to channels with quantum inputs are straightforward). We are able to determine the exact classical capacity of this channel in the settings of "very strong" and "strong" interference, by exploiting Winter's successive decoding strategy and a novel two-sender quantum simultaneous decoder, respectively. We provide a proof that a Han-Kobayashi strategy is achievable with Holevo information rates, up to a conjecture regarding the existence of a three-sender quantum simultaneous decoder. This conjecture holds for a special class of quantum multiple-access channels with average output states that commute, and we discuss some other variations of the conjecture that hold. Finally, we detail a connection between the quantum interference channel and prior work on the capacity of bipartite unitary gates. © 2012 IEEE.
The discrete memoryless interference channel is modelled as a conditional probability distribution with two outputs depending on two inputs and has widespread applications in practical communication scenarios. In this paper, we introduce and study the quantum interference channel, a generalization of a two-input, two-output memoryless channel to the setting of quantum Shannon theory. We discuss three different coding strategies and obtain corresponding achievable rate regions for quantum interference channels. We calculate the capacity regions in the special cases of "very strong" and "strong" interference. The achievability proof in the case of "strong" interference exploits a novel quantum simultaneous decoder for two-sender quantum multiple access channels. We formulate a conjecture regarding the existence of a quantum simultaneous decoder in the three-sender case and use it to state the rates achievable by a quantum Han-Kobayashi strategy.
We prove coding theorems for two scenarios of cooperating encoders for the multiple access channel with two classical inputs and one quantum output. In the first scenario (ccq-MAC with common message), the two senders each have their private messages, but would also like to transmit common messages. In the second scenario (ccq-MAC with conferencing encoders), each sender has its own set of messages, but they are allowed to use a limited amount of noiseless classical communication amongst each other prior to encoding their messages. This conferencing protocol may depend on each individual message they intend to send. The two scenarios are related to each other not only in spirit - the existence of a capacity-achieving construction scheme for codes for the ccq-MAC with common messages is used for proving the existence of another such scheme for the ccq-MAC with conferencing encoders.
We consider the one-shot coding of multiple access channels one-time pad. Suppose that the senders and the receiver share an entangled state in the multi-party systems. Using the position-based coding, each sender encodes the classical messages on their systems, then they transmit their systems over the ideal quantum channels. The receiver applies a decoding operator to all the systems in order to figure out which message was transmitted with respect to the quantum joint typicality lemma. We provide the upper bound of the information leakage by the convex split lemma. Combining quantum max-information with quantum hypothesis testing mutual information, we give the inner bound of the achievable rate.