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.
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.
§1. Introduction. Our understanding of Nature comes in layers, so should the development of logic. Classic logic is an indispensable part of our knowledge, and its interactions with computer science have recently dramatically changed our life. A new layer of logic has been developing ever since the discovery of quantum mechanics. G. D. Birkhoff and von Neumann introduced quantum logic in a seminal paper in 1936 [1]. But the definition of quantum logic varies among authors (see [2]). How to capture the logic structure inherent in quantum mechanics is very interesting and challenging. Given the close connection between classical logic and theoretical computer science as exemplified by the coincidence of computable functions through Turing machines, recursive function theory, and λ-calculus, we are interested in how to gain some insights about quantum logic from quantum computing. In this note we make some observations about quantum logic as motivated by quantum computing (see [5]) and hope more people will explore this connection. The quantum logic as envisioned by Birkhoff and von Neumann is based on the lattice of closed subspaces of a Hilbert space, usually an infinite dimensional one. The quantum logic of a fixed Hilbert space ℍ in this note is the variety of all the true equations with finitely many variables using the connectives meet, join and negation. Quantum computing is theoretically based on quantum systems with finite dimensional Hilbert spaces, especially the states space of a qubit ℂ2. (Actually the qubit is merely a convenience.
This paper deals with the foundations of quantum mechanics. We start by outlining the characterisation, due to Birkhoff and Von Neumann, of the logical structures of the theories of classical physics and quantum mechanics, as boolean and modular lattices respectively. We then derive these descriptions from what we claim are basic properties of any physical theory - i.e. the notion that a quantity in such a theory may be analysed into parts and that the results of this analysis may be treated in languages with an underlying boolean structure. We shall see that in the course of constructing a model of a theory with these properties different indistinguishable possibilities will arise for how the elements of the model may be named, that is to say different possibilities arise for how they can be associated with points from Set. Taking a particular collection of possibilities gives the usual boolean lattice of the propositions of classical physics. Taking all possibilities - in a sense, the set of all things that may be described by physical theories - gives the lattice of quantum mechanical propositions. This gives an interpretation of quantum mechanics as the complete set of such possible descriptions, the complete physical description of the world.
Quantum logic has been introduced by Birkhoff and von Neumann as an attempt to base the logical primitives, the propositions and the relations and operations among them, on quantum theoretical entities, and thus on the related empirical evidence of the quantum world. We give a brief outline of quantum logic, and some of its algebraic properties, such as nondistributivity, whereby emphasis is given to concrete experimental setups related to quantum logical entities. A probability theory based on quantum logic is fundamentally and sometimes even spectacularly different from probabilities based on classical Boolean logic. We give a brief outline of its nonclassical aspects; in particular violations of Boole-Bell type consistency constraints on joint probabilities, as well as the Kochen-Specker theorem, demonstrating in a constructive, finite way the scarcity and even nonexistence of two-valued states interpretable as classical truth assignments. A more complete introduction of the author can be found in the book "Quantum Logic" (Springer, 1998)
We show that in quantum computation almost every gate that operates on two or more bits is a universal gate. We discuss various physical considerations bearing on the proper definition of universality for computational components such as logic gates. Introduction It has been known for several years that the theory of quantum computers --- i.e. machines that rely on characteristically quantum phenomena to perform computations [1] --- is substantially different from the classical theory of computation, which is essentially the theory of the universal Turing machine. We may identify three important differences. Firstly, the properties of quantum computers are not postulated in abstracto but are deduced entirely from the laws of physics. Logically, this was already true of the classical theory, as Landauer [2] has pointed out, but the intuitive nature of the classically-available computational operations, and the millennia-long history of their study, allowed pioneers such as Turing, Chu...
. We put forward a new take on the logic of quantum mechanics, following Schrödinger's point of view that it is composition which makes quantum theory what it is, rather than its particular propositional structure due to the existence of superpositions, as proposed by Birkhoff and von Neumann. This gives rise to an intrinsically quantitative kind of logic, which truly deserves the name ‘logic’ in that it also models meaning in natural language, the latter being the origin of logic, that it supports automation, the most prominent practical use of logic, and that it supports probabilistic inference. The physics and the logic of quantum-ish logic. In 1932 John von Neumann formalized Quantum Mechanics in his book “Mathematische Grundlagen der Quantenmechanik”. This was effectively the official birth of the quantum mechanical formalism which until now, some 75 years later, has remained the same. Quantum theory underpins so many things in our daily lives including chemical industry, energy production and information technology, which arguably makes it the most technologically successful theory of physics ever. However, in 1935, merely three years after the birth of his brainchild, von Neumann wrote in a letter to American mathematician Garrett Birkhoff: “I would like to make a confession which may seem immoral: I do not believe absolutely in Hilbert space no more.” (sic)—for more details see [73]. Soon thereafter they published a paper entitled “The Logic of Quantum Mechanics” [13]. Their ‘quantum logic’ was cast in order-theoretic terms, very much in the spirit of the then reigning algebraic view of logic, with the distributive law being replaced with a weaker (ortho)modular law. This resulted in a research community of quantum logicians [68, 71, 47, 30]. However, despite von Neumann's reputation, and the large body of research that has been produced in the area, one does not find a trace of this activity neither in the mainstream physics, mathematics, nor logic literature. Hence, 75 years later one may want to conclude that this activity was a failure. What went wrong? The mathematics of it. Let us consider the raison d'être for the Hilbert space formalism.
The current models of computation share varying levels of correspondence with actual implementation schemes. They can be arranged in a hierarchical structure depending upon their level of abstraction. In classical computing, the circuit model shares closest correspondence with physical implementation, followed by finite automata techniques. The highest level in the abstraction hierarchy is that of the theory of computation.Likewise, there exist computing paradigms based upon a different set of defining principles. The classical paradigm involves computing as has been applied traditionally, and is characterized by Boolean circuits that are irreversible in nature. The reversible paradigm requires invertible primitives in order to perform computation. The paradigm of quantum computing applies the theory of quantum mechanics to perform computational tasks.Our analysis concludes that descriptions at lowest level in the abstraction hierarchy should be uniform across the three paradigms, but the same is not true in case of current descriptions. We propose a mathematical representation of logic and computation that successfully explains computing models in all three paradigms, while making a seamless transition to higher levels of the abstraction hierarchy. This representation is based upon the theory of linear spaces and, hence, is referred to as the linear representation. The representation is first developed in the classical context, followed by an extension to the reversible paradigm by exploiting the well-developed theory on invertible mappings. The quantum paradigm is reconciled with this representation through correspondence that unitary operators share with the proposed linear representation. In this manner, the representation is shown to account for all three paradigms. The correspondence shared with finite automata models is also shown to hold implicitly during the development of this representation. Most importantly, the linear representation accounts for the Hamiltonians that define the dynamics of a computational process, thereby resolving the correspondence shared with underlying physical principles.The consistency of the linear representation is checked against a current existing application in VLSI CAD that exploits the linearity of logic functions for symbolic representation of circuits. Some possible applications and applicability of the linear representation to some open problems are also discussed.