Basic Properties of Quantum Automata

Foundations of Physics 30 (2):301-319 (2000)
  Copy   BIBTEX

Abstract

This paper develops a theory of quantum automata and their slightly more general versions, q-automata. Quantum languages and η-quantum languages, 0≤η<1, are studied. Functions that can be realized as probability maps for q-automata are characterized. Quantum grammars are discussed and it is shown that quantum languages are precisely those languages that are induced by a quantum grammar. A quantum pumping lemma is employed to show that there are regular languages that are not η-quantum, 0≤η<1.

Categories

Keywords

Reprint years

DOI

10.1023/a:1003649201735

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 107,599

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On Relation Between Linear Temporal Logic and Quantum Finite Automata.Amandeep Singh Bhatia & Ajay Kumar - 2020 - Journal of Logic, Language and Information 29 (2):109-120.
Free Quantum Field Theory from Quantum Cellular Automata.Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti & Alessandro Tosini - 2015 - Foundations of Physics 45 (10):1137-1152.
Weyl, Dirac and Maxwell Quantum Cellular Automata: Analitical Solutions and Phenomenological Predictions of the Quantum Cellular Automata Theory of Free Fields.Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti & Alessandro Tosini - 2015 - Foundations of Physics 45 (10):1203-1221.
From where do quantum groups come?Moshé Flato, Zhi-Cheng Lu & Daniel Sternheimer - 1993 - Foundations of Physics 23 (4):587-598.
Quantum calculation of thermal effect in quantum‐dot cellular automata.Ioan Sturzu & Mahfuza Khatun - 2005 - Complexity 10 (4):73-78.
Duality Between a Deterministic Cellular Automaton and a Bosonic Quantum Field Theory in 1+1 Dimensions.Gerard ’T. Hooft - 2013 - Foundations of Physics 43 (5):597-614.
Quantum Walks, Weyl Equation and the Lorentz Group.Paolo Perinotti, Giacomo Mauro D’Ariano & Alessandro Bisio - 2017 - Foundations of Physics 47 (8):1065-1076.
Analogues of quantum complementarity in the theory of automata.K. Svozil - 1998 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 29 (1):61-80.
On Quantum Mechanical Automata, Gödel Numbers, and Self-Referring Consciousness.Fred Alan Wolf - 2018 - Cosmos and History 14 (1):217-246.
Super Quantum Measures on Finite Spaces.Yongjian Xie, Aili Yang & Fang Ren - 2013 - Foundations of Physics 43 (9):1039-1065.

Analytics

Added to PP
2013-11-22

Downloads
85 (#274,998)

6 months
16 (#244,836)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references