A Framework for Quantum Finite-State Languages with Density Mapping

Symbols $\mathbb{R}$ and $\mathbb{C}$ denote the set of real numbers and the set of complex numbers, respectively. For a finite set $Q$ with $n$ elements, ${\mathbb{C}}^{Q}$ and ${\mathbb{C}}^{Q\times Q}$ denote the set of column vectors of dimensions $n$ and the set of matrices of sizes $(n,n)$ whose components are indexed by elements of $Q$ and $Q\times Q$, respectively. For an element $a\in Q$, $\ket{a}\in{\mathbb{C}}^{Q}$ is a unit vector whose components are all zero, except an $a$-indexed component. The set $\{\ket{a}\mid a\in Q\}$ is a standard basis of the vector space ${\mathbb{C}}^{Q\times 1}$. A vector $\psi\in{\mathbb{C}}^{Q\times 1}$ has a unique expression as a linear combination:

Then, $|\psi|:=\sqrt{\sum_{a\in Q}|\alpha_{a}|^{2}}$ denotes the length of $\psi$.

We use ${\mathbf{M}}^{T},{\mathbf{M}}^{-1}$, $\overline{{\mathbf{M}}}$ and ${\mathbf{M}}^{\dagger}$ to denote a transpose, inverse, conjugate and conjugate-transpose of a matrix ${\mathbf{M}}$, respectively. $\det{\mathbf{M}}$ denotes the determinant of a given matrix ${\mathbf{M}}$. A matrix ${\mathbf{U}}$ is considered unitary if it satisfies the equality: ${\mathbf{U}}^{-1}={\mathbf{U}}^{\dagger}$. Given a finite set $A$ of indices and a set $S\subseteq A$, a projection matrix ${\mathbf{P}}_{S}$ onto $S$ is a zero-one diagonal matrix where $({\mathbf{P}}_{S})_{(a,a)}=1$ if $a\in S$ and $({\mathbf{P}}_{S})_{(a,a)}=0$, otherwise. For matrices ${\mathbf{M}}_{1}\in{\mathbb{C}}^{A\times A}$ and ${\mathbf{M}}_{2}\in{\mathbb{C}}^{B\times B}$ with $A\cap B=\emptyset$, their direct sum is

A superposition of $n$ qubits is formalized as a $2^{n}$-dimensional complex vector with a length of 1, and its evolution is described by a unitary matrix. The basis vectors of the superposition are represented by $\ket{00\cdots 0},\ket{10\cdots 0},\ldots,\ket{11\cdots 1}$, where each digit corresponds to the value of each qubit. The measurement of the superposition is formalized by an observable, which is a partitioning $A_{1}\cup\cdots\cup A_{k}$ of the dimensions. When a superposition $\ket{\psi}$ is measured with an observable, it collapses to one of the vectors $\ket{\psi^{\prime}_{i}}:=P_{A_{i}}\ket{\psi}$, each with a probability $|\ket{\psi^{\prime}_{i}}|^{2}$.

A finite-state automaton (FA) is a model that simulates the behavior of a system changing its state between a fixed number of distinct states. The automaton updates its state in an online manner in response to external inputs—formalized as strings over a finite alphabet. A quantum finite-state automaton (QFA) is a quantum variant of FA, which can exist in a superposition comprised of a finite number of states. We consider two different types of QFAs: an MO-QFA, which is observed only at the end of sequential inputs [25], and an MM-QFA, which is observed after every step of the sequence [11].

Let $\Sigma$ denote a finite input alphabet, which consists of the symbols used in sequential input. A semi-QFA then describes the evolution of a QFA for each symbol. Fig. 2 shows how transitions of a semi-QFA are represented graphically.

We can define MO-QFAs and MM-QFAs as semi-QFAs with two defining distinctions: the inclusion of an initial state as well as that of final states, which are either accepting or rejecting.

