Quantum Representation for Deterministic Push-Down Automata

Abstract

There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push-down automata, context-free grammars, etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper, we start from a deterministic push-down automaton (DPDA). We present circuits for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.

1. Introduction

Quantum computing is growing in popularity. A good brief review of the status of the field can be found in [1]. The authors compare the basic units of information in classical and quantum systems, namely the bit and the qubit; list the quantum equivalent of a transistor; list the source of errors in both systems; and list error correction techniques. Natural qubits employ naturally emerging physical systems such as electrons of atoms.

Current active research directions mostly tend to focus on those areas that provide justification in terms of quantum advantages, such as variational quantum algorithms. There is little work that views quantum computing as a general programming paradigm even though there were several early works on computing models and algorithm development that parallel classical computing. The papers on computational models such as quantum finite state machines define new quantum models. To our knowledge, there is no paper that is based on applying established classical definitions to a quantum framework. Programming languages that run on classical models have as their foundation classical theoretical formal language models such as finite state machines, push-down automata, etc. These classical models have proven to be very effective in practice as demonstrated by the powerful programming languages in use today, but this is missing in quantum programming models.

Several authors [2,3,4,5] have proposed quantum finite state machines (QFAs) and quantum push-down automata (QPDA). The presentations are theoretical, and the definitions are new and are not the same as classical definitions. In [2], Moore and Crutchfield defined the QPDA. In all these cases, while the idea is motivated by classical models, definitions are given in terms of quantum states and quantum transitions. The languages defined by these models may not be the same as those of the corresponding classical models. In this paper, we follow a different path from the other published work on quantum automata. For our work in this paper, we consider the deterministic push-down automaton model. We start from the classical definition and propose algorithms to implement a deterministic push-down automaton (DPDA) in a quantum framework and thus bridge the classical definition with the quantum definition. The classical definitions of the PDA and DPDA are adopted from [6]. The goal is to define a DPDA in classical terms and generate a quantum circuit equivalent to a QDPDA. Classical states and alphabets are encoded as quantum objects, Hilbert space vectors, and unitary matrices and avoid entanglement. This approach is expected to provide a method for designing quantum automata, starting from a familiar model with deterministic outcomes.

In this paper, we explore techniques for implementing classical automata with quantum computing operations. We do not provide a new definition of automata but rather base the research on the established classical definitions and explore connections to the new definitions. Our focus in this paper is to develop methods for designing quantum circuits to implement a classical computing model and develop useful methods for building quantum circuits.

In classical computing, high-level programming languages such as Java are typically compiled by a series of translation steps. Initially, a source program in Java is compiled into intermediate code (e.g., bytecode) that is processed by an abstract machine, such as a push-down automaton (PDA), before eventually being translated into machine code that the underlying hardware can execute. This is the standard model of a compiler pipeline, where the abstract computational model helps bridge the gap between high-level logic and low-level machine instructions. We assume a similar process for quantum computing. A quantum program, written in a high-level quantum programming language, could first be translated into an intermediate representation defined by quantum gates. This intermediate representation may be processed by a quantum variant of a push-down automaton (Q-PDA), which would serve as an abstraction layer between the quantum logic and the low-level quantum operations that the hardware can execute. The quantum gates, much like classical machine code, would then be converted into instructions that are understandable by the quantum computer, allowing efficient and correct execution of quantum algorithms.

Our motivation is to generate the necessary tools and code to bridge these abstractions and implement a quantum computing model using well-understood principles from classical computing, making the transition to quantum systems more intuitive and consistent with traditional software development approaches.

The contributions of this paper are as follows: (1) it presents a direct method for implementing a DPDA as a quantum circuit, (2) it proposes encoding that represents a stack as a state vector and provides methods for constructing stack operations as quantum circuits, and (3) state transition presents a method for building quantum circuits from a function that is defined as a logical matrix.

Particularly, our innovative approach to implementing the quantum stack exemplifies this transition from theory to practice. While prior models might propose a quantum stack in an infinite-dimensional Hilbert space theoretically, they fall short of demonstrating how such a stack can be managed or even realized within the practical limitations of current quantum technologies. This project develops precise algorithms and quantum gate sequences to effectively implement stack operations in a real quantum computational setting.

The remainder of this paper is organized as follows: Section 2 describes papers related to our work, Section 3 describes the classical PDA and DPDA models and describes encodings to enable quantum definitions, Section 4 presents algorithms and implementations, and Section 5 provides the conclusion.

2. Related Work

Several quantum computational models have been proposed in the open literature. The paper “Quantum Automata and Quantum Grammars” by Moore and Crutchfield [2] presents a comprehensive quantum analog to that of automata and formal languages. In [2], the authors introduced quantum counterparts to classical finite state machines, push-down automata, regular languages, and context-free grammars. The authors not only provided quantum-based definitions of these fundamental concepts but also established essential closure properties for quantum regular languages (QRLs) and a quantum pumping lemma, paralleling their classical counterparts. The quantum automata and grammar models integrate unitary matrices with alphabets and grammar symbols. In quantum finite automata (QFA), symbol consumption involves applying the corresponding unitary transformation (matrix) to the current state, with states represented as vectors within a Hilbert space. In the context of push-down automata, the stack was modeled as an infinite-dimensional Hilbert space. The state and the stack were combined as the tensor product of the state space and the stack. In [5,7], authors provided a survey of quantum theoretical models, such as the QFA, QPDA, and QTM.

In the literature on hybrid models, Ambainis and Watrous [8] introduced a hybrid model of quantum finite automata (2QCFA) with quantum and classical states. In this model, when processing an input symbol, the internal states evolve in a unique manner. Initially, the quantum component undergoes a transformation, either a unitary operator or a projective measurement, which is determined by the current classical state and the scanned symbol. Subsequently, the classical segment obtains the selection of a new classical state and guides the movement of the tape head (left, right, or stationary) upon the scanned symbol and the outcome if the quantum component performs a measurement. Their research in [8] conclusively demonstrated that 2QCFA outperforms its classical counterpart, two-way probabilistic finite automata (2PFA), thus underscoring the heightened computational capabilities of this quantum–classical hybrid model. A new version of the 2QCFA was developed in [9]. It was shown that the 1QCFA is more efficient than deterministic and probabilistic finite automata for specific languages. Another hybrid model, the ‘one-way quantum finite automaton with control language’, was proposed by Bertoni [3]. They proved that the CL-1QFA (Control Language-1QFA) is capable of precisely recognizing regular languages. Moreover, the CL-1QFA is more efficient in terms of fewer states than deterministic finite automata (DFA) when handling specific regular languages. Further, Qiu et al. [10] proposed a new version of the hybrid model 1-QFAC, where the results are exponentially faster than those of deterministic finite automata for some specific languages. ‘On hybrid models of quantum finite automaton’ by Li and Feng, ref. [11], investigated three hybrid models of QFA, CL-1QFA, 1QFAC, and 1QCFA, which differ from other QFA models by consisting of two interactive components: a quantum one and a classical one. In this research, they proposed a uniform way to obtain a relationship between these three models, 2QFA, CL-1QFA, and 1QFAC, similar to the MO-1GQFA. They represented each hybrid model as a communication system that consists of a quantum processor and a classical processor. In [12], Li et al. studied the equivalence problem of measure-once one-way general quantum finite automata (MO-1gQFA) and measured-many one-way general quantum finite automata (MM-1gQFA). In these models, the input alphabet is viewed as a trace-preserving quantum operator and not a unitary operation. They showed that MM-1gQFA and MO-1gQFA recognize the same class of languages with bounded error. Two quantum finite automata are equivalent if for any input string x, the two automata accept x with equal probability. With this definition, Li and Qiu [4] derived a condition for the equivalence of CL-1QFAs and MM1QFAs.

