Skip to main content Skip to main navigation

Publikation

Self-Inverse Functions and Palindromic Circuits

Mathias Soeken; Michael Kirkedal Thomsen; Gerhard W. Dueck; D. Michael Miller
In: Reed-Muller Workshop. Reed-Muller Workshop, May 21, Waterloo, Canada, 2015.

Zusammenfassung

We investigate the subclass of reversible functions that are self-inverse and relate them to reversible circuits that are equal to their reverse circuit, which are called palindromic circuits. We precisely determine which self-inverse functions can be realized as a palindromic circuit. For those functions that cannot be realized as a palindromic circuit, we find alternative palindromic representations that require an extra circuit line or quantum gates in their construction. Our analyses make use of involutions in the symmetric group S2n which are isomorphic to self-inverse reversible function on n variables.