I Introduction and motivation
Quantum computing combines quantum physics, computer science, and mathematics by studying computational models based on quantum physics. Quantum computing is based on the quantum phenomena of entanglement and superposition to perform operations on quantum computers (which is substantially different from classical computers) 1. It may allow us to perform computational tasks which are neither possible nor efficient. In 1994, Shor 2 designed a quantum algorithm for calculating the factor of a large number with space complexity and runs in on a quantum computer, and then perform post processing time on a classical computer, which could be applied for cracking the RSA algorithm at Bell Laboratories (US). In 1996, Grover 3 designed an algorithm for searching an element in an unsorted database set of size n in operations approximately.
Soon after the design of Shor’s algorithm, interest in quantum computation and information has been increased significantly. A number of different models, their language recognition capability and properties have been introduced 6. Till now, quantum versions for various classical automata’s has been introduced such as quantum Turing machine (QTM) 8 of Turing machine; quantum finite automata (Moore and Crutchfield 4; Kondacs and Watrous 5) of deterministic finite automata; quantum pushdown automata (Moore and Crutchfield 4; Golovkins 9; Gudder 10; Qiu 11) of pushdown automata, quantum realtime onecounter automaton (rtQ1CA) Say et al. 28 of classical realtime onecounter automaton (rt1CA) and many more since last two decades. Some of these constructions are more powerful than their classical counterparts 32.
In 1936, the same fruitful year Turing introduced the Turing machine, Post 12; 13; 15 proposed the concept of Post machine (PM), which is equivalent to Turing machine model in computation. Later on, Manna 14 followed the approach of Post and defined a automaton equipped with data structure queue called Post machine. Till now, it has been extensively studied from several perspectives. Vollmar 16 investigated the automaton employed with buffer storage, which is basically queue automaton and proved that it can be designed for recursive enumerable languages. In 1980, Brandenburg 24 considered queue automaton (called post machine) and investigated its features. It has also characterized the class of languages recognized by multireset machines and equality sets. The computation power of queue automata by putting restriction on time has been investigated on several occasions. Cherubini et al. 29 considered the queue automaton which works in quasi realtime i.e. limit the number of transitions by a constant and proved that emptiness problem is undecidable. In 2013, Jakobi et al. 30 introduced queue automaton of constant length and studied its descriptional complexity. Recently, Kutrib et al. 25; 26 introduced the concept of reversible queue automata. It has been shown that the class of languages recognized by reversible queue automata strictly consists regular languages. It has been investigated that the computational power of reversible queue automata and Turing machines is an equivalent. Further, the working of reversible queue automata in quasi realtime has been shown. Moreover, the language recognition power of reversible queue automata is compared with reversible pushdown automata and inputdriven queue automata and examined their closure properties.
Scegulnaja 31 introduced the concept of realtime quantum Turing machine and proved that a language can be recognized by realtime quantum Turing machine with single worktape, but cannot be recognized by realtime deterministic Turing machine with single worktape. In this paper, we have introduced a notion of quantum queue automata. Further, we have shown that a language which cannot be recognized by any realtime deterministic queue automata can be recognized by quantum queue automata in realtime. Moreover, we have proved that realtime quantum queue automata is more powerful than realtime nondeterministic queue automata in language recognition. The organization of the paper is as follows: In section 2, some preliminaries and definitions are given. Further, we have introduced the concept of quantum queue automata with its wellformedness conditions in Section 3. Furthermore, the power of realtime quantum queue automata over classical counterparts is shown in Section 4, followed by a conclusion in Section 5.
i.1 Motivation

It is known that deterministic finite automata equipped with queue can perform universal computations. In fact, it has been proved several times that the computational power of deterministic queue automata and Turing machine is equivalent.

QTM is more efficient than classical Turing machine from a computational complexity point of view. For example, integer factorization and discrete logarithm problems are intractable on classical Turing machine, but they are tractable on QTM 17. Moreover, realtime QTM is more powerful than realtime DTM 31.