There are extensions of classical definitions of automata to probabilistic automata. Hromkovic and Schnitger [13] study probabilistic computation models for PDA. The classical definition of a PDA is modified by adding a probability distribution to the state transition and an error condition is associated to acceptance. Enrique Vidal et al. [14] survey probabilistic finite state models. A probabilistic finite state automaton is defined by treating states as probability distributions and adding probabilities to state transitions.

The two types of memory underlying a PDA are the state and the stack. So, managing the stack is as important as managing the state. Therefore we review here some of the work from which ideas could be adopted for stack implementation for the PDA. In [15,16], the authors discuss various aspects of classical and quantum data structures, focusing on the theory and implementation of algorithms suited to both computing models. While these papers do not explicitly mention stack data structure in the literature, they investigate how data structures can be optimized for set membership and predecessor search problems, both in classical and quantum computing paradigms. In [17], a functional quantum language is introduced, including operational semantics in terms of a quantum stack. Quantum basic terminology and computation was clearly provided in [18].

3. Push-Down Automaton Formalism

The classical definitions used in this paper are adopted from [6]. A (nondeterministic) push-down automaton (PDA) is defined as a six-tuple $M=\left(Q, \Sigma , \Gamma , \mathsf{\Delta }, q_0, A\right)$, where Q is a finite set of states, Σ (the alphabet) is a finite set of symbols, $\Gamma$ represents the stack alphabet, q₀ ∈ Q is the initial state, A ⊆ Q is the set of accepting or final states, and Δ is the transition relation. Δ is defined as a function from $Q\times \Sigma \cup \left\{\epsilon \right\}\times \Gamma \cup \left\{\epsilon \right\}$ to subsets of $Q\times \Gamma \cup \left\{\epsilon \right\}$. The transition defines the possible next (state, stack) pairs from the current input position as the PDA processes the input string. The action on the stack is to either push a symbol, pop the top symbol, or change the top symbol depending on the top symbol of the stack. There is no change to the stack below the top symbol. If the action is to pop, the second symbol from the current top will become the top symbol. If the stack is empty, then pop is illegal.

A computation by M is a finite sequence of configurations C₀, C₁, C₂, …, C_n, where each configuration is denoted by the triplet (q, w, $\gamma$), where q ∈ Q, w ∈ ${\Sigma }^{*}$, and $\gamma$ ∈ ${\Gamma }^{*}$. In this definition, w represents the remaining input to be processed by the PDA. The relation ($⊢$), called the yield, between the configurations is defined by the transition function. Let C₁ = (p, aw, $\alpha \gamma$) and C₂ = (q, w, $\beta \gamma$) where ∈ ($\Sigma$ ∪ {ε}), w ∈ ${\Sigma }^{*}$, $\alpha ,\beta$ ∈ (Γ ∪ {ε}), and γ $\mathsf{ϵ} {\Gamma }^{\mathrm{*}}$ then C₁ ⊢ C₂ if and only if (q, $\beta$) ∈ Δ (p, a, $\alpha$). In a computation, we have C_i $⊢$ C_i+1.

The definitions of PDA and computation presented above are among the classical definitions found in textbooks. We refer to Q as the set of classical states or control states. In this paper, we are interested in a deterministic push-down automata (DPDA). A DPDA is a PDA with no competing moves from any state while changing configurations. Specifically, the transition is defined as $\delta :Q\times \left(\Sigma \cup \left\{\epsilon \right\}\right)\times \left(\Gamma \cup \left\{\epsilon \right\}\right)\to Q\times \left(\Gamma \cup \left\{\epsilon \right\}\right) \cup \varnothing$, a function. We modify the definition of the DPDA by adding an initial stack element Z and changing the transition function to $\delta :Q\times \left(\Sigma \cup \left\{\epsilon \right\}\right)\times \Gamma \cup \left\{Z\right\}\to Q\times {\Gamma }^{*}$. Dead states could be added to handle null transitions {$\varnothing$}. The above modifications do not affect the languages accepted. This will allow us to keep the current stack-top element in all transitions, and the transition will also depend on the stack-top. An example is shown below, which accepts the language {aⁿbⁿ⁺¹ | n ≥ 1} (Figure 1).

3.1. Alternate View of $\delta$

The function $\delta$ maps a triplet (q, a, $\alpha$) to a pair (p, $\beta$), where p, q ∈ Q, a $ϵ (\Sigma \cup \left\{\epsilon \right\})$, and $\alpha ϵ \Gamma and \beta ϵ {\Gamma }^{*}$. This function is the basis for configuration change and computations. We can view this as a pair of mappings (f, g) associated with the input strings and the current stack top as follows:

(1)

f_a,α: q → p and

(2)

f_a,α: $\alpha \gamma \to ({\alpha }^{\prime }, \beta \gamma )$, such that $\alpha , {\alpha }^{\prime }\in \Gamma and \beta \gamma ϵ {\Gamma }^{*}$ for each input symbol a or ε. α represents the current stack top, and ${\alpha }^{\prime }$ represents the new stack top.

With this view, we consider the computation as changes of configurations effected by an input string or a control string. A configuration will have two components—the current state and the current stack—both of which are transformed by the input action being processed (either consuming the current symbol or not) depending on the stack top. We call the current state and the current stack top together the augmented state. We can represent the symbols as vectors and functions as matrices. Augmented states can be viewed as the cross product of the control state space Q and stack top space Γ. The elements of $\Gamma \cup \left\{Z\right\}$ are the stack elements and can also be represented as vectors. The alphabet symbols in combination with the stack top make three changes: (1) change the current state, (2) change the current stack top, and (3) change the stack. The states can be represented by the basis vectors of a |Q| dimensional vector space. Each input symbol-stack symbol combination defines a matrix defining the state transition. The entries of the matrix are 0 s and 1 s, where 1 s represents the state transitions. The matrix operations are Boolean operations “and” and “or”.

