Orthologic and quantum logic: models and computational elements

ABSTRACT

Motivated by a growing need to understand the computational potential of quantum devices we suggest an approach to the relevant issues via quantum logic and its model theory. By isolating such notions as quantum parallelism and interference within a model-theoretic setting, quite divorced from their customary physical trappings, we seek to lay bare their logical underpinnings and possible computational ramifications. In the first part of the paper, a brief account of the relevant model theory is given, and some new results are derived. In the second part, we model the simplest classical gate, namely the N-gate, propose a quantization scheme (which translates between classical and quantum models, and from which emerges a logical interpretation of the notion of quantum parallelism), and apply it to the classical N-gate model. A class of physical instantiations of the resulting quantum N-gate model is also briefly discussed.

REFERENCES

• 1: Andrea Asperti , Giuseppe Longo, Categories, types, and structures: an introduction to category theory for the working computer scientist, MIT Press, Cambridge, MA, 1991
• 2: BAER, R. 1952. Linear Algebra and Projective Geometry. Academic Press, New York.
• 3: Michael Barr , Charles Wells, Category theory for computing science, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: BELL, J. L. 1983. Orthologic, forcing and the manifestation of attributes. In Proceedings of the Southeast Asian Conference on Logic. Studies in Logic, vol. III. North-Holland, Amsterdam, The Netherlands, pp. 13-36.
• 5: BELL, J.L. 1986. A new approach to quantum logic. Brit. J. Phil Sci. 37, 83-99.
• 6: BELL, J. L. 1988. Toposes and Local Set Theories. Oxford Logic Guides: 14, Clarendon Press, Oxford, England.
• 7: BERMAN, G., DOOLEN, G. D., MAINIERI, R., AND TSIFRINOVICH, g. I. 1998. Introduction to Quantum Computers. World Scientific Publishing, Singapore.
• 8: BuB, J. 1997. Interpreting the Quantum World. Cambridge University Press, Cambridge, England. BURGHARDT, F.J. 1984. Modalities and quantum mechanics. Int. J. Theoret. Phys. 23, 1171-1195 .
• 9: CHELLAS, B. F. 1980. Modal Logic: An Introduction. Cambridge University Press, Cambridge, England.
• 10: DALLA CHIARA, M.L. 1979. Some metalogical pathologies of quantum logic. In Current Issues in Quantum Logic, Workshop on Quantum Logic, (Erice), E. G. Beltrametti and B. C. van Fraassen, Eds. Plenum Press, New York, pp. 147-159.
• 11: DALLA CHIARA, M. L. 1986. Quantum logic. In Handbook of Philosophical Logic, Vol. III. D. Gabbay and F. Guenther, Eds. D. Reidel Publishing Company.
• 12: DEUTSCH, D. 1985. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Royal Soc. London A400, 97-117.
• 13: DEUTSCH, D. 1989. Quantum computational networks. Proc. Royal Soc. London A425, 73-90.
• 14: DISHKANT, H. 1977. Imbedding of the quantum logic in the modal system of Brower (sic). J. Symb. Logic 42, 3, 321-328.
• 15: EKERT, A., AND JOZSA, R. 1996. Quantum computation and Schor's factoring algorithm. Rev. Mod. Phys. 68, 3, 733-753.
• 16: GOLDBLATT, R.I.1973. The stone space of an ortholattice. Bull. London Math. Soc. 7, 45-48.
• 17: GOLDBLATT, R.I. 1974. Semantic analysis of orthologic. J. Phil. Logic 3, 19-35.
• 18: GOLDBLATT, R.I. 1984a. Orthomodularity is not elementary. J. Symb. Logic 49, 401-404.
• 19: GOLDBLATT, R.I. 1984b. Topoi: The Categorial Analysis of Logic. North-Holland, Amsterdam, The Netherlands.
• 20: GRAVES, W. H., AND SELESNICK, S.A. 1973. A generalization of the Stone theorem for orthomodular lattices. Colloq. Math. 27, 1, 21-30.
• 21: GREECHIE, R. 1981. A non-standard quantum logic with a strong set of states. In Current Issues in Quantum Logic. Vol. 8 of Ettore Majorana International Science Series, E. G. Beltrametti and B. C. van Fraassen, Eds. Plenum Press, New York, pp. 375-380.
• 22: HUGHES, G. E., AND CRESSWELL, M.J. 1968. An Introduction to Modal Logic: Methuen and Co., Ltd., London, England.
• 23: HUGHES, G. E., AND CRESSWELL, M.J. 1984. A Companion to Modal Logic. Methuen, London, England.
• 24: HUGHES, R. I.G. 1979. Realism and quantum logic. Current Issues in Quantum Logic, Workshop on Quantum Logic, (Erice), E. G. Beltrametti and B. C. van Fraassen, Eds. Plenum Press, New York, pp. 77-87.
• 25: ISHAM, C. J., AND BUTTERFIELD, J. 1998. Topos perspective on the Kochen-Specker Theorem: I. Quantum states as generalised valuations. Int. J. Theoret. Phys. 37, 2669-2733.
• 26: ISHAM, C. J., AND BUTTERFIELD, J. 1999. Topos perspective on the Kochen-Specker Theorem: II Conceptual aspects and classical analogues. Int. J. Theoret. Phys. 38, 827-859.
• 27: KALMBACH, G. 1983. Orthomodular Lattices. Cambridge University Press, Cambridge, Mass.
• 28: SELESNICK, S.A. 1998. Quanta, Logic and Spacetime: Variations on Finkelstein's Quantum Relativity. World Scientific Publishing, Singapore.
• 29: VARADARAJAN, V.S. 1985. Geometry of Quantum Theory (2nd ed.). Springer-Verlag, New York.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Modal logic

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

General Terms:
Theory

Keywords:
Hilbert spaces, quantum computing, quantum logic, quantum physics