# Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?

Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table

00 0
01 0
10 0    (*)
11 1


but such that the case (*) is wrong 1/3 of the time, i.e. it gives 1 with probability 1/3, and 0 with probability 2/3.

Is this gate family universal, in the sense that one can write a logic formula with these gates only, and that the probability of obtaining the right outcome is >1/2? (You also have noise-free SWAP and FANOUT, in case that helps).

Thanks!

• Is this an exercise? Jun 7, 2021 at 9:59
• No. My background isn't in the field, but this is a question that came up in a research topic I'm working on. If it is this simple, I'd also be super happy for a "look at the standard textbook XY" of course! :) Jun 7, 2021 at 10:01

## 1 Answer

Let $$\land_p$$ be a gate with error $$p$$ only when the inputs are $$1$$ and $$0$$. What can we say about $$(x \land_p y) \land_p (x \land_p y)?$$ If $$x=y=1$$ then we always get $$1$$. If $$x = 0$$ then we always get $$0$$. When $$x = 1$$ and $$y = 0$$, we get the wrong answer $$1$$ with probability $$p \cdot p + p \cdot (1-p) \cdot p = p^2(2-p).$$ Call that function $$f(p)$$. We conclude that this construction results in an $$\land_{f(p)}$$ gate.

The function $$f(p)$$ is monotone increasing over $$[0,1]$$, and satisfies $$f(p) \leq 2p^2 = (2p)^2/2$$. Therefore $$f(f(p)) = (2f(p))^2/2 = (2p)^4/2$$. More generally, $$f^{(t)}(p) = (2p)^{2^t}/2$$. Consequently, if we apply this construction recursively $$O(\log\log(1/\epsilon))$$ times to your $$\land_{1/3}$$ gate, we get an $$\land_q$$ gate with error $$q \leq \epsilon$$. This requires a gadget of size $$2^{O(\log\log(1/\epsilon))} = \operatorname{polylog}(1/\epsilon)$$.

To handle a circuit of size $$S$$, you need to choose $$\epsilon = 1/(2S)$$, which results in a blowup of $$\operatorname{polylog}(S)$$.

• Thanks a bunch! That's a super clear answer, no wonder why you were asking whether this was an exercise! :) Jun 7, 2021 at 10:28
• @YuvalFilmus I think $polylog(S)$ is an outer bound and I have some thoughts on this. Perhaps I can email you if I get more insights. This answer is a good lead to me. Jun 8, 2021 at 20:12