An MO-QFA reads each symbol of string one by one and updates its superposition of states at each based on their transition matrix corresponding to the symbol. After reading the entire string, the MO-QFA measure the the superposition of states. It accepts the string if and only if the measured state is an accepting state; otherwise, it reject the string.

Formally, for a string $x=x_{1}x_{2}\cdots x_{n}\in\Gamma^{*}$ on the tape alphabet, we denote the unitary matrix ${\mathbf{U}}_{x_{n}}{\mathbf{U}}_{x_{n-1}}\cdots{\mathbf{U}}_{x_{1}}$ as ${\mathbf{U}}_{x}$. We also denote ${\mathbf{P}}_{Q_{\textsf{acc}}}$, ${\mathbf{P}}_{Q_{\textsf{rej}}}$ and ${\mathbf{P}}_{Q_{\textsf{non}}}$ as ${\mathbf{P}}_{\textsf{acc}}$, ${\mathbf{P}}_{\textsf{rej}}$ and ${\mathbf{P}}_{\textsf{non}}$, respectively, for simplicity of notation. Then, the probability of an MO-QFA $M$ accepting string $w$ is $|{\mathbf{P}}_{\textsf{acc}}\ket{\psi}|^{2}$, where $\ket{\psi}$ is the superposition ${\mathbf{U}}_{{\#}w{\$}}\ket{q_{\textsf{init}}}$ of the QFA after reading the end-of-string symbol.

The MM-QFA reads the tape symbols one by one for a given string and updates the superposition according to the transition matrix, similar to MO-QFAs. However, unlike MO-QFAs, it measures their superposition at the end of each step, causing it to collapse onto one of three sub-spaces ${\mathbb{C}}^{Q_{\textsf{acc}}}$, ${\mathbb{C}}^{Q_{\textsf{rej}}}$ or ${\mathbb{C}}^{Q_{\textsf{non}}}$. The MM-QFA then accept or reject the string immediately if the resulting superposition is on ${\mathbb{C}}^{Q_{\textsf{acc}}}$ the MM-QFA $M$or ${\mathbb{C}}^{Q_{\textsf{rej}}}$, respectively. Otherwise, it keeps reading the next symbol.

Kondacs and Watrous [11] introduced total states to formalize the decision process of MM-QFAs. A total state is a triple $(\psi,p^{\prime}_{\textsf{acc}},p^{\prime}_{\textsf{rej}})\in{\mathbb{C}}^{Q}\times{\mathbb{R}}\times{\mathbb{R}}$, where $p^{\prime}_{\textsf{acc}}$ and $p^{\prime}_{\textsf{rej}}$ are the accumulated probabilities of acceptance and rejection. The vector $\psi$ denotes the superposition and the probability of non-halting by its direction and the square of its length, respectively. For an MM-QFA $M$, $T_{\gamma}$ is an evolution function of the internal state of $M$ with respect to $\gamma$ defined as follows:

where

For a string $x=x_{1}x_{2}\cdots x_{n}\in\Gamma^{*}$ on the tape alphabet, we use $T_{x}$ to denote $T_{x_{n}}\circ T_{x_{n-1}}\circ\cdots\circ T_{x_{1}}$. Then, $(\psi,p_{\textsf{acc}},p_{\textsf{rej}}):=T_{{\#}w{\$}}(\ket{q_{\textsf{init}}},0,0)$ denotes the final total state, and $p_{\textsf{acc}}$ is the probability that $M$ accepts a given string $w$.

We say that an MM-QFA $M$ is valid if $p_{\textsf{acc}}+p_{\textsf{rej}}=1$ for any $w\in\Sigma^{*}$. If $p_{\textsf{acc}}=0$ for every $w\in\Sigma^{*}$ such that $(\_,p_{\textsf{acc}},\_):=T_{{\#}w}(\ket{q_{\textsf{init}}},0,0)$, then we say that $M$ is end-decisive. In other words, $M$ does not accept strings before reading the end-of-string symbol. Similarly, $M$ is co-end-decisive if it only rejects strings when reading the end-of-string symbol [12]. For the rest of the paper, we focus solely on valid MM-QFAs.

Let $M$ be an MO-QFA or an MM-QFA and $f_{M}(w)$ denote the probability that a given $M$ accepts $w$. We call the function $f_{M}:\Sigma^{*}\to\mathbb{R}$ the stochastic language of $M$. We say an MO- or MM-QFA $M$ recognizes $L$ with a positive one-sided error of margin $\varepsilon>0$ if (1) $f_{M}(w)=0$ for $w\notin L$ and (2) $f_{M}(w)>\varepsilon$. In other words, $M$ always rejects $w\notin L$ and accepts $w\in L$ with probability $f_{M}(w)>\varepsilon$. Similarly, we say $M$ recognizes $L$ with a negative one-sided error of margin $\varepsilon>0$ if (1) $f_{M}(w)=1$ for $w\in L$ and (2) $f_{M}(w)<1-\epsilon$ for $w\notin L$.

We define the following classes of quantum finite-state languages (QFLs) ${\mathsf{MOQFL}}$, ${\mathsf{MMQFL}}$, ${\mathsf{MMQFL}}_{\mathsf{end}}$ and ${\mathsf{MMQFL}}_{\mathsf{coend}}$ as those recognized by MO-QFAs, MM-QFAs, end-decisive MM-QFAs and co-end-decisive MM-QFAs, respectively. We also define the class of complements for each language family, which are denoted using a prefix ${\mathsf{co}}$-. For example, ${\mathsf{co\text{-}MOQFL}}$ denotes the class $\left\{L\subseteq\Sigma^{*}\mid\overline{L}\in{\mathsf{MOQFL}}\right\}$.

Stochastic languages of QFAs possess known closure properties, specific to MO-QFAs under the following operations [25, 13, 26].

1. (Hadamard product)

   $(f_{M}\otimes f_{N})(w)=f_{M}(w)\cdot f_{N}(w)$

2. (Convex linear combination)

   For $c_{1},c_{2}\in[0,1]$ with $c_{1}+c_{2}=1$,

   $$(c_{1}f_{M}\oplus c_{2}f_{N})(w)=c_{1}\cdot f_{M}(w)+c_{2}\cdot f_{N}(w)$$

3. (Complement)

   $\overline{f_{M}}(w)=1-f_{M}(w)$

4. (Inverse homomorphism)

   $(h^{-1}\circ f_{M})(w)=f_{M}(h^{-1}(w))$

Compared to the stochastic languages of MO-QFAs, those of MM-QFAs are closed under linear combination, complement and inverse homomorphism [13, 27] but not under the Hadamard product. For the cases of end-decisive and co-end-decisive MM-QFAs, their stochastic languages are closed under linear combination and inverse homomorphism. However, end-decisive MM-QFAs, in particular, are also closed under the Hadamard product [27]. Table 1 summarizes the closure properties of stochastic languages of QFAs. We also present a construction for the convex linear combination to complete the paper.

We settled on small and simple QFAs as the building blocks of our framework and give the characteristics and properties of two QFAs ${\mathsf{MOD}}_{n}$ and ${\mathsf{EQU}}_{k}$.

First, we revisit ${\mathsf{MOD}}_{n}:=\{a^{j}\mid j\equiv 0\mod n\}$ that has several previous approaches due to its small and simple circuit [16]. It is known that there exists a two-state MO-QFA that recognizes the language ${\mathsf{MOD}}_{n}$ with a negative one-sided bounded error. Furthermore, for each prime $p$, there exists an $O(\log p)$-state MO-QFA recognizing ${\mathsf{MOD}}_{p}$ with an error margin of $1/8$, which is independent of the choice of $p$. The circuit of ${\mathsf{MOD}}_{n}$ and ${\mathsf{MOD}}_{p}$ requires only one and $O(\log{\log p})$ qubits, respectively [28]. Next, we present our construction of an MM-QFA for ${\mathsf{EQU}}_{k}:=\{a^{k}\}$.

One might need to execute the QFA matching process multiple times to obtain a correct result, as the probability of obtaining the correct results decreases with the increasing length of the input string. The subsequent theorem describes how many repetitions are required to achieve a predetermined probability of accuracy.

Note that Theorems 1 and 2 examine the condition where parameters $\theta$ and $\varphi$ are chosen independently to the target language $L_{k}$. The following proposition describes how our framework finds optimal parameters that maximize the error margin for each $k$.

In our framework, we consider Boolean operation over ${\mathsf{QFL}}$, and distinguish the closure and error-bound properties of each operation. The closure operations are considered for each language class: ${\mathsf{MOQFL}}$, ${\mathsf{MMQFL}}$, ${\mathsf{MMQFL}}_{\mathsf{end}}$ and ${\mathsf{MMQFL}}_{\mathsf{coend}}$. These also include the basic constructions of each language. Unlike other classes that are defined based on cut-points as mentioned in previous literature[12, 28], the properties of these classes have only been indirectly discussed. We examine properties of one-sided error-bounded languages, including closure properties for operations, to clarify how our framework supports the operations.

From an MO- and MM-QFA, we can obtain their complement QFAs by exchanging the set of accepting states and the set of rejecting states. We establish the following properties from the construction that transforms an end-decisive MM-QFA from a co-end-decisive MM-QFA and vice versa.

The proof of Property 1 follows from the closure property of stochastic languages of QFAs under complement.

We show that the operations are closed under stochastic language and correlate with the properties of QFLs.

The next statement directly follows the fact that there exists a co-end-decisive MM-QFA for each unary finite language. The corollary leverages the closure property of ${\mathsf{MMQFL}}_{\mathsf{coend}}$ with regard to its union and the concept of singleton language construction from Theorem 1.

Table 2 summarizes the upper bounds of operational complexities as well as the complexities of inverse homomorphism and word quotient—both of which can be easily established from the their constructions [25, 12].

We propose a technique called density ($\mathcal{D}$-) mapping which is applied before the transpilation stage of the quantum circuit. Rather than mapping QFA states to qubit basis vectors in an arbitrary manner, our $\mathcal{D}$-mapping reorders these vectors based on the number of qubits with value $1$. Then we assign the accepting and rejecting states to the basis vectors with a low and high number of qubits having the value $1$, respectively.

$\mathcal{D}$-mapping maximizes the localization of accepting and rejecting states, thereby reducing the probability of bit-flip errors. These errors can arise from a decoherence or depolarization, and causes an accepting state to change into a rejecting state, and vice versa. Additionally, the basis vectors representing the accepting and rejecting states are separated by basis mapped to non-final states and basis that are not mapped to any states. This method helps to isolate the errors and reduce possible error situations. Fig. 3 conceptually illustrates how our proposal reduces a bit-flip error from altering the acceptance of a QFA.

We measured the ${\mathsf{MOD}}_{5}$ language using the Falcon processor, as depicted in Fig. 4. This measurement was to demonstrate the current capabilities and state of quantum computers. Note that the automaton of ${\mathsf{MOD}}_{5}$ accepts strings of length divisible by $5$ with probability $1$. Otherwise, it accepts the string with a probability less than 0.875. However, we can see that the measurements for the real-world computer accept strings with a probability close to 0.5. We analyze the low accuracy attributed to the large size of the resulting quantum circuit, exceeding 1,000 gates for even a length 2 input.

We also notice despite the small error rates of the simulator, the output of the simulator becomes inaccurate as the length of the string becomes longer. The inaccuracy is caused by the size of the circuit that grows linearly to the length of the input string. The accumulated errors eventually dominate and reduce the output closer to random guessing.

Our experiments from this point on are conducted using a quantum simulator to focus on the effectiveness of $\mathcal{D}$-mapping. We use error mirroring rates designed to reflect the capabilities of near-future quantum computers with error suppression and mitigation.

We demonstrate the usefulness of our $\mathcal{D}$-mapping for emulating QFAs. We evaluate the accepting probability of input strings with the automaton of ${\mathsf{MOD}}_{5}$ implemented by quantum circuits. Fig. 5 compares the experimental results for two quantum circuits recognizing ${\mathsf{MOD}}_{5}$, one utilizes our mapping and the other does not.

The experimental results confirm that $\mathcal{D}$-mapping increases the accuracy of the simulation for most cases. The mapping increases the accepting probability of strings in ${\mathsf{MOD}}_{5}$ up to length $30$ and decreases the accepting probability of strings that are not in ${\mathsf{MOD}}_{5}$. The effectiveness of $\mathcal{D}$-mapping diminishes with longer strings. Both mapping methods are increasingly affected by accumulating errors as discussed in Section 4.1, resulting in similar outcomes.

Table 3 presents the mean absolute percentage error (MAPE) of the experimental results for ${\mathsf{MOD}}_{p}$ and ${\mathsf{EQU}}_{k}$ implementations using the naive mapping and $\mathcal{D}$-mapping. Each cell denotes the dissimilarity between ideal probabilities $P(w_{i})$ and measured $\overline{P}(w_{i})$ for inputs $w_{1},\ldots,w_{n}$, and a simulation with a lower MAPE indicates higher accuracy. MAPE is calculated as follows:

We use strings with length from $2$ to $40$ to compute the MAPE for each language. Note that the maximum achievable value of MAPE varies for each language, hence we cannot directly compare simulation accuracy between different languages using MAPE. For instance, consider the following cases: (1) $\eta_{g}=0.1\%$ and $\eta_{r}=0.1\%$; and (2) $\eta_{g}=1\%$ and $\eta_{r}=1\%$, where the latter case has greater error rate. Nevertheless, we use the according formulation to shows the difference between probabilities and its difference.

The experimental results indicate that $\mathcal{D}$-mapping is effective for QFAs of languages ${\mathsf{MOD}}_{3}$, ${\mathsf{MOD}}_{5}$, but not for ${\mathsf{MOD}}_{7}$. $\mathcal{D}$-mapping reduces the difference between the accepting probabilities of ideal results and simulation for ${\mathsf{MOD}}_{3}$ to $57.43\%(1.43/2.49)$ of the former case and $46.24\%(11.31/24.46)$ of the latter case. Similarly, for ${\mathsf{MOD}}_{5}$, $\mathcal{D}$-mapping reduces the difference to $80.49\%$ and $59.97\%$ of the former and latter case, respectively.

Note that the number of quantum circuit for ${\mathsf{MOD}}_{p}$ increases with the growth of $p$. We observe that the effect of $\mathcal{D}$-mapping is not evident for ${\mathsf{MOD}}_{7}$, as the simulation remains inaccurate regardless of the mapping used. This emphasizes the challenge posed by the large size of ${\mathsf{MOD}}_{7}$ QFAs and the resulting quantum circuits, which involve a significant number of gates.

We also examine the impact of $\mathcal{D}$-mapping on QFAs of ${\mathsf{EQU}}_{n}$, although its effect is less pronounced compared to ${\mathsf{MOD}}_{p}$. Note that QFAs of ${\mathsf{EQU}}_{n}$ are MM-QFAs. Unlike MO-QFAs for ${\mathsf{MOD}}_{p}$, simulations of MM-QFAs have the possibility of terminating before reading all symbols in each string. We suggest that the simulation for MM-QFAs receives less effect from gate errors because they may ignore trailing gates, thereby resulting in the reduced effectiveness of $\mathcal{D}$-mapping.

The overall experimental results reveal that gate error rates dominate simulation accuracy for QFAs, and our experiments do not show a clear relation between readout error rates and simulation accuracy. This is primarily due to the fact that the quantum circuits for QFAs have few measurement gates.