Example 1.

In this example, we describe the DPDA shown in Figure 1 with the formalism described above.

A state–stack pair can be specified by a 5 × 2 matrix. The augmented states are (states × stack symbols = [1, 2, 3, 4, 5] × [a, Z]). The five control states are as follows:

$$A_1=\left[\begin{array}{c}\begin{array}{c}1\\ 0\end{array}\\ \begin{array}{c}0\\ 0\\ 0\end{array}\end{array}\right] A_2=\left[\begin{array}{c}\begin{array}{c}0\\ 1\end{array}\\ \begin{array}{c}0\\ 0\\ 0\end{array}\end{array}\right] A_3=\left[\begin{array}{c}\begin{array}{c}0\\ 0\end{array}\\ \begin{array}{c}1\\ 0\\ 0\end{array}\end{array}\right] A_4=\left[\begin{array}{c}\begin{array}{c}0\\ 0\end{array}\\ \begin{array}{c}0\\ 1\\ 0\end{array}\end{array}\right] A_5=\left[\begin{array}{c}\begin{array}{c}0\\ 0\end{array}\\ \begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\right]$$

The state transition matrices are as follows:

$$T_{a,Z}=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1\end{array}\right] T_{a,a}=\left[\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right] T_{b,Z}=\left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1\end{array}\right] T_{b,a}=\left[\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]$$

The stack and stack-top transitions are as follows:

$$g_{a,z}:Z\to \left(a,aZ\right)|\left(Z,Z\right),q_{a,a}:a\to \left(a,a^{+}Z\right),q_{b,z}:Z\to \left(Z,Z\right),q_{b,a}:\left(a,a^{\mathrm{*}}Z\right).$$

Example transitions from state 1 to state 2 are given by $T_{a,Z}{A}_1$, those from state 3 are given by $T_{b,a}{A}_3$, and those from state 3 and $T_{b,Z}{A}_3$ are given by state 4.

This view of PDA closely matches the quantum push-down automata (QPDA) definition that follows. According to the QPDA definitions, the transition functions are unitary operations. The matrices and functions defined above can be translated into quantum circuits, as we show later.

3.2. Quantum Push-Down Automata (QPDA)

We adopt the QPDA definition given by Moore and Crutchfield [2]. They define a quantum PDA as the tensor product of a finite dimensional space called the control state and an infinite-dimensional stack space S. Each basis vector of S corresponds to a finite word over the stack alphabet Γ. The transitions are affected by unitary operation in the state and stack spaces $⟨$(q₁, $\sigma$₁) | U_a = $\left|\mathrm{q}2,\sigma 2\right.⟩$, where q₁ and q₂ are in the state space and ${\sigma }_1$ and ${\sigma }_2$ are in the stack space.

This definition of the QPDA requires knowledge of the symbol on the stack at the second position from the top when a pop operation is performed. This is because of the state transition from the top to the second when a pop operation is performed. In the alternate view of δ described above, the possible stack tops are kept in the same state. The correct stack top is determined dynamically during computation. Therefore, it will match the quantum pop operation.

Our goal is to construct an implementation of a DPDA described using a classical definition as a quantum system. For quantum formalism, we will adopt quantum circuits. We will focus on the computation of the PDA, as it is the computation sequence that determines whether an input string is accepted. As computation is accomplished by a sequence of configuration changes, we will focus on the implementation of a configuration change. To accomplish this, we develop a method to implement the yield relation.

3.3. The Yield Relation

We begin with the yield relation C₁ ⊢ C₂, where C₁ = (q, aw, $\alpha \gamma$), C₂ = (p, w, $\beta \gamma$), a ∈ ($\Sigma$ ∪ {ε}), w ∈ ${\Sigma }^{*}$, $\alpha ,\beta$ ∈ (Γ ∪ {ε}), and γ $ϵ {\Gamma }^{\mathrm{*}}$, as defined earlier. The yield determines the transitions based on the transition rules defined by the PDA depending on three variables: the control state p, the input symbol (or ε), and the top stack symbol of the stack instance. We will redefine the configurations based on the alternate view of the transition function we described above to distinguish the current stack top as a distinguishable entity. This does not change the computation sequence and hence does not impact the language defined. We define the configuration as (q, α, aw, γ), where q is the current state, α is the current stack top, aw is the remaining input to the process, and γ is the current stack. If C₁ = (q, $\alpha$, aw, $\gamma$) and C₂ = (p, $\beta$, w, ${\gamma }^{\prime }$), we say C₁ ⊢ C₂ if and only if there are maps f_a,α:q → p and g_a,α: γ → $(\beta , \beta \gamma )$. This view of the configuration change is shown in Figure 2. Our QDPDA implements algorithms for circuits to implement the yield relation.

4. QDPDA as Quantum Circuits

In this section, we will present algorithms for the implementation of deterministic push-down automata in a quantum framework such as quantum deterministic push-down automata (QDPDA). We construct quantum circuits corresponding to the computation of DPDA transitions. Let M = (K, Σ, Γ, $\delta$, q₀, A) denote the deterministic push-down automata with k states (|K| = k). Assume that the states of M are labeled q_i, where i ∈ (0, 1, 2 $\cdots$ k − 1). Then, we can represent each state as a K-dimensional bit vector $q_i={\left[\begin{array}{ccc}{x}_1& \dots & x_k\end{array}\right]}^T$ with x_j = 1 if j = i and 0 otherwise. Then, q_i will span an n-dimensional vector space. As a DPDA transition can make only one move from the current state, the computation path of the control states will be a sequence of states. Therefore, the transitions of control states can be represented by unitary matrices.

