A Theory of Computation Based on Quantum Logic (I)

Details A Theory of Computation Based on Quantum Logic (I) A Theory of Computation Based on Quantum Logic (I)

2004-03-29

arxiv.org/abs/cs/0403041v1

Computer Science

Logic in Computer Science

Scientific paper

The (meta)logic underlying classical theory of computation is Boolean (two-valued) logic. Quantum logic was proposed by Birkhoff and von Neumann as a logic of quantum mechanics more than sixty years ago. The major difference between Boolean logic and quantum logic is that the latter does not enjoy distributivity in general. The rapid development of quantum computation in recent years stimulates us to establish a theory of computation based on quantum logic. The present paper is the first step toward such a new theory and it focuses on the simplest models of computation, namely finite automata. It is found that the universal validity of many properties of automata depend heavily upon the distributivity of the underlying logic. This indicates that these properties does not universally hold in the realm of quantum logic. On the other hand, we show that a local validity of them can be recovered by imposing a certain commutativity to the (atomic) statements about the automata under consideration. This reveals an essential difference between the classical theory of computation and the computation theory based on quantum logic.

Affiliated with

Also associated with

No associations

Rating

A Theory of Computation Based on Quantum Logic (I) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Theory of Computation Based on Quantum Logic (I), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Theory of Computation Based on Quantum Logic (I) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-240911