Fundamental theories of physics

Partition Logics, Finite Automata and Generalized Urn Models

Karl Svozil

Published Jan 1, 2018• 0 citations

Abstract

Complementarity was first encountered in quantum mechanics. In what follows we shall present finite deterministic models featuring complementarity. The type of complementarity discussed in this chapter grew out of an attempt to understand quantum complementarity by some finite, deterministic, quasi-classical (automaton) model.

DOI: 10.1007/978-3-319-70815-7_19

Related papers

Finite automata models of quantized systems: conceptual status and outlook

Karl Svozil

Since Edward Moore, finite automata theory has been inspired by physics, in particular by quantum complementarity. We review automaton complementarity, reversible automata and the connections to generalized urn models. Recent developments in quantum information theory may have appropriate formalizations in the automaton context.

arXiv:quant-ph/0209089Sep 15, 20020 citations

Quantum automata and quantum computing

Marats Golovkins

Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).

Jan 1, 20020 citations

Contexts in quantum, classical and partition logic

Karl Svozil

Contexts are maximal collections of co-measurable observables "bundled together" to form a "quasi-classical mini-universe." Different notions of contexts are discussed for classical, quantum and generalized urn-automaton systems.

arXiv:quant-ph/0609209Sep 27, 20066 citations

Chapter 8 Quantum computing in automata theory

G. Ignisha Rajathi, R. Vedhapriyavadhana, R. Niranjana +2 more

In the contemporary era we dwell in, every now and then, new technologies are developed by master brains such as researchers and scientists. This also paves the way to discover replacements to classical computers. One such progression among the great inventions is the essence of quantum computing. They are brought to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and in the least span of time. The study of quantum computing focuses on finding new ways to compute by using quantum physics phenomena. A qubit, in contrast to a typical computer bit, can be either 0 or 1, or it can be a superposition of both 0 and 1. Quantum theory commemorates with automata theory, thereby formulating quantum finite automata. Quantum finite automaton, or basically a deterministic finite automaton, is one of the simplest models of computation, which is an input-driven model, which takes an input, and according to the input, we just read the machine, and it changes its state. This proves that any quantum finite automata are completely capable of recognizing languages like Tally with given cut point too. Such languages recognized by a cut point, by quantum finite automata, are called stochastic languages. It further collaborates with the chemical industry with its qubit power over molecular collide, interactive models, and collaborative string processing using nonregular languages.

De Gruyter eBooksAug 7, 20232 citations

Quantum finite automata: A modern introduction

A. C. Cem Say, Abuzer Yakaryılmaz

We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum computation concepts to computer scientists. We also describe a modern QFA model involving superoperators that is able to simulate all known QFA and classical finite automaton variants.

arXiv:1406.4048Jun 16, 20145 citations

Models and characterizations of 1-way quantum finite automata

Brodsky, Alexander

In the past year two different models of quantum finite automata have been proposed. The first model, introduced by Moore and Crutchfield[MC98], makes one measurement on its state at the end of its computation and is called a measure-once quantum finite automata. The second model, introduced by Kondacs and Watrous[KW97], makes a measurement of its state after every transition and is called a measure-many quantum finite automata. In this thesis we investigate the characteristics of the two models. We characterize measure-once quantum finite automata when they are restricted to acceptance with bounded error, and we show that, when they are not so restricted, they can solve the word problem over the free group. We show that they can be simulated by probabilistic finite automata, which implies that they are no more powerful than probabilistic finite automata. We also describe an algorithm that determines if two automata are equivalent. We show that the class of languages accepted by measure-many quantum finite automata is closed under quotient, complement, and inverse homomorphisms. We prove a necessary condition for a language to be accepted by a measure-many automaton with bounded error and we show that certain sets, including piecewise testable sets, can be accepted with bounded error by this automata.

Jan 1, 20091 citation