© The Author, 2005. Published by Oxford University Press. All rights reserved.
Original Articles |
Many-valued Logics in Classical and Quantum Gates
Group of Logic, State University of Campinas, SP, Brazil. E-mail: lungarzo{at}hotmail.com
The research on many valued interpretation in quantum computing [1,3] is rather recent and the theory is not fully developed yet.
The main advantage of this approach seems to be the complexity gain when a computation is based upon general quantum digits (usually called qudits) if compared with time spent by the same algorithm, when running in a equivalent system built up by means of qubits (binary digits). If this assumption is sound, then temporal complexity of algorithms could be significantly simplified.
The use of many-valued semantics in classical logic doesn't convey any precise idea of its physical application, as it happens in the framework of quantum gates. However, we propose an analysis motivated by the known use of finite-many-valued semantic in non-quantum logics. We shall produce a propositional representation for classical gates.
We make explicit the usually implicit relationship between classical and quantum logics, extend in a natural way the many-valued semantics, as used in axiomatic systems of classical logical, to the quantum case (by using Toffoli gate and algebraic properties), define many-valued digits (qu-d-its) and reversible gates based upon them, and extend the functional completeness ("universality") of some gates to the new situation. We conjecture the possibility of enhancing the performance of quantum algorithms, when running in a many-valued quantum system.
Key Words: quantum gates, qudits, complexity
Received 16 December 2003. Revised version 16 June 2004.