Motivated by the efficiency of QTM and classical queue automata, we investigate a quantum version of classical queue automata and its superiority over classical counterparts in realtime.
Ii Preliminaries and definitions
In this section, we review some formal definitions. Throughout the paper, we have used the following notations: the prefix “R”, “D”, “ND”, “Q” and “rt” signify reversible, deterministic, nondeterministic, quantum and realtime respectively. An input alphabet does not contains left and rightend markers (#, $), empty queue symbol is not an element of queue alphabet . The length of input string x is denoted by . We assume that the reader is familiar with the notation of quantum computation; otherwise, reader can refer to 6; 34 for quantum models.
Definition 1.
A deterministic queue automaton (DQA) is defined as a septuple , where

Q is a set of states,

is an input alphabet,

is a finite set of queue symbols,

is a starting state,

is an empty queue symbol ,

The transition function is defined by , where signifies empty symbol. It must never be used as an input symbol.

is a set of accepting states ().
In DQA, it is possible to enqueue the symbol at the rear of queue and dequeue (remove) or keep the symbol at the front of the queue. In order to process the input string x by , we assume that x is written on input tape employed with a queue. A computation process of is a sequence of configurations , where is an initial configuration. The configuration of is defined as a quadruple , where denotes the already read part of input string, is the present state, is unread part of x and s indicates the content of queue, where leftmost symbol is at the front of queue. Suppose the configuration of is , where is in state and R/W head is under the symbol and are the symbols at the front and read of the queue respectively, where and . Thus, after reading the symbol , the resultant configuration is as . Thus, the above configuration is transformed into if the transition function is . Similarly, in order to remove the symbol from head and put the other symbol at rear, then the resultant configuration will be if transition function is . In case, the queue is empty at initial stage, then the resultant configuration is computed by with empty queue symbol such as . Fig 1 shows the pictorial representation of above configurations of a DQA.
The definition of reversible DQA (RDQA) is same as above DQA. The only difference lies in the transitions i.e. any configuration of RDQA must have one configuration which can be computed by DQA. It has also to be deterministic backward and the symbols are enqueued at the front and dequeued from rear of the queue. Any automaton is said to be realtime if it complete its computation in realtime i.e the running time of automaton on any input string is less than equal to . But, the notion realtime depends upon the model of automata studied. Kutrib et al. 25 studied the restricted versions of DQA by putting restriction on time. A RDQA is said to be realtime DQA (rtRDQA) if there are no steps in computation. It is said to be quasi realtime if there is a constant number of steps applicable for all computations.
Iii Quantum queue automata
Quantum queue automata (QQA) is constructed similarly as quantum pushdown automata (QPDA). QQA employs a data structure queue referred to as FirstIn, FirstOut (FIFO), whereas QPDA employs stack which referred to as LastIn, FirstOut (LIFO) 11. QQA consists input tape, queue and finite state control. QQA can be defined as a modification of classical queue automata by adding weighted superposition to the configurations of classical queue automata in such a way that processing of input string corresponds a unitary transformation. QQA choose a transition by considering current state and the symbols at the front and end of the queue.
Definition 2.
A quantum queue automaton is defined as septuple , where

is a set of states. Moreover, , where represent the set of accepting, rejecting and nonhalting states respectively.

is an input alphabet,

is a queue alphabet such that , where endmarkers {#,$} are not included in . For convenience, we have used such that represents an empty word and is the empty queue symbol such that (),

Transition function is defined by , where represent the head function for the left, stationary and right direction of R/W head, where represent the dequeue and enqueue operations respectively. In following conditions, we have used , where signifies first and last symbol of queue respectively Transition function must satisfy the following conditions:

Local probability condition:
(1) 
Orthogonality condition:
(2) 
Separability condition I:

(3) 
(4)


Separability condition II:
(5) 
Separability condition III:

(6) 
(7) 
(8)


To process the input string by , we assume that input string x is written on input tape enclosed with both endmarkers such as #x$. It processes the input tape employed with queue which is potentially infinite on the rightside. The automaton is in the state q, R/W head is above the symbol . Then, with the amplitude , where , are the symbols at the front and end of queue respectively. It moves to state , moves the R/W head one cell towards left, stationary and in right direction, and puts the symbol at the end of the queue. The automaton for processing an input x corresponds a unitary evolution in the innerproduct space . Definition 1 utilizes the concept of deterministic queue automata 14; 25 and quantum pushdown automata 9; 11.
A computation of QQA is a sequence of superpositions where is an initial configuration. When the automaton is observed in a superposition state, for any , it has the form , where C defines the set of configurations, and the configuration is measured with the probability 5. Superposition is valid; if the sum of the absolute squares of their amplitudes is unitary.
Time evolution of quantum systems is given by unitary transformations. Suppose if the system is in , then at a later time it will be , where
is unitary time evolution operator. If is any linear transformation, then it will be unitary transformation if
or , where is a conjugate transpose of U. Therefore, evolution operator specifies how QQA will progress the input string. Each transition function induces a linear time evolution operator over the space . Let . For any configuration , the evolution of a QQA is given by the linear operator such that(9) 
where and
(10) 
When R/W head is stationary in equation (10), then the resultant state is reading the same symbol on input tape and enqueue the symbol at the end of queue. The resultant state reads the next symbol on moving the R/W head towards right. Further, the resultant state reads the on moving towards the left direction and puts the symbol at the rear of the queue.
Theorem 1.
Wellformedness conditions 1.1 are satisfied iff the time evolution operator is unitary.
Proof.
For each input x,
is unitary iff the vectors
for of the QQA evolution matrix are orthonormal. Condition (a) i.e. local probability condition is satisfied to the statement that for each configuration Correspondingly, the column vectors of the QQA evolution matrix are orthogonal iff Condition (b) i.e. orthogonality condition is satisfied such that , where for . Separability conditions (c, d, e) are satisfied in equivalent to the above statement. Separability condition d is satisfied such that , in which states and are reading the different symbols and resultant state is same, where , where R/W head moves right and remains stationary for respectively according to the condition. Thus, the columns of the evolution matrix are orthogonal for each input x iff conditions (b, c, d, e) are satisfied. We can say that, if is a unitary operator, transition function satisfies the wellformedness conditions 1.1.It is not an easy task to check all the wellformedness conditions for trivial QQA (i.e. there is no other state that it can exist in). Consider a QQA, whose evolution matrix columns are orthonormal for each configuration, but the evolution is not unitary. and transition function is defined as: . The other values of the transitions . Therefore, we have defined simple notation of QQA similar as 2QFA and QPA, by which wellformed machines can be more easily specified. The method is to decompose the transition function into transforming of states with queue automata operations (enqueue, dequeue) and other head functions. ∎
Definition 3.
A QQA is simplified, for each , if there exists a function on the inner product space such that where Q is the set of states, . Define transition function as
(11) 
where a state q results in to on reading , dequeue a symbol from head and puts the at end of the queue.
Theorem 2.
A simple QQA satisfies the wellformedness conditions 1.1 if there exists a transition function for any , on the inner product space and such that
(12) 
Proof.
Firstly rewrite the wellformedness conditions:
(13) 
We can see that is wellformed iff the above condition is satisfied, for every and . The local probability condition (a) is satisfied iff the columns of every transition are normalized (i.e. length 1) for each enqueue and dequeue operation. Similarly, the columns vectors of transition are orthogonal iff the orthogonality condition (b) and separability conditions (c, d, e) are satisfied. Equivalently, is wellformed when every transition is unitary for and . ∎
The definition of a realtime quantum queue automaton (rtQQA) is same as QQA. The only difference lies in the movement of R/W head. It is only allowed to move towards the right direction Thus, every step rtQQA reads a new symbol. On reading the rightend marker $, the computation is finished. The input string is said to be recognized by rtQQA if the R/W reads the rightend marker $ and queue is empty. Thus, rtQQA accepts the language L, if it takes time not more than for every word .
iii.1 Language recognition
We assume that QQA has to be observed to produce information about its processing. Consider an observable O for finitedimensional Hilbert space , which is decomposed into subspaces such as refers to the subspace of ‘accept’, ‘reject’ and ‘nonhalting’ respectively. Each of these subspaces are traversed by configurations such that and , where .
We assume that input string is written on input tape with both endmarkers such that #x$. It is equipped with a queue (i.e. initially empty). The processing of input string starts with an initial state and R/W points towards the first symbol on input tape. The transition depends upon the symbol under R/W head and the symbols at the front and end of the queue respectively. Firstly, the evolution operator is applied to the current state and computes several paths simultaneously (quantum parallelism); however, as a result of measurement, it is possible to get the results of only one computation path. In meanwhile, each path performs an enqueue or dequeue operations on queue and moves the R/W head corresponding to the resultant state. Then the result is observed by an observable O. Suppose if the automaton is in a superposition state , where are amplitudes and , then the superposition is projected into abovementioned subspaces . The result is observed randomly, and each result j is realized with probability . The result of each observation will be either ‘accept’ or ‘reject’ or ‘nonhalting’. The processing remains continue until the observation does not undergo ‘acceptance’ or ‘rejectance’ state. Therefore, when the R/W head reaches at right end of the input tape and queue is empty, then the string is said to accepted otherwise the string is rejected after processing the input string.
Iv The power of quantum queue automata
The computational power of automata employed with queue has been widely studied by various researchers. It is known that queue automata and Turing machines have the same computational power i.e capable of performing universal computations. Kutrib et al. 25 shown the several languages recognized by rtRDQA and proved its closure properties. It has been examined that languages can be recognized by some reversible DQA in realtime. But, the union of i.e cannot be recognized by any rtDQA 25. Further, it has been investigated that cannot be recognized by any nondeterministic queue automata in realtime (rtNDQA) 26. In this Section, we have investigated the computational power of realtime quantum queue automata. Thus, by Theorems 4.1 and 4.2, the realtime quantum queue automata has been shown to outperform its classical variants in the regime of language recognition by imposing same restrictions.
Theorem 3.
A language can be recognized by realtime quantum queue automata, but cannot be recognized by any deterministic queue automata in realtime.
Proof.
Let be a realtime QQA, . The transition function is defined in the manner as described in Section 3. It must be noted that the head moves always towards the right direction on reading a new symbol at each step. The specification of transition functions is defined as follows:
In Table 1, transition functions are applicable in the case where is in state and R/W is above the symbol and , are the symbols at the front and end of queue respectively are represented as:
(14) 
starts by splitting into two computational paths. Each path possesses equal amplitude . In the first path, state reads a and empty queue symbol , then it enqueues symbol A at the rear of queue and moves the R/W towards right. This process continues and state remains same. On reading symbol b, the change its state to rejectance state . The state is changed into on reading a symbol c from input tape and symbol A is at the front and end of queue. Further, it starts dequeue each A from front of queue on reading a from tape. If in case, state reads a and queue gets empty or reads b symbol and symbol A is at the front and end of queue, then it goes to rejectance state . Otherwise, the state is changed in to on reading b and empty queue symbol .
While in the second path, R/W keeps moving towards right of the input tape and neither enqueue nor dequeue any symbol from the queue. Whenever a state reads a symbol b, it splits the computation into two paths, where first path follows the above procedure and other path follows the loop. But, on reading state a symbol c and empty queue, state is changed into state and moves to the right. If the first path finds the difference in number of a’s before the symbol c and after it, then it goes to rejectance state. Otherwise, on reading symbol $ from the input tape and empty queue symbol, the working states and go to the accepting states and respectively. At the end, the total amplitude can be written as the product of the amplitudes associated with each subpath. Thus, the number of subpaths depends upon the number of b’s occur before the symbol c in second path. If the input string w , then both the paths reads the rightend marker $ i.e the string is said to be accepted with probability at most 1. If w , then it is rejected by one of the path and the input string is said to be rejected with probability at most 1/2. Thus, the inputs which are not in are accepted with probability at most , where i depends upon the number of b’s occur before the symbol c. For instance, consider an input string written on input tape as #bcb$ enclosed with both end markers. On reading the first b, the computation is split into two paths with . In both paths, state and state reads the next symbol c with an empty queue and changed into state and respectively. Finally, the both paths go to the accepting states and string is said to be accepted with probability 1. If the input string is taken as w=#bacb$ i.e. , then it is rejected with probability 1/2. ∎
Theorem 4.
There exists a language , that can be recognized by realtime quantum queue automata, but cannot be recognized by nondeterministic queue automata in realtime.
Proof.
Let be a realtime QQA, . Each transition in Table 2 is unitary by inspection and the other transitions are impulsive so that the transformations are unitary. For convenience, we have used the symbols to represent the symbols at the front and rear of the queue. The specification of transition functions is defined as follows:
Comments
There are no comments yet.