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

Polar Codes for Arbitrary Classical-Quantum Channels and Arbitrary cq-MACs

Rajai Nasser, Joseph M. Renes

Published Sep 21, 2018• 11 citations
arXivHTMLPDF

Abstract

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation, and an Arıkan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary cq multiple access channels. The encoder can be implemented inO(NlogN) operations, whereNis the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2(-N)βfor any β <; (1/2).

DOI
10.1109/tit.2018.2869460

Related papers

Polar codes for arbitrary classical-quantum channels and arbitrary cq-MACs

Rajai Nasser, Joseph M. Renes

We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arikan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in O(N log N) operations, where N is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2-Nβfor any β <; ½.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•3 citations

Polar Codes for Classical-Quantum Channels

Mark M. Wilde, Saikat Guha

Holevo, Schumacher, and Westmoreland's coding theorem guarantees the existence of codes that are capacity-achieving for the task of sending classical data over a channel with classical inputs and quantum outputs. Although they demonstrated the existence of such codes, their proof does not provide an explicit construction of codes for this task. The aim of this paper is to fill this gap by constructing near-explicit “polar” codes that are capacity-achieving. The codes exploit the channel polarization phenomenon observed by Arikan for the case of classical channels. Channel polarization is an effect in which one can synthesize a set of channels, by “channel combining” and “channel splitting,” in which a fraction of the synthesized channels are perfect for data transmission, while the other channels are completely useless for data transmission, with the good fraction equal to the capacity of the channel. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and “frozen” bits through the useless ones. The main technical contributions of this paper are threefold. First, we leverage several known results from the quantum information literature to demonstrate that the channel polarization effect occurs for channels with classical inputs and quantum outputs. We then construct linear polar codes based on this effect, and the encoding complexity isO(NlogN), whereNis the blocklength of the code. We also demonstrate that a quantum successive cancellation decoder works well, in the sense that the word error rate decays exponentially with the blocklength of the code. For this last result, we exploit Sen's recent “noncommutative union bound” that holds for a sequence of projectors applied to a quantum state.

arXiv:1109.2591•IEEE Transactions on Information Theory•Sep 14, 2012•115 citations

Polar Codes for CQ Channels: Decoding via Belief-Propagation with Quantum Messages

Avijit Mandal, Sam Brandsen, Henry D. Pfister

This paper considers the design and decoding of polar codes for general classical-quantum (CQ) channels. It focuses on decoding via belief-propagation with quantum messages (BPQM) and, in particular, the idea of paired-measurement BPQM (PM-BPQM) decoding. Since the PM-BPQM decoder admits a classical density evolution (DE) analysis, one can use DE to design a polar code for any CQ channel and then efficiently compute the trade-off between code rate and error probability. We have also implemented and tested a classical simulation of our PM-BPQM decoder for polar codes. While the decoder can be implemented efficiently on a quantum computer, simulating the decoder on a classical computer actually has exponential complexity. Thus, simulation results for the decoder are somewhat limited and are included primarily to validate our theoretical results.

arXiv:2401.07167•Jan 13, 2024•1 citation

Polar codes for q-ary channels, q =2r

Woomyoung Park, Alexander Barg

We study polarization for nonbinary channels with input alphabet of size q = 2r, r = 2,3,.... Using Arikan's polarizing kernel H2, we prove that virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,..., r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-Nα), where N is the code length and α is any constant less than 0.5.

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

Constructing polar codes for non-binary alphabets and MACs

Ido Tal, Artyom Sharov, Alexander Vardy

Consider a channel with an input alphabet that is finite but not necessarily binary. A method for approximating such a channel having a large output alphabet size by a degraded version of it having a smaller output alphabet size is presented and analyzed. The approximation method is used to construct polar codes for both single-user and multiple-access channels with prime input alphabet sizes.

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

Purely Quantum Polar Codes

Frédéric Dupuis, Ashutosh Goswami, Mehdi Mhalla +1 more

We provide a purely quantum version of polar codes, achieving the coherent information of any quantum channel. Our scheme relies on a recursive channel combining and splitting construction, where a two-qubit gate randomly chosen from the Clifford group is used to combine two single-qubit channels. The inputs to the synthesized bad channels are frozen by preshared EPR pairs between the sender and the receiver, so our scheme is entanglement assisted. We further show that quantum polarization can be achieved by choosing the channel combining Clifford operator randomly, from a much smaller subset of only 9 two-qubit Clifford gates. Subsequently, we show that a Pauli channel polarizes if and only if a specific classical channel over four symbol input set polarizes. We exploit this equivalence to prove fast polarization for Pauli channels, and to devise an efficient successive cancellation based decoding algorithm for such channels. Finally, we present a code construction based on chaining several quantum polar codes, which is shown to require a rate of preshared entanglement that vanishes asymptotically.

