What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we have an OR gate. Can I achieve that using XOR gates?


1 Answer 1


You can simulate an OR gate using a constant number of AND and XOR gates:

$$x \lor y = ((x \oplus 1) \land (y \oplus 1)) \oplus 1.$$

Consequently, anything you can do in depth $d$ using AND and OR gates, can be done in depth $\le 3d$ using AND and XOR gates.

  • $\begingroup$ I'm trying to build a SwHE scheme. Can you please tell me the minimum depth circuit for addition and multiplication in which each gate takes just two inputs at a time? The carry lookahead adder ensures constant depth using gates with variable fan-in. $\endgroup$
    – AdveRSAry
    May 13, 2017 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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