Assume that the PDA has ‘m’ stack symbols (for convenience, ε is also viewed as a symbol), where m = (|Γ| + 1). For convenience, we assume that m is a power of 2. We label each stack symbol as s_i, i = 0, 1, 2, ……, m − 1 and encode it as a basis vector s_i = ${\left[x_0, \cdots , x_{\log \left(\mathrm{m}\right)}\right]}^T$ (x_i = 0/1) of a log(m)-dimensional Hilbert space. For example, suppose that if we have three stack symbols Γ = {s₁, s₂, s₃}, ε will be assigned to s₀. Then, in the quantum circuit, s₀ will be represented as ‘00’; similarly, s₁ = 01, s₂ = 10, and s₃ = 11. A transition function can be represented as three tuples f_a,α | $\alpha$ | ${\beta }^{\prime }$, where f_a,α (for all a ∈ $\Sigma$) is the transition matrix, one for each symbol in the alphabet-stack top pair. A transition matrix is a transformation that defines the transition from the current state of the PDA to the next state reading an input symbol. The entries of f_a,α (i, j) will be 1 if there is a transition from state i to state j reading the input symbol ‘a’, while α is the top stack symbol, and 0 otherwise. ‘$\alpha$’ represents the top symbol of the stack and the element to be popped from the stack, and $\beta$ is the string of stack elements (may be empty or up to two stack elements combined) to be pushed onto the stack. The stack operations depend upon the values of $\alpha$ and β. There are two different cases for stack operations:

Case 0: $\alpha \ne$ ε and $\beta$ = ε, pop α

Case 1: $\alpha \ne$ ε and $\beta =\gamma \alpha$, push γ (if γ = ε, then no stack operation may be performed);

Therefore, we divide Case 1 into two parts, Case 1a and Case 1b.

Case 1a: $\beta \ne$ ε and γ = ε; then, $\beta =\alpha$;

Case 1b: $\beta \ne$ ε and γ $\ne$ ε.

To create a quantum circuit equivalent to the abovementioned computation of the DPDA transition, we present a set of algorithms. These algorithms perform two distinct operations to accomplish a state transition: (1) control state transition (observe that the DPDA transition consists of a change in the control state and stack) and (2) changes in the stack. We outline the algorithms in the following two subsections.

4.1. Control State Change as a Quantum Circuit

The control state transition of a DPDA may be expressed as Ax $⟹$ y, where x and y are state vectors and A is a matrix representing the state transition. To construct the quantum circuit for the state transitions, we need one quantum register for the state vector. Assuming there are k states in the DPDA, the registration size is $q^{\otimes k}$ (means $q\otimes q\otimes q$ …… $\otimes$ q, k times). The transition matrix should be encoded as a unitary transformation. Transition matrices ($T_{a,\alpha }$ where a ∈ $\Sigma$ and $\alpha \in \Gamma$) are associated with the pairs (a, $\alpha$), where a is the current input symbol and $\alpha$ is the current stack-top symbol. While it is possible to encode the transition matrices as unitary matrices, we follow an algorithmic approach and present an efficient algorithm (Algorithm 1) to generate a quantum circuit equivalent to the state transition matrix.

Algorithm 1: Control state transition ( )

Input: Ta,α, q (current state vector)

Output: Quantum circuit equivalent to the computation of Ta,α

Begin  (1) int p;  (2) for i = 1 to k:    (a)  if (q(i) = = 1):        a.  p = i        b.  Add the NOT gate to $|{\mathit{q}}_{\mathrm{i}}⟩$    (b)  End_if  (3) end _for  (4) For i = 1 to k:   a.  For j = 1 to k:       i.  if (Tii = = 1):  1. continue       ii.  else_if (Tij = = 1)  1. A CNOT gate with a control qubit is added as $|i⟩$ and a target qubit is added as $|j⟩$.       iii.  else  1. do_nothing.   b.  End_For  (5) End_For  (6) Initialize Count = 0  (7) For i = 1 to k:   a.  If ($|{\mathit{q}}_i⟩$ = = 1)       i.  Count ++  (8) If (Count > 1):   a.  Add the NOT gate to $|{\mathit{q}}_p⟩$  (9) End_if End

Algorithm 1 will create a quantum circuit that performs the computations specified by the transition matrix T_a,α given the current state vector |q⟩. As mentioned previously, the states are encoded as vectors $|q⟩={[q_1, q_2, \cdots , q_n]}^T$, where q_i = 1 if |q⟩ represents state i and q_j = 0 for j ≠ i. The number of states is n. A register is initialized as ${|0⟩}^{\otimes \mathrm{n}}$. If the ith component q(i) is 1, then the respective ith qubit will flip from $|0⟩$ to $|1⟩$ using a NOT gate.

In Step 2.a.a., we assign the value ‘p’ to ‘i’, for which q(i) = 1. Since it is a DPDA, there will be only one zero element in vector q. We need to store the index of the nonzero entry in the initial state vector because, by the end of Step 4, we may have two nonzero entries in the state vector. We must ensure that the nonzero entry in the initial state vector becomes 0, as we will observe in Steps 7 and 8.

In Step 4, we iterate through each element of the transition matrix with two nested loops, checking each element’s condition to determine the necessary quantum gate operations. If the diagonal element (Tii) equals 1, it skips any operation for that state, maintaining its current state without change. For off-diagonal elements (Tij) equal to 1, a CNOT gate is applied with the ith qubit as the control and the jth qubit as the target, giving the transition between states as defined by the matrix. In cases where neither condition is met, the algorithm performs no action, moving on to the next element. This approach allows the algorithm to construct a quantum circuit that accurately represents the transitions given by T_a,α for state transition.

After completing Step 4, if there are multiple nonzero entries in the register q indicating state changes due to reading the input symbol, we proceed to add a NOT gate to the $|\mathit{q}$_p$⟩$ qubit. This additional operation helps adjust the state appropriately for further computation. However, if only one nonzero entry remains in q after Step 4, this signifies that there is no change in the state upon reading the input symbol. Therefore, in such cases, no further modification is needed, and we proceed with the computation without adding any extra gates.

Example 2.

As an illustrative example, consider the DPDA shown in Figure 1. Let us consider the transition from state 4. The current state vector is denoted as ${\displaystyle {\mathit{A}}_4}={\displaystyle \left[\begin{array}{c}\begin{array}{c}0\\ 0\end{array}\\ \begin{array}{c}0\\ 1\\ 0\end{array}\end{array}\right]}$, the stack top is Z, and we are reading the symbol b. In this case, the transition matrix is ${\displaystyle {\mathit{T}}_{\mathit{b},\mathit{Z}}}={\displaystyle \left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1\end{array}\right]}$. Following Algorithm 1, we can construct the quantum circuit shown in Figure 3 to compute the next state vector. In the current state, vector q(4) = 1; hence, p = 4, and the NOT gate is added to $|q$₄ $⟩$. There are three off-diagonal elements equal to 1 and one diagonal element equal to 1. Therefore, we need to append 3 CNOT gates, (1, 5), where the 1st qubit is the control and the 5th qubit is the target, similar to (3, 4) and (4, 5), while ignoring (5, 5), as instructed in the algorithm. There are two 1 s in the resulting vector, and then an NOT gate is added to $|q$_p$⟩$, which is $|q$₄$⟩$. The resulting quantum circuit is shown in Figure 3 which is implemented in Qiskit [19]. The circuit clearly shows that the output corresponds to state 5, that is, ${\displaystyle {\mathit{A}}_5}={\displaystyle \left[\begin{array}{c}\begin{array}{c}0\\ 0\end{array}\\ \begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\right]}$.

