Towards a Theory of Conservative Computing

Cattaneo, Gianpiero; Della Vedova, Gianluca; Leporati, Alberto; Leporini, Roberto

Towards a Theory of Conservative Computing

Authors

Cattaneo, Gianpiero

Della Vedova, Gianluca

Leporati, Alberto

Leporini, Roberto

Description

We extend the notion of conservativeness, given by Fredkin and Toffoli in 1982, to generic gates whose input and output lines may assume a finite number d of truth values. A physical interpretation of conservativeness in terms of conservation of the energy associated to the data used during the computation is given. Moreover, we define conservative computations, and we show that they naturally induce a new NP-complete decision problem. Finally, we present a framework that can be used to explicit the movement of energy occurring during a computation, and we provide a quantum implementation of the primitives of such framework using creation and annihilation operators on the Hilbert space C^d, where d is the number of energy levels considered in the framework.
11 pages, 1 figure