On reliable computation over larger alphabets
share
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 ℓ = q the threshold for denoising using gates subject to q-ary symmetric noise with error probability ϵ is strictly larger that possible for Boolean computation and we demonstrate a clone of q-ary functions that can be reliably computed up to this threshold. Secondly, we provide an example where ℓ < q, showing that reliable Boolean computation can be performed using 2-input ternary logic gates subject to symmetric ternary noise of strength ϵ < 1/6 by using the additional alphabet element for error signalling.
READ FULL TEXT