4.2. DPDA Transition

A DPDA transition is a configuration change, as shown in Figure 2, that consists of a control state transition and stack transition. Section 4 (a) provides an algorithm and example for generating a quantum circuit from the classical transition matrix description of the state transition in a DPDA. In this section, we will examine the associated stack operations and the transition as a unit. Computation by a DPDA is a sequence of configuration changes that are affected by transitions. Therefore, we can view the DPDA transition (combined state and stack) as a unit of computation. In the following descriptions, we focus on the DPDA transition, i.e., the unit of computation. A conceptual view of the unit of computation is shown in Figure 4 (also referred to Algorithm 2). The computation is structured as initialization, computation (control state and stack changes), and possible measurement. Algorithms for parts of the computation will be given in this section.

The initial quantum state is prepared for each transition. To prepare this initial state, the inputs needed are the current state vector (q) and the current top element of the stack (top). The transition ‘f_a,α’ is defined for all symbols ‘a’ in the alphabet Σ, the stack element to be popped (α), and the stack element to be pushed (β). In our implementation scheme, stack elements represent quantum states represented as binary numbers. The elements to be pushed represented by β = αγ may consist of 0–2 stack elements. The quantum register for β is initialized with 2 m qubits (where m = log(|Γ| + 1)), that is, the first m qubits for $\alpha$ and the next m qubits for $\gamma$. Earlier, we defined the possible cases for the transition functions of a PDA. To decide to which case the respective transition belongs, we need 2 qubits, ‘aux0’ and ‘aux1’, which are initially reset to $|0⟩$. Based on the inputs of $\beta$, the ‘Aux’ qubits change. Subsequently, we set up two quantum registers, $\alpha$ and $\gamma$, each containing m qubits. We start by resetting all the qubits in the quantum registers of $\alpha$ and $\gamma$ to |0⟩. Then, if any qubit in the β register is 1, we use a NOT gate to flip that respective qubit in α or $\gamma$ from $|0⟩$ to $|1⟩$. These registers participate in change computations.

The next steps will be initialization of $|q$_i$⟩$, $|top$_i$⟩$ which represents the current state vector and current top element of the stack. A dynamic quantum register is initialized to maintain stack memory. A view of the quantum circuit initialization is shown in Figure 5. Using the initialization shown in Figure 5, Algorithm 2 provides the steps of the DPDA transition and other algorithms also use initialization.

Algorithm 2: Computation of a transition ( )

Input: The initial state from Algorithm 3

Output: Computation of the DPDA transition function ‘fa |$\alpha$| $\beta$’

Begin:  1. for i = 1 to m: (a) Add the NOT gate to $|{\beta }_i⟩$//Include both $|{\alpha }_i⟩$ and $|{\gamma }_i⟩$  2. end _for  3. Add Multi control NOT gate with controls (${\displaystyle |{\mathit{\beta }}_1⟩ \dots |{\mathit{\beta }}_{\mathit{m}}⟩}$) and target ${\displaystyle |\mathit{aux}0⟩}$  4. ${\displaystyle |\mathit{aux}0⟩}$ was used as the control, and Case 0 was used as the target.  5. for i = 1 to m: (a) Add a CNOT gate as a control $|$aux0$⟩$ and target $|{\gamma }_i⟩$  6. end _for  7. Multiple control NOT gates with controls ($|{\gamma }_1⟩$ … $|{\gamma }_m⟩$) and target $|$aux1$⟩$ are added  8. The control_function oracle was added to the control as $|$aux1$⟩$, and the target was Case 1a ().  9. Add NOT gate to $|$aux1$⟩$  10. The control_function oracle was added to the control as $|$aux1$⟩$, and the target was Case 1b ().  11. Measure ${\mathit{q}}^{\otimes \mathit{n}}$ and ${\mathit{t}\mathit{o}\mathit{p}}^{\otimes \mathbf{m}}$ End

Algorithm 3 Initial state is prepared as shown in Figure 5.

Algorithm 3: Prepare the initial state for the quantum circuit.

Input: q(current state vector), top (current top element) and action and element if any(Push or pop)

Output: Initial state preparation for Quantum circuit.

Begin:  a. Initialize ${\beta }^{\otimes 2\mathrm{m}}$ register of m qubits for stack element which needs to be push.  b. Initialize ${aux}^{\otimes 2}$ qubits defined.  c. Initialize ${\alpha }^{\otimes \mathrm{m}}$ register of m qubits for stack element which needed to be popped.  d. Initialize ${\gamma }^{\otimes \mathrm{m}}$ register of m qubits for stack element which needs to be push.  e. Initialize ${top}^{\otimes \mathrm{m}}$ register of m qubits for current top of the stack.  f. Initialize $q^{\otimes k}$ register of n qubits for state transition vector.  g. Initialize ‘${stack}^{\otimes x}$’ register of x qubits, where assuming x is dynamic in nature. End

Qubit requirement for the computation: If there are ‘k’ states and n = (|Γ| + 1) stack symbols, then the size of the circuit is 5m + k + 2 + x, where m = log(n) and

(1)

2m qubits are required to initialize ${\beta }^{\otimes \mathrm{m}}$;

(2)

Two qubits are required to initialize $aux$0 and $aux$1;

(3)

2m qubits are required to initialize ${\alpha }^{\otimes \mathrm{m}}$ and ${\gamma }^{\otimes \mathrm{m}}$;

(4)

m qubits are required to initialize ${top}^{\otimes \mathrm{m}}$;

(5)

k qubits are required to initialize ${\mathrm{q}}^{\otimes \mathrm{n}}$ register;

(6)

For stack management, we need variable qubits; for now, we assume ‘x’ qubits.

It should be noted that comparisons with classical circuits may not be a fair comparison and hence are not attempted.

Algorithm 2 provides the steps in the DPDA transition computation, as shown in Figure 4. We encode all essential values and then determine the specific case based on β. The three cases are as follows:

Case 0: $\alpha \ne$ ε and $\beta$ = ε, pop α;

Case 1a: $\beta \ne$ ε and γ = ε; then, $\beta =\alpha$;

Case 1b: $\beta \ne$ ε and γ $\ne$ ε.

