Interference Automata M. V. Panduranga Rao⋆ Department of ComputerScience and Automation Indian Instituteof Science Bangalore 560 012 India [email protected] 7 0 0 Abstract. Weproposeacomputingmodel,theTwo-WayOpticalInterferenceAutomata 2 (2OIA),thatmakesuseofthephenomenonofopticalinterference.Weintroducethismodel n toinvestigatetheincrease in power,in termsof language recognition, ofaclassical Deter- a ministic Finite Automaton (DFA) when endowed with the facility of optical interference. J The question is in the spirit of Two-Way Finite Automata With Quantum and Classical 2 States(2QCFA)[A.AmbainisandJ.Watrous,Two-wayFiniteAutomataWithQuantum 2 and Classical States,Theoretical ComputerScience,287 (1),299-311, (2002)] wherein the classicalDFAisaugmentedwithaquantumcomponentofconstantsize.Wetestthepower ] C of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA al- C gorithms to recognize languages for which 2QCFA machines have been shown to exist, as wellaslanguageswhosestatusvis-a-vis2QCFAhasbeenposedasopenquestions.Finally . s we show the existence of a language that cannot be recognized by a 2OIA but can be c recognized by an O(n3) space Turing machine. [ 1 v Wepresentamodelofautomata,theTwo-WayOpticalInterference Automata (OIA), 8 2 that uses the phenomenon of interference to recognize languages. 1 We augment the classical 2DFA with an array of sources of monochromatic light and 1 a detector. The guiding principle behind the design of the 2OIA model is to deny it any 0 7 resource other than a finite control and the ability to create interference. Our interest 0 lies essentially in wave interference; for concreteness and ease of exposition we choose / s light. c ∗ : Specifically, weaddressthefollowing question:given alanguage L a,b ,aninput v ∗ ⊆ { } w a,b , and a 2DFA augmented with w “sources of interference”, is it possible to i X ∈ { } | | decide efficiently if w L by examining their interference patterns? While this question r is interesting in its ow∈n right, the model abstracts out the phenomenon of interference a fromquantumautomatamodels[MC00,KW97,BP02,AK03,ANTSV02,AF98]inthemost general sense. A typical example of an automata model having a restricted quantum component is the 2-way Finite Automata model with Quantum and Classical states (2QCFA) of Ambainis and Watrous [AW02], which is essentially a classical 2DFA that reads input off a read-only tape and is augmented with a quantum component of constant size: the number of dimensions of the associated Hilbert space does not depend on the input length. Unitary operations on the quantum component, which are performed interleaved ⋆ Apreliminary versionofthispaperappearsintheproceedingsofthe16th Australasian Workshopon Combinatorial Algorithms (AWOCA 2005). with classical transitions, evolve the quantum state vector, producing interference in probability amplitudes of the vector. The classical component takes the result of mea- surement operations on the quantum state vector into account while deciding member- ship of a given input string. Ambainis and Watrous [AW02] showed 2QCFA that accept L = anbn n N in polynomial time and palindromes (L = wwR w a,b ∗ eq pal { | ∈ } { | ∈ { } where wR is w reversed ) in exponential time with bounded error. } The interference produced by the sources in our model is the analogue of unitary operations on the quantum part and detection of light by the detector is the analogue of the measurement operation. Wave amplitude serves as a parallel to the complex prob- ability amplitudes and wave phase serves as a parallel to the relative phase among the probability amplitudes. Thispaperisorganizedasfollows. Thenextsection gives abriefintroductiontosome principles of optics pertinent to our model. In section 3 we define the model. Section 4 presents interference automata for recognizing the following languages: ∗ 1. L = w aw w ,w a,b , w = w . centre 1 2 1 2 1 2 { | ∈{ } | | | |} 2. L = anbn n N . eq 3. L ={ wwR| w∈ }a,b ∗ where wR is w reversed . pal { | ∈∗ { } } 4. L = w (,) parentheses in w are balanced . bal 5. L = {anb∈n2{ n} N| . } sq 6. L ={ anb2n| n∈ N} . pow { | ∈ } Section 5 shows the existence of a language that no interference automata can recognize, but that can be recognized by an O(n3) space Turing machine. The final section closes with a discussion and some open problems. 1 A Brief Introduction to the Physics of Light We now briefly discuss the mathematical formalism for interference of monochromatic lightofwavelengthλ.Forexcellentexpositionsonthephenomenonofopticalinterference see [BW99] and [FLS70]. Theequation of a light wave at a point pin space can bedescribed as R = Aei(ωt+φ), where A is the amplitude, ω the angular frequency, and φ the phase associated with the wave atthat point.TheamplitudeAat pis A /r,wherer is its distancefrom thesource 0 and A the initial amplitude at r = 0. The intensity of the wave is the average energy 0 arriving per unit time per unit area. At any given point, it is proportional to the square of the amplitude of the wave. If two (or more) waves exist at the same point in space, they interfere with each other and give rise to a new resultant wave. Suppose the waves have the same angular frequency and are described by R = 1 A ei(ωt+φ1) and R = A ei(ωt+φ2). Then, the resultant is given by R = R + R = 1 2 2 1 2 A eiωteiφ1 + A eiωteφ2. The amplitude of the resultant wave is the length of R. Since 1 2 R is a complex number, the amplitude is √RR¯. Thus, the intensity associated with the wave is proportional to A2+A2+2A A cos(φ φ ). 1 2 1 2 2− 1 If two interfering waves have equal amplitude and a phase difference φ φ = π, 2 1 − the resultant intensity at that point is zero. A light detector placed at that point fails to detect any light. To use this formalism for calculating the intensity at a point, only the difference φ φ is necessary. This phase difference might arise because of (a) the 2 1 − intrinsic phase difference at their source, or (b) the difference ∆ between the distances traveled by each before reaching that point. Hence, φ φ = α+ 2π∆ where the first 2 − 1 λ term is the difference in the intrinsic phases and the second is the difference between the distances in terms of phase. In general, if n monochromatic waves R = A eiωt+φi n interfere at a point, the resultant wave is described by the vector{sumi R =i n }Ai=e1iωt+φi. A useful point to i=1 i note is that if the sources are simply different pointsPon the same wavefront, they have zero intrinsic phase difference. Moreover, the phase of a wave can be shifted as required. 2 The Model Informally, the interference automaton proposed in this work consists of a finite control, an optical arrangement and a read-only tape which contains the input w demarcated by end-markers and $ in w +2 cells. The optical arrangement consists of a linear array of ¢ | | w +2 monochromatic light sources, each source corresponding to a tape cell, capable of | | emitting light with an initial relative phase of 0 or π. These sources can only be toggled. The distance between any two consecutive sources is the same, a constant independent of the size of the input. Wehaveadetectorwhosemovementisdictatedbythefinitecontrol.Sincethecontrol is finite, the movement of the detector has to be discretized. The easiest way to do this is to imagine that the detector moves along the lines of a grid placed before the array of sources as shown in figure 3.1. The detector “points” in the direction of the source array, parallel to the vertical grid-lines. It has a field of vision, which makes an angle θ with the vertical gridline passing through it. We use θ = π/4. We associate a coordinate system with the grid by defining horizontal and vertical lines at every half integer point on the horizontal and vertical axes. Therefore the vertical gridlines are at x= 0,1/2,1,3/2,...,n+1 and the horizontal grid-lines are at y = 0,1/2,1,3/2,...,n+1. The light sources are placed at (0,0),(1,0),...,(n + 1,0). While the sources at (0,0) and (n + 1,0) correspond to the end markers and $ respectively, those at (1,0),...,(n,0) correspond to w ,...,w 1 n ¢ respectively, where w = w w ...w is the input. 1 2 n Thus, the position of the tape head is referred to by its x-coordinate. The location of the detector is given by (i,j) with i,j 0,1/2,1,3/2,...,n+1 . We now define the ∈ { } model formally. Definition 1. A 2-way Optical Interference Automaton (2OIA) is defined by a 7-tuple (Q,Σ,Q ,Q ,q ,Σ ,δ) where acc rej 0 I – Q is a finite set of states. – Σ is a finite alphabet. – Γ = Σ , $ is the tape alphabet. { ¢ } – Qacc,QSrej Q are sets of accepting states and rejecting states respectively. ⊆ – q is a special state designated as the start state. 0 Detector π/4 c a b a a b b $ Finite A utomaton Fig.1. The arrangement. Also illustrates the algorithm for recognizing L . The centre source at $ comes into the field of vision at the position where the detector is shown. – Σ = 0,1 is the output alphabet of the detector. I { } – The Instantaneous Description of a 2OIA is given by the tuple (q,i,(j,k),S), where q Q, i 0,...n + 1 is the position of the head on the tape, (j,k), j,k ∈ ∈ { } ∈ 0,1/2,1,3/2,...,n + 1 gives the position of the detector, and S is a vector of { } length n+2 with entries from 0,π, , signifying if a source corresponding to a tape { ×} cell is switched on with phase 0 or π, or switched off, respectively. δ is a transition function– δ : Q Γ Σ Q D D (toggle(φ) ) I t d × × → × × × ∪− where D = left, right, stationary , D = left, right, up, down, stationary and t d { } { } switch on the current source with phase φ if the source is off toggle(φ) = (cid:26) switch the current source off if the source is already on where φ 0,π and “–” indicates that no action is to be taken on the current source. ∈ { } By current source we mean the source associated with the tape cell currently being scanned by the head. ′ If δ(q,σ,σ ) = (q ,d ,(d ,d ),p) then we denote the change in the instantaneous I h l u ′ ′ ′ ′ ′ ′ description during this one step as (q,i,(j,k),S) (q ,i,(j ,k ),S ) where i = i+d , h ′ ′ ⊢ j = j +d , k = k+d and l u ′ S [m]=S[m] for m = i 6 =toggle(p) for m = i, if p 0,π ∈ { } =S[m] for m = i if p = . − Foranygivensource, a maximalsequenceoftogglesisasequenceoversuccessivetime steps (ti,ti+1,...,tj) such that either (a) the source is not toggled at ti−1 and tj+1 or, (b) t =t or t = t where t and t are the time steps at which computation starts i 0 j T 0 T and ends, respectively. A maximal toggle sequence is called transient if its length is evenand non-transient if its length isodd. We place the restriction that non-transient sequences be allowed at most a constant number k number of times: on attempting a non-transient sequence of toggles a k+1th time, the machine crashes. The detector has an output alphabet through which it can indicate whether it has detected any light. It responds with a 1 if it has, and with a 0 if it has not. Depending on the current state q, the symbol σ Γ currently being scanned, and ∈ ′ the output of the detector, δ changes the state of the finite control to q and moves the tape head by d D and the detector by d D . t t d d ∈ ∈ Theprimaryuseofthesourcesistoproduceopticalinterferenceatthegrid.However, unrestrictedtogglingwouldenabletheiruseasmemoryelements:thedetectorwhenclose to the array, could “read” an individual source while the finite control could “write” to it by toggling it. In order to avoid this, we place restrictions on moves that involve toggle operations. A source that is toggled twice in quick succession cannot be used as a memoryelement, asitisrestoredtoitsoriginal(switchedonoroff)stateintheverynext ′ ′ ′ ′ time step. Therefore, transient toggling of the kind (q,i,(j,k),S) (q ,i,(j ,k ),S ) ′ ′ ′′ ′′ ⊢ ⊢ (q ,i,(j ,k ),S) are permitted any number of times. Non-transient toggles which allow changing the state of a source for an extended period of time can potentially be used as memory operations. Hence, we restrict number such sequences to at most a constant for any source. In all interference automata that we will discuss henceforth, we use at most two such non-transient sequences per source duringtheentire courseof computation. Figure3.2 showstheexampleprofilesof allowed and disallowed sequences of toggle operations on a given source. The sum of the number of moves made by the head and the detector serves as a measure of the time taken by a 2OIA machine. Thefollowingfactsandconventionswillbecommontoall2OIAmachinesthatfollow. – Initially, all the sources are switched off. – Q = q and Q = q will be the accepting and rejecting subsets. The acc acc rej rej { } { } machines accept by final state and 0 detector output. – Thetransition functionis specifiedasatable, therowsof whichareindexedbyq Q ∈ and columns by (σ,I), with σ Γ and I Σ . The table entries are tuples of the I ′ ′ ∈ ∈ form (q ,t;d,φ) with q Q, t D = L, ,R , d , , , , , , , , t ∈ ∈ { − } ∈ {← → ↑ ↓ ր տ ց ւ −} and φ 0, ,π . In any field of a tuple, “ ” stands for a “no change” in its ∈ { − } − value. Although D and D imply movement by only one unit(tape cell and grid-line t d respectively), movement by two units can be carried out by the finite control. ′ An element indexed by row q and column (a,1), say, (q ,R; ,0) is to be interpreted ր as follows. If the machine is in state q and the head is reading an a, and the detector outputs 1, then the source corresponding to the current cell is switched on with a phase0,tapeheadmoves righttothenexttapecell, thedetector moves firstupwards ′ andthentotherightbytwogridlines,andthemachineentersstateq .Insomeplaces 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (a) Disallowed Sequence 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (b) Allowed Sequence Fig.2. Example toggle profiles of a source during the course of computation. we show both movements in the same entry for the sake of brevity, but the two are not atomic. If the detector output changes after moving up but before moving to the right, the configuration changes as dictated by the transition function. 3 Language recognition In this section we show recognition schemes for the languages mentioned in Section 1. In all cases we show the existence of a locus of points on the grid where the intensity of light will be zero if and only if the input word is in the language. The idea behind all algorithms on this model is to move the detector to the locus. We begin with a simple but important example. 3.1 Recognizing the centre of an input string ∗ A word in L = w aw w ,w a,b , w = w will be of odd length (say centre 1 2 1 2 1 2 { | ∈ { } | | | |} 2n+1). This can be easily verified with a DFA. We accept the string, if the (n+1)th element is a. Theorem 1. There exists a 2OIA machine that recognizes L in time linear in size centre of the input string. Proof. As proof, we describe such a machine. Consider a 2OIA M having a set of centre states Q = q ,q ,q ,q ,q and a transition function as specified by the following 0 1 2 rej acc { } table. ,0 ,1 a,0 a,1 ¢ ¢ q (q ,R; ,0) φ φ (q ,R; , ) 0 0 0 − − − q φ (q , ; , ) φ (q ,L; , ) 1 2 1 − − − − − q φ (q ,R; , ) (q , ; , ) (q ,R; , ) 2 2 acc 2 ր − − − − ր − b, 0 b,1 $, 0 $, 1 q φ (q ,R; , ) φ (q ,L; ,π) 0 0 1 − − − q φ (q ,L; , ) φ φ 1 1 − − q (q , ; , ) (q ,R; , ) φ φ 2 rej 2 − − − ր − The machine starts with the detector initially in position (0,1) and the tape head at 0, reading . While in state q , the sources at and $ are switched on with phase 0 0 ¢ ¢ and π respectively in one rightward scan of the input after which the head returns to the beginning of the input. To begin with, the source corresponding to $ is out of the detector’s field of vision. However, the intensity at the detector due to the source at is non-zero. The detector ¢ thenmovesupwardsandtotherightinsuchawaythatatalltimesduringthemovement, it can detect light from the source at . The head also moves to the right in tandem with ¢ the detector. When the detector reaches a certain x-coordinate, the source at $ falls into the detector’s field of vision and the resultant intensity falls to zero. We claim that this coordinate is the geometric centre of the input. Lemma 1. The detector will record zero intensity if and only if its x-coordinate is n+1. Proof. The resultant wave at the detector is A A ψ = 0 eiφ1 + 0 eiφ2 i2+j2 (2n+2 i)2+j2 − p p for j 1. Given that φ = φ +π, the detector reads zero resultant intensity if and only 2 1 ≥ if its x-coordinate is n+1. (cid:3) Therefore at this moment, if the head reads an a, the machine accepts; otherwise it rejects. It is easy to see that the automaton takes O(n) time to decide the language. Using the ideas behind the 2OIA algorithm for L , we can recognize a related lan- centre guage, namely L = anbn n N . This language can be recognized with bounded eq { | ∈ } error on 2QCFA [AW02]. Corollary 1. The above algorithm can be used to recognize L in linear time. eq ∗ ∗ Proof. The DFA first verifies that the input is indeed of the form a b and that the input is indeed of even length. Next, the centre is detected using the above algorithm. The input is of even length and therefore, the detector has to be initially positioned at (1/2,1). TheDFA then checks if the current symbol beingread is a and that to the right is b. If it is not, reject the input, else accept. This too takes time linear in the input size. 3.2 Palindromes In this section we give a 2OIA machine that recognizes the language L = wwR w pal a,b ∗ where wR stands for w reversed . We use light of wavelength rπ wh{ere r is| an∈y { } } algebraic number greater than zero. This restriction on the wavelength yields algorithms that are more elegant and faster, and brings out the main features of the model better. Later in the section we give a machine that recognizes L without this restriction. pal Theorem 2. There exists a 2OIA machine that decides L in time linear in the input pal size. Proof. We describe a 2OIA M that decides L . The automaton M has the state pal pal pal ′ ′ set q ...q ,q ...q ,q ,q and its transition function is as shown in the following { 0 10 3 10 acc rej} table. ,0 ,1 a,0 a,1 ¢ ¢ q (q ,R; ,0) φ φ (q ,R; , ) 0 0 0 − − − q φ (q , ; , ) φ (q ,L; , ) 1 2 1 − − − − − q φ (q ,R; , ) (q ,R; ,0) (q ,R; , ) 2 2 3 2 ր − − ր − q φ φ φ (q ,L; , ) 3 4 − − q φ φ (q ,L; , ) (q , ; , ) 4 5 4 ↑ − − ↓ − q φ (q ,R; , ) φ (q ,L; , ) 5 6 5 − − − − q φ φ (q ,R; , ) (q ,R; ,0) 6 7 6 − − − q φ φ (q ,R; ,π) φ 7 7 − q φ φ φ φ 8 q φ φ φ φ 9 q φ φ φ φ 10 ′ q φ φ φ (q , ; , ) 3′ rej − − − q φ φ φ φ 4 ′ ′ ′ q φ (q ,R; , ) φ (q ,L; , ) 5′ 6 − − ′5 − − q φ φ φ (q ,R; , ) 6′ ′ 6 − − q φ φ (q ,R; , ) φ 7′ 7 − − q φ φ φ φ 8 ′ q φ φ φ φ 9 ′ q φ φ φ φ 10 b, 0 b,1 $, 0 $, 1 q φ (q ,R; ,0) φ (q ,L; ,π) 0 0 1 − − q φ (q ,L; , ) φ φ 1 1 ′ − − q (q ,R; ,0) (q ,R; , ) φ φ 2 3 − 2 ր − q φ (q , ; , ) φ φ 3 rej − − − q φ φ φ φ 4 q φ (q ,L; , ) φ φ 5 5 − − q φ (q ,R; , ) φ φ 6 6 − − q (q ,R; , ) φ (q , ; , ) φ 7 7 8 − − − − − q φ φ (q , ; ,π) φ 8 9 − ↑ q φ φ (q , ; ,π) (q , ; ,π) 9 8 10 − − − − q φ φ (q , ; , ) (q , ; , ) 10 acc rej ′ ′ − − − − − − q φ (q ,L; , ) φ φ 3′ ′ 4′ − − q (q ,L; , ) (q , ; , ) φ φ 4′ 5 ↑ − ′4 − ↓ − q φ (q ,L; , ) φ φ 5′ ′ 5′ − − q (q ,R; , ) (q ,R; ,0) φ φ 6′ 7′ − − 6 − ′ q (q ,R; ,π) φ (q , ; , ) φ 7′ 7 − 8′ − − − q φ φ (q , ; ,π) φ 8′ ′9 − ↑ ′ q φ φ (q , ; ,π) (q , ; ,π) ′9 8 − − 10 − − q φ φ (q , ; ,π) (q , ; , ) 10 acc − − rej − − − The automaton, in states q ,q and q , finds the centre as in the previous section. 0 1 2 Since the input is of even length, say 2n, at this stage the head reads the nth input symbol w = σ a,b and the detector is on the grid-line x= n+1/2. The case of w n n ∈ { } ′ ′ beinga is handled by states q ...q ,while w being b is handledby thestates q ...q . 3 10 n 3 10 By the arrangement of the sources and the fact that Σ = a,b , it is sufficient to show { } symmetry of any one σ Σ about the centre of the input string. We show the proof for ∈ the case when w = a. The argument for the other case is symmetric. n If w = w , the input is rejected at the outset (see rows indexed by q and q ). n n+1 2 3 6 Else, switch on the source corresponding to w and bring the detector to (n+1/2,1/2) n so that only the sources corresponding to w and w lie in the field of vision of the n n+1 detector (row q ). This is done by using the fact that as the detector moves down along 4 the grid-line x = n+1/2, the detector falls to 0 when the source corresponding to w n moves out of its field of vision, that is, at y = 1/2. Then, the head starts from w , switching on all sources corresponding to a and with 1 phase 0 until it reaches w (rows q and q ). We can deduce when the head has reached n 5 6 thecentrebecausewhenthesourceatw istoggled,thedetectorrecordszerointensity. n+1 As the head moves further to the right, all sources from w to w that correspond n+1 2n to a are switched on with relative phase π (row q ). 7 Now that all the sources corresponding to a have been switched on appropriately, we move the detector away from the x-axis along the grid-line x = n+1, bringing two sources (one from each side of the centre) into its field of vision at each step. Let us now note a useful lemma. Lemma 2. Suppose sources to the left of x= n+1/2 are switched on with phase 0 and those to the right with phase π. Then, the resultant intensity at x = n+1/2 is zero if and only if either (1) for every jth source to the left of x = n+1/2 switched on, the jth source to the right of x= n+1/2 is also switched on and vice versa or (2) both sources are off. Therefore, as the detector is moved away, if theintensity is non-zero at any step i,we know that the input is not a palindrome, and reject it. Otherwise, we stop when and $ ¢ fall into the field of vision of the detector and accept. We can detect when this happens by periodically toggling the source corresponding to . This is done in states q to q . 8 10 $ All we need now is a proof of the above lemma. Proof. (of lemma) The jth source from the centre on either side may or may not be switchedon,dependingontheinput.Letthebooleanvariablesa andb indicatewhether j j the jth source is switched on to the left and right of x= n+1/2 respectively. Thus, the resultant wave at x = n+1/2 is (a b )r eiφ1 +(a b )r eiφ2 +...+(a b )r eiφn 1 1 1 2 2 2 n n n − − − where φ = j√2πd/λ for 1 j n, and d distance between two consecutive vertical (or j ≤ ≤ horizontal) grid-lines. Therefore, we have to prove that the resultant is zero if and only if a = b , for j j 1 j n. One direction is trivial. For the other direction, we use the following theorem ≤ ≤ of Lindemann (see [Niv56]). Theorem 3. Givenanydistinctalgebraicnumbersφ ,φ ,...,φ ,thevalueseφ1,eφ2,...,eφn 1 2 n are linearly independent over the field of algebraic numbers. Since we have chosen λ = rπ for some algebraic number r, we have φ = j√2d/r for j 1 j n. Therefore, the resultant can be zero if and only if a = b , 1 j n. j j ≤ ≤ ≤ ≤ TherunningtimeofthealgorithmisO(n)astheheadscanstheinputonlyaconstant number of times and the detector movement is also O(n). Interestingly,L canberecognizedbya2OIAwithoutrestrictiononthewavelength. pal However, this comes at the cost of increased time complexity. Theorem 4. There exists a 2OIA machine that recognizes L in O(n2) time. pal Proof. Without loss of generality let w and w be a. If the centre is x= x , then for n n+1 c every a to the left of x = x we try to find the corresponding a at the same distance c ′ to the right, and vice versa. For the sake of brevity, we describe a 2OIA machine M pal that checks only one way: if for every a to the left of the centre, there exists an a to the right. In doing so, sources corresponding to a’s of only the first half of the input string will be toggled twice in a non-transient manner. Therefore, when the extended 2OIA for L checks for the existence of an a to the left of x corresponding to every a to the pal c right, the sources in the second half of the input can be toggled non-transiently. The set of states and the transition matrix for the complete case will involve a simple and ′ symmetric extension of M . pal ′ ′ ′ Consider the 2OIA M with states q ...q ,q ...q ,q ,q and transition func- pal { 0 7 3 7 acc rej} tion as shown in the following table. The detector is initially at (1/2,1/2). ,0 ,1 a,0 a,1 ¢ ¢ q (q ,R; ,0) φ φ (q ,R; , ) 0 0 0 − − − q φ (q , ; , ) φ (q ,L; , ) 1 2 1 − − − − −