# Minimum depth of addition and multiplication circuit using XOR and AND gates

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

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.

• 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. – AdveRSAry May 13 '17 at 16:21