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

Mathematics of Computation

Reliable Computation in the Presence of Noise

Richard W. Hamming, Shmuel Winograd, Jack D. Cowan

Published Jul 1, 1964• 253 citations
Publisher
DOI
10.2307/2003803

Related papers

Deterministic Simulation of Noise

Thomas Grurl, Jürgen Fuß, Robert Wille

Synthesis lectures on engineering, science, and technology•Nov 29, 2024•0 citations

Reliable Computation by Large-Alphabet Formulas in the Presence of Noise

Andrew K. Tan, Matthew H. Ho, Isaac L. Chuang

We present two new positive results for reliable computation using formulas over physical alphabets of size$q \gt 2$. First, we show that for logical alphabets of size$\ell = q$the threshold for denoising using gates subject to q-ary symmetric noise with error probability$\varepsilon $is strictly larger than that for Boolean computation, and we show that reliable computation is possible as long as signals remain distinguishable, i.e.$\epsilon \lt (q - 1) / q$, in the limit of large fan-in$k \rightarrow \infty $. We also determine the point at which generalized majority gates with bounded fan-in fail, and show in particular that reliable computation is possible for$\epsilon \lt (q - 1) / (q (q + 1))$in the case of q prime and fan-in$k = 3$. Secondly, we provide an example where$\ell \lt q$, showing that reliable Boolean computation,$\ell = 2$, can be performed using 2-input ternary,$q = 3$, logic gates subject to symmetric ternary noise of strength$\varepsilon \lt 1/6$by using the additional alphabet element for error signaling.

arXiv:2306.13262•IEEE Transactions on Information Theory•Nov 1, 2024•2 citations

Reliable Devices Yield Stable Quantum Computations

Samudra Dasgupta, Travis S. Humble

Stable quantum computation requires noisy results to remain bounded even in the presence of noise fluctuations. Yet non-stationary noise processes lead to drift in the varying characteristics of a quantum device that can greatly influence the circuit outcomes. Here we address how temporal and spatial variations in noise relate device reliability to quantum computing stability. First, our approach quantifies the differences in statistical distributions of characterization metrics collected at different times and locations using Hellinger distance. We then validate an analytical bound that relates this distance directly to the stability of a computed expectation value. Our demonstration uses numerical simulations with models informed by the washington superconducting transmon device. We find that the stability metric is consistently bounded from above by the corresponding Hellinger distance, which can be cast as a specified tolerance level. These results underscore the significance of reliable quantum computing devices and the impact for stable quantum computation.

arXiv:2307.05381•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•6 citations

Classical and probabilistic computation

Joseph M. Landsberg

Graduate studies in mathematics•Jun 19, 2024•0 citations

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

Error correction and fault-tolerant computation

Chiara Macchiavello, Guillermo Palma

Springer eBooks•Jun 1, 2001•2 citations
We present two new positive results for reliable computation using formulas over physical alphabets of sizeq>2q \gt 2q>2. First, we show that for logical alphabets of sizeℓ=q\ell = qℓ=qthe threshold for denoising using gates subject to q-ary symmetric noise with error probability$\varepsilon isstrictlylargerthanthatforBooleancomputation,andweshowthatreliablecomputationispossibleaslongassignalsremaindistinguishable,i.e.is strictly larger than that for Boolean computation, and we show that reliable computation is possible as long as signals remain distinguishable, i.e.isstrictlylargerthanthatforBooleancomputation,andweshowthatreliablecomputationispossibleaslongassignalsremaindistinguishable,i.e.\epsilon \lt (q - 1) / q,inthelimitoflargefan−in, in the limit of large fan-in,inthelimitoflargefan−ink \rightarrow \infty .Wealsodeterminethepointatwhichgeneralizedmajoritygateswithboundedfan−infail,andshowinparticularthatreliablecomputationispossiblefor. We also determine the point at which generalized majority gates with bounded fan-in fail, and show in particular that reliable computation is possible for.Wealsodeterminethepointatwhichgeneralizedmajoritygateswithboundedfan−infail,andshowinparticularthatreliablecomputationispossiblefor\epsilon \lt (q - 1) / (q (q + 1))inthecaseofqprimeandfan−inin the case of q prime and fan-ininthecaseofqprimeandfan−ink = 3.Secondly,weprovideanexamplewhere. Secondly, we provide an example where.Secondly,weprovideanexamplewhere\ell \lt q,showingthatreliableBooleancomputation,, showing that reliable Boolean computation,,showingthatreliableBooleancomputation,\ell = 2,canbeperformedusing2−inputternary,, can be performed using 2-input ternary,,canbeperformedusing2−inputternary,q = 3,logicgatessubjecttosymmetricternarynoiseofstrength, logic gates subject to symmetric ternary noise of strength,logicgatessubjecttosymmetricternarynoiseofstrength\varepsilon \lt 1/6$by using the additional alphabet element for error signaling.
Stable quantum computation requires noisy results to remain bounded even in the presence of noise fluctuations. Yet non-stationary noise processes lead to drift in the varying characteristics of a quantum device that can greatly influence the circuit outcomes. Here we address how temporal and spatial variations in noise relate device reliability to quantum computing stability. First, our approach quantifies the differences in statistical distributions of characterization metrics collected at different times and locations using Hellinger distance. We then validate an analytical bound that relates this distance directly to the stability of a computed expectation value. Our demonstration uses numerical simulations with models informed by the washington superconducting transmon device. We find that the stability metric is consistently bounded from above by the corresponding Hellinger distance, which can be cast as a specified tolerance level. These results underscore the significance of reliable quantum computing devices and the impact for stable quantum computation.
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.