3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Is this an exercise? $\endgroup$ Jun 7 at 9:59
  • $\begingroup$ 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! :) $\endgroup$
    – J Bausch
    Jun 7 at 10:01
4
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thanks a bunch! That's a super clear answer, no wonder why you were asking whether this was an exercise! :) $\endgroup$
    – J Bausch
    Jun 7 at 10:28
  • $\begingroup$ @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. $\endgroup$
    – Mr.
    Jun 8 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.