M O D E L S A N D C H A R A C T E R I Z A T I O N S O F 1-WAY Q U A N T U M F I N I T E A U T O M A T A By Alexander Brodsky B . M a t h . (Computer Science w i t h Physics M i n o r ) University of Waterloo A THESIS SUBMITTED IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS MASTER; FOR T H E DEGREE OF OF SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE W e accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA 1998 © Alexander Brodsky, December, 1998 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia 2366 Main Mall Vancouver, Canada V 6 T 1Z4 Date: Abstract 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. 11 Table of Contents Abstract ii Table of Contents iii List of Figures v Acknowledgement vi 1 Introduction 1 1.1 Quantum Finite Automata 1 1.2 Related Work 3 1.3 Organization 4 2 Background and Definitions 5 2.1 Quantum Mechanics 5 2.2 Notation 8 2.3 Deterministic Finite Automata 8 2.4 Reversible Finite Automata 9 2.5 Probabilistic Finite Automata 9 2.6 Closure Properties 11 2.7 Definition of Measure-Once Quantum Finite Automata 11 2.8 Definition of Measure-Many Quantum Finite Automata 13 2.9 Language Acceptance by a Quantum Finite Automaton 14 2.10 Equivalence of Quantum Finite Automata 14 2.11 Equivalence of MO-QFAs and Moore-Crutchfield QFAs 14 iii 2.12 Equivalence of MM-QFAs and Kondacs-Watrous QFAs 3 Measure-Once Quantum Finite Automata 17 19 3.1 Characterization of MO-QFAs That Accept with Bounded Error 19 3.2 Closure Properties 22 3.3 MO-QFAs Can Accept Non-Regular Sets 25 3.4 Equivalence of MO-QFAs 26 3.5 Simulation of MO-QFAs by PFAs 29 4 Measure-Many Quantum Finite Automata 31 4.1 Closure Properties 31 4.2 Simulation of MO-QFAs 36 4.3 MO-QFAs Are Strictly Less Powerful than MM-QFAs 37 4.4 M M - Q F A s That Accept with Bounded Error 38 4.5 M M - Q F A s Can Accept Piecewise Testable Sets 42 5 Conclusions and Future Work 5.1 50 Open Problems 51 Bibliography 52 iv List of Figures 3.1 GFA M 24 3.2 R F A M' 24 v Acknowledgement I would like to thank my supervisor, Nick Pippenger, for the freedom he gave me in pursuing this topic, for the patience while I stumbled over definitions and for the guidance that narrowed my focus and made these results possible. I would also like to thank Kevin Hare for answering my endless math questions and Mike McAllister for the Herculean task of proof reading this thesis and suggesting many improvements. I owe thanks to many members of the computer science department for making my stay here stimulating and enjoyable, specifically, my office mates Stephane and Dave for their friendship and for tolerating my monopolization of our office, Alan for invaluable advice on academic matters, and Mike for his never-ending encouragement. Finally, I would like to thank my parents, my brother, Matt, and Paul for their overwhelming support in my academic life. Without it things would have turned out quite differently. vi Chapter 1 Introduction Models of 1-way quantum finite automata (QFA) have been introduced by Kondacs and Watrous[KW97] in 1997 and Moore and Crutchfield[MC98] in 1998. Unlike quantum Turing machines, which are conjectured to be more powerful than their classical, probabilistic analogs, quantum finite automata that accept with bounded error are more restricted than their classical analogs. In this thesis we define two different models of quantum fi- nite automata and investigate their properties, limitations and relationships with classical probabilistic finite automata. 1.1 Quantum Finite Automata Quantum finite automata are finite automata whose transitions are governed by the postulates of quantum mechanics. According to quantum mechanics the state of a system may be indeterminate until it is measured. This means that the system can be in a superposition of possible states and will remain so until it is collapsed into a single state by a measurement. Furthermore, the evolution, or progress, of the system must be reversible, until a measurement is performed. Thus, quantum finite automata make at least one measurement on their state during computation. Unless otherwise stated, "quantum finite automata" will mean 1-way quantum finite automata, which use a classical head that reads the string once. We focus on two different models of 1-way quantum finite automata. The measure- once quantum finite automata (MO-QFA)was introduced by Moore and Crutchfield[MC98], and the measure-many quantum finite automata (MM-QFA) was introduced by Kondacs and Watrous[KW97]. The crucial difference between the two models is that an M M - Q F A 1 Chapter 1. Introduction 2 makes a measurement of state after each symbol is read, allowing it to decide whether to accept, reject or continue, while an M O - Q F A makes no measurements until the end of the computation. The ability accept or reject a string without having to read all of it makes the M M - Q F A model significantly more powerful. The power of a finite model of computation can refer to either the conciseness of one model over the other or to the set of languages that a model can accept. In this thesis the power of a machine refers to its acceptance capability. Measure-once quantum finite automata are the simpler of the two models because they perform only one measurement and only at the end of their computation. Despite this limitation we show that the M O - Q F A can accept non-regular languages and can solve the word-problem over the free group, but only with unbounded error. We prove that the class of languages accepted by these automata is closed under quotient and that this class is properly contained within the class of languages accepted by probabilistic finite automata. Two corollaries from this result are that probabilistic finite automata can solve the word problem over the free group and that there exists a computable method to determine if two measure-once quantum finite automata have the same distribution. It is well known that probabilistic finite automata can only accept regular languages if we require that they accept with bounded error[Rab63]. Similarly we show that measure-once quantum finite automata that accept with bounded error accept exactly the set of group languages, a proper subset of the set of regular languages. Measure-many quantum finite automata perform a measurement of state after every transition and can halt and accept before reading the entire input. These automata can simulate the measure-once quantum finite automata exactly by using at most twice as many states as the measure-once automata. We show that the class of languages accepted by these automata is closed under complement, inverse homomorphisms, and quotient. Similar to the measure-once automata the measure-many automata that accept with bounded error can only accept a proper subset of the regular languages. In fact, we show that this class of Chapter 1. 3 Introduction languages is not closed under homomorphisms. We state and prove a necessary condition for acceptance with bounded error and prove a lemma that relates the sufficiency of the condition to closure of the class under boolean operations. Finally, we show by construction that measure-many automata can accept piecewise testable sets with bounded error. 1.2 Related Work Quantum finite automata were first introduced by Kondacs and Watrous [KW97]. The model is similar to the measure-many model and was derived from the model for 2-way quantum finite automata, which was introduced in the same paper. Using a technique similar to Rabin's[Rab63], Kondacs and Watrous proved that 1-way quantum finite automata that accept with bounded error are restricted to accepting a proper subset of the set of regular languages. Further investigation by Ambainis and Freivalds [AF98] showed that measure- many quantum finite automata could accept languages with probability higher than | if and only if the language could be accepted by a reversible finite automata. They noted that any reversible finite automata can be simulated by a measure-many automata with certainty. It is not yet known whether there exists a language that cannot be accepted by a reversible finite automata but that can be accepted by a measure-many automata with probability greater than m 0.68. Ambainis and Freivalds [AF98] also showed that, for some languages, measure-many automata can be exponentially more concise than deterministic automata. A later paper by Ambainis, Nayak and Vazirani[ANV98] showed that there also exist languages for which the deterministic automaton is exponentially more concise than any measure-many automaton. Moore and Crutchfield[MC98] introduced a variant of the measure-once quantum finite automata in 1998. They showed that the class of languages accepted by this model is closed under inverse homomorphisms and boolean operations. They also described a technique for simulating measure-once automata by a generalized stochastic system with only a polynomial Chapter 1. 4 Introduction increase in the number of states. Probabilistic finite automata (PFA) are the classical analog of quantum finite automata and both models share many characteristics. Many results about probabilistic automata are adaptable to quantum automata. Rabin[Rab63] showed that PFAs that accept with bounded error can only accept regular languages. However, with unbounded error, PFAs can accept non-regular languages. In 1971, Paz[Paz71] described an algorithm to determine if two probabilistic automata have the same distributions. This was followed in 1989 by a result of Tzeng[Tze89] who showed that the equivalence problem could be solved in polynomial time. Automata that allow a 2-way read head are closely related to 1-way automata, but can be surprisingly more powerful. In 1959, Sheperdson[She59] showed that 2-way deterministic automata are no more powerful than their 1-way counterparts. However, Freivalds[Fre81] showed that 2-way probabilistic finite automata can accept non-regular languages with bounded error and exponential run-time. Dwork and Stockmeyer[DS90] proved a complementary result in that showed that 2-way probabilistic automata must take exponential time for infinitely many inputs if they accept a non-regular language with bounded error. Kondacs and Watrous[KW97] showed that the quantum counterpart to 2-way probabilistic automata, 2-way quantum finite automata, can accept non-regular languages with bounded error in linear time. 1.3 Organization This thesis is organized in the following way: chapter 2 defines quantum automata and explains background information, chapter 3 discusses measure-once quantum finite automata, chapter 4 discusses measure-many quantum finite automata, and chapter 5 summarizes our work and discusses some open problems. Chapter 2 Background and Definitions The computations of quantum finite automata are based on the postulates of quantum mechanics rather than classical mechanics. To facilitate the definition of QFAs, we briefly discuss the relevant points of quantum mechanics. This is followed by a discussion of various finite automata, including group finite automata, reversible finite automata and probabilistic finite automata. Finally, we define measure-once quantum finite automata and measure- many quantum finite automata, and discuss the differences between our definitions and those of Moore and Crutchfield[MC98] and Kondacs and Watrous[KW97]. 2.1 Quantum Mechanics The four concepts central to our discussion of finite quantum systems include: include: superposition, measurement, reversible time evolution, and representation. Superposition describes the configuration of a quantum system, measurement describes what we can determine about the system, reversible time evolution describes how the system evolves with time, and representation describes how we formally describe and manipulate the system. According to quantum mechanics, a quantum system can be in a superposition of states, rather than a single state. For each physical state that the system can be in there is a corresponding complex probability density amplitude whose absolute square is the probability of the system being in the corresponding state after a measurement occurs. The sum of the squares of all the amplitudes sum to 1 to conserve probability. For example, at any point in time a classic 2-state system will either be in state |0) or state can be in a superposition of both states, e.g. a|0) + A quantum system The probability of measuring the Chapter 2. Background and Definitions 6 system in state |0) is | a | and the probability of measuring the system in state |1) is \(3\ 2 2 where |Q| + \/3\ = 1. 2 2 The act of measurement collapses the superposition of states into a determinate state. A measurement changes the configuration of the system by reducing the superposition of the system to a single state. This is different from classical physics where a measurement is generally a passive operation on the system. Morrison[Mor90] discusses some of the theory of measurement, however most of this theory is unnecessary for our purposes. For our purposes a measurement causes the immediate collapse of the superposition of states. Until a measurement occurs the system remains in a superposition of states and is indeterminate. This is unlike a classical system where a measurement of a system in some state implies that the system was in that state for some amount of time e before the measurement. A measurement of the superposition of states determines what state the system is in, but destroys the superposition of states in the process. A partial measurement of the system is also possible. A partial measurement does not measure whether the system is in a particular state, but whether it is in a subset of states. The result of a partial measurement is a partial collapse of the superposition. After every measurement the surviving amplitudes are normalized to conserve probability. If the system evolves after a measurement, the system evolves from the state it was measured in. Between measurements, the evolution of a quantum system, with respect to time, must be completely reversible. Furthermore, the evolution of the system must conserve probability. Since the amplitudes are complex numbers whose absolute squares must sum to 1, this implies that the evolution must be unitary. The system evolves through the application of operators, which perform operations on the quantum system. A n operator is unitary if it causes the system to evolve in a time-reversible manner and conserves amplitude. Apart from measurement, the system must evolve in a unitary manner; hence, operators must be unitary. Since the operators are unitary, they can be composed to form more complicated unitary operators. The requirement of unitary evolution with respect to time is the most Chapter 2. Background and Definitions 7 limiting restriction on quantum mechanical systems, especially in the case of finite state systems. In order to reason about a quantum system we must be able to represent it. An n-state quantum finite system is represented by an n-dimension complex unit vector within an ndimension complex Hilbert space H. Each dimension of the 7f corresponds to one of the n states of the system and the set of vectors that form the standard basis of ri correspond to the system being in each of its states with certainty. The configuration of the system at any time is a superposition of basis states denoted by a vector n i=l where \qi) is the zth vector of the standard basis, which corresponds to state qi of the system, and a; is the corresponding amplitude. The probability of a quantum system in superposition |$) being in state qi is Pr[system in state q ] = |(qi|*)| 2 ; where (qi\^) is the amplitude of state (2.1) For the rest of the thesis we use vector notation to refer to states of the system. For example, instead of referring to state qi we refer to the corresponding vector |t7;). Operations performed on the system are represented by matrices. Unitary matrices represent unitary operators and projection matrices represent measurement operators. A unitary matrix is a complex matrix whose inverse is equal to the transpose of its complexconjugate. A projection matrix is an idempotent matrix which projects a vector onto some subspace. We restrict our attention to diagonal projection matrices where entries in the diagonal are zero or one. This restriction does not affect the acceptance power of the models. If a system is in configuration |$ ) 0 configuration of the system is a n d w e apply the unitary operation U to it, then the new = U\^o). In terms of projection matrices Equation 2.1 can be rewritten as Fr[system in state q ] = (*|P |*) s ; Chapter 2. Background and 8 Definitions where P is a projection matrix whose ith diagonal entry is a one, and, 2 and \ty) are the row and column vectors representing the configuration of the system. A partial measurement projects the superposition represented by onto a subspace of ri, which may be spanned by many basis vectors. After a projection the vector is renormalized, but for our purposes this step is not necessary. The majority of our discussion will utilize matrix manipulations involving both unitary and projection matrices. 2.2 Notation In this thesis the notation ||u|| represents the norm of the vector. The operator ® is the 2 tensor product operator. The notation [c] is the indicator of the condition; [c] = 1 if condition c is true and [c] — 0 otherwise. We usually use the bracket notation for vectors, \v) represents is a column vector v, while (v\ represents a row complex conjugate of v. The notation (v\u) represents the inner product of v and u. The over-line c denotes either the complement or the complex conjugate, we will state which if it is not clear from context. The * denotes either the Kleene star operator or the complex conjugate of a vector or matrix, the meaning will be clear from the context. 2.3 Deterministic Finite Automata Deterministic finite automata (DFAs), discussed by Rabin and Scott[RS59], are models of finite state computation and serve as the underlying model for automata theory. A D F A is a 5-tuple M = (Q, E , 8, qo, F) where Q is a finite set of states, E is a finite alphabet, and 8 is a transition function of the form 8 : Q x E -»• Q that defines the new state of M given its state and the next symbol. The state qo is the initial state of M and F is the set of accepting states. If M reads a string x and ends 9 Chapter 2. Background and Definitions in an accepting state, then M is said to accept x, otherwise M is said to reject x. The configuration of a DFA during the computation is its instantaneous description that consists of its current state. An important fact about DFAs is that all DFAs have a canonical form, also known as minimal form[HU79]. This fact is the result of the Myhill-Nerode theorem and will be used in some of our proofs. 2.4 Reversible Finite Automata Quantum finite automata are quantum systems that usually operate in a unitary fashion. Since unitary operations are necessarily reversible, QFAs bear strong resemblance to various variants of reversible finite automata. A group finite automaton (GFA) is a DFA M = ( Q , E , 5, cyo, F) with the restriction that for every state q £ Q and every input symbol CT £ E there exists exactly one state q' £ Q such that 5(q', <r) = q, i.e. 5 is a complete one-to-one function and the automata derived from M by reversing all transitions is deterministic. A reversible finite automata (RFA) is a D F A M — (Q, E , c5, qo, F) such that for every state q £ Q and for every symbol a £ E there is at most one state q' £ Q such that 8(q', o) = <7, or, if there exist states qi, q £ Q and symbol a £ S such that S(qi, a) = q = 5(q , CT), then 2 2 5(q, E) = q. This definition is equivalent to the one used by Ambainis and Freivalds[AF98] and is an extension of Pin's[Pin87] definition. 2.5 Probabilistic Finite Automata Quantum finite automata are probabilistic models of computation, hence it is not surprising that they share many characteristics with probabilistic finite automata (PFAs) introduced by Rabin[Rab63} and discussed at length by Paz[Paz71]. A P F A is represented by a 5-tuple M = (Q, E , 8, qo, F) where Q is the set of states, E is the alphabet, qo is the initial state, F 10 Chapter 2. Background and Definitions is the set of accepting states, and 5 is the transition function 5 : Q x S x Q -+ [0,1] such that S(q, cr, g') denotes the probability of a transition from state q to state q' upon reading a symbol a, such that for each state q and symbol o it holds that Ylq'eQ ^(l-> -> l') a ( = 1- It is convenient to describe PFAs using matrix notation. The configuration of an n-state PFA is represented by an n-dimensional stochastic vector. For each symbol in the alphabet there is a \Q \ X \Q \ stochastic matrix A that determines the transitions that the P F A makes a upon reading symbol a. The initial configuration is represented by a stochastic row vector 7T, which is usually (1,0,0, . . . , 0 ) , and the set of accepting states is represented by a zero-one column vector r\ where 77, = [qi £ F\. The probability of a P F A M accepting a word 1 6 S * is P M ( X ) where x — xiX2...x m and A(x) = A A ...A . Xl X2 Xm = T T A ( X ) T ] A P F A M accepts a language L C S* with cut-point A £ [0,1] if for all x £ L the probability of M accepting x is greater than A and for all a; 0 L the probability of M accepting x is at most A. A P F A M accepts L with bounded error if there exists a margin e > 0 such that x £ L implies that PM(X) > A + t and x L implies that PM(X) < A — e. A language accepted by a P F A with some cut-point A is known as a probabilistic cutpoint event (PCE). The P F A corresponds to a stochastic system S = (n, {A } z, a ae il)- A n equivalent definition of a P C E is the set of words for which the stochastic system returns a value greater than the cut-point. If we allow arbitrary matrices instead of stochastic matrices we call the system a pseudo-stochastic system. A language accepted with cut-point A by the pseudo-stochastic system is called a generalized cut-point event (GCE). A useful result of Paz[Paz71] is that the class of GCEs is equal to the class of PCEs. Theorem 2.1 (Paz, 1971) The class of PCEs is identical to the class of GCEs. 11 Chapter 2. Background and Definitions 2.6 Closure Properties The set of operations under which a class of languages is closed can provide insight into the characteristics of the computation model. A class C is said to be closed under a particular operation if applying the operation to any language L £ C yields a language that is also in C. In this thesis we focus on closure of boolean operations, homomorphisms, inverse homomorphisms, and word quotient. The boolean operations are union, intersection and complement. The union of two languages L and V over alphabet E is defined as L U V = {x £ E * | x £ L V a; £ L'}, intersection is defined as L fl L' = {x £ E * | x £ L A x £ L'}, and complement of a language is defined as L = {x £ E * | x £ L}. A homomorphism h is a one-to-one function of the form h : E -> E * that maps symbols to strings and has the properties that h(c) = e and h(xy) = h(x)h(y). The homomorphism of a language L is defined as h(L) = {h(x) £ £* | x £ L). The inverse homomorphism of a language L is the set h~ (L) — {x £ E * | h(x) £ L}. l The left word quotient of L for some word w £ E* is defined as w~ L = {x £ E * | wx £ L}. Symmetrically l the right word quotient of L is defined as Lw~ x = {x £ E * | xw £ L}. If we specified left or right end-markers as part of our computation models, then word quotients correspond to inverse homomorphisms on the end markers, a fact that will be useful later on. 2.7 Definition of Measure-Once Quantum Finite Automata A measure-once quantum finite automaton is defined by a 5-tuple M = (Q, E , 8, qo, F) where Q is a finite set of states, E is the input alphabet with an end-marker symbol $, 8 is the transition function of the form 5:QxEx(2-+C Chapter 2. Background and Definitions 12 such that for all a £ E and 171,172 £ Q £ % I , C T , C 7 ' ) % 2 , <r, q') = \ v'eQ 1 q i = " (2.2) q [ 0 <7i ^ C72 and r5(<7, a, g') denotes the amount of probability density amplitude that flows from state q to state q' upon reading symbol a. T h e state go is the initial state of the system and F is the set of accepting states. E q u a t i o n 2.2 requires that the operators corresponding to the transition function 5 be unitary. T h e configuration of M is represented by an n-dimensional complex vector and is denoted by l*> = X>l<ft> »=i where n = \Q\, {I?;)} is the set of standard basis vectors corresponding to the states of M, a{ is the probability density amplitude of the machine being i n state 17;, and |a;| = 1. 2 U p o n reading a symbol <r, M evolves i n unitary fashion according to the equation where U is a unitary operator represented by a unitary m a t r i x . a If M is i n configuration 1 ^ ) and reads string x = xiX2-..x , m having read x is U(x)\ty) where U(x) = U U _ ...U . Xm Xm l then the configuration of M , T h e i n i t i a l configuration of M is Xx denoted |\& ) and usually corresponds to the machine starting out i n state q$. A l l input to 0 M is i n the form x% where x £ (E\{$})* and $ is the end-marker. W h e n M finishes reading the input string, it measures its configuration; i f it is i n an accepting state then i t accepts. If M is i n configuration l ^ } , having read x, then the probability of it accepting is given by PM(X) = {* \P\* ) X X = \\P\^ )\\ 2 X = \{P\\y*)\ 2 where P is the projection operator onto the subspace spanned by the set {\qi)} eF- T h e qi operator P is represented by a diagonal projection m a t r i x where Pa = [qi £ F] or the row vector (P\ where Pi = [qi £ F]. Chapter 2. Background and Definitions 2.8 13 Definition of Measure-Many Quantum Finite Automata A measure-many quantum finite automaton is defined by a 6-tuple M = (Q, S, 8, qo, Q a c c i Qrej) where Q is a finite set of states, S is the alphabet, 8 is a unitary transition function of the same form as MO-QFAs, q is the initial state, Q 0 5= Q\Qacc Qrej Qacci acc Q Q is the set of accepting states, and is the set of rejecting states. The set Q is partitioned into three disjoint sets: Q j re and Qnon = Q\(Qacc U Qrej) where Qnon is the set of non-halting states. The operation of an M M - Q F A is similar to that of an M O - Q F A except for one major difference. After a symbol is read, the M M - Q F A measures whether or not it is in the subspace spanned by the set of accepting, rejecting, or non-halting states. Measuring the subspaces of the QFA collapses the superposition onto a particular subspace and leaves the superposition within the subspace unchanged except for a renormalization. If the measurement yields that M is in a halting subspace, i.e. accepting or rejecting, then M halts and accepts or rejects. Otherwise, the superposition in the non-halting subspace is renormalized and M proceeds to read the next symbol of its input. The transition for the end-marker $ is required to transfer all amplitudes into the halting subspaces, guaranteeing that M will halt upon the measurement. Similar to an M O - Q F A , the configuration of an M M - Q F A is denoted by an n-dimensional complex vector where n = \Q\. However, because M can have a non-zero probability of halting part-way through the computation, it is useful to keep track of the cumulative accepting and rejecting probabilities. Because of this, we sometimes use the representation defined by Kondacs and Watrous[KW97], which uses a triple {\^),p ,p j) acc tion of M. The evolution of M is denoted by (P U \V),p + \\PaccU \$)\\ ,p 2 non where p and p j acc Pj re re and P on n a acc a re to represent the configura- + ||P -^|*>|| ) 2 reJ rej are the cumulative probabilities of accepting and rejecting, and P a c c , are the diagonal projection matrices that project the configuration onto the non-halting, accepting or rejecting subspaces. Chapter 2. Background and Definitions 2.9 14 Language Acceptance by a Q u a n t u m Finite A u t o m a t o n A QFA M is said to accept a language L with cut-point A if for all x £ L the probability of M accepting x is greater than A and for all x £" L the probability of M accepting x is at most A. A QFA M accepts L with bounded error if there exists an e > 0 such that for all x £ L the probability of M accepting x is greater than A + e and for all x (£ L the probability of M accepting x is less than A — e. We call the e the margin. Hence, if the'margin is greater than zero, then M accepts with bounded error. We look at QFAs with both types of acceptance, but we pay more attention to QFAs that accept with bounded error. 2.10 Equivalence of Q u a n t u m Finite A u t o m a t a We say that two QFAs are equivalent if they have the same acceptance probability distribution on the set of words over an alphabet E . Formally, QFAs Mi and M are equivalent if 2 for every word x £ £ * the probability of Mi accepting x is equal to the probability of M-i accepting x, i.e. 2.11 PM {X) X = for all x £ E * . PM {X) 2 Equivalence of M O - Q F A s and Moore-Crutchfield QFAs The QFA introduced by Moore and Crutchfield[MC98] is similar to the M O - Q F A . A MooreCrutchfield QFA M = (TC, E , {U }„ -£, a \si it),TLa) consists of an n-dimensional Hilbert space e n H, an initial configuration vector \si i ), an accepting subspace 7i n t a with a corresponding projection matrix P , an input alphabet E , and a unitary matrix U for each symbol in E . a a The probability of a Moore-Crutchfield automaton accepting a string x is defined as f(x) = \\P U(x)\s )\\ 2 a tnit is almost the same as an M O - Q F A automaton except that |s,-„,-t) may be an arbitrary unit vector, P is not necessarily a diagonal projection matrix and there is no end-marker $. Howa ever, there is a correspondence that preserves acceptance probability distribution between Chapter 2. Background 15 and Definitions MO-QFAs and Moore-Crutchfield QFAs. Lemma 2.2 There is a correspondence that preserves acceptance probability distribution between MO-QFAs that have left and right string end-markers and Moore-Crutchfield QFAs. Proof: Let M = a cre im an equivalent MO-QFA M' = (Q, Q = {<lo, Q , (7$}. I , < 7 n - i } be a Moore-Crutchfield QFA. We construct (TC,T*,{U } z,\s t),'Ha) where £ U . { c i , $ } , <5, q , F) 0 ci is the left end-marker. Let where n = dim(ffi), and let <5 be defined by the set of matrices {U<j}<jeE U We can write the projection matrix P as P = U'~ PU' where P is a diagonal zerol a a one matrix and U' is a unitary matrix. Let F = {qi E Q \ Pa = 1} and let U$ = U'. Finally, since | s in ,t) is a unit vector and therefore a rotation of \q ), there exists a unitary matrix U" such 0 that U"\qo) — \sinit); let = U". The probability of M' accepting a word x, bracketed by the end-markers, is p ,(x) M = = = = = ||Pt/(cix$)|c7o)|| 2 \\PU U ...U U U^\ )\\ 2 $ Xn X2 Xl qo \\PU'U(x)U"\q )f 0 IIU'-'PU'U^U"^ 2 \\PaU(x)\ )\\ 2 Smtt and is the same as for the Moore-Crutchfield QFA. Starting with an MO-QFA with end-markers we can construct a Moore-Crutchfield QFA by applying the above procedure in reverse. Hence the correspondence preserves the acceptance probability distribution. • Our definition of an M O - Q F A does not use a left end-marker. Fortunately, the left endmarker is unnecessary because for every M O - Q F A that uses a left and right end-marker, we can construct an M O - Q F A that uses only one end-marker. Theorem 2.3 (End-Marker Theorem for MO-QFAs) Let M be an MO-QFA that has both left and right end-markers, then there exists an MO-QFA marker and is equivalent to M. M' that uses only one end- 16 Chapter 2. Background and Definitions Proof: Let M = (Q,E,8,q ,F) be an M O - Q F A with left and right end-markers, effectively 0 allowing M to start in any possible configuration. We now define M' = (Q, £ , 5', qo, F) from M. Let 8 be defined in terms of the transition matrices {<7 -} £ and we define 8' from 8 in the 0 <7e following way; for every a £ E let U' = UfU.Uf a and let Now consider what happens when M and M' read a string x = x ...x . x n The probability of M accepting x is (x) = PM ||P<y(cM)|c7o)ir = \\PUiU ...U Uf\qo)\\* Xn Xl and the probability that M' accepts x is ,(x) PM = iip^(x$)i >ir = ll^^-^ko)|| = \\PU U ...U U. go $ Xn 2 Xl is the same as M's. Thus one end-marker on the right suffices, and by symmetry one left endmarker would also suffice. Therefore, an M O - Q F A starting in configuration \q ) can simulate an 0 M O - Q F A starting in any arbitrary configuration. • The converse of this follows by making the left end-marker transition matrix the identity matrix. This yields the corollary that there is a correspondence that preserves acceptance probability distribution between Moore-Crutchfield QFAs and MO-QFAs. Chapter 2. Background and Definitions 17 Corollary 2.4 There is a correspondence that preserves acceptance probability distribution between Moore-Crutchfield QFAs and MO-QFAs. Proof: Follows directly from Lemma 2.2 and Theorem 2.3. • In some of the proofs we assume that the M O - Q F A starts in a configuration other than |(7o). However, by Theorem 2.3 we know that such automata are equivalent to ones that can only start in configuration \q ). 0 2.12 Equivalence of MM-QFAs and Kondacs-Watrous QFAs The definition of an M M - Q F A is almost identical to the model defined by Kondacs and Watrous[KW97]. The only difference is that the Kondacs-Watrous Q F A requires both a left end-marker j, and a right end-marker $. Our definition of the M M - Q F A only requires one end-marker at the right end of the tape. The left end-marker is unnecessary and is an artifact from their treatment of 2-way quantum finite automata. Theorem 2.5 (End-Marker Theorem for MM-QFA) Let M be an MM-QFA that has both left and right end-markers, then there exists an MM-QFA M' that uses only the right end-marker and is equivalent to M. Proof: Let M = (Q,T<,5,Q ,Q j) acc re be an MM-QFA that uses two end-markers and accepts L. Assume without loss of generality that Qnon — {qi G Q | 0 I <^ n on\ Qacc — {qi G Q | T^non Qrej = n {qi G Q | n ^ <C ^acc} < i < n acc rej = n = \Q\} which allows a simpler description of M'. We now construct M' = (Q',^,S',Q' ,Q' j) acc accepts L with only the right end-marker. Let Q' = Q U {q , q +i, n n — , that re <l2n-n }, non Q' acc = {tjn+i—n-non € Q' | qi e Qacc} and Q'- = {q +i-n n non € Q' \ qi G Qrej}- Assume that S is Chapter 2. Background and Definitions 18 defined in terms of transition matrices {Ua}ae's- The construction of { U i s similar to that in the proof of Theorem 2.3. Let f\ represent an identity matrix of size / and m — n — n , r We now define 8' in terms of its unitary block matrices. For all a G £ let K = ^sweep 1771 UL = ^771 asweep where U. sweep transfers all probability amplitude from states in the old halting states to the new halting states. The old halting states, those in Q ACC and Q j, are no longer halting states in M'. The operation re of M' is similar to the operation of the QFA constructed in Theorem 2.3, The 'sweeping' operation saves the amplitude that was in the old states, while it performs the U^ 1 halting states, otherwise the U^ 1 operation in the new corrupts the amplitude stored in the original halting states. • The converse of this theorem follows from having the left end-marker transition be the identity. In some of our proofs we assume, for convenience, that M M - Q F A s can start in an arbitrary configuration because we know that there exists an equivalent M M - Q F A that starts in configuration \qo)- Chapter 3 Measure-Once Quantum Finite Automata Measure-once quantum finite automata can either be restricted to accepting with bounded error or unrestricted. Accordingly, for each model there is a corresponding class of languages that the model accepts. Define the R M O as the class of languages which can be accepted £ by an M O - Q F A with a margin of at least e. Define the 'unrestricted' class of languages as UMO = R M O and define the 'restricted' class of languages RMO = U>o R M O . 0 t ( In Section 3.1 we completely characterize the class of languages accepted by restricted MO-QFAs. In Section 3.2 we prove some general closure properties of the languages accepted by both the restricted and unrestricted model. Section 3.3 proves that the unrestricted model can accept non-regular sets. Section 3.4 describes an algorithm to determine if two MO-QFAs are equivalent and Section 3.5 proves that the set of languages accepted by MO-QFAs is a subset of the languages accepted by a P F A . 3.1 Characterization of MO-QFAs That Accept with Bounded Error The restriction of bounded error on MO-QFAs is, not surprisingly, as limiting as in the case of PFAs[Rab63]. Kondacs and Watrous[KW97] showed that M M - Q F A s can only accept a proper subset of regular languages if they are required to accept with bounded error. We show in Theorem 4.6 that every M O - Q F A can be simulated exactly by a M M - Q F A . This limits the class R M O to a proper subset of regular languages. The class R M O is exactly the class of languages accepted by GFAs, otherwise known as group languages. This completely characterizes MO-QFAs that accept with bounded error. We prove this result in the rest of this section, starting with Lemma 3.1. 19 Chapter 3. 20 Measure-Once Quantum Finite Automata Lemma 3.1 Let U be a unitary matrix. For any e > 0 there exists an integer n > 0 such that for all vectors Proof: Let x, \\x\\ < 1, where m — dim(U). 2 it is true that — ( 7 ) x | | < e. n 2 Since U is a normal matrix and has eigenvalues that are of the form e , U can be written as t6 n rjn ppynp-r = where P is a unitary matrix and D is the diagonal matrix of eigenvalues with the jth eigenvalue having the form e J7rrj is rational, then let '. If all eigenvalues in D are rotations through rational fractions of n = 2 r i j L i 9j w n e r e Qj i S the denominator of r Thus r D N IT, i.e. r, and we are = I done. Otherwise, at least one eigenvalue is a rotation of unity through an irrational fraction of n. Let / < m be the number of these eigenvalues. For the other m — I eigenvalues compute n, just as above, and let The values on the diagonal of D' = D . N are either 1 or D' e 4 7 r n r J where rj is some irrational real number. Consider taking D' to some power k G Z . The values + that are 1 do not change, but the other / values, which are of the form e^ 4 fc where 9j = irnrj, represent a vector that rotates in an /-dimensional dense torus. Hence, there exists k such that the /-dimensional vector is arbitrarily close to 1. Thus for any e' > 0 there exists a k > 0 such that - D' )l\\ h 2 < t'. Hence ||(/- U )x\\ nk 2 = < Select e' such that e' < If t w o c o n f i g u r a t i o n s configurations = PD^P-^xW ||(/- \\P{I - ||(7-7) 2 D ' ^ P - ' X W , f c )ml|| 2 = m ||(7-7}' )l|| < m e' 2 f c 2 2 2 to complete the proof. • a r e close, t h e n t h e differences i n p r o b a b i l i t y d i s t r i b u t i o n s o f t h e is also s m a l l . T h e following l e m m a , due to Bernstein a n d Vazirani[BV97], Chapter 3. Measure-Once Quantum Finite 21 Automata allows us to relate the closeness of configurations to the variance in their probability distributions. This is necessary in order for us to partition the set of allowable configurations into equivalence classes. Lemma 3.2 (Bernstein and Vazirani, 1997) that HIV^II = 2 Hlv)!! = 1 7 2 a n d || 1 ^ ) — lv)l| < 2 e Let \tp) and \ip) be two complex vector such Then the total variation distance between the probability distributions resulting from measurement of |V>) and |c/>) is at most At. Using these two lemmas, we prove our main result of this section. Theorem 3.3 A language L can be accepted by a MO-QFA with bounded error if and only if it can be accepted by a GFA. Proof: The first direction is easy. Let M = (Q, S, 8, q , F) be a GFA that accepts L. Let 8 be 0 defined in terms of transition matrices. Since the transition matrices of a GFA are permutation matrices, and permutation matrices are unitary, the same matrices can be used in the definition of a MO-QFA. Since the matrices are permutation matrices, the MO-QFA will accept L with certainty. For the other direction, by contradiction, assume that there exists a language L that can be accepted by a MO-QFA with bounded error but cannot be accepted by a GFA. Since the class R M O is a subset of the regular languages, L must be regular. Let M = (Q,T,,8,q , 0 F) be a MO-QFA that accepts L with bounded error, by the Myhill-Nerode theorem[HU79] the space of configurations of M's computation can be partitioned into a finite number of equivalence classes. We denote such an equivalence class [x] where i g S * and [x] ~ L [ X ' ] if for all y £ £*, xy £ L if and only if x'y £ L. Since L cannot be accepted by a GFA, there must exist two distinct equivalence classes [y] and [y'}, an equivalence class [x], and a symbol o, such that [ye] ~ L [y'o~] ~ L [x]. If U is the transition matrix for symbol a, \tb) £ [y] and \(p) £ [y ] then 1 a U \xl>) £ [x] and U„\tp) £ [x]. a Since M accepts L with bounded error, let e be the margin. By Lemma 3.1 there exists an integer k > 0 such that ||(/ - c7*)^>|| < f and ||(/ - U „)\tp)\\ 2 k 2 < f. Hence, « 7 » £ [y] Chapter 3. 22 Measure-Once Quantum Finite Automata because if IIU-^MII 2 = IIIV>)-^|V>)II 2 = iini^)-^i^))n 2 e < 4 where V is an arbitrary unitary matrix, then by Lemma 3.2 the probability of VU \ip) k being measured in a particular state is within e of V\ib) being measured in the same state; this probability is less than the margin. Similarly U \<p) 6 [y']. Hence [y] ~£ [ycr ] and [y'\ k We assumed [,T] ~ L [y<r] [y] ~ L [xcr* ] --1 ~ L [y']. Let k ~ L [y'<7 ]. fc [y'cr] and showed that [y] ~ ^ [ycr^] and [y'} ~ £ \y'o~ \, therefore, k z be the string that distinguishes [y] and [y']. Therefore v~z k x partitions [x] into at least two distinct equivalence classes, but this is a contradiction. Hence, there cannot exist a language L that can be accepted by a M O - Q F A with bounded error but not by a GFA. • Theorem 3.3 implies that R M O e = RMO < for all e > 0, hence there are most two £ distinct classes of languages accepted by M O - Q F A s , the restricted class R M O , which is equivalent to the class of languages accepted by a G F A , and the unrestricted class UMO. 3.2 Closure Properties One important characteristic of a set of languages is its closure properties. A class is closed under an operation if applying the operation to any language in the class yields a language in the same class. The fact that a class is closed under a particular operation is called a closure property of that class. The common operations on languages include boolean operations, homomorphisms, inverse homomorphisms, and word quotients. Moore and Crutchfield[MC98] showed that the unrestricted class of languages accepted by their model was closed under boolean operations and inverse homomorphisms. By Corollary 2.4 it follows that the class U M O is also closed Chapter 3. Measure-Once Quantum Finite Automata 23 under boolean operations and inverse homomorphisms. Lemma 3.4 shows that their result also holds for the class R M O . Lemma 3.4 The class R M O is closed under boolean operations and inverse homomor- phisms. Proof: By Theorem 3.3 the class R M O is the same as the class of group languages. Since the class of group languages is closed under boolean operations and inverse homomorphisms[Eil76], the result follows. • Since both classes, R M O and U M O , are closed under inverse homomorphisms, it follows in Theorem 3.5 that they are also closed under left and right word quotients. Theorem 3.5 Proof: The classes R M O and U M O are closed under left and right quotient. Let M = (Q,T,,8,q , F) be a MO-QFA with a left and right marker that accepts L 0 and let w G E + be the quotient word. We show that there exists MO-QFAs M' and M" that accept w~ L and Lw~ with the same cut-point and margin as M. For the left quotient define l x the homomorphism otherwise The inverse homomorphism of the L is precisely w L and by Lemma 3.4 there exists a MO-QFA l M' that accepts w L with the same cut-point and margin as M accepting L. For right quotient 1 use the homomorphism CT = $ h(o) a that yields Lw 1 otherwise in the same way. • The class R M O is not closed under homomorphisms. We proved in Section 3.1 that the class R M O is exactly the set of languages accepted by a G F A . Using this result, we can construct a G F A whose language, under a simple homomorphism, is not a group language. Chapter 3. Measure-Once Quantum Finite Automata 24 Theorem 3 . 6 The class RMO is not closed under homomorphisms. Proof: Consider GFA M in Figure 3.1 and the language L that it accepts. Let h be a homomorphism h(a) = a, h{h) = 6, h(c) = b let V = h(L), and let M' be the automaton that accepts V. F i g u r e 3.2: R F A M' The minimal automaton that accepts U is found in Figure 3.2 and is not a GFA but an RFA. Since the class R M O is exactly the class of languages accepted by a GFA, the language L is accepted by a G F A , but h(L) is not. It follows that the class R M O is not closed under homomorphisms. • Chapter 3. Measure-Once Quantum Finite Automata 3.3 25 M O - Q F A s Can Accept Non-Regular Sets Measure-once quantum finite automata that accept with bounded error can only accept a proper subset of regular languages, but using a technique similar to Rabin's[Rab63] we show that MO-QFAs can accept non-regular languages with unbounded error. This is similar to PFAs that can only accept regular languages when restricted to accepting with bounded error but can accept non-regular languages with unbounded error. Lemma 3.7 Let L = {x £ {a,<?}* | \x\ a = |a:|&} there exists a 2 state MO-QFA M that ; accepts x with certainty if x £ L and rejects x with a probability strictly greater than 0 if x g" L. Proof: Let M = (Q,T,,8,q ,F) 0 where Q — {<7o,<7i}. £ = {a, b}, F = {q }, 0 and 8 is defined by the transition matrices cos a sin a — sin a cos a where a is an irrational fraction of ix. Since U is a rotation matrix and a is an irrational fraction a of 7T, then the orbit formed by applying U to \q ) is a dense circle, and there exists only one k, a 0 such that U \qo) = \qo), namely k = 0. This is also true for U~ — Ub- Hence, U(x)\q ) = |<?o) k l 0 if and only if the number of U rotations applied to \q ) is equal to the number of Ub rotations. a 0 This only happens if the number of a's read is equal to the number of b's read. Otherwise, \qi) will have a non-zero amplitude and a non-zero probability of rejection. In this case the end-marker is simply the identity operation because it is not necessary. Since L is a non-regular language, the result follows. • Lemma 3.7 implies that the class R M O is properly contained within the class U M O and therefore the two classes are distinct. A free group is a group in which there is no relation on the generators. The word problem over the free group is the problem of deciding whether a product of elements from the free group is equal to the identity. Concretely, let £ = {1, a, a , b, - 1 ...} be a finite alphabet Chapter 3. Measure-Once Quantum Finite Automata 26 whose elements form a free group. Let w 6 £ * represent a composition of a finite number of elements. Define L = {w G E * | w = wiW2---w = 1} to be the set of words over E such n that the product of the elements in the word is equal to the identity. If an automaton can accept L then it solves the word problem over the free group. The M O - Q F A in the above lemma solves the word problem for the free group. In this case the free group is generated by two elements {a, a - 1 = b}. We can generalize this result to the general word problem for the free group. Lemma 3.8 The word problem for the free group language can be accepted by an MO-QFA. Proof: Construct a free group of rotation matrices from SO3 as discussed by Wagon[Wag85]. Let M = ( Q , £ , 5 , t 7 o , F ) be a 3-state MO-QFA where S = {a, a~\6, ...} such that |S| is equal to the sum of the number of rotation matrices and their inverses, 8 is defined by the rotation matrices and their inverses, and F = {qo}- The MO-QFA will accept identity words with certainty and reject non-identity words with a strictly non-zero probability, hence solving the word problem for the free group. • 3.4 Equivalence of MO-QFAs In classical automata theory there is an algorithm to determine if two automatons are equivalent. We face a similar problem with respect to MO-QFAs. Given two MO-QFAs we would like to determine if they are equivalent or not. Using a technique described by Paz[Paz71] and combining it with a preprocessing step developed by Moore and Crutchfield[MC98] we construct a method for testing the equivalence of two MO-QFAs. The key problem with M O QFAs, unlike PFAs, is that measurement is a not bilinear operation. In PFAs the probability of some P F A M accepting string x is given by P M ( X ) = T T A ( X ) T ] Chapter 3. Measure-Once Quantum Finite Automata 27 and is bilinear. In the case of MO-QFAs the probability of a M O - Q F A M' accepting string x P M ' ( X ) ||P/7(x)|vI/ }|| = 2 0 is not bilinear. The first step is to bilinearize the M O - Q F A . Moore and Crutchfield[MC98] showed that any language accepted by a Moore-Crutchfield QFA is a G C E and provided a construction for the corresponding pseudo-stochastic system. Theorem 3.9 (Linearization Theorem, Moore and Crutchfield, 1998) If L is a language accepted by an n-state MO-QFA M with some cut-point X then L is a GCE and can be accepted by a pseudo-stochastic system with the same cut-point and with 2n states. 2 Proof: Let M = (Q,T,,8,q , F) be a MO-QFA with n-states that accepts L. Let M' = 0 (Q', 2,,8',q ,F') 0 be an automaton where Q' = Q x Q, q' = (<?o,<?o). F' — {(<7;,<7j) G Q' \ qi G 0 F A qj G F} and 8' is defined in terms transition matrices {U^.} ^ where U' = (U*) -1 a a ® U~ l and U are the transition matrices defining 8. Let ( P | be the row vector corresponding to the a accepting states of M, let state vector where IT be the initial row vector representing |(t7 , qo)), and let t] be the final 0 = [q^ G F'\. The probability of M accepting string x is PM(X) = \\PU(x)\q )\\ = \(P\U(x)\qo)\ = 2 0 2 \( \U-\x)\P)\ 2 qo = (q* ®qo\(U- )*®U- \P*®P) 1 1 0 = 7TU'(x)r] - PM'(x) and PM> = irU'(x)r] is bilinear. The new automaton has n states but also might have non-real 2 entries in its transition function. Since any complex number a + ib can be represented by the Chapter 3. Measure-Once Quantum Finite Automata 28 matrix a b —b a we can construct a 2n -state pseudo-stochastic system that is equivalent to M', is bilinear and 2 uses real entries in its transition matrices. Let n' = (ir,0), let A„ correspond to U' where each a entry in U' is replaced by a 2 x 2 real matrix defined above, and let n' be the acceptance vector a such that rj' = [q[ £ F']. This is a pseudo-stochastic system S — (IT , {A^}^^, rj') that accepts 1 2i L with the same cut-point as M. Hence, L is a GCE and 5" has 2n states. • 2 Given two MO-QFAs M and M' with m and n states respectively we use the method of Moore and Crutchfield[MC98] to convert them into pseudo-stochastic systems N = (n,{A },q) and N' = (IT', {A' }, v') with 2m and 2n states respectively. We now con2 a 2 a struct a 2m + 2n state pseudo-stochastic system N" = (TT", {A" },q") where 2 2 a A" a 7T = [7r,7T j , q A a 0 0 A! _ a The two automata M and M' are equivalent if for all x £ E* the system A^" always returns 0, i.e. p „ ( S * ) = 7r"A"(E*)77" = 0 N This reduces the M O - Q F A equivalence problem to the initial distribution equivalence problem, which is, given two initial distributions and a pseudo-stochastic system are the two distributions equivalent, i.e. do they yield the same probability for each word in S*. To solve this problem we look at all vectors, ordered lexicographically with respect to x £ £*, of the form A"(x)rj" where \x\ < d = 2m + 2n and select the maximal independent set 2 2 in lexicographic order. Paz[Paz71] showed that looking at all vectors generated by words of length d or less is sufficient to find a basis B for the smallest space that contains the vector set {A"(T,*)r)"}. We now get the following theorem, which is a modification of a corollary of Paz[Paz71]. Chapter 3. Measure-Once Theorem 3.10 Quantum Finite 29 Automata Let n and p be two initial distributions, let {A } the set of matrices, let r\ a be the final state vector, and let B be the basis for the minimal space that contains { A ( £ * ) } generated by the above method. If irv = pv for all v £ B then i\:A[x)r] = pA(x)rj for all x e £*. Proof: TrA(x)r) = 7T ^ vteB *i = X ! a V i' i (l KV = X ] vieB a i vieB P V i = P ^2 i a Vi = PM )V X vieB • This leads us to an algorithm to determine the equivalence of two MO-QFAs. Theorem 3.11 Given two MO-QFAs M and M' we can determine if they are equivalent. Proof: Using the Moore-Crutchfield method we convert M and M' into pseudo stochastic systems and A/'. We construct a new pseudo stochastic system N" as detailed above. We compare the initial distribution w" to the zero distribution 0. If the two are equivalent then we know that N and N' have the same distribution because N" subtracts the second from the first. This yields the constant 0 if and only if the two are the same. Thus, we can determine if two MO-QFAs are equivalent. • 3.5 Simulation of MO-QFAs by PFAs Most classical computation is either deterministic or probabilistic, hence it is useful to ask how probabilistic automata compare to their quantum analogs. In the case of MO-QFAs, any language accepted by an M O - Q F A can also be accepted by a PFA. If L can be accepted by an M O - Q F A with bounded error, then it be accepted by a P F A with bounded error. Theorem 3.12 Let M be a MO-QFA that accepts L with cut-point A then 1. There exists a PFA that accepts L with some cut-point A'. 2. If M accepts L with bounded error, then there exists a PFA that accepts L with bounded error. Chapter 3. Measure-Once Quantum Finite Automata 30 Proof: The second result follows from Theorem 3.3 that states that that the set of languages accepted by an MO-QFA with bounded error is a proper subset of the regular language. Since PFAs can accept regular sets with zero error, the second result follows. By Theorem 3.9 if L is accepted by an MO-QFA then L is a GCE. By Theorem 2.1 the class of GCEs is equal to the class of PCEs[Paz71], which are accepted by PFAs. Hence there exists a PFA that can accept the same language as M with some cut-point A'. • This theorem along with Lemma 3.8 shows that PFAs can solve the word problem for the free group, we get the following result. Corollary 3.13 The word problem for the free group language can be solved by a PFA. Chapter 4 Measure-Many Quantum Finite Automata Measure-many quantum finite automata are more powerful than MO-QFAs because a measurement is performed after every transition. This allows the machine to terminate before reading the entire string and simulate spin states. Just as in the case of MO-QFAs, M M - Q F A S can accept without or with bounded error. Let R M M be the class of lan( guages that can be accepted by an M M - Q F A where the allowed margin is at least e. Let U M M = R M M be the 'unrestricted' class of languages accepted by an M M - Q F A and let 0 R M M be the class of 'restricted' languages where R M M = U >o R M M . e £ In Section 4.1 we prove several closure properties of both classes of languages. Section 4.2 shows how M M - Q F A s can simulate MO-QFAs exactly. In Section 4.3 we show that M M QFAs are strictly more powerful then MO-QFAs. We then focus our attention on MM-QFAs that accept with bounded error. Section 4.4 proves a necessary condition for a language to be in the class R M M . In Section 4.5 we prove that piecewise testable sets are members of the class R M M . In the same section we introduce a couple of novel techniques for constructing M M - Q F A s and note some special characteristics of the construction that could be applicable elsewhere. 4.1 Closure Properties The languages accepted by MM-QFAs belong to either R M M or U M M , just like M O QFAs. However, it is unknown whether these classes are closed under the same operations as the classes R M O and U M O which contain the languages accepted by MO-QFAs. In this section we show that the classes R M M and U M M are closed under complement, inverse 31 Chapter 4. Measure-Many Quantum Finite Automata 32 homomorphisms, and word quotient. However, it is still unknown whether the classes are closed under intersection, and hence, under boolean operations. We do know however that the restricted class R M M is not closed under homomorphisms, which is similar to the restricted class of languages accepted by MO-QFAs. We prove closure for the class R M M e for all e > 0, under complement, inverse homomorphisms, and word quotient in Theorem 4.1. This implies that the classes R M M and U M M are also closed under the same operations Theorem 4.1 The class R M M is closed under complement, inverse homomorphisms, and e word quotient. Proof: Let M be an MM-QFA that accepts L with cut-point A and margin e. Let M be the same MM-QFA except that the accept and reject states are transposed, i.e. all accept states become reject states and all reject states become accept states. Hence, the probability of M accepting a string x £ L is P M ( X ) < l - ( A + e) = A - e and the probability of M accepting x ^ L is P M ( X ) > 1 - (A - e) = A + e where A = 1 — A. Therefore M accepts L with cut-point A and a margin of e. This implies that the class R M M £ is closed under complement. Given M and a homomorphism h we construct a machine M' that accepts h~ (L). l M = (Q,H,6,Q ,Q j) acc re and M' = (Q',T,,8',Q' ,Q' ). acc terms of matrices {U^}^^ and {UUnlike rej Let Assume that 8 and 8' are defined in the proof for MO-QFAs in [MC98], the direct construction of K = U(h(a)) will not work unless h only maps symbols to symbols, instead of the general case of symbols to strings. This is because a measurement occurs between transitions, and combining transitions without taking this into account could produce incorrect configurations. Specifically after every Chapter 4. Measure-Many Quantum Finite Automata 33 transition some amount of probability amplitude is placed in the halting states. This probability amplitude is not allowed to interact with the non-halting states in the following transitions. However, because the transitions are unitary, interaction could occur. To solve this problem we use extra states to store the amplitude while transition combination U(h(a)) is executed so that it does not interact with the amplitude in the non-halting states. Assume without loss of generality that where n = \Q\ and n non = Qnon — {qi £ Q | 0 Qhalt = {qi € Q 1 ^ ^non} In <i<n} non Let m = max z{\h(a)\}, i.e the maximum length of all |<5non|- ae strings that h maps to. Let Q' = Q u Q'hait where ^halt _ — r -i n+m(n-n on) iyijt=n+l n Q'acc = Qacc U {q +](i-n ) Q'rej Qrej = n non U {q +j(i-n ) n non € Q' | qi € Qacc, 1 < j < £ Q'hait I Qi € Qrej, 1 < J < m} haU m] Intuitively, we clone the halting states m times. Hence, M' has m + 1 copies of the halting sets, starting with set 0, the original set, followed by m copies. To complete the construction, we now define 5' in terms of the matrices that define 8. Let V be a unitary block matrix a K = U hift s Im(n-n ) non where non n Ushift Lm(n—n„on) J 34 Chapter 4. Measure-Many Quantum Finite Automata The matrix U hijt is a unitary matrix that shifts the amplitudes in the halting set i to the halting s set i + l and the amplitude in halting set m to halting set 0. We are now ready to construct U' . a In analogy to the MO-QFA case where U' — a U(h(o)), for MM-QFAs where h{o) = x = x x ...x\ x 2 and / < m, let U'„ = V(h(o)) = V(x) = V(x )V(x _ )...V(x ) / / 1 1 After every x, sub-transition the halting amplitude is shifted and stored in the m + 1 halting sets of states. When the x i sub-transition is done, the amplitude in halt state set 0 is zero, t + which means that no undesired interaction between the halting and non-halting states occurs. A minimum of m transitions must occur before halting set m contains non-zero amplitude, however m is the maximum length of the string that h maps to, which is sufficient to guarantee that halting set 0 will never receive non-zero amplitude from halting set m. This construction delays the need for a measurement by storing the amplitude in an auxiliary set of states. If M is in configuration (|\t7),p ,p j) and M' is in a corresponding configuration acc (\ty'),p ,p j) where acc re = |vl/)|0). The result of M' reading a is equivalent to M reading re h(a) = x = xix ...xi. The resulting configuration of M is 2 +£ (p U(l)\^),p non acc V WPacM^miWPrej + E l ^ t t y ) I * > If) t=l i=l / while the resulting configuration of M' is {P'nonKm.Pacc + = (PLnV(H°)W),Pacc + Pacc {P V -Vz \y'),Pacc+ = (pLnV(lW),Pacc non Xr I *'> II') re3 + \\Ke V(h(a)W)r) 3 V(x) | ) || ) 2 + \\K eJ | | / a c c K . . . V | * ' > H , P r « + || P'rej V* • • ^ , l | r 2 i=\ i=l C + EII^OI*)®!! V i=l ((PnonU(m)\Q),Pacc + 2 ,^ + £ II ( ^ c c ^ ( » ) I *) ) |0> f , i=\ I *') 2 X l + E \\PLV(i)m\\ *Prej + £ II Ke^) \ V II P'rejK ac 3 = (pLnV(m\d),Pac = + \\P' <y(Ka)W)\\\p + \\PLV{*W)\\\Pre = {PLnV(xW), = \\KccKW)\W Prej II') I *'> II') I E ll^'e/(0l*)|0)|| ) 2 i=l Prej I + E || i=l (P U(l) rej | * » |0> || ) 2 / 35 Chapter 4. Measure-Many Quantum Finite Automata where U(i) n^i^,^ P = n o n ) and V(i) = n ; i ( K = 1 + 1 _ ^ J o n ). The new configuration of M' corresponds to the new configuration of M in exactly the same way as the original configurations. Therefore M' can accept h~ [L) with the same distribution as M, which means that R M M is l e closed under inverse homomorphisms. The closure under word quotient follows from closure under inverse homomorphism, because of the presence of end-markers. For left quotient use the homomorphism htf) = {w h(a) = a h{%) = $ to accept w~ L and for right quotient use the homomorphism, l Hi) = i h(cr) — a = w$ to accept the language Lw~ . This is identical to the argument used in Theorem 3.5. • x Corollary 4.2 The classes R M M and U M M are closed under complement, inverse homomorphisms, and word quotients. Just like the class R M O , the restricted class R M M is not closed under homomorphisms. This is proved in Theorem 4.5 and uses Lemma 4.3 and Lemma 4.4. Lemma 4.3 (Kondacs and Watrous, 1997) The language L = {a,b}*b cannot be accepted by an MM-QFA with bounded error. Lemma 4.4 (Ambainis and Freivalds, 1998) accepted by an MM-QFA with certainty. If L can be accepted by a RFA, it can be 36 Chapter 4. Measure-Many Quantum Finite Automata Theorem 4.5 The restricted class of languages accepted by MM-QFAs is not closed under homomorphisms. Proof: Let L = {a,b}*c. Since this language can be accepted by an RFA, by Lemma 4.4 it can be accepted by an MM-QFA with bounded error. Define the homomorphism h as h(a) = a h(b) = b h(c) = b Applying this homomorphism to L we get L' = h(L) = {a,b}*b. By Lemma 4.3 L' cannot be accepted by an MM-QFA with bounded error. The result follows. • A more interesting question is whether the classes R M M and U M M are closed under boolean operations. Unlike MO-QFAs that have two types of states, accept and reject, M M QFAs have three types of states, accept, reject, and non-halt. Because of this, the standard procedure of taking the tensor product of two automata to compose their intersection or union does not work. A general method of intersecting two M M - Q F A s is not known. Thus, it is not known whether R M M and U M M are closed under boolean operations. 4.2 Simulation of MO-QFAs The transition mechanism of an M M - Q F A is more complex than that of an M O - Q F A , therefore, intuitively, MM-QFAs should be more powerful than MO-QFAs. Ambainis and Freivalds[AF98] mentioned that MM-QFAs are a more general model than MO-QFAs but no proof was given. In Theorem 4.6 we show that an M O - Q F A with n states can be simulated exactly by an M M - Q F A with 2n states. To simulate exactly means that the distributions of both automata are identical. Theorem 4.6 tribution as M. For every MO-QFA M there exists an MM-QFA M' that has the same dis- Chapter 4. Proof: Measure-Many Quantum Finite Automata 37 Let M = (Q, £, S, g , F) be an MO-QFA and let M' = ( Q ' , E , 8', q , Q' , Q' ) be an 0 0 MM-QFA where n = \Q\, Q' = Q U {q , q n n + 1 acc , g n - i } is the set of states and, Q' rej 2 acc and Q' rej are defined as Q'acc = e <5' | ^ e F} The set Q' consist of the original set of states, plus an additional state for each original state. Let 8 be represented by the set of unitary matrices {U } ^ a {^}<7eE a and define 8' by the set of matrices where the matrix U' is a v. In and U $ UL Uflip where UfUp = In The matrix Ufu exchanges all amplitude between the states in Q and their corresponding states p in Q'\Q. Thus, M' has a 0 probability of halting until the end-marker is read and has an identical distribution to M when it does halt. Thus M' simulates M exactly. • 4.3 MO-QFAs Are Strictly Less Powerful than MM-QFAs By Theorem 4.6 it follows that the class R M O , the class of languages accepted with bounded error by MO-QFAs, is contained within the class R M M . Similarly the class U M O , the class of languages accepted with unbounded error by M O - Q F A s , is contained within the class UMM. While we do not know if the latter containment is proper, Theorem 4.7 proves that the former containment is proper; this implies that M M - Q F A s are strictly more powerful than MO-QFAs. Chapter 4. Measure-Many Quantum Finite Automata 38 Theorem 4.7 The class RMO is properly contained within the class R M M . Proof: Let L be the finite language L = {a}. Since L is a finite language it can be accepted by an RFA. By Lemma 4.4 L can be accepted by a MM-QFA with bounded error. Hence L is in the class R M M . By Theorem 3.3 the class R M O is identical to the class of languages accepted by a GFA. Since GFAs cannot accept finite languages, the result follows. • 4.4 MM-QFAs That Accept with Bounded Error The restriction of bounded error acceptance reduces the class of languages that an M M QFA can accept to a proper subclass of the regular languages[KW97]. To study the class of languages accepted by MM-QFAs with bounded error we look at the corresponding minimal automata for the languages. As we mentioned earlier, Ambainis and Freivalds[AF98] showed that if the minimal DFA M = (Q, £, S, q , F) for language L contains an irreversible 0 construction, defined by two distinct states (71,172 £ Q and strings x,y,z £ E + such that S(qi,x) = 8(q ,x) = 172, 8(q ,y) £ F and 8(q ,z) £" F, then an R F A cannot accept L and 2 2 2 an M M - Q F A cannot accept it with a probability greater than | . In fact, we have not been able to construct any M M - Q F A that could accept a language not accepted by an R F A with probability greater than ~0.68. Ambainis and Freivalds[AF98] showed that it is a necessary and sufficient condition that the minimal DFA corresponding to a language L cannot contain the above construction for L to be accepted by an R F A or by an M M - Q F A with a probability greater than | . We derive a similar necessary condition for a language L to be a member of the class RMM. This condition, called the partial order condition, is a relaxed version of a condition defined by Meyer and Thompson[MT69]. A language L is said to satisfy the partial order condition if the minimal DFA for L satisfies the partial order condition. A DFA satisfies the partial order condition if it does not contain two distinguishable states qi,q £ Q such that 2 there exists strings x,y £ E + such that 8(qi,x) = 8(q ,x) = C72, and 8(q ,y) = q\. States qi 2 2 Chapter 4. Measure-Many Quantum Finite Automata 39 and 172 are said to be distinguishable if there exists a string z £ £ * such that 8(qi,z) £ F and 5(q ,z) $ F or vice versa[HU79]. Theorem 4.8 proves that the partial order condition 2 is necessary for an M M - Q F A to accept L with bounded error. Theorem 4.8 If M = (Q, £ , 5, qo, F) is a minimal DFA for language L that does not satisfy the partial order condition then L R M M . Proof: By contradiction assume that L £ R M M . Let Lb = {a,b}*b. Since states qi and g are distinguishable states in the minimal DFA, the Myhill-Nerode theorem tells us that there 2 exists a string z that distinguishes the two states, i.e. 5(qi,z) £" F and 8(q ,z) £ F or vice 2 versa. Without loss of generality assume that 8(qi,z) g F and 8(q ,z) £ F. (If the opposite - 2 is true then we can simply take the complement of L by flipping all the non-accepting states to accepting and all accepting states to non-accepting. This does not change the structure of M except for the accepting set.) Since the minimal DFA for L does not satisfy the partial order condition there exist strings x, y £ £ + as defined above and a distinguishing string z £ £*. Let s be the shortest string such that 5(170,3) = q\. Let L' — s~ Lz~ . l l By Theorem 4.1 R M M is closed under word quotient. It follows that V £ R M M . Define the homomorphism h as h(a) = xy h(b) = x h(E — {a, b}) — xy where the last definition is for completeness. Let L" = /7 (L'). _1 By Theorem 4.1 R M M is closed under inverse homomorphisms, therefore the language L" £ R M M . But L" = Lb, which by Lemma 4.3, is not in R M M . Hence L £ R M M . • The partial order condition is so named because once the state q is visited, there is 2 no path back to state 171. Thus, there exists a partial order on the states of the D F A . At 40 Chapter 4. Measure-Many Quantum Finite Automata the current time, we do not know whether or not this condition is sufficient for M M - Q F A acceptance with bounded error. As mentioned before, we do not know whether the class R M M is closed under boolean operations. However, Theorem 4.11 relates closure under intersection to the partial order condition. In order to prove it we first need a couple of lemmas. Lemma 4.9 Let M be a DFA that satisfies the partial order condition. The minimal DFA M' that accepts L{M) satisfies the partial order condition. Proof: Let M = (Q, £ , 5, q , F) and M' = (Q', E , 8', q' , F'). Assume by contradiction that 0 0 M' does not satisfy the partial order condition. Hence, M' has two states that correspond to the equivalence classes [c^] and [q' ] such that [q[]x ~^ [q' ]x ~ L [q' ] ° d [l' }y ~L [q[]- By the Myhilla 2 2 2 2 Nerode theorem the equivalence classes partition the set Q. Hence, for each equivalence class [q ^ 1 there is a corresponding subset of Q. Let Qi and Q denote the subsets of Q corresponding to 2 the equivalence classes [q^] and [q' ] and assign an arbitrary order on the subsets. Select the first 2 state, say pi £ Q and define the set R = {q £ Q | 3n,m £ Z , 8(pi,x ) = 8(q,x ) = q}. + it m n 2 If there exists a state r £ R and string y £ £ + such that 8(r,y) = pi, then M does not satisfy the partial order condition, and this is a contradiction. Otherwise, there does not exist a y £ E + such that 5(r,y) = p\ for all r £ R. In this case there is a partial order on pi and on Q\\{pi} because p will never be visited again if M reads a sufficient number of xs. Remove pi from Qi x and repeat the procedure on p £ Q\. After a finite number of iterations we will either find a pi 2 that satisfies our requirements, which means that M does not satisfy the partial order condition and is a contradiction, or none of the states in Qi will have the required characteristics, in which case M' satisfies the partial order condition. Hence, if M satisfies the partial order condition, so will its minimal equivalent M'. • Lemma 4.10 Let M' and M" be minimal automata that satisfy the partial order condition and accept the languages V and L" respectively. The minimal automaton M that accepts L = U fl L" also satisfies the partial order condition. 41 Chapter 4. Measure-Many Quantum Finite Automata Proof: Let M' = (Q', T,,S',q' , F') and M" = (Q",E,8",q' ',F"). 0 0 We first construct an automaton M that accepts L' fl L" by combining M' and M" using a direct product. Define M . = (Q, £ , 8, g , F) where Q = Q'xQ", q 00 00 = (g , g '), F = {(g', g") € Q | g' € F ' A q" G F"} 0 0 and 8(( >,q"),o-) = (8>( ',a),8"(q",o)). q q We argue that if M' and M " satisfy the partial order condition, then so will M. Assume, by contradiction, that M does not satisfy the partial order condition. Then there exists two states Qij = (<?»><?") a n d Qki = Wk^ ") a a n d strings x,y,z £ £ + such that 8(q ,x) = 8{q x) = q i, i:i kh k 8(qki,y) = q%j and 8(qij,z) G F if and only if 8(qu,z) £ F. In the first case assume that either i ^ k or j ^ I, and without loss of generality, assume the former. Then there exists state q\ G Q' and state q' G k such that 8'(q[,x) = J'(g^,a;) = g^., 8i(q' ,y) = q\. But this means that M' k does not satisfy the partial order condition, a contradiction. In the second case assume that i — k and j = This implies that qij = q^i and hence there cannot exist a string z that distinguishes the two states, also a contradiction. Therefore M must satisfy the condition. Since M satisfies the partial order condition and accepts L, Lemma 4.9 proves that the minimal automaton that accepts L also satisfies the partial order condition. • Theorem 4.11 If the partial order condition is sufficient for acceptance with bounded error by MM-QFAs then the class R M M is closed under intersection. Proof: By Lemma 4.10 the intersection of two languages that satisfy the partial order condition is a language that satisfies the partial order condition. The result follows. • A possible attempt to prove that the class R M M is not closed under intersection would involve intersecting two languages in R M M and showing that the resulting language is not. Theorem 4.11 shows that this method will not work unless it is shown that the partial order condition is insufficient. To study whether the partial order condition is sufficient, as well as necessary, we describe a naturally defined class of languages that can be accepted by an M M - Q F A with bounded error. Chapter 4. Measure-Many Quantum Finite Automata 4.5 42 MM-QFAs Can Accept Piecewise Testable Sets A piecewise testable set is a boolean combination of sets of the form where X{ G £ [Per94]. Intuitively, L is the language of strings that contain the subsequence x x. We define a partial piecewise testable set as the language of strings that have a common subsequence; hence, a piecewise testable set is then a boolean combination of partial piecewise testable sets. We show, by construction, that M M - Q F A s can accept partial piecewise testable sets with bounded error. Furthermore, the MM-QFAs we construct are of a special kind we call 'end-decisive' and the languages accepted by end-decisive M M - Q F A s with bounded error are closed under intersection, which implies that M M - Q F A s can accept piecewise testable sets with bounded error. To construct the M M - Q F A s we introduce several useful concepts: junk states, trigger chains and end-decisiveness. A junk state is a halting state that does not contribute to the probability of accepting or rejecting a particular string. In general, any probability amplitude flowing into the junk state is split, usually evenly, between an accepting and rejecting state. That is, if a amplitude flows into a junk state, then ^ amplitude flows into an accept state, and the same amount will flow into a reject state. A machine is end-decisive if the probability of the machine accepting a string before reading the end-marker is the same irrespective of the string. The machine may halt before reading the full string, but it may only do so in a junk state because junk states do not contribute to the probability of accepting or rejecting a string. A n end-decisive or decisive state is a halting state that contributes to the probability of a string being accepted or rejected. A n end-decisive M M - Q F A will only place amplitude in a decisive state upon reading the end-marker. Chapter 4. Measure-Many Quantum Finite Automata 43 A trigger chain is a construction of junk states and transition matrices that causes a reduction in amplitude of a particular state only if the amplitude of another state is changed, presumably by some previous transition. Trigger chains correspond directly to partial piecewise testable sets. Consider the matrix 1 V2 U = J _ V2 n V2 U 1 '72 This matrix is a special case of one of the transition matrices introduced by Ambainis and Freivalds[AF98]. This matrix operates on three states and is a triggering mechanism of the chain. Consider the vectors h/>> = ( a , 0 , / ? ) and (a 8 a 8 T a 8\ The two are equal if and only if a = 8. If a ^ 8 then the result is that the amplitudes of the first and third state are averaged with the remainder of the amplitude in the second state. We define a generalized version of U by embedding it into a larger identity block matrix. Define Ui to be r h u= t u In—i—3 where I m is an m x m identity matrix, U is defined as above, and n is the number of states or, equivalently, the size of £/,-. Usually the second state of the state triple is a halting state; this implies that at the start of every transition it is going to have 0 amplitude. The matrix Ui operates on a triple of states qi through to qi+2- We assume that state <7;+i, the second state, is a junk state unless otherwise noted. Each junk state consists of two states, an accepting and a rejecting one. However, for the purposes of clarity we do not describe the accepting 44 Chapter 4. Measure-Many Quantum Finite Automata and rejecting states that implement a junk state. Theorem 4.12 proves, by construction, that partial piecewise testable sets can be accepted by M M - Q F A s with bounded error. T h e o r e m 4 . 1 2 Let L be a-partial-piecewisetestable language. There exists an end-decisive x MM-QFA Proof: that accepts L with bounded error. x We construct an MM-QFA that accepts L . Let x n = \x\, m = An + 8 and Q = {q ,q }. 0 {qi G Q | 0 < i < 2n A i = 1 Qacc = {c?2n+l} U {q Qrej = {qi G Q | 3 n + 6 < i < An + 8 } l c, aC where Qrej) Define m = Qjunk £ , 8, qo, Q M = (Q, (mod 2)} U {q +3, q2n+i] 2n G Q | 2n + 4 < i < 3 n + 6 } where the last 2n + 4 states are used to implement the junk states. We now construct the transition matrices for M. Let 8 be defined by the transition matrices {U } £-£. Each transition matrix U will consist of a product of n matrices. Let A A A JU:U:_ ..U^ u = V a where i —0 A S Uf XQ = cr U i-2 1 < i < n A Xi = a Im otherwise 2 and 0 s 1 1 0 'm-2 The matrix S shifts the amplitude of q to the junk state qi. This is the first trigger that is 0 activated when x i is read. The initial configuration of the machine is \tpi i ) n t where a,: = < _L= 0 0<i<2n-r-2 A i = 0 (mod 2) otherwise = (cx , 0 c t i , a 2 n + 4 ) T Chapter 4. Measure-Many Quantum Finite Automata 45 This means that the amplitude is evenly distributed among all non-halting states. The matrix J implements the junk states; it transfers the amplitude from the junk states to the accepting and rejecting states, i.e. flushes the junk states. Finally we define the transition matrix for the end-marker $ as U = JFU % 2n where R R F 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 <2n+4 and 0 1 1 0 R sends all amplitude into the junk states because junk states have 0 amplitude at the start of every transition. The matrix U sends some minimum amount of amplitude, into an accept state if 2n the amplitudes of states q and q + 2n 2n a r e 2 unequal. We now describe the operation of the machine. The only decisive accepting state in the machine is q +i, and amplitude only flows into it when the end-marker is read. In order for 2n it to get a non-zero amplitude, the amplitudes for states q 2n and q +2 2n must differ. Since all non-halting states start with the same amplitude, and since the amplitude of state q 2n+2 will not change during the execution of the machine, until the end-marker is read, it follows that in order for the amplitude of state q 2n to change, the amplitude of state q -2 2n must change. Following 46 Chapter 4. Measure-Many Quantum Finite Automata the same argument, state 172; will not change in amplitude, until state (721-2 changes in amplitude. Furthermore the change in amplitude of state 172; is governed by the matrix components U i2 2 and U~2i- Hence, the initial change of amplitude of state q i depends exclusively on a change in 2 amplitude of state and is governed by component q i2 2 U i2 2 that is located in the transition matrix U . It also follows that if any other transition matrix is applied, then the amplitude of Xi state qu will not change since the corresponding component is not part of the transition matrix. Hence M can read ( £ — {x;})* without changing the amplitude of state 072;, but, as soon as X{ is read, component U i2 2 will be applied and c7 2t will have a decreased amplitude, provided that state q {- already had a decrease in its amplitude. Finally, the amplitude of any state q { will 2 2 2 never increase beyond its initial value, and once the amplitude of state q { decreases, it will never 2 increase beyond ^ 1 + 2 — (\) n+2 . The main observation is that the amplitude of state 172, will not decrease until the amplitude of state q i2 2 decreases, and until symbol x- is read. Reading t any other symbol instead will not change the amplitude of state 172; and if state retains its q i2 2 original amplitude, then reading symbol X{ will not change the amplitude of state q {. For the 2 case of symbol x , the amplitude of state q is changed by matrix S to 0 and is the starting 0 0 trigger. When the end-marker is read, some amount of amplitude, a minimum of placed into the accepting state only if the amplitudes of states q 2n and c7 +2 2n ^p ( ) 2 n + 3 2 > differ. The rest of the amplitude, from all n + 2 non-halting states is channeled into junk states. If the amplitudes of q 2n and 172,1+2 do not differ then all amplitude is channeled into junk states. The probability of M accepting a string not in the language is | , while the probability of M accepting a string in the language is at least | + ^ ( | ) n + 4 - Therefore M accepts with bounded error. • The M M - Q F A construction in Theorem 4.12 is end-decisive. This means that we can take the intersection of partial piecewise testable languages and their complement. We prove these two results in the next two lemmas. Lemma 4.13 Let M be an end-decisive MM-QFA that accepts with bounded error. The Chapter 4. Measure-Many Quantum Finite Automata complement of M is also an end-decisive MM-QFA 47 that accepts with bounded error. Proof: Leave the junk states as they are, and flip all the deciding accepting and rejecting states of M . - The new automaton is also end-decisive and has the same margin as M and therefore accepts with bounded error. • Lemma 4.14 Let M and M' be end-decisive MM-QFAs There exists an end-decisive MM-QFA that accept with bounded error. M" that accepts L = L(M) fl L(M') with bounded error. Proof: To facilitate the proof we use a different formalism from the one defined in Section 2.8 for MM-QFAs. Let M = (Q,X,8,q ,Q ,Q ,Q ) 0 acc rej and M' = (Q', E , S', q' , Q' , Q' , junk 0 be end-decisive MM-QFAs that accept L(M) and L(M'). rej , unk Q' ) junk We construct a MM-QFA M" = that accepts L = L{M) fl L ( M ' ) . In this case Q (Q' ,^,S",q^,Q'i ,Q'C,Q'; ) cc acc acc are sets that contain deciding accept and reject states, while Qj k un and Q rej contains junk halting states, each of which can be implemented by an accepting and rejecting state. The two formalisms are equivalent. Let Q" = Q x Q' and q' ' = (qo,q ). The three sets of halting states are defined as Q 0 Q'junk = {(quVj) tQ" Q'L = {(<&,?;) € Q" | qi G Qacc {buQj) G Q" I M ) t Qjunk Qrej = \ Qi e Qjunk v q\ e Q' } junk A q] € Q' ] acc A (* € Qrej Vflj€ Q' )} rej and the transition function 5" is a tensor product of the transition functions 8 and 8'. Since M and M' are end-decisive, the decisive states will only have non-zero amplitude when the end-marker is read. Since the junk states do not contribute to the probability of acceptance or rejection of a string, only the decisive states play a role and these states will only have a non-zero amplitude at the end of the computation. Thus, the only measurement that will measure any amplitude in the decisive states is the one after the end-marker is read. Hence, we return to the situation where we have two types of states, accepting and rejecting. We handle this in the Chapter 4. Measure-Many Quantum Finite Automata 48 same way as MO-QFAs. The fact that M" accepts with bounded error follows from the fact that taking the tensor product and defining accepting and rejecting states as above implies that the probability of M" accepting a string x is P[M"(x) = accept] = P[M(x) = accept] P[M'(x) = accept] Let M and M' accept with respective cut-points A and A' and margins e and e'. If x G L then P[M"(x) = accept] > XX' + Ac' + A'e + ee' = (XX' + ee') + (Ac' + A'e) > A" + e" where A" = AA' + ee' and e" = min{Ae', A'e}. If x g L then without loss of generality assume - that x g L(M). It follows that P[M"(x) = accept] < XX' - Ac' + A'e - ee' < A A ' - Ac'+ A'e - ee'+ 2ee' = (AA'+ ee') + ( A e ' - A'e) < A"-e" If both languages L(M) and L(M') are in R M M , then the language L is in R M M » C £ R M M . The MM-QFA M" accepts L with bounded error and the decisive states are only used when the end-marker is read, even though junk states may occur throughout the computation. Thus, M" is an end-decisive MM-QFA that accepts with bounded error. • Corollary 4.15 Let M and M' be end-decisive MM-QFAs that accept with bounded error. There exists an end-decisive MM-QFA M" that accepts L — L(M) U L(M') with bounded error. Since the class of languages that are accepted by end-decisive M M - Q F A s with bounded error is closed under boolean operations, and since M M - Q F A s that accept partial piecewise Chapter 4. Measure-Many Quantum Finite Automata 49 testable sets with bounded error can be constructed such that they are end-decisive, it follows that we can construct M M - Q F A s that accept piecewise testable sets with bounded error. Theorem 4.16 MM-QFAs can accept piecewise testable sets with bounded error. Chapter 5 Conclusions and Future Work We have defined two different models of 1-way quantum finite automata. These computation models, termed measure-once and measure-many, are probabilistic and are similar to probabilistic finite automata. The measure-once automaton operates by performing unitary operations, on its configuration, corresponding to the symbols that it reads. At the end of its computation it measures its state and accepts if it is in an accepting state. The measuremany model also performs unitary operations on its configuration, which correspond to the symbols that it reads, but also performs a partial measurement after every transition collapsing its superposition to a subspace spanned by the non-halting, accepting or rejecting states. This allows measure-many automata to halt part way through the computation. We showed that the class of languages accepted by measure-once automata with bounded error (RMO) is exactly the class of languages accepted by group finite automata. This implies that the class R M O is closed under boolean operations, inverse homomorphisms, and word quotients. This complements the results of Moore and Crutchfield[MC98] that proved that the class of languages accepted by a measure-once automaton with unbounded error (UMO) is also closed under these operations. Measure-once automata that accept with unbounded error can accept non-regular languages and, in particular, can solve the word problem over the free group. We showed that any language accepted by a measureonce automaton can also be accepted by a probabilistic finite automaton, which means that probabilistic finite automata can also solve the word problem over the free group. Finally, we presented an algorithm for determining if two measure-once automata are equivalent, i.e. have the same distribution. 50 Chapter 5. 51 Conclusions and Future Work We defined the class of languages accepted by measure-many automata with bounded error ( R M M ) and the class of languages accepted by measure-many automata with unbounded error ( U M M ) . We showed that both classes are closed under complement, inverse homomorphism, and word quotient. We showed by construction that the class R M O is properly contained within R M M and that the class U M O is contained within U M M . We proved a necessary condition for a language to be in the class R M M , which we call the partial ordering condition. We have shown by construction that piecewise testable sets are contained within the class R M M and, in the process, introduced the concepts of junk states, trigger chains, and end-decisiveness. We have also shown that the class of languages accepted by end-decisive measure-many automata are closed under boolean operations. 5.1 Open Problems The partial ordering condition is necessary for a language to be a member of the class R M M . However it is still unknown whether the condition is sufficient. We conjecture that the partial ordering condition is also sufficient for membership in the class R M M . C o n j e c t u r e 5.1 The partial ordering condition is necessary and sufficient for a language L to be a member of the class R M M . We showed that if the partial ordering condition was sufficient for membership within the class R M M then the class R M M is closed under boolean operations. A n easier open problem is to determine if the class R M M is closed under boolean operations. A negative result would prove the above conjecture false. Finally, Ambainis and Freivalds[AF98] state any language that has irreversible transitions into non-spin states cannot be accepted by a measure-many automaton with a probability greater than | . We have not been able to construct an automaton that can accept such a language with a probability greater than -""a 0.68. Narrowing this gap is also an open problem. Bibliography [AF98] Andris Ambainis and Rusins Freivalds. 1-way quantum finite automata: Strengths, weaknesses and generalizations. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 332-342, November 1998. [AKN98] Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, pages 20-30, 1998. [Ang82] Dana Angluin. Inference of reversible languages. Journal of the Association Computing Machinery, 29(3):741-765, July 1982. for [ANV98] Andris Ambainis, Ashwin Nayak, and Umesh Vazirani. On the space-efficiency of 1-way quantum finite automata. Preprint, cessing Letters, (quant-ph/9804043), To be submitted to Information Pro- 1998. [Ben73] Charles Bennett. Logical reversibility of computation. and Development, 17:198-200, November 1973. IBM Journal of Research [Ber76] S. Berberian. Introduction to Hilbert Spaces. Chelsea Publishing Company, New York, 1976. [BH97] Gilles Brassard and Peter H0yer. An exact quantum polynomial-time algorithm for Simon's problem. In Proceedings of the Fifth Israeli Symposium Computing and Systems, on Theory of 1997. [BV97] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SI AM of Computing, pages 1411-1473, October 1997. [Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London, A400:97-117, Journal 1985. [Deu89] D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of London, A425:73-90, 1989. [DS89] Cynthia Dwork and Larry Stockmeyer. On the power of 2-way probabilisitic finite state automata. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 480-485, 1989. [DS90] Cynthia Dwork and Larry Stockmeyer. A time complexity gap for two-way probabilisitic finite-state automata. SIAM Journal of Computing, pages 1474-1483, December 1990. 52 Bibliography 53 [Eil76] S. Eilenberg. Automata, New York, 1976. [Fre81] Rusins Freivalds. Probabilistic two-way machines. In Proceedings of 10th International Symposium Languages and Machines, volume B. Academic Press, on Mathematical Foundations of Computer Science, volume 118 of Lecture Notes on Computer Science, pages 33-45, September 1981. [Gas96] Stephen Gasiorowiz. 1996. Quantum Physics. John Wiley and Sons, Inc., New York, [GKP94] Ronald L. Graham, Donald E . Knuth, and Oren Patashnik. Concrete Addison-Wesley Publishing Company, New York, New York, 1994. Mathematics. [Gos92] Amit Goswami. Quantum Mechanics. W m . C. Brown Publishers, New York, 1992. [Gro96] Lov Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996. [HU79] John E . Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishers, Reading, Massachusetts, 1979. [KW97] Attila Kondacs and John Watrous. On the power of quantum finite state automata. In Proceedings of the 38th Annual Symposium on Foundations of Computer Sci- ence, pages 66-75, 1997. [LMT97] Klaus-Jorn Lange, Pierre McKenzie, and Alain Tapp. deterministic space. In Proceedings of the 12th IEEE Reversible space equals Conference on Computational Complexity, pages 45-50, 1997. [MC98] Cristopher Moore and James P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science, 1998. [Mor90] Michael A. Morrison. Understanding Quantum Physics. Prentice Hall, Englewood Cliffs, NJ, 1990. [MT69] A. R. Meyer and C. Thompson. Remarks on algebraic decomposition of automata. Mathematical Systems Theory, 3(2):110—118, 1969. [Paz71] Azaria Paz. Introduction to Probabilistic Automata. New York, 1971. Academic Press, New York, [Per94] Dominique Perrin. Finite automata. In J . van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 1. Elsvier Science Publisher, 1994. 54 Bibliography [Pin87] J . Pin. On languages accepted by finite reversible automata. In Proceedings of the 14th International Colloquium on Automata, Languages and Programming, volume 267 of Lecture Notes on Computer Science, pages 237-249, 1987. [Rab63] M . Rabin. Probabilistic automata. Information and Control, 6:230-245, 1963. [RS59] M . Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:114-125, April 1959. [She59] J . Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal [Sho94] of Research and Development, 3:198-200, April 1959. Peter W . Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Com- puter Science, pages 124-134, 1994. [Sho97] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):14841509, 1997. [Sim97] Dan Simon. On the power of quantum computation. SIAM Journal of Computing, pages 1474-1483, October 1997. [Tze89] Wen-Guey Tzeng. The equivalence and learning of probabilistic automata. Proceedings of the 30th Annual Symposium on Foundations of Computer In Science, pages 268-273, 1989. [Tze92] Wen-Guey Tzeng. A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM Journal on Computing, 21(2):1484-1509, August 1992. [Wag85] Stan Wagon. The Banach-Tarski York, New York, 1985. [Yao93] Andrew Chi-Chi Yao. Quantum circuit complexity. In Proceedings of the 3\ih Annual Symposium on Foundations Paradox. Cambridge University Press, New of Computer Science, pages 352-361, 1993.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Models and characterizations of 1-way quantum finite...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Models and characterizations of 1-way quantum finite automata Brodsky, Alexander 1998
pdf
Page Metadata
Item Metadata
Title | Models and characterizations of 1-way quantum finite automata |
Creator |
Brodsky, Alexander |
Date Issued | 1998 |
Description | 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. |
Extent | 2742602 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-06-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051605 |
URI | http://hdl.handle.net/2429/8895 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1999-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1999-0011.pdf [ 2.62MB ]
- Metadata
- JSON: 831-1.0051605.json
- JSON-LD: 831-1.0051605-ld.json
- RDF/XML (Pretty): 831-1.0051605-rdf.xml
- RDF/JSON: 831-1.0051605-rdf.json
- Turtle: 831-1.0051605-turtle.txt
- N-Triples: 831-1.0051605-rdf-ntriples.txt
- Original Record: 831-1.0051605-source.json
- Full Text
- 831-1.0051605-fulltext.txt
- Citation
- 831-1.0051605.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051605/manifest