Reliable computation by large-alphabet formulas in the presence of noise

Abstract

We present two new positive results for reliable computation using formulas over physical alphabets of size $q>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 $\epsilon$ is strictly larger than that for Boolean computation, and is possible as long as signals remain distinguishable, i.e. $\epsilon <(q-1)/q$, in the limit of large fan-in $k\to \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 <(q-1)/(q(q+1))$ in the case of $q$ prime and fan-in $k=3$. Secondly, we provide an example where $\ell <q$, showing that reliable Boolean computation can be performed using $2$-input ternary logic gates subject to symmetric ternary noise of strength $\epsilon <1/6$ by using the additional alphabet element for error signaling.

20 pages, 4 figures

References in corpus (1)

• Qudits and high-dimensional quantum computing