5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Great question! Also, added a few tags (: $\endgroup$
    – user820789
    Nov 4, 2018 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, 2018 at 17:59

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

Your Answer

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

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