The β value is crucial for triggering the correct case. The auxiliary qubits, labeled as aux0 and aux1, are used to determine the specific case for the transition function of the push-down automaton (PDA). Initially set to |0⟩, these auxiliary qubits change based on the inputs of β, the stack element to be pushed. By setting the values of aux0 and aux1 according to the conditions defined in the transition, the circuit can identify which case (such as pushing or popping certain elements) applies for the computation. This selective activation of aux0 and aux1 allows the quantum circuit to control stack operations dynamically within the quantum implementation of the PDA.

To check the condition $\beta$ = ε, we first apply a NOT gate to β. Then, we utilize a multicontrol-NOT gate, where β acts as the control and aux0 serves as the target. This configuration enables the activation of the aux0 qubit if the β value is 0; otherwise, aux0 remains at 0. Therefore, initiating Case 0 is defined. To trigger Case 1a, we need to express β in terms of α and γ. Given that α ≠ 0 in any case, as at least one element pops in each transition, we aim to trigger Case 1a when γ = 0. It follows that if β = 0, then aux0 should be triggered, leading to Case 0. Trivially, if β = 0, then γ = 0. However, to avoid triggering Case 1a when Case 0 is already triggered, we proceed as follows:

First, we add control gates with an aux0 qubit as the control and γ as the target to set γ to 0 if all are 1 s. If Case 0 is not triggered, meaning that both α and γ equal 0, then γ remains unchanged. Next, we added multiple control gates with only the γ register as controls and aux1 as the target. Consequently, if only γ equals 0, aux1 will be triggered at this point. Subsequently, we incorporate the control function oracle for Case 1a, with aux1 as the control and the target being a set of registers defined in Algorithm 4. If γ ≠ 0, then Case 1b should be triggered. In this scenario, we add a NOT gate to the same aux1 register and then incorporate the control function oracle for Case 1b, with aux1 as the control and the target being the set of registers defined in Algorithm 5.

Algorithm 2 refers to circuits associated with the three cases as oracles. The algorithms for the cases are given below. Algorithm 4 handles the case where β = ε (case 0 in Figure 4). This case results in a change in the DPDA stack. The current top element α is to be popped. This will change the top element of the stack. The current element second from the top will become the new stack top. An overview of the circuit generated by the algorithm is given in Figure 6.

Algorithm 4: Case 0 ( )

Input: ‘fa,α |$\alpha$| $\beta$’ defined for each alphabet a $\in$ Σ, $\alpha , \beta \in \left(\Gamma \left\{\right\}\right)$ and q (current state vector) and top (current top element)

Output:

Begin  (1) for i = 1 to m:   (a) CNOT gate with control $|{\alpha }_i⟩$ and target $|{\mathrm{top}}_{\mathrm{i}}⟩$  (2) end _for  (3) for i = 1 to m:   (a) Adding the NOT gate to $|{\mathrm{top}}_i⟩$  (4) end _for  (5) Control_function oracle is added with control as ${\displaystyle |{\mathit{top}}_{\mathit{i}}⟩}$ and target as Algorithm_statetransition ( ).  (6) Reset $|{\mathrm{top}}_{\mathrm{i}}⟩$  (7) Algorithm_pop() is added to the stack and top registers. End

In Algorithm 4, we first need to check whether α equals the top of the stack. We accomplish this by adding CNOT gates with control $|\mathit{\alpha }$_i$⟩$ and target $|\mathit{t}\mathit{o}\mathit{p}$_i⟩. If they are equal, i.e., $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ = 0, then we apply a NOT gate to make $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ = 1. Next, we add a controlled_function oracle with $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ as the control and Algorithm_statetransition() as the target. Subsequently, we need to reset and update the top. Now, we need to manage the stack. Here, we need to pop the top element from the stack and update the top register. This is executed by Algorithm_pop(). The details of Algorithm_statetransition() and Algorithm_pop() are given later. The quantum circuit in Figure 6 provides a circuit representation of Case 0 according to the instructions outlined in Algorithm 4.

If the values of β are not equal to ε and γ is ε, then in Case 1a, no stack computations are performed. Then, indirectly, β = α. This is because the stack elements to be pushed or popped are ‘α’ itself, signifying that the stack is ignored in this case. In Algorithm 5, we need to check whether α equals the top of the stack. We accomplish this by adding CNOT gates with control $|\mathit{\alpha }$_i$⟩$ and target $|\mathit{t}\mathit{o}\mathit{p}$_i⟩. If they are equal, i.e., $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ = 0, then we apply a NOT gate to make $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ = 1. Next, we add a controlled_function oracle with $|\mathit{t}\mathit{o}\mathit{p}$_i$⟩$ as the control and Algorithm_statetransition() as the target. Subsequently, we need to reset and update the top, which will remain the same as α. Figure 7 provides a circuit representation of Case 1a per the instructions outlined in Algorithm 4.

Algorithm 5: Case 1a ()

Input: ‘fa,α |$\alpha$| $\beta$’ defined for each alphabet a $\in$ Σ, $\alpha , \beta \in \left(\Gamma \left\{\right\}\right)$ and q (current state vector) and top (current top element)

Output:

Begin  (1) for i = 1 to m:   (a) CNOT gate with control |αi⟩ and target |topi⟩  (2) end _for  (3) for i = 1 to m:   (a) Adding the NOT gate to |topi⟩  (4) end _for  (5) Control_function oracle is added with control as ${\displaystyle |{\mathit{top}}_{\mathit{i}}⟩}$ and target as Algorithm_statetransition ( ).  (6) Reset $|{\mathrm{top}}_i⟩$  (7) for i = 1 to m:   (a) CNOT gate with control $|{\alpha }_i⟩$ and target $|{\mathrm{top}}_i⟩$  (8) end _for End

When the values of β and γ are not equivalent to ε, Case 1b involves executing stack operations. Given β = γα, the required transition involves popping ‘α’ from the stack and subsequently pushing ‘γα’. However, this action can be simplified to not popping any element but only pushing ‘γ’. Therefore, the circuit computations in Algorithm 5 resemble this simplified approach. The only difference is to execute the Algorithm_Push_gamma() for the stack register. Figure 8 provides a circuit representation of case 1b per the instructions outlined in Algorithm 6.

Algorithm 6: Case 1b ()

Input: ‘fa,α $\left|\alpha \right|$ $\beta$’ defined for each alphabet a $\in$ Σ, $\alpha , \beta \in \left(\Gamma \left\{\mathsf{\epsilon }\right\}\right)$ and q (current state vector) and top (current top element)

Output:

