A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in a sense just be “turned in reverse” without changing the circuit architecture.

An invertible function is not defined in terms of computational models, but in terms of whether the function is injective.

How are these two concepts related? Does an invertible function always have a corresponding reversible circuit? How does this relate to one-way functions? (Note that if for any invertible function there is a reversible circuit, that doesn’t disprove the existence of one-way functions, since the fast-to-compute circuit might not be reversible).

  • $\begingroup$ I suggest asking about one-way function separately, since that seems like a fairly separate/orthogonal question. This post seems to have a single well-defined question: Does every invertible function have a corresponding reversible circuit? $\endgroup$ – D.W. Sep 22 '18 at 6:18
  • $\begingroup$ Every permutation (i.e., invertible function) can be expressed as a composition of transpositions, so it suffices to check whether every transposition can be computed by a reversible circuit. Designing such a circuit sounds like an exercise that might be feasible. Or, one can use any other set of generators for the symmetric group on $\{0,1\}^n$ (e.g., cycles). It also suggests a follow-up question: can every invertible function that can be computed by an ordinary circuit of polynomial size, be computed by a reversible circuit of polynomial size? $\endgroup$ – D.W. Sep 22 '18 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.