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

enter image description here

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.

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

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

The process for mapping ANF to toffoli network works, but only if the ANF is correct.

  • $\begingroup$ For completeness of the answer for a later reader, remove step 3 of the circuit construction above. $\endgroup$ – AHusain Nov 5 '18 at 5:30
  • 1
    $\begingroup$ Don’t forget to ‘uncompute’ the ancilla s afterwards. $\endgroup$ – DaftWullie Nov 5 '18 at 6:29

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.