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

IBM Journal of Research and Development

Computation in the Presence of Noise

Peter Eliaš

Published Oct 1, 1958• 72 citations
Publisher

Abstract

The behavior of a system consisting of a preliminary coder, an unreliable computer, and a decoder is investigated. Coding input blocks of k binary digits into output blocks of n>k binary digits, it is shown that a simple combinational computer which can take the and or or of k or more input blocks can only be made arbitrarily reliable by making n/k arbitrarily large, so that the capacity for computation, in an information theory coding sense, is zero. Incomplete results for a single and or or circuit give the same result if the output gives no information about the inputs except for the information about their and or or; if this is not demanded, then for n>2k, reliable computation through noisy computing circuits is possible, but the computing is done in the decoder.

DOI
10.1147/rd.24.0346

Related papers

Coding for Logical Operations

Shmuel Winograd

The behavior of a computation system consisting of encoders, an unreliable logical operator and a decoder is investigated. It is shown that for almost all Boolean functions, coding each block of k input bits into a block of n bits such that all sets of s or less errors will be corrected requires that n ≥ (2s + 1)k. This result suggests that the capacity (in the information theoretical sense) of such a computation system is zero.

IBM Journal of Research and Development•Oct 1, 1962•12 citations

Performance of LDPC Codes Under Faulty Iterative Decoding

Lav R. Varshney

Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided.

arXiv:0806.1215•IEEE Transactions on Information Theory•Jun 21, 2011•112 citations

Fault-Tolerant Quantum Input/Output

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor’s algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and Müller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction of random errors.

arXiv:2408.05260•IEEE Transactions on Information Theory•Mar 10, 2026•11 citations

Memory effects can make the transmission capability of a communication channel uncomputable

David Elkouss, David Pérez-García

Most communication channels are subjected to noise. One of the goals of information theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels-information-stable finite state machine channels-restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.

arXiv:1601.06101•Nature Communications•Mar 14, 2018•27 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

Min-Sum-based decoders running on noisy hardware

Christiane L. Kameni Ngassa, Valentin Savin, David Declercq

This paper deals with Low-Density Parity-Check decoders running on noisy hardware. This represents an unconventional paradigm in communication theory, since it is traditionally assumed that the error correction decoder operates on error-free devices and the randomness (in the form of noise and/or errors) exists only in the transmission channel. However, with the advent of nanoelectronics, it starts to be widely accepted that the future generations of circuits and systems will need to reliability compute and solve statistical inferences, by making use of unreliable “noisy” components. It is then critical to properly evaluate the robustness of the existing decoders in the presence of an additional source of noise at the circuit level. To this end, we first introduce a new error model approach and carry out the “noisy” density evolution analysis of the fixed-point Min-Sum decoding. Then, for different parameters of the noisy components of the decoder, we determine the range of the signal-to-noise ratio values for which the decoder is able to achieve a target bit error rate performance. Finally, we evaluate the finite-length performance of the Min-Sum and two other Min-Sum-based decoders running on noisy hardware.

Globecom•Dec 1, 2013•42 citations
The behavior of a system consisting of a preliminary coder, an unreliable computer, and a decoder is investigated. Coding input blocks of k binary digits into output blocks of n>k binary digits, it is shown that a simple combinational computer which can take the and or or of k or more input blocks can only be made arbitrarily reliable by making n/k arbitrarily large, so that the capacity for computation, in an information theory coding sense, is zero. Incomplete results for a single and or or circuit give the same result if the output gives no information about the inputs except for the information about their and or or; if this is not demanded, then for n>2k, reliable computation through noisy computing circuits is possible, but the computing is done in the decoder.
Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided.
Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor’s algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and Müller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction of random errors.
Most communication channels are subjected to noise. One of the goals of information theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels-information-stable finite state machine channels-restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.
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.
This paper deals with Low-Density Parity-Check decoders running on noisy hardware. This represents an unconventional paradigm in communication theory, since it is traditionally assumed that the error correction decoder operates on error-free devices and the randomness (in the form of noise and/or errors) exists only in the transmission channel. However, with the advent of nanoelectronics, it starts to be widely accepted that the future generations of circuits and systems will need to reliability compute and solve statistical inferences, by making use of unreliable “noisy” components. It is then critical to properly evaluate the robustness of the existing decoders in the presence of an additional source of noise at the circuit level. To this end, we first introduce a new error model approach and carry out the “noisy” density evolution analysis of the fixed-point Min-Sum decoding. Then, for different parameters of the noisy components of the decoder, we determine the range of the signal-to-noise ratio values for which the decoder is able to achieve a target bit error rate performance. Finally, we evaluate the finite-length performance of the Min-Sum and two other Min-Sum-based decoders running on noisy hardware.