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

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

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

Published Nov 1, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2024.3486278

Related papers

On reliable computation by noisy random Boolean formulas

Alexander Mozeika, David Saad

We study noisy computation in randomly generated k-ary Boolean formulas. We establish bounds on the noise level above which the results of computation by random formulas are not reliable. This bound is saturated by formulas constructed from a single majority-like gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.

arXiv:1206.4851•Jan 1, 2012•0 citations

Better gates can make fault-tolerant computation impossible.

Falk Unger

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least β2 = (3− √ 7)/4 ≈ 8.856%, faulttolerant computation is not possible. On the other hand, if all gates fail with probability < β2 and is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with exactly the same probability is pretty strong and unrealistic in real-world scenarios. Furthermore, one might be tempted to think that it can be removed easily, since making gates “better” should not hurt. Surprisingly, this is not the case, as we show in this work: there is a constant α2 < β2 such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range [0, α2]. Hence, while a hardware manufacturer who consistently produces bad gates with noise rate α2 can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most α2 cannot.

Electronic colloquium on computational complexity•Jan 1, 2010•4 citations

Noise threshold for universality of 2-input gates

Falk Unger

Evans and Pippenger showed in 1998 that e-noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability isin and isin0= (3 - radic7)/4 ap8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least isin0cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is isin0. We conjecture that the same threshold also holds for circuits.

arXiv:0711.0351•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•2 citations

Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise

Noah Shutty, Mary K. Wootters, Patrick M. Hayden

It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.

arXiv:1809.09748•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•6 citations

Noise Threshold for Universality of Two-Input Gates

Falk Unger

It is known that epsi-noisy gates with two inputs are universal for arbitrary computation (i.e., can compute any function with bounded error), if all gates fail independently with probability epsi and epsi2= (3 - radic7)/4 ap 8.856%. In this paper, it is shown that this bound is tight for formulas, by proving that gates with two inputs, in which each gate fails with probability at least beta2cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with two-input gates and it is beta2. It is conjectured that the same threshold also holds for circuits.

IEEE Transactions on Information Theory•Jul 24, 2008•17 citations

The Robustness of QAC0

Daniel Grier, Jackson Morris, Kewen Wu

In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.

quant-pharXiv:2610.02154•Oct 2, 2026•0 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 εis strictly larger than that for Boolean computation, and we show that reliable computation is possible as long as signals remain distinguishable, i.e.ϵ<(q−1)/q\epsilon \lt (q - 1) / qϵ<(q−1)/q, in the limit of large fan-ink→∞k \rightarrow \infty k→∞. 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ϵ<(q−1)/(q(q+1))\epsilon \lt (q - 1) / (q (q + 1))ϵ<(q−1)/(q(q+1))in the case of q prime and fan-ink=3k = 3k=3. Secondly, we provide an example whereℓ<q\ell \lt qℓ<q, showing that reliable Boolean computation,ℓ=2\ell = 2ℓ=2, can be performed using 2-input ternary,q=3q = 3q=3, logic gates subject to symmetric ternary noise of strengthε<1/6\varepsilon \lt 1/6ε<1/6by using the additional alphabet element for error signaling.
We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least β2 = (3− √ 7)/4 ≈ 8.856%, faulttolerant computation is not possible. On the other hand, if all gates fail with probability < β2 and is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with exactly the same probability is pretty strong and unrealistic in real-world scenarios. Furthermore, one might be tempted to think that it can be removed easily, since making gates “better” should not hurt. Surprisingly, this is not the case, as we show in this work: there is a constant α2 < β2 such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range [0, α2]. Hence, while a hardware manufacturer who consistently produces bad gates with noise rate α2 can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most α2 cannot.
Evans and Pippenger showed in 1998 that e-noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability isin and isin0= (3 - radic7)/4 ap8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least isin0cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is isin0. We conjecture that the same threshold also holds for circuits.
It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.
It is known that epsi-noisy gates with two inputs are universal for arbitrary computation (i.e., can compute any function with bounded error), if all gates fail independently with probability epsi and epsi2= (3 - radic7)/4 ap 8.856%. In this paper, it is shown that this bound is tight for formulas, by proving that gates with two inputs, in which each gate fails with probability at least beta2cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with two-input gates and it is beta2. It is conjectured that the same threshold also holds for circuits.
In this work we study the robustness of QAC0\mathsf{QAC}^0QAC0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC0\mathsf{QAC}^0QAC0 circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel WWW-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that QAC0\mathsf{QAC}^0QAC0 can \textit{exactly} simulate TC0\mathsf{TC}^0TC0 with polynomially many copies of the classical input and that for every fixed prime ppp exact QAC0\mathsf{QAC}^0QAC0, EQAC0\mathsf{EQAC}^0EQAC0, can compute total Boolean functions outside of AC0[p]\mathsf{AC}^0[p]AC0[p]. Second, we ask to what extent the computational power of QAC0\mathsf{QAC}^0QAC0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC0\mathsf{QAC}^0QAC0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC0\mathsf{QAC}^0QAC0 circuit can be approximately implemented by a QAC0\mathsf{QAC}^0QAC0 circuit consisting of just generalized Toffoli, SSS, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.