0
\$\begingroup\$

I read the following from a textbook: "applying the Toffoli gate twice to a set of bits has the effect (a, b, c) → (a, b, c ⊕ ab) → (a, b, c), and thus the Toffoli gate is a reversible gate, since it has an inverse – itself."

I'm confused why we write the first transformation as c ⊕ ab? I understand the modulo part, however, I don't understand what it means by "ab", is this multiplying a and b together?

\$\endgroup\$
1
  • \$\begingroup\$ ab = a and b in standard notation \$\endgroup\$ Aug 19 '21 at 20:11
1
\$\begingroup\$

It means to multiply them, but in boolean this defines the "and" function. This is reversible because if you repeat the exclusive or with the same value, the original left side value is restored. This can be extended to a tricky way to swap two values without intermediate storage:

a ^= b

b ^= a

a ^= b

Now a' = a ^ b ^ a = b, and b' = b ^ a ^ b = a.

\$\endgroup\$

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.