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

Coding for Logical Operations

Shmuel Winograd

Published Oct 1, 1962• 12 citations
Publisher

Abstract

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.

DOI
10.1147/rd.64.0430

Related papers

Computation in the Presence of Noise

Peter Eliaš

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.

IBM Journal of Research and Development•Oct 1, 1958•72 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

On the error-correcting capability of optimum linear block codes

O.O. Olaniyan, L.F. Turner

The performance of optimum linear block codes has been examined by computer simluation, and the error distribution at the decoder output, the block-error probability and the bit-error probability have been determined for the codes when they are used on a binary symmetric channel with random errors. A table showing the distribution of errors in the decoder output is presented, and it is shown how the table can be used to determine exact values for the bit-error probability and the block-error probability. The exact values of bit-error probability computed from the table are compared with values obtained using a known theoretical approximation to the bit-error probability, and some conclusions are drawn as to the general usefulness of the theoretical approximation. Also, block-error probabilities are computed from the information presented in the table and these values are compared with the estimates of block-error probability obtained from minimumdistance considerations.

Proceedings of the Institution of Electrical Engineers•Jan 1, 1976•4 citations

Reed–Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

Avijit Mandal, Henry D. Pfister

The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of$2^{o(\sqrt{\log N})}$bits can be decoded with high probability when the code rate is less than the Holevo capacity.

arXiv:2502.03785•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

Error-correcting codes for list decoding

Peter Eliaš

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>

IEEE Transactions on Information Theory•Jan 1, 1991•184 citations

Disjointness of Stabilizer Codes and Limitations on Fault-Tolerant Logical Gates

Tomas Jochym-O’Connor, Aleksander Kubica, Theodore J. Yoder

A new analysis quantifies computational limitations on stabilizer codes (codes that correct errors in quantum information) for practical operations and provides insight into how to design stabilizer codes for useful and interesting applications.

arXiv:1710.07256•Physical Review X•May 21, 2018•60 citations
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.
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.
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.
The performance of optimum linear block codes has been examined by computer simluation, and the error distribution at the decoder output, the block-error probability and the bit-error probability have been determined for the codes when they are used on a binary symmetric channel with random errors. A table showing the distribution of errors in the decoder output is presented, and it is shown how the table can be used to determine exact values for the bit-error probability and the block-error probability. The exact values of bit-error probability computed from the table are compared with values obtained using a known theoretical approximation to the bit-error probability, and some conclusions are drawn as to the general usefulness of the theoretical approximation. Also, block-error probabilities are computed from the information presented in the table and these values are compared with the estimates of block-error probability obtained from minimumdistance considerations.
The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of2o(log⁡N)2^{o(\sqrt{\log N})}2o(logN​)bits can be decoded with high probability when the code rate is less than the Holevo capacity.
In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>