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

Allerton Conference on Communication, Control, and Computing

Can a noisy encoder be used to communicate reliably?

Yaoqing Lamar Yang, Pulkit Grover, Soummya Kar

Published Sep 1, 2014• 17 citations
Publisher

Abstract

In this paper the problem of reliable communication with a noisy encoder is examined. We explicitly provided the construction of the encoder and show that even when all logic gates that constitute the encoder are noisy, reliable communication with a positive rate is still possible. The encoding complexity is shown to be O(log 1/ptar/log1/ε) per bit to achieve a target bit error rate ptar, where ε denotes the error probability of each noisy gate. This complexity upper bound is shown to coincide with a lower bound in order sense, and is hence tight. The key technique in the proposed construction is to embed noisy decoders inside the noisy encoder, which are utilized repeatedly to prevent the bit error rate from escalating. The proposed noisy encoder has a direct application in noisy computing of a linear transform.

DOI
10.1109/allerton.2014.7028518

Related papers

Computing Linear Transformations With Unreliable Components

Yaoqing Lamar Yang, Pulkit Grover, Soummya Kar

We consider the problem of computing a binary linear transformation when all circuit components are unreliable. Two models of unreliable components are considered: probabilistic errors and permanent errors. We introduce the “ENCODED” technique that ensures that the error probability of the computation of the linear transformation is kept bounded below a small constant independent of the size of the linear transformation even when all logic gates in the computation are noisy. By deriving a lower bound, we show that in some cases, the computational complexity of the ENCODED technique achieves the optimal scaling in error probability. Further, we examine the gain in energy-efficiency from the use of a “voltage-scaling” scheme, where gate-energy is reduced by lowering the supply voltage. We use a gate energy-reliability model to show that tuning gate-energy appropriately at different stages of the computation (“dynamic” voltage scaling), in conjunction with ENCODED, can lead to orders of magnitude energy-savings over the classical “uncoded” approach. Finally, we also examine the problem of computing a linear transformation when noiseless decoders can be used, providing upper and lower bounds to the problem.

arXiv:1506.07234•IEEE Transactions on Information Theory•Apr 7, 2017•54 citations

Computing linear transforms with unreliable components

Yaoqing Lamar Yang, Pulkit Grover, Soummya Kar

We consider the problem of computing a binary linear transform when all circuit components are unreliable. We propose a novel “ENCODED” technique that uses LDPC (low-density parity-check) codes and embedded noisy decoders to keep the error probability of the computation below a small constant independent of the size of the linear transform, even when all logic gates in the computation are prone to probabilistic errors. Unlike existing works on applying coding to computing with unreliable components, the “ENCODED” technique explicitly considers the errors that happen during both the encoding and the decoding phases. Further, we show that ENCODED requires fewer operations (in order sense) than repetition techniques.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

Reliable quantum memories with unreliable components

Anuj Keshava Nayak, Eric Chitambar, Lav R. Varshney

Quantum memory systems are vital in quantum information processing for dependable storage and retrieval of quantum states. Inspired by classical reliability theories that synthesize reliable computing systems from unreliable components, we formalize the problem of reliable storage of quantum information using noisy components. We introduce the notion of stable quantum memories and define the storage rate as the ratio of the number of logical qubits to the total number of physical qubits as well as the circuit complexity of the decoder, which includes both quantum gates and measurements. We demonstrate that a strictly positive storage rate can be achieved by constructing a quantum memory system with quantum expander codes. Moreover, by reducing the reliable storage problem to reliable quantum communication, we provide upper bounds on the achievable storage capacity. In the case of physical qubits corrupted by noise satisfying hypercontractivity conditions, we provide a tighter upper bound on storage capacity using an entropy dissipation argument. Furthermore, observing that the time complexity of the decoder scales nontrivially with the number of physical qubits, achieving asymptotic rates may not be possible due to the induced dependence of the noise on the number of physical qubits. In this constrained nonasymptotic setting, we derive upper bounds on storage capacity using finite blocklength communication bounds. Finally, we numerically analyze the gap between upper and lower bounds in both asymptotic and nonasymptotic cases, and provide suggestions to tighten the gap.

arXiv:2406.05599•Physical Review A•Sep 18, 2024•4 citations

Error correction, authentication, and false acceptance, probabilities for communication over noisy quantum channels: converse upper bounds on the bit transmission rate

Pete Rigas

We obtain strict upper bounds on the bit transmission rate for communication of Classical bit codewords over Quantum channels. Albeit previous arguments in arXiv: 1804.01797 which have demonstrated that lower bounds can be shown to hold for the bit transmission rate without the presence of significant noise over the channel shared by Alice and Bob for the purposes of encoding, decoding, transmission and authentication, the author suggests that upper bounding the bit transmission rate could be of use towards classifying paradoxical aspects of communication protocols, as well as constructing error correcting codes which are resilient to noise. The upper bound that is obtained in this work for the bit transmission rate, as a converse result, is dependent upon the natural logarithm of the size of each player's alphabet, as well as smaller alphabets, which can be leveraged for simultaneously realizing Quantum advantage for maximizing error correction and minimizing false acceptance. Crucially, the upper bound to the bit transmission rate is dependent upon a pruning procedure, which seeks to determine whether letters from player's alphabets can be removed so that prospective Quantum advantage, in order for Alice and Bob to implement error correction protocols with high probability, despite the fact that there is more noise over the channel between Alice and Bob in comparison to that between Bob and Eve.

arXiv:2507.03035•Jul 3, 2025•0 citations

Lower bounds for the complexity of reliable Boolean circuits with noisy gates

