×

Towards a theory of conservative computing. (English) Zbl 1119.81312

Summary: We extend the notion of conservativeness, given by E. Fredkin and T. Toffoli [Int. J. Theor. Phys. 21, 219–253 (1982; Zbl 0496.94015)], 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 \(\mathbb C^{d}\), where \(d\) is the number of energy levels considered in the framework.

MSC:

81P68 Quantum computation
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Citations:

Zbl 0496.94015
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cattaneo, G.; Leporati, A.; Leporini, R., Fredkin gates for finite-valued reversible and conservative logics, Journal of Physics A: Mathematical and General, 35, 9755-9785 (2002) · Zbl 1049.81012 · doi:10.1088/0305-4470/35/46/304
[2] Cattaneo, G., Leporati, A., and Leporini, R. (in press). Quantum conservative gates for finite-valued logics. International Journal of Theoretical Physics. · Zbl 1063.81025
[3] Fredkin, E.; Toffoli, T., Conservative logic, International Journal of Theoretical Physics, 21, 219-253 (1982) · Zbl 0496.94015 · doi:10.1007/BF01857727
[4] Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability. A Guide to the Theory on NP-completeness, W. H. Freeman and Company. · Zbl 0411.68039
[5] Gottesman, D., Fault-tolerant quantum computation with higher-dimensional systems, Chaos, Solitons, and Fractals, 10, 1749-1758 (1999) · Zbl 0964.81017
[6] Leporati, A. (2002). Threshold Circuits and Quantum Gates. Ph.D. thesis, Computer Science Department, University of Milan, Italy.
[7] Petri, C. A. (1967). Gründsatzliches zur Beschreibung diskreter Prozesse. In Proceedings of the 3rd Colloquium über Automatentheorie, Hannover, 1965; Birkhäuser Verlag, Basel, pp. 121-140 (English translation: Fundamentals of the Representation of Discrete Processes, ISF Report 82.04 (1982)). · Zbl 0157.33701
[8] Rescher, N., Many-Valued Logics (1969), New York: McGraw-Hill, New York · Zbl 0248.02023
[9] Rosser, J. B.; Turquette, A. R., Many-Valued Logics (1952), Amsterdam: North Holland, Amsterdam · Zbl 0047.01503
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.