XOR-AND-XOR Logic Forms for Autosymmetric Functions and Applications to Quantum Computing

We propose a new three-level XOR-AND-XOR form for autosymmetric functions, called XORAX expression. In general, a Boolean function f over n variables is k-autosymmetric if it can be projected onto a smaller function fk, which depends on n-k variables only. We show that XORAX expressions can ease the reversible synthesis of autosymmetric functions, producing compact reversible networks, without inserting additional new input lines. Autosymmetry occurs especially for functions that exhibit a regular structure, as for instance arithmetic functions. For this reason, compact reversible networks for autosymmetric functions might be interesting for quantum computing. Experimental results validate the proposed approach.