Anna Gál

It is proved that the reliable computation of any Boolean function with, sensitivity s requires Omega (s log s) gates if the gates of the circuit fail independently with a fixed positive probability. The Omega (s log s) bound holds even if s is the block sensitivity instead of the sensitivity of the Boolean function. Some open problems are mentioned.>

Annual Symposium on Foundations of Computer Science•Dec 9, 2002•22 citations

Fault-Tolerant Coding for Quantum Communication

Matthias Christandl, Alexander Müller‐Hermes

Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel$T$and every$\epsilon >0$there exists a threshold$p(\epsilon,T)$for the gate error probability below which rates larger than$C-\epsilon $are fault-tolerantly achievable with vanishing overall communication error, where$C$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.

arXiv:2009.07161•IEEE Transactions on Information Theory•Apr 21, 2022•15 citations
In this paper the problem of reliable communication with a noisy encoder is examined. We explicitly provided the construction of the encoder and show that even when all logic gates that constitute the encoder are noisy, reliable communication with a positive rate is still possible. The encoding complexity is shown to be O(log 1/ptar/log1/ε) per bit to achieve a target bit error rate ptar, where ε denotes the error probability of each noisy gate. This complexity upper bound is shown to coincide with a lower bound in order sense, and is hence tight. The key technique in the proposed construction is to embed noisy decoders inside the noisy encoder, which are utilized repeatedly to prevent the bit error rate from escalating. The proposed noisy encoder has a direct application in noisy computing of a linear transform.
We consider the problem of computing a binary linear transformation when all circuit components are unreliable. Two models of unreliable components are considered: probabilistic errors and permanent errors. We introduce the “ENCODED” technique that ensures that the error probability of the computation of the linear transformation is kept bounded below a small constant independent of the size of the linear transformation even when all logic gates in the computation are noisy. By deriving a lower bound, we show that in some cases, the computational complexity of the ENCODED technique achieves the optimal scaling in error probability. Further, we examine the gain in energy-efficiency from the use of a “voltage-scaling” scheme, where gate-energy is reduced by lowering the supply voltage. We use a gate energy-reliability model to show that tuning gate-energy appropriately at different stages of the computation (“dynamic” voltage scaling), in conjunction with ENCODED, can lead to orders of magnitude energy-savings over the classical “uncoded” approach. Finally, we also examine the problem of computing a linear transformation when noiseless decoders can be used, providing upper and lower bounds to the problem.
We consider the problem of computing a binary linear transform when all circuit components are unreliable. We propose a novel “ENCODED” technique that uses LDPC (low-density parity-check) codes and embedded noisy decoders to keep the error probability of the computation below a small constant independent of the size of the linear transform, even when all logic gates in the computation are prone to probabilistic errors. Unlike existing works on applying coding to computing with unreliable components, the “ENCODED” technique explicitly considers the errors that happen during both the encoding and the decoding phases. Further, we show that ENCODED requires fewer operations (in order sense) than repetition techniques.
Quantum memory systems are vital in quantum information processing for dependable storage and retrieval of quantum states. Inspired by classical reliability theories that synthesize reliable computing systems from unreliable components, we formalize the problem of reliable storage of quantum information using noisy components. We introduce the notion of stable quantum memories and define the storage rate as the ratio of the number of logical qubits to the total number of physical qubits as well as the circuit complexity of the decoder, which includes both quantum gates and measurements. We demonstrate that a strictly positive storage rate can be achieved by constructing a quantum memory system with quantum expander codes. Moreover, by reducing the reliable storage problem to reliable quantum communication, we provide upper bounds on the achievable storage capacity. In the case of physical qubits corrupted by noise satisfying hypercontractivity conditions, we provide a tighter upper bound on storage capacity using an entropy dissipation argument. Furthermore, observing that the time complexity of the decoder scales nontrivially with the number of physical qubits, achieving asymptotic rates may not be possible due to the induced dependence of the noise on the number of physical qubits. In this constrained nonasymptotic setting, we derive upper bounds on storage capacity using finite blocklength communication bounds. Finally, we numerically analyze the gap between upper and lower bounds in both asymptotic and nonasymptotic cases, and provide suggestions to tighten the gap.
We obtain strict upper bounds on the bit transmission rate for communication of Classical bit codewords over Quantum channels. Albeit previous arguments in arXiv: 1804.01797 which have demonstrated that lower bounds can be shown to hold for the bit transmission rate without the presence of significant noise over the channel shared by Alice and Bob for the purposes of encoding, decoding, transmission and authentication, the author suggests that upper bounding the bit transmission rate could be of use towards classifying paradoxical aspects of communication protocols, as well as constructing error correcting codes which are resilient to noise. The upper bound that is obtained in this work for the bit transmission rate, as a converse result, is dependent upon the natural logarithm of the size of each player's alphabet, as well as smaller alphabets, which can be leveraged for simultaneously realizing Quantum advantage for maximizing error correction and minimizing false acceptance. Crucially, the upper bound to the bit transmission rate is dependent upon a pruning procedure, which seeks to determine whether letters from player's alphabets can be removed so that prospective Quantum advantage, in order for Alice and Bob to implement error correction protocols with high probability, despite the fact that there is more noise over the channel between Alice and Bob in comparison to that between Bob and Eve.
Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channelTTTand everyϵ>0\epsilon >0ϵ>0there exists a thresholdp(ϵ,T)p(\epsilon,T)p(ϵ,T)for the gate error probability below which rates larger than$C-\epsilon arefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereare fault-tolerantly achievable with vanishing overall communication error, wherearefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereC$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.