Begin  (1) for i = 1 to m:   (a) CNOT gate with control $|{\alpha }_i⟩$ and target $|{top}_i⟩$  (2) end _for  (3) for i = 1 to m:   (a) Adding the NOT gate to $|{top}_i⟩$  (4) end _for  (5) Control_function oracle is added with control as $|{\mathit{top}}_{\mathit{i}}⟩$ and target as Algorithm_statetransition ( ).  (6) Reset $|{\mathit{top}}_{\mathrm{i}}⟩$  (7) for i = 1 to m:   (a) CNOT gate with control $|{\alpha }_{\mathrm{i}}⟩$ and target $|{\mathit{top}}_{\mathrm{i}}⟩$  (8) end _for  (9) Algorithm_Push_gamma() is used to push gamma into the stack. End

The algorithms described to accomplish DPDA transition involve control state transition and stack update. The algorithm state transition controls the state transition. Algorithm 1 is presented at the beginning of this section. The algorithms for the stack update actions push and pop are presented in the next section. Example simulation results in qiskit [19] are given in the Appendix A section below.

4.3. Stack Management

The algorithms for stack update actions are as follows: (1) push, named Algorithm_push_gamma(), and (2) pop, named Algorithm_pop(). They are given in this section. We present two approaches for designing the algorithms:

Swap Gate Approach: This approach may entail greater depth than the auxiliary qubit approach but utilizes fewer qubits.

Auxiliary Qubit Approach: This approach typically results in substantially less depth than does the swap gate approach.

Swap gate approach: This approach follows the array implementation of stack I conventional programming. The array is replaced by a quantum register |stack⟩. The register |stack> is composed of blocks-stack[0] … stack[stack_size]-of m-qubit registers representing stack elements. The first block represents the stack top. SWAP gates are used to move elements up or down, implementing the pop and push operations. The stack operation push is the tensor product ∣$\gamma$⟩ $⨂$ ∣α$\theta$⟩ $\to$ |$\gamma {\theta }^1$⟩, where $\gamma$ is the stack element to push onto the stack, α is the current top of the stack, and $\theta$ is the rest of the stack. After pushing, the operation $\gamma$ becomes the current top, and ${\theta }^1$ = α. The process is outlined in Algorithm 7. An example circuit is shown in Figure 9.

Algorithm 7: Algorithm_push_gamma( )
Begin
	(1) int z = size of the stack.
	(2) while (z > m):
	(a) Adding a swap gate by swapping $|x_z⟩$ and $|x_{x-m}⟩$
	(b) z --
	(3) end_while
	(4) for i = 0 to m − 1:
	(a) CNOT gate with control $|gamm{a}_{\mathrm{i}}⟩$ and target $|{stack}_{\mathrm{i}}⟩$
	(5) end _for
End

Example 3.

Consider a DPDA with Γ ∪ $\left\{\epsilon \right\}$ = {ε, a, b}. Elements of the stack alphabet and ε are represented as |ε⟩ = |00⟩, |a⟩ = |01⟩ and |b⟩ = |10⟩. The current stack is assumed to be [a, b, b, a], where the leftmost element, a, corresponds to the stack top. Specifically, Stack[0] and Stack[1] represent ‘a’, Stack[2] and Stack[3] represent ‘b’, Stack[4] and Stack[5] represent ‘b’, and Stack[6] and Stack[7] represent ‘a’. Now, we aim to push an element onto the stack. The quantum circuit given in Figure 9 shows the resulting circuit following Algorithm 7.

Algorithm 8 outlines the procedure to generate the circuit for the pop operation, which is tr_alpha(∣α$\theta$⟩) $\to$ ∣$\theta$⟩, where α is the current top and stack element that will pop and $\theta$ is the rest of the stack. Figure 10 shows a circuit generated by Algorithm 8 assuming that the current stack is [a, b, b, a].

Algorithm 8: Algorithm_stack_Pop ( )

Begin

(1) int i = 0;

(2) while (i < (z − m)):

(a) Adding a swap gate by swapping $|x_{\mathrm{i}}⟩$ and $|x_{\mathrm{i}+\mathrm{m}}⟩$

(b) i ++

(3) end_while

(4) for i = 0 to m − 1:

(a) CNOT gate with control $|x_{\mathrm{i}}⟩$ and target $|{top}_{\mathrm{i}}⟩$

(5) end _for

End

For Algorithms 7 and 8, which utilize a quantum counter to maintain the stack size, the following scheme [20] can be implemented on a quantum computer:

Quantum Counter Register: A separate quantum register is allocated for the stack size counter. This register will store the current size of the stack and will be updated with each push and pop operation.

Push Operation (+1): Each time an element is pushed onto the stack, the quantum counter register will be incremented by 1. This can be achieved using a quantum addition [20] circuit that performs controlled addition of 1 to the register. The process involves representing the stack size in binary form within the register and applying a quantum adder circuit to increment the value by 1 whenever a push operation occurs. This can be completed using a set of controlled CNOT gates and Toffoli gates (if needed for multi-bit addition).

Pop Operation (−1): Each time an element is popped from the stack, the quantum counter register will be decremented by 1. This can be performed using a quantum subtraction circuit that subtracts 1 from the register value:

Like addition, this subtraction involves using a quantum adder circuit configured for subtraction. The quantum register representing the stack size will be updated by subtracting 1 whenever a pop operation is triggered.

Stack Overflow/Underflow: Care must be taken to prevent stack overflow or underflow. For example, if the counter reaches a predefined maximum stack size, the quantum circuit must handle this by blocking further push operations. Similarly, if the counter reaches zero, pop operations should be restricted to avoid negative stack sizes.

By keeping the quantum counter in a separate register, the size of the stack can be efficiently tracked and maintained with minimal overhead. These operations allow for the dynamic control of the stack size, ensuring that the stack behaves correctly under quantum operations.

Auxiliary Qubit Approach: The auxiliary qubit approach is similar to the linked-list implementation of a stack in conventional programming, which is more efficient. In this approach, we avoid the top register. The primary distinction between the swap gate approach and the auxiliary qubit approach lies in how the stack indices are handled. In the auxiliary qubit approach, the stack indices are inverted, with the top element residing in the last block register. This contrasts with the swap gate approach, where the top element is consistently positioned in the first block register of the stack. We partition the quantum register representing the stack into blocks, each block consisting of m + 1 qubits, where m = log(n) (n stack symbols). Within each block, the first m qubits represent the stack element, while the additional qubit indicates whether it is the stack top. Push and pop add or remove elements at the free end of the stack register.

Example 4.

