@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Brodsky, Alexander"@en ; dcterms:issued "2009-06-09T20:05:17Z"@en, "1998"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms: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."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/8895?expand=metadata"@en ; dcterms:extent "2742602 bytes"@en ; dc:format "application/pdf"@en ; skos:note "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 B y Alexander Brodsky B . M a t h . (Computer Science with Physics Minor) University of Waterloo A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R ; O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S D E P A R T M E N T O F C O M P U T E R S C I E N C E We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A 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 V6T 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 ac-ceptance 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 proba-bilistic 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 er-ror 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 17 3 Measure-Once Quantum Finite Automata 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 MM-QFAs That Accept with Bounded Error 38 4.5 MM-QFAs Can Accept Piecewise Testable Sets 42 5 Conclusions and Future Work 50 5.1 Open Problems 51 Bibliography 52 iv List of Figures 3.1 G F A 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 over-whelming 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 Tur-ing machines, which are conjectured to be more powerful than their classical, probabilis-tic 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 postu-lates 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 measure-ment 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 MO-QFA 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 MO-QFA 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. Introduction 3 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. Introduction 4 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 comple-mentary 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 de-termine 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 cor-responding 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 A quantum system can be in a superposition of both states, e.g. a|0) + The probability of measuring the Chapter 2. Background and Definitions 6 system in state |0) is |a | 2 and the probability of measuring the system in state |1) is \\(3\\2 where |Q|2 + \\/3\\2 = 1. 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 inde-terminate. 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 partic-ular 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. An 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 n-dimension 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 (2.1) where (qi\\^) is the amplitude of state 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 complex-conjugate. 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) a n d w e apply the unitary operation U to it, then the new configuration of the system is = U\\^o). In terms of projection matrices Equation 2.1 can be rewritten as Fr[system in state qs] = (*|P ; |*) Chapter 2. Background and Definitions 8 where P2 is a projection matrix whose ith diagonal entry is a one, and, 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|| 2 represents the norm of the vector. The operator ® is the 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 DFA 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 Chapter 2. Background and Definitions 9 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', a->(l') = 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 Aa that determines the transitions that the PFA makes 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 PFA M accepting a word 1 6 S * is P M ( X ) = T T A ( X ) T ] where x — xiX2...xm and A(x) = AXlAX2...AXm. A PFA 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 PFA 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 PFA with some cut-point A is known as a probabilistic cut-point event (PCE). The PFA corresponds to a stochastic system S = (n, {Aa}aez, il)- An 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. Chapter 2. Background and Definitions 11 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 lan-guages 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(L) — {x £ E* | h(x) £ L}. The left word quotient of L for some word w £ E* is defined as w~lL = {x £ E* | wx £ L}. Symmetrically 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 : Q x E x ( 2 - + C Chapter 2. Background and Definitions 12 such that for all a £ E and 171,172 £ Q £ % I , C T , C 7 ' ) % 2 , = X>l »=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 in state 17;, and |a;| 2 = 1. Upon reading a symbol || 2) where pacc and prej are the cumulative probabilities of accepting and rejecting, and P a c c , Prej and Pnon are the diagonal projection matrices that project the configuration onto the non-halting, accepting or rejecting subspaces. Chapter 2. Background and Definitions 14 2.9 L a n g u a g e A c c e p t a n c e b y a Q u a n t u m F i n i t e 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 E q u i v a l e n c e o f Q u a n t u m F i n i t e A u t o m a t a We say that two QFAs are equivalent if they have the same acceptance probability distribu-tion on the set of words over an alphabet E . Formally, QFAs Mi and M2 are equivalent if for every word x £ £* the probability of Mi accepting x is equal to the probability of M-i accepting x, i.e. PMX{X) = PM2{X) for all x £ E*. 2.11 E q u i v a l e n c e o f M O - Q F A s a n d M o o r e - C r u t c h f i e l d Q F A s The QFA introduced by Moore and Crutchfield[MC98] is similar to the MO-QFA. A Moore-Crutchfield QFA M = (TC, E , {Ua}„e-£, \\sinit),TLa) consists of an n-dimensional Hilbert space H, an initial configuration vector \\sinit), an accepting subspace 7ia with a corresponding projection matrix P a , an input alphabet E , and a unitary matrix Ua for each symbol in E . The probability of a Moore-Crutchfield automaton accepting a string x is defined as f(x) = \\\\PaU(x)\\stnit)\\\\2 is almost the same as an MO-QFA automaton except that |s,-„,-t) may be an arbitrary unit vector, P a is not necessarily a diagonal projection matrix and there is no end-marker $. How-ever, there is a correspondence that preserves acceptance probability distribution between Chapter 2. Background and Definitions 15 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 = (TC,T*,{Ua}crez,\\simt),'Ha) be a Moore-Crutchfield QFA. We construct an equivalent MO-QFA M' = (Q, £ U.{c i , $} , <5, q0, F) where ci is the left end-marker. Let Q = {ir = l l ^ ^ - ^ k o ) | | 2 = \\\\PU$UXn...UXlU. is the same as M's. Thus one end-marker on the right suffices, and by symmetry one left end-marker would also suffice. Therefore, an M O - Q F A starting in configuration \\q0) can simulate an MO-QFA 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 MO-QFA 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 \\q0). 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 QFA 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,Qacc,Qrej) be an MM-QFA that uses two end-markers and accepts L. Assume without loss of generality that Qnon — {qi G Q | 0 I <^ nnon\\ Qacc — {qi G Q | T^non ^ o RMO ( . 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 PFA. 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 MM-QFAs 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 MO-QFA can be simulated exactly by a M M - Q F A . This limits the class RMO to a proper subset of regular languages. The class RMO 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. Measure-Once Quantum Finite Automata 20 Lemma 3.1 Let U be a unitary matrix. For any e > 0 there exists an integer n > 0 such that for all vectors x, where \\\\x\\\\2 < 1, it is true that — (7 n )x|| 2 < e. Proof: Let m — dim(U). Since U is a normal matrix and has eigenvalues that are of the form et6, Un can be written as 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 J 7 r r j ' . If all eigenvalues in D are rotations through rational fractions of I T , i.e. r , is rational, then let n = 2 r i jL i 9j w n e r e Qj i S the denominator of rr Thus DN = I and we are 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 D' = DN. The values on the diagonal of D' are either 1 or 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 ^ f c 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'h)l\\\\2 < t'. Hence ||(/- Unk)x\\\\2 = | | ( / - PD^P-^xW2 = \\\\P{I - D ' ^ P - ' X W 2 < | | ( 7 - 7 ) , f c ) m l | | 2 = m 2 | | ( 7 - 7 } ' f c ) l | | 2 < m2e' Select e' such that e' < to complete the proof. • If two conf igurat ions are 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 of t h e conf igurat ions is also s m a l l . T h e f o l l o w i n g l e m m a , due t o B e r n s t e i n a n d V a z i r a n i [ B V 9 7 ] , Chapter 3. Measure-Once Quantum Finite Automata 21 allows us to relate the closeness of configurations to the variance in their probability distri-butions. This is necessary in order for us to partition the set of allowable configurations into equivalence classes. Lemma 3.2 (Bernstein and Vazirani, 1997) Let \\tp) and \\ip) be two complex vector such that HIV^II2 = Hlv7)!!2 = 1 a n d || 1 ^ ) — lv)l|2 < e- 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, q0, F) be a GFA that accepts L. Let 8 be 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,q0, 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 Ua is the transition matrix for symbol a, \\tb) £ [y] and \\(p) £ [y1] then Ua\\xl>) £ [x] and U„\\tp) £ [x]. 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*)^>|| 2 < f and ||(/ - Uk„)\\tp)\\\\2 < f . Hence, « 7 » £ [y] Chapter 3. Measure-Once Quantum Finite Automata 22 because if I I U - ^ M I I 2 = IIIV>)-^|V>)II2 = iini^)-^i^))n2 e < 4 where V is an arbitrary unitary matrix, then by Lemma 3.2 the probability of VUk\\ip) 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 Uk\\ 0, hence there are most two distinct classes of languages accepted by MO-QFAs, the restricted class RMO, which is equivalent to the class of languages accepted by a GFA, 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, in-verse 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 UMO 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 The classes R M O and U M O are closed under left and right quotient. Proof: Let M = (Q,T,,8,q0, F) be a MO-QFA with a left and right marker that accepts L and let w G E + be the quotient word. We show that there exists MO-QFAs M' and M\" that accept w~lL and Lw~x with the same cut-point and margin as M. For the left quotient define the homomorphism The inverse homomorphism of the L is precisely w lL and by Lemma 3.4 there exists a MO-QFA otherwise M' that accepts w 1L with the same cut-point and margin as M accepting L. For right quotient use the homomorphism CT = $ h(o) a otherwise that yields Lw 1 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 GFA. Using this result, we can construct a GFA 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 RMO is exactly the class of languages accepted by a GFA, the language L is accepted by a GFA, but h(L) is not. It follows that the class RMO is not closed under homomorphisms. • Chapter 3. Measure-Once Quantum Finite Automata 25 3.3 MO-QFAs 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, = irU'(x)r] is bilinear. The new automaton has n2 states but also might have non-real 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 2n2-state pseudo-stochastic system that is equivalent to M', is bilinear and uses real entries in its transition matrices. Let n' = (ir,0), let A„ correspond to U'a where each entry in U'a is replaced by a 2 x 2 real matrix defined above, and let n' be the acceptance vector such that rj'2i = [q[ £ F']. This is a pseudo-stochastic system S — (IT1, {A^}^^, rj') that accepts L with the same cut-point as M. Hence, L is a GCE and 5\" has 2n 2 states. • 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,{Aa},q) and N' = (IT', {A'a}, v') with 2m 2 and 2n 2 states respectively. We now con-struct a 2m 2 + 2n 2 state pseudo-stochastic system N\" = (TT\", {A\"a},q\") where Aa 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 N „ ( S * ) = 7r\"A\"(E*)77\" = 0 This reduces the MO-QFA equivalence problem to the initial distribution equivalence prob-lem, 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 = 2m2 + 2n 2 and select the maximal independent set 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]. 7T = [7r,7T j , q A\" a Chapter 3. Measure-Once Quantum Finite Automata 29 Theorem 3.10 Let n and p be two initial distributions, let {Aa} the set of matrices, let r\\ 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 ^ a*Vi = X ! (li'KVi = X ] a i P V i = P ^2 aiVi = PMX)V vteB vieB vieB 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 MO-QFA can also be accepted by a PFA. If L can be accepted by an MO-QFA with bounded error, then it be accepted by a PFA 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 mea-surement is performed after every transition. This allows the machine to terminate be-fore reading the entire string and simulate spin states. Just as in the case of MO-QFAs, MM-QFAS 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 0 be the 'unrestricted' class of languages accepted by an M M - Q F A and let R M M be the class of 'restricted' languages where R M M = Ue>o R M M £ . In Section 4.1 we prove several closure properties of both classes of languages. Section 4.2 shows how MM-QFAs 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 MM-QFAs 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 RMO and UMO 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 e is closed under complement, inverse homomorphisms, and 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). Let M = (Q,H,6,Qacc,Qrej) and M' = (Q',T,,8',Q'acc,Q'rej). Assume that 8 and 8' are defined in terms of matrices {U^}^^ and {UUnlike 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 Qnon — {qi £ Q | 0 1 ^ ^non} Qhalt = {qi € Q I nnon If) V i=l t=l / while the resulting configuration of M' is {P'nonKm.Pacc + \\\\KccKW)\\W Prej + II P'rejK I *'> II') = (PLnV(H°)W),Pacc + \\\\P'ac H 2 , P r « + || P'rej V*r • • ^ I *') II') = (pLnV(lW),Pacc + E \\\\PLV(i)m\\\\2*Prej + £ II Ke^) I *'> II') \\ i=l i=\\ I = (pLnV(m\\d),PacC + E I I ^ O I * ) ® ! ! 2 , ^ + E l l ^ ' e / ( 0 l * ) | 0 ) | | 2 ) V i=l i=l I = ((PnonU(m)\\Q),Pacc + £ II ( ^ c c ^ ( » ) I *) ) |0> f , Prej + E || (PrejU(l) | * » |0> | | 2) V i=\\ i=l / Chapter 4. Measure-Many Quantum Finite Automata 35 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[L) with the same distribution as M, which means that R M M e is 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~lL and for right quotient use the homomorphism, Hi) = i h(cr) — a = w$ to accept the language Lw~x. This is identical to the argument used in Theorem 3.5. • Corollary 4.2 The classes R M M and U M M are closed under complement, inverse ho-momorphisms, and word quotients. Just like the class RMO, 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 ac-cepted by an MM-QFA with bounded error. Lemma 4.4 (Ambainis and Freivalds, 1998) If L can be accepted by a RFA, it can be accepted by an MM-QFA with certainty. Chapter 4. Measure-Many Quantum Finite Automata 36 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 MM-QFAs 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 MO-QFA, 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 MO-QFA 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 For every MO-QFA M there exists an MM-QFA M' that has the same dis-tribution as M. Chapter 4. Measure-Many Quantum Finite Automata 37 Proof: Let M = (Q, £, S, g 0 , F) be an MO-QFA and let M' = ( Q ' , E , 8', q0, Q'acc, Q'rej) be an MM-QFA where n = \\Q\\, Q' = Q U {qn, q n + 1 , g 2 n - i } is the set of states and, Q'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 {Ua}a^ and define 8' by the set of matrices {^}<7eE where the matrix U'a is v. In and UL U$ Uflip where UfUp = In The matrix Ufup exchanges all amplitude between the states in Q and their corresponding states 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 RMO, the class of languages accepted with bounded error by MO-QFAs, is contained within the class R M M . Similarly the class UMO, the class of languages accepted with unbounded error by MO-QFAs, is contained within the class U M M . While we do not know if the latter containment is proper, Theorem 4.7 proves that the former containment is proper; this implies that MM-QFAs 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 RMO 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 min-imal automata for the languages. As we mentioned earlier, Ambainis and Freivalds[AF98] showed that if the minimal DFA M = (Q, £, S, q0, F) for language L contains an irreversible construction, defined by two distinct states (71,172 £ Q and strings x,y,z £ E + such that S(qi,x) = 8(q2,x) = 172, 8(q2,y) £ F and 8(q2,z) £\" F, then an RFA cannot accept L and 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 RFA 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 RFA 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 R M M . 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,q2 £ Q such that there exists strings x,y £ E + such that 8(qi,x) = 8(q2,x) = C72, and 8(q2,y) = q\\. States qi 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(q2,z) $ F or vice versa[HU79]. Theorem 4.8 proves that the partial order condition 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 g2 are distinguishable states in the minimal DFA, the Myhill-Nerode theorem tells us that there exists a string z that distinguishes the two states, i.e. 5(qi,z) £\" F and 8(q2,z) £ F or vice versa. Without loss of generality assume that 8(qi,z) g- F and 8(q2,z) £ F. (If the opposite 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~lLz~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 _ 1 (L') . 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 q2 is visited, there is no path back to state 171. Thus, there exists a partial order on the states of the DFA. At Chapter 4. Measure-Many Quantum Finite Automata 40 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, q0, F) and M' = (Q', E , 8', q'0, F'). Assume by contradiction that M' does not satisfy the partial order condition. Hence, M' has two states that correspond to the equivalence classes [c^ ] and [q'2] such that [q[]x ~^ [q'2]x ~ L [q'2] a ° d [l'2}y ~L [q[]- By the Myhill-Nerode theorem the equivalence classes partition the set Q. Hence, for each equivalence class [q1^ there is a corresponding subset of Q. Let Qi and Q2 denote the subsets of Q corresponding to the equivalence classes [q^] and [q'2] and assign an arbitrary order on the subsets. Select the first state, say pi £ Qit and define the set R = {q £ Q2 | 3n,m £ Z + , 8(pi,xm) = 8(q,xn) = q}. 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 px will never be visited again if M reads a sufficient number of xs. Remove pi from Qi and repeat the procedure on p2 £ Q\\. After a finite number of iterations we will either find a pi 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. Chapter 4. Measure-Many Quantum Finite Automata 41 Proof: Let M' = (Q', T,,S',q'0, F') and M\" = (Q\",E,8\",q'0',F\"). 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 0 0 , F) where Q = Q'xQ\", q00 = (g 0, g0'), F = {(g', g\") € Q | g' € F ' A q\" G F\"} and 8((q>,q\"),o-) = (8>(q',a),8\"(q\",o)). 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 , 0 , / ? ) T and (a 8 a 8 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 ut= u In—i—3 where Im 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 Chapter 4. Measure-Many Quantum Finite Automata 44 and rejecting states that implement a junk state. Theorem 4.12 proves, by construction, that partial piecewise testable sets can be accepted by MM-QFAs with bounded error. T h e o r e m 4 . 1 2 Let Lx be a -partial -piecewise testable language. There exists an end-decisive MM-QFA that accepts Lx with bounded error. P r o o f : We construct an MM-QFA that accepts Lx. Let M = (Q, £ , 8, qo, QaCc, Qrej) where n = \\x\\, m = An + 8 and Q = {q0,qm}. Define Qjunk = {qi G Q | 0 < i < 2n A i = 1 (mod 2)} U {q2n+3, q2n+i] Qacc = {c?2n+l} U {ql G Q | 2n + 4 < i < 3 n + 6} Qrej = {qi G Q | 3 n + 6 < i < An + 8} 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 {UA}A£-£. Each transition matrix UA will consist of a product of n matrices. Let where Uf ua = JU:U:_V..U^ S i — 0 A XQ = cr U2i-2 1 < i < n A Xi = a Im otherwise and s 0 1 1 0 'm-2 The matrix S shifts the amplitude of q0 to the junk state qi. This is the first trigger that is activated when x i is read. The initial configuration of the machine is \\tpinit) = (cx0, c t i , a 2 n + 4 ) T where _ L = 0 < i < 2 n - r - 2 A i = 0 (mod 2) 0 otherwise a,: = < 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% = JFU2n where F R R 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 <2n+4 and R 0 1 1 0 sends all amplitude into the junk states because junk states have 0 amplitude at the start of every transition. The matrix U2n sends some minimum amount of amplitude, into an accept state if the amplitudes of states q2n and q2n+2 a r e unequal. We now describe the operation of the machine. The only decisive accepting state in the machine is q2n+i, and amplitude only flows into it when the end-marker is read. In order for it to get a non-zero amplitude, the amplitudes for states q2n and q2n+2 must differ. Since all non-halting states start with the same amplitude, and since the amplitude of state q2n+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 q2n to change, the amplitude of state q2n-2 must change. Following Chapter 4. Measure-Many Quantum Finite Automata 46 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 U2i-2 and U~2i- Hence, the initial change of amplitude of state q2i depends exclusively on a change in amplitude of state q2i-2 and is governed by component U2i-2 that is located in the transition matrix UXi. It also follows that if any other transition matrix is applied, then the amplitude of 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 U2i-2 will be applied and c72t will have a decreased amplitude, provided that state q2{-2 already had a decrease in its amplitude. Finally, the amplitude of any state q2{ will never increase beyond its initial value, and once the amplitude of state q2{ decreases, it will never increase beyond ^ 1 + 2 — (\\) n + 2 . The main observation is that the amplitude of state 172, will not decrease until the amplitude of state q2i-2 decreases, and until symbol xt- is read. Reading any other symbol instead will not change the amplitude of state 172; and if state q2i-2 retains its original amplitude, then reading symbol X{ will not change the amplitude of state q2{. For the case of symbol x0, the amplitude of state q0 is changed by matrix S to 0 and is the starting trigger. When the end-marker is read, some amount of amplitude, a minimum of ^ p 2 ( 2 ) n + 3 > placed into the accepting state only if the amplitudes of states q2n and c7 2 n+2 differ. The rest of the amplitude, from all n + 2 non-halting states is channeled into junk states. If the amplitudes of q2n 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 47 complement of M is also an end-decisive MM-QFA 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 that accept with bounded error. There exists an end-decisive MM-QFA 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,q0,Qacc,Qrej,Qjunk) and M' = (Q', E , S', q'0, Q'acc, Q'rej, Q'junk) be end-decisive MM-QFAs that accept L(M) and L(M'). We construct a MM-QFA M\" = (Q',,^,S\",q^,Q'icc,Q'C,Q';unk) that accepts L = L{M) fl L ( M ' ) . In this case Qacc and Qrej are sets that contain deciding accept and reject states, while Qjunk 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'Q' = (qo,q0). The three sets of halting states are defined as Q'junk = {(quVj) tQ\" \\ Qi e Qjunk v q\\ e Q'junk} Q'L = {(<&,?;) € Q\" | qi G Qacc A q] € Q'acc] Qrej = {buQj) G Q\" I M ) t Qjunk A (* € Qrej V flj € 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') + (Ae'- 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 MM-QFAs with bounded error is closed under boolean operations, and since MM-QFAs 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 MM-QFAs 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 computa-tion 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 measure-many 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 col-lapsing 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 RMO 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 measure-once 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. Conclusions and Future Work 51 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 un-bounded 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 O p e n P r o b l e m s 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. An 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 for Computing Machinery, 29(3):741-765, July 1982. [ANV98] Andris Ambainis, Ashwin Nayak, and Umesh Vazirani. On the space-efficiency of 1-way quantum finite automata. Preprint, To be submitted to Information Pro-cessing Letters, (quant-ph/9804043), 1998. [Ben73] Charles Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17:198-200, November 1973. [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 on Theory of Computing and Systems, 1997. [BV97] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SI AM Journal of Computing, pages 1411-1473, October 1997. [Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quan-tum computer. Proceedings of the Royal Society of London, A400:97-117, 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 prob-abilisitic finite-state automata. SIAM Journal of Computing, pages 1474-1483, December 1990. 52 Bibliography 53 [Eil76] S. Eilenberg. Automata, Languages and Machines, volume B. Academic Press, New York, 1976. [Fre81] Rusins Freivalds. Probabilistic two-way machines. In Proceedings of 10th Inter-national Symposium on Mathematical Foundations of Computer Science, volume 118 of Lecture Notes on Computer Science, pages 33-45, September 1981. [Gas96] Stephen Gasiorowiz. Quantum Physics. John Wiley and Sons, Inc., New York, 1996. [GKP94] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley Publishing Company, New York, New York, 1994. [Gos92] Amit Goswami. Quantum Mechanics. Wm. C. Brown Publishers, New York, 1992. [Gro96] Lov Grover. A fast quantum mechanical algorithm for database search. In Pro-ceedings 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, Lan-guages 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. Reversible space equals deterministic space. In Proceedings of the 12th IEEE 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. Academic Press, New York, New York, 1971. [Per94] Dominique Perrin. Finite automata. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 1. Elsvier Science Publisher, 1994. Bibliography 54 [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 of Research and Development, 3:198-200, April 1959. [Sho94] 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):1484-1509, 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. In Proceedings of the 30th Annual Symposium on Foundations of Computer 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 Paradox. Cambridge University Press, New York, New York, 1985. [Yao93] Andrew Chi-Chi Yao. Quantum circuit complexity. In Proceedings of the 3\\ih Annual Symposium on Foundations of Computer Science, pages 352-361, 1993. "@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "1999-05"@en ; edm:isShownAt "10.14288/1.0051605"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms: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."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Models and characterizations of 1-way quantum finite automata"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/8895"@en .