•Aug 25, 2019•1 citation
We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation, and an Arıkan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary cq multiple access channels. The encoder can be implemented inO(NlogN) operations, whereNis the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2(-N)βfor any β <; (1/2).
We prove polarization theorems for arbitrary classical-quantum (cq) channels. The input alphabet is endowed with an arbitrary Abelian group operation and an Arikan-style transformation is applied using this operation. It is shown that as the number of polarization steps becomes large, the synthetic cq-channels polarize to deterministic homomorphism channels that project their input to a quotient group of the input alphabet. This result is used to construct polar codes for arbitrary cq-channels and arbitrary classical-quantum multiple access channels (cq-MAC). The encoder can be implemented in O(N log N) operations, where N is the blocklength of the code. A quantum successive cancellation decoder for the constructed codes is proposed. It is shown that the probability of error of this decoder decays faster than 2-Nβfor any β <; ½.
Holevo, Schumacher, and Westmoreland's coding theorem guarantees the existence of codes that are capacity-achieving for the task of sending classical data over a channel with classical inputs and quantum outputs. Although they demonstrated the existence of such codes, their proof does not provide an explicit construction of codes for this task. The aim of this paper is to fill this gap by constructing near-explicit “polar” codes that are capacity-achieving. The codes exploit the channel polarization phenomenon observed by Arikan for the case of classical channels. Channel polarization is an effect in which one can synthesize a set of channels, by “channel combining” and “channel splitting,” in which a fraction of the synthesized channels are perfect for data transmission, while the other channels are completely useless for data transmission, with the good fraction equal to the capacity of the channel. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and “frozen” bits through the useless ones. The main technical contributions of this paper are threefold. First, we leverage several known results from the quantum information literature to demonstrate that the channel polarization effect occurs for channels with classical inputs and quantum outputs. We then construct linear polar codes based on this effect, and the encoding complexity isO(NlogN), whereNis the blocklength of the code. We also demonstrate that a quantum successive cancellation decoder works well, in the sense that the word error rate decays exponentially with the blocklength of the code. For this last result, we exploit Sen's recent “noncommutative union bound” that holds for a sequence of projectors applied to a quantum state.
This paper considers the design and decoding of polar codes for general classical-quantum (CQ) channels. It focuses on decoding via belief-propagation with quantum messages (BPQM) and, in particular, the idea of paired-measurement BPQM (PM-BPQM) decoding. Since the PM-BPQM decoder admits a classical density evolution (DE) analysis, one can use DE to design a polar code for any CQ channel and then efficiently compute the trade-off between code rate and error probability. We have also implemented and tested a classical simulation of our PM-BPQM decoder for polar codes. While the decoder can be implemented efficiently on a quantum computer, simulating the decoder on a classical computer actually has exponential complexity. Thus, simulation results for the decoder are somewhat limited and are included primarily to validate our theoretical results.
We study polarization for nonbinary channels with input alphabet of size q = 2r, r = 2,3,.... Using Arikan's polarizing kernel H2, we prove that virtual channels that arise in the process of polarization converge to q-ary channels with capacity 1,2,..., r bits, and that the total transmission rate approaches the symmetric capacity of the channel. This leads to an explicit transmission scheme for q-ary channels. The error probability of decoding using successive cancellation behaves as exp(-Nα), where N is the code length and α is any constant less than 0.5.
We provide a purely quantum version of polar codes, achieving the coherent information of any quantum channel. Our scheme relies on a recursive channel combining and splitting construction, where a two-qubit gate randomly chosen from the Clifford group is used to combine two single-qubit channels. The inputs to the synthesized bad channels are frozen by preshared EPR pairs between the sender and the receiver, so our scheme is entanglement assisted. We further show that quantum polarization can be achieved by choosing the channel combining Clifford operator randomly, from a much smaller subset of only 9 two-qubit Clifford gates. Subsequently, we show that a Pauli channel polarizes if and only if a specific classical channel over four symbol input set polarizes. We exploit this equivalence to prove fast polarization for Pauli channels, and to devise an efficient successive cancellation based decoding algorithm for such channels. Finally, we present a code construction based on chaining several quantum polar codes, which is shown to require a rate of preshared entanglement that vanishes asymptotically.