Let us consider the scenario of Example 3, a DPDA with Γ ∪ $\left\{\epsilon \right\}$ = {ε, a, b}. Elements of the stack alphabet and ε are represented as |ε> = |00>, |a> = |01> and |b> = |10>. The current stack is assumed to be [a, b, b, a], where the leftmost element, a, corresponds to the stack top. The quantum circuit for push is shown in Figure 11.

Stack[0] and Stack[1] represent ‘a’, and the auxiliary qubit for ‘a’ is aux0. Stack[2] and Stack[3] represent ‘b’, and the auxiliary qubit for ‘b’ is aux1. Stack[4] and Stack[5] represent ‘b’, and the auxiliary qubit for ‘b’ is aux2. Stack[2] and Stack[3] represent ‘a’, and the auxiliary qubit for ‘a’ is aux3. The qubit aux3 is activated as ‘a’ (the fourth symbol in the list), which is the top symbol.

To push an element, we need to identify the target blocks for insertion. It is the block following the block whose aux qubit is 1. In this scenario, the target block consists of a stack of registers[8] and a stack[9]. Following this, we apply CNOT gates with the control being the auxiliary qubit associated with the gamma resistor, effectively preparing these target blocks for accommodating the new symbol. Subsequently, we activate the auxiliary qubit aux4, linked with the last block, indicating its occupation by the newly inserted element. Simultaneously, another CNOT gate is employed to deactivate aux3, the auxiliary qubit associated with the previous top symbol. This action resets aux3 to 0, signifying the removal of the symbol from the top position of the stack. This process ensures the smooth addition of the new element while accurately maintaining the activation and deactivation of auxiliary qubits, which is crucial for tracking the stack’s top element and preserving its integrity.

In the pop operation of the auxiliary qubit approach, we reset the last block from the stack, similar to the pop operation in classical stacks. However, to preserve the integrity of the top element before resetting, we introduce a CNOT operation of the auxiliary qubit of the last block to the auxiliary qubit of the last but one block. This activation ensures that the auxiliary qubit associated with the last block, is activated in the last but one block, effectively maintaining the top element. This step is crucial for accurately tracking the top element of the stack before its measurement.

If we consider the same scenario as above, assume the current stack contents [a, b, b, a], where the leftmost element is the stack top. If we pop an element, the new stack is [b, b, a]. Figure 12 shows the circuit used to compute the pop operation. Figure 12 illustrates the initial utilization of CNOT gates from aux3 to aux2. This operation is crucial because it activates aux2 before the reset of aux3, ensuring the preservation of the properties of the top element. Subsequently, the reset operation on the top element provides the essence of a pop operation, maintaining the fundamental properties of the stack.

While the auxiliary qubit approach offers advantages in minimizing swap gates and reducing error susceptibility, it comes with the limitation of requiring additional qubits. Each stack element now necessitates an auxiliary qubit, leading to increased qubit usage compared to traditional methods. This heightened qubit demand can pose challenges, especially in scenarios where qubit resources are limited. Therefore, while the auxiliary qubit approach improves error management and computational efficiency, its reliance on extra qubits must be carefully considered, particularly in resource-constrained quantum systems.

5. Conclusions

This paper provides a constructive methodology for defining a DPDA in the conventional sense and producing a quantum circuit equivalent to it. The construction follows a modular approach. The salient parts of the computation are compartmentalized as oracles. Circuit schemes for the oracles are presented. The approach followed is new and constructive. It presents a denotation for a stack in terms of quantum computation operations of tensor products and partial traces. An algorithm is presented to produce efficient quantum circuit generation, given a Boolean matrix defining a relation.

In the case of a DPDA, at any given time, only one instance of the stack will be valid. However, in the case of general PDA, at any given time during the computation, multiple valid stack instances will be present due to the many valid computation paths. This makes stack management difficult.

It should be observed that the circuit generation corresponding to DPDA transition has the effect of embedding a nonunitary matrix within a larger unitary matrix. So, even though the application of a quantum circuit is reversible, the nonunitary part of the computation may not be reversible. This can be illustrated by the following example. Consider the matrices $A=\left[\begin{array}{cc}1/2& 1/2\\ 0& 0\end{array}\right]$ and $U=\left[\begin{array}{c}0.5 0.5 0.7071 0\\ 0 0 0 1.0\\ 0.5 0.5 -0.7071 0\\ -0.7071 0.7071 0 0\end{array}\right]$, where A is a nonreversible computation embed in the unitary matrix U. Now, consider the vectors $x={\left[1,0,0,0\right]}^T$ and $y={[0,1,0,0]}^T$. Then $Ux={[0.5,0,0.5,-0.7071]}^T$ and $Uy={[0.5,0,0.5,0.7071]}^T$ which are different and hence reversible. However, A applied to ${[1,0]}^T$ and ${[0,1]}^T$ will be the same as ${[0.5,0]}^T$ and hence is not reversible.

The NISQ (Noisy Intermediate-Scale Quantum) era represents the current stage of quantum computing, characterized by devices with 50 to a few hundred qubits that are prone to noise and lack full error correction capabilities. While NISQ devices cannot yet perform fault-tolerant computations, they are capable of demonstrating quantum advantage on specific tasks and advancing research in quantum algorithms. This era focuses on leveraging available quantum hardware for practical applications, despite limitations, through noise mitigation techniques and algorithmic optimization.

On Noisy Intermediate-Scale Quantum (NISQ) devices, errors have a profound impact on implementing deterministic push-down automata (DPDA) in a quantum framework. Quantum gate errors, often due to low gate fidelity, can alter the precise state transitions essential for maintaining DPDA control, leading to incorrect results. Decoherence, where quantum states lose information quickly, is another significant issue since DPDA computations involve sequential state and stack transitions that rely on coherence over time. Additionally, qubit noise and readout inaccuracies can distort the state of auxiliary qubits used in stack operations, causing erroneous push and pop operations. Crosstalk between qubits during multi-qubit operations like controlled-NOT (CNOT) gates further jeopardizes computation accuracy, as unintended qubit interactions can disrupt the deterministic nature of state transitions. Stack management is especially vulnerable, as any inconsistency in auxiliary qubit states used to track stack elements could lead to misinterpretations of the stack’s contents. Each of these error sources challenges the practical deployment of DPDA on NISQ devices by compromising the deterministic reliability of state and stack operations, essential for quantum automata’s intended computational accuracy. Addressing these challenges with error-tolerant algorithms and optimized circuit designs could help, though these solutions require additional resources, increasing circuit depth and hardware demands. Developing effective error mitigation strategies and exploring efficient methods for stack management on NISQ devices could be valuable directions for future work

Additionally, the future works include developing efficient methodologies for managing multiple stack instances. This approach will aid in developing a constructive methodology to build a quantum circuit equivalent to any PDA.