Closed Systems of Invertible Maps

Publication date 28 January 2020

Full work available at URL https://arxiv.org/abs/1512.06813, https://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-32-number-5-6-2019/mvlsc-32-5-6-p-565-605/

zbMATH Keywords

clones general algebra iterative algebras mappings multiple-valued logic reversible computation Toffoli gate

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Other nonclassical models of computation (68Q09) Quantum computation (81P68)

Abstract: We generalise clones, which are sets of functions

f : A^{n} i g h t a r r o w A

, to sets of mappings

f : A^{n} i g h t a r r o w A^{m}

. We formalise this and develop language that we can use to speak about it. We then look at bijective mappings, which have connections to reversible computation, which is important for physical (e.g. quantum computation) as well as engineering (e.g. heat dissipation) reasons. We generalise Toffoli's seminal work on reversible computation to arbitrary arity logics. In particular, we show that some restrictions he found for reversible computation on alphabets of order 2 do not apply for odd order alphabets. For

A

odd, we can create all invertible mappings from the Toffoli 1- and 2-gates, demonstrating that we can realise all reversible mappings from four generators. We discuss various forms of closure, corresponding to various systems of permitted manipulations. These correspond, amongst other things, to discussions about ancilla bits in quantum computation.

Recommendations

Cited in

(4)

This page was built for publication: Closed Systems of Invertible Maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212300)