# Mapping Algebraic Normal Form of Exclusive Sum of Products to Toffoli Network

How does one map an ANF to a toffoli network? Is there a straight-forward procedure for doing this?

For example, given the ANF for the Sum function of an adder: $$S = A \oplus B \oplus C \oplus ABC$$

I thought that mapping would be trivial following the process of

1) Perform $$A \oplus B$$ with two CNOT gates, storing the result in ancilla bit, call it $$Anc_1$$

2) Perform $$Anc_1 \oplus C$$ with two CNOT gates, storing the result in $$Anc_2$$

3) Perform $$Anc_2 \oplus ABC$$ using a CNOT and a 3-control bit toffoli, storing the result in the output, $$S$$

This process results in this circuit Why does this not work? What is the process to map an ANF to a toffoli network?

Thank you

PS I apologize for not being able to find an appropriate tag.

• Great question! Also, added a few tags (: Nov 4, 2018 at 23:54
• "Why does this not work?" is hard to answer when you don't say why you think it doesn't work. Nov 5, 2018 at 17:59

My mistake. The ANF for the sum function of an adder is $$S = A \oplus B \oplus C$$