Workshop on Physics and Computation (PhysComp)

Linear Logic For Generalized Quantum Mechanics

Vaughan Pratt

Published Aug 24, 2005• 31 citations

Abstract

Quantum logic is static, describing automata having uncertain states but no state transitions and no Heisenberg uncertainty tradeoff. We cast Girard's linear logic in the role of a dynamic quantum logic, regarded as an extension of quantum logic with time nonstandardly interpreted over a domain of linear automata and their dual linear schedules. In this extension the uncertainty tradeoff emerges via the "structure veil." When VLSI shrinks to where quantum effects are felt, their computer-aided design systems may benefit from such logics of computational behavior having a strong connection to quantum mechanics. 1 Motivation VLSI designers will eventually need to reckon with quantum mechanics (QM), certainly within 50 years and possibly by the 2010's. Computer-aided design (CAD) tools will need to adapt accordingly. Does this entail changing only the theory or also the logic of CAD verification systems? That is, will it be enough just to change those nonlogical axioms defining how elect...

DOI: 10.1109/phycmp.1992.615518

Related papers

A Uniform Mathematical Representation of Logic and Computation.

Mahesh M. Bandi

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.

Sep 4, 20020 citations

Logic Synthesis for Quantum State Generation

Philipp Niemann, Rhitam Datta, Robert Wille

Quantum computation established itself as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided-design (CAD). However, quantum mechanical phenomena such as superposition, phase shifts, or entanglement lead to a logic model which poses serious challenges to the development of a proper design flow for quantum circuits. Consequently, researchers addressed synthesis of quantum circuits not as a single design step, but considered sub-tasks such as synthesis of Boolean components or synthesis of restricted subsets of quantum functionality. Generating a particularly desired quantum state is another of these sub-tasks. However, logic synthesis of quantum circuits accomplishing that has hardly been considered yet. In this work, we propose a generic method which automatically synthesizes a quantum circuit generating any desired quantum state from an initially given basis state. The proposed method allows for both, a theoretical determination of upper bounds as well as an experimental evaluation of the number of quantum gates needed for this important design step.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 201631 citations

Quantum logic as motivated by quantum computing

Jon Michael Dunn, Tobias Hagge, Lawrence S. Moss +1 more

§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.

arXiv:math/0412144Journal of Symbolic LogicJun 1, 200526 citations

A Theory of Computation Based on Quantum Logic (I)

Mingsheng Ying

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.

arXiv:cs/0403041Mar 29, 20040 citations

Semantic Analysis of a Linear Temporal Extension of Quantum Logic and Its Dynamic Aspect

Tsubasa Takagi

Although various dynamic or temporal logics have been proposed to verify quantum protocols and systems, these two viewpoints have not been studied comprehensively enough. We propose Linear Temporal Quantum Logic (LTQL), a linear temporal extension of quantum logic with a quantum implication, and extend it to Dynamic Linear Temporal Quantum Logic (DLTQL). This logic has temporal operators to express transitions by unitary operators (quantum gates) and dynamic ones to express those by projections (projective measurement). We then prove some logical properties of the relationship between these two transitions expressed by LTQL and DLTQL. A drawback in applying LTQL to the verification of quantum protocols is that these logics cannot express the future operator in linear temporal logic. We propose a way to mitigate this drawback by using a translation from (D)LTQL to Linear Temporal Modal Logic (LTML) and a simulation. This translation reduces the satisfiability problem of (D)LTQL formulas to that of LTML with the classical semantics over quantum states.

ACM Transactions on Computational LogicDec 16, 20221 citation

A Pragmatic Interpretation of Quantum Logic

Claudio Garola

Scholars have wondered for a long time whether quantum mechanics (QM) subtends a quantum concept of truth which originates quantum logic (QL) and is radically different from the classical (Tarskian) concept of truth. We show in this paper that QL can be interpreted as a pragmatic language of pragmatically decidable assertive formulas, which formalize statements about physical systems that are empirically justified or unjustified in the framework of QM. According to this interpretation, QL formalizes properties of the metalinguistic concept of empirical justification within QM rather than properties of a quantum concept of truth. This conclusion agrees with a general integrationist perspective, according to which nonstandard logics can be interpreted as theories of metalinguistic concepts different from truth, avoiding competition with classical notions and preserving the globality of logic. By the way, some elucidations of the standard concept of quantum truth are also obtained.

arXiv:quant-ph/0507122Jul 13, 20058 citations