Reversible Logic Gates

Fredkin: Conditional Swap

• (a, b, c) => a ? (a, c, b) : (a, b, c)
• (a, b, c) => (a, a and c or !a and b, a and b or !a and c)

Toffoli CCNOT

• invert c iff a and b
• (a, b, c) => a and b ? (a, b, !c) : (a, b, c)
• (a, b, c) => (a, b, (a and b) xor c)

Variant: empty bullets for inverted input