2 Preliminaries on Quantum Computing and QFA

For the sake of readability, in this section we outline basic notations and principles in quantum computing and review the definitions of MO-1QFA, MM-1QFA, and RFA. For more details, we can refer to Nielsen and Chuang (Reference Nielsen and Chuang2000) and Qiu et al. (Reference Qiu, Li, Mateus, Gruska and Wang2012), Say and Yakaryılmaz (2014), Ambainis and Yakaryilmaz (Reference Ambainis, Yakaryilmaz and Pin2021), and Bhatia and Kumar (Reference Bhatia and Kumar2019).

2.1 Basics in quantum computing

Let $\mathbb{C}$ denote the set of all complex numbers, $\mathbb{R}$ the set of all real numbers, and $\mathbb{C}^{n\times m}$ the set of $n\times m$ matrices having entries in $\mathbb{C}$ . Given two matrices $A\in \mathbb{C}^{n\times m}$ and $B\in\mathbb{C}^{p\times q}$ , their tensor product is the $np\times mq$ matrix, defined as

$$A\otimes B=\begin{bmatrix} A_{11}B & \dots & A_{1m}B \\ \vdots & \ddots & \vdots \\ A_{n1}B &\dots & A_{nm}B \ \end{bmatrix}.$$

$(A\otimes B)(C\otimes D)=AC\otimes BD$ holds if the multiplication of matrices is satisfied.

If $MM^\dagger=M^\dagger M=I$ , then matrix $M\in\mathbb{C}^{n\times n}$ is unitary, where $\dagger$ denotes conjugate-transpose operation. M is said to be Hermitian if $M=M^\dagger$ . For n-dimensional row vector $x=(x_1,\dots, x_n)$ , its norm $||x||$ is defined as $||x||=\big(\sum_{i=1}^n x_ix_i^{*}\big)^{\frac{1}{2}}$ , where symbol $*$ denotes conjugate operation. Unitary operations preserve the norm, i.e., $||xM||=||x||$ for each $x\in \mathbb{C}^{1\times n}$ and any unitary matrix $M\in\mathbb{C}^{n\times n}$ .

According to the basic principles of quantum mechanics (Nielsen and Chuang, Reference Nielsen and Chuang2000), a state of quantum system can be described by a unit vector in a Hilbert space. More specifically, let $B=\{q_1,\dots,q_n\}$ associated with a quantum system denote a basic state set, where every basic state $q_i$ can be represented by an n-dimensional row vector $\langle q_i|=(0\dots1\dots0)$ having only 1 at the ith entry (where $\langle \cdot|$ is Dirac notation, i.e., bra-ket notation). At any time, the state of this system is a superposition of these basic states and can be represented by a row vector $\langle \phi|=\sum_{i=1}^nc_i\langle q_i|$ with $c_i\in\mathbb{C}$ and $\sum_{i=1}^n|c_i|^2=1$ ; $|\phi\rangle$ represents the conjugate-transpose of $\langle \phi|$ . So, the quantum system is described by Hilbert space $\mathcal{H}_Q$ spanned by the base $\{|q_i\rangle: i=1,2,\dots,n\}$ , i.e. $\mathcal{H}_Q=span\{| q_i\rangle: i=1,2,\dots,n\}$ .

The state evolution of quantum system complies with unitarity. Suppose the current state of system is $|\phi\rangle$ . If it is acted on by some unitary matrix (or unitary operator) $M_1$ , then $|\phi\rangle$ is changed to the new current state $M_1|\phi\rangle$ ; if the second unitary matrix, say $M_2$ , is acted on $M_1|\phi\rangle$ , then $M_1|\phi\rangle$ is changed to $M_2 M_1|\phi\rangle$ . So, after a series of unitary matrices $M_1, M_2, \ldots, M_k$ are performed in sequence, the system’s state becomes $M_kM_{k-1}\cdots M_1|\phi\rangle$ .

To get some information from the quantum system, we need to make a measurement on its current state. Here we consider projective measurement (i.e. von Neumann measurement). A projective measurement is described by an observable that is a Hermitian matrix $\mathcal{O}=c_1P_1+\dots +c_s P_s$ , where $c_i$ is its eigenvalue and, $P_i$ is the projector onto the eigenspace corresponding to $c_i$ . In this case, the projective measurement of $\mathcal{O}$ has result set $\{c_i\}$ and projector set $\{P_i\}$ . For example, given state $|\psi\rangle$ is made by the measurement $\mathcal{O}$ , then the probability of obtaining result $c_i$ is $\|P_i|\psi\rangle\|^2$ and the state $|\psi\rangle$ collapses to $\frac{P_i|\psi\rangle}{\|P_i|\psi\rangle\|}$ .

2.2 Review of one-way QFA and RFA

For non-empty set $\Sigma$ , by $\Sigma^{*}$ we mean the set of all finite length strings over $\Sigma$ , and $\Sigma^n$ denotes the set of all strings over $\Sigma$ with length n. For $u\in \Sigma^{*}$ , $|u|$ is the length of u; for example, if $u=x_{1}x_{2}\ldots x_{m}\in \Sigma^{*}$ where $x_{i}\in \Sigma$ , then $|u|=m$ . For set S, $|S|$ denotes the cardinality of S.

2.2.1 MO-1QFA

We recall the definition of MO-1QFA. An MO-1QFA with n states and input alphabet $\Sigma$ is a five-tuple

(1) \begin{equation}\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r) \end{equation}

where

• • $Q=\{|q_1\rangle,\dots,|q_n\rangle\}$ consist of an orthonormal base that spans a Hilbert space $\mathcal{H}_Q$ ( $|q_i\rangle$ is identified with a column vector with the ith entry 1 and the others 0); at any time, the state of $\mathcal{M}$ is a superposition of these basic states;

• • $|\psi_0\rangle\in \mathcal{H}$ is the initial state;

• • for any $\sigma\in \Sigma$ , $U(\sigma)\in \mathbb{C}^{n\times n}$ is a unitary matrix;

• • $Q_a, Q_r\subseteq Q$ with $Q_a\cup Q_r=Q$ and $Q_a\cap Q_r=\emptyset$ are the accepting and rejecting states, respectively, and it describes an observable by using the projectors $P(a)=\sum_{|q_i\rangle\in Q_a}|q_i\rangle\langle q_i|$ and $P(r)=\sum_{|q_i\rangle\in Q_r}|q_i\rangle\langle q_i|$ , with the result set $\{a,r \}$ of which “a” and “r” denote “accepting” and “rejecting”, respectively. Here Q consists of accepting and rejecting sets.

Given an MO-1QFA $\mathcal{M}$ and an input word $s=x_1\dots x_{n}\in\Sigma^{*}$ , then starting from $|\psi_0\rangle$ , $U(x_1),\dots,U(x_n)$ are applied in succession, and at the end of the word, a measurement $\{P(a),P(r)\}$ is performed with the result that $\mathcal{M}$ collapses into accepting states or rejecting states with corresponding probability. Hence, the probability $L_\mathcal{M}(x_1\dots x_n)$ of $\mathcal{M}$ accepting w is defined as:

(2) \begin{align}L_\mathcal{M}(x_1\dots x_n)=\|P(a)U_s|\psi_0\rangle\|^2\end{align}

where we denote $U_s=U_{x_n}U_{x_{n-1}}\cdots U_{x_1}$ .

2.2.2 RFA

Now we recollect RFA. As mentioned above, there are three equivalent definitions for RFA (Qiu, Reference Qiu2007), that is, group automata, BM-reversible automata, and AF-reversible automata. Here we describe group automata. First we review DFA. A DFA $G=(S, s_0, \Sigma, \delta, S_a)$ , where S is a finite state set, $s_0\in S$ is its initial state, $S_a\subseteq S$ is its accepting state set, $\Sigma$ is an input alphabet, and $\delta$ is a transformation function, i.e., a mapping $\delta: S\times \Sigma\rightarrow S$ .

An RFA (group automaton) $G=(S, s_0, \Sigma, \delta, S_a)$ is DFA and satisfies that for any $q\in S$ and any $\sigma\in\Sigma$ , there is unique $p\in S$ such that $\delta(p,\sigma)=q$ .

The languages accepted by MO-1QFA with bounded error are exactly the languages accepted by RFA (Brodsky and Pippenger, Reference Brodsky and Pippenger2002). In fact, RFA are the special cases of MO-1QFA, and this is showed by the following proposition.

Proposition 1. (1) For any MO-1QFA $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r) $ with $|\psi_0\rangle\in Q$ , if all entries in $U(\sigma)$ for each $\sigma\in \Sigma$ are either 0 or 1, then $\mathcal{M}$ is actually a group automaton. (2) If $G=(S, s_0, \Sigma, \delta, S_a)$ is a group automaton, then G is actually an MO-1QFA.

Proof.

1. (1) Suppose the base states $Q=\{|q_i\rangle: i=1,2,\ldots,n\}$ , where $|q_i\rangle$ is an n-dimensional column vector with the ith entry 1 and the others 0. Let $|\psi_0\rangle=|q_{i_0}\rangle$ for some $i_0\in \{1,2,\ldots,n\}$ . It is clear that $U(\sigma)$ (for each $\sigma\in\Sigma$ ) is a permutation matrix and therefore $U(\sigma)$ is also a bijective mapping from Q to Q. So, $\mathcal{M}$ is a group automaton.

2. (2) If $G=(S, s_0, \Sigma, \delta, S_a)$ is a group automaton with $|S|=n$ , then we denote $S=\{q_1,q_2,\ldots, q_n\}$ and $s_0$ is some $q_i\in S$ . According to the definition of group automata, for each $\sigma\in\Sigma$ , $\delta(\cdot,\sigma)$ is a bijective mapping from S to S. So, we can identify $q_i$ with an n-dimensional column vector with the ith entry 1 and the others 0. Then for each $\sigma\in\Sigma$ , $\delta(\cdot,\sigma)$ induces a unitary matrix $U(\sigma)$ acting on the n-dimensional Hilbert space spanned by the base states S. Finally, $S_a\subseteq S$ and $S_r=S\setminus S_a$ are accepting and rejecting sets of states, respectively. As a result, G is actually equivalent to an MO-1QFA.

2.2.3 MM-1QFA

We review the definition of MM-1QFA. Formally, given an input alphabet $\Sigma$ and an end-maker $\$\notin\Sigma$ , an MM-QFA with n states over the working alphabet $\Gamma=\Sigma\cup\{\$\}$ is a six-tuple $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r,Q_g)$ , where

• • Q, $|\psi_0\rangle$ , and $U(\sigma)$ ( $\sigma\in \Gamma$ ) are defined as in the case of MO-1QFA; $Q_a,Q_r,Q_g$ are disjoint to each other and represent the accepting, rejecting, and going states, respectively.

• • The measurement is described by the projectors P(a), P(r), and P(g), with the results in $\{a,r,g \}$ of which “a,” “r,” and “g” denote “accepting,” “rejecting,” and “going on,” respectively.

Any input word w to MM-1QFA is in the form: $w\in\Sigma^{*}\$$ , with symbol $\$$ denoting the end of a word. Given an input word $x_1\dots x_n\$$ where $x_1\dots x_n\in \Sigma^n$ , MM-1QFA $\mathcal{M}$ performs the following computation:

• 1. Starting from $|\psi_0\rangle$ , $U(x_1)$ is applied, and then we get a new state $|\phi_1\rangle= U(x_1)|\psi_0\rangle$ . In succession, a measurement of $\mathcal{O}$ is performed on $|\phi_1\rangle$ , and then the measurement result i ( $i\in \{a,g,r\}$ ) is yielded as well as a new state $|\phi_1^{i}\rangle=\frac{P(i)|\phi_1\rangle}{\sqrt{p_1^i}}$ is obtained, with corresponding probability $p_1^i=||P(i)|\phi_1\rangle||^2$ .

• 2. In the above step, if $|\phi_1^{g}\rangle$ is obtained, then starting from $|\phi_1^{g}\rangle$ , $U(x_2)$ is applied and a measurement $\{P(a),P(r),P(g)\}$ is performed. The evolution rule is the same as the above step.

• 3. The process continues as far as the measurement result “g” is yielded. As soon as the measurement result is “a” (“r”), the computation halts and the input word is accepted (rejected).

Thus, the probability $L_\mathcal{M}(x_1\dots x_n)$ of $\mathcal{M}$ accepting w is defined as:

(3) \begin{align} &L_\mathcal{M}(x_1\dots x_{n})\end{align}

(4) \begin{align}=&\sum^{n+1}_{k=1}||P(a)U(x_k) \prod^{k-1}_{i=1}\big(P(g)U(x_i)\big) |\psi_0\rangle ||^2,\end{align}

or equivalently,

(5) \begin{align}&L_\mathcal{M}(x_1\dots x_{n})\end{align}

(6) \begin{align}=&\sum^{n}_{k=0}||P(a)U(x_{k+1}) \prod^{k}_{i=1}\big(P(g)U(x_i)\big) |\psi_0\rangle ||^2,\end{align}

where, for simplicity, we can denote $\$$ by $x_{n+1}$ if no confusion results.

3 Learning MO-1QFA

First we recall a definition concerning model learning with an oracle in polynomial time.

In order to learn a model with polynomial time via an oracle, we hope this oracle is as weaker as possible. For learning MO-1QFA, suppose an oracle can only answer the amplitudes of accepting states for each input string, then can we learn MO-1QFA successfully with polynomial time via such an oracle? We name such an oracle as ${\boldsymbol{AA}}$ oracle. For clarifying this point, we try to use ${\boldsymbol{AA}}$ oracle to learning DFA. In this case, ${\boldsymbol{AA}}$ oracle can answer if it is either an accepting state or a rejecting state for each input string. Equivalently, ${\boldsymbol{AA}}$ oracle is exactly MQ for learning DFA as the target model. Therefore, learning DFA via ${\boldsymbol{AA}}$ oracle is not polynomial by virtue of the following Angluin’s result (Angluin, Reference Angluin1988).

Therefore, we have the following proposition.

For learning DFA and RFA, ${\boldsymbol{AA}}$ oracle is exactly equal to MQ oracle, so we conclude that DFA and MO-1QFA are not learnable using ${\boldsymbol{AA}}$ oracle only.

So, we consider a stronger oracle, named as ${\boldsymbol{AD}}$ oracle that can answer all amplitudes (instead of the amplitudes of accepting states only) of the superposition state for each input string. For example, for quantum state $|\psi\rangle=\sum_{i=1}^{n}\alpha_i|q_i\rangle$ where $\sum_{i=1}^{n}|\alpha_i|^2=1$ , ${\boldsymbol{AA}}$ oracle can only answer the amplitudes of accepting states in $\{|q_1\rangle, |q_2\rangle, \ldots, |q_n\rangle\}$ , but ${\boldsymbol{AD}}$ oracle can answer the amplitudes for all states in $\{|q_1\rangle, |q_2\rangle, \ldots, |q_n\rangle\}$ . Using ${\boldsymbol{AD}}$ oracle, we can prove that MO-1QFA and MM-1QFA are polynomially learnable. Therefore, for learning DFA or RFA, ${\boldsymbol{AD}}$ oracle can answer a concrete state for each input string, where the concrete state is the output state of the target automaton to be learned.

First we can easily prove that RFA are linearly learnable via ${\boldsymbol{AD}}$ oracle, and this is the following proposition.

Our main concern is whether ${\boldsymbol{AD}}$ oracle is too strong, that is to say, whether ${\boldsymbol{AD}}$ oracle possesses too much information for our learning tasks. To clarify this point partially, we employ a consistency problem that, in a way, demonstrates ${\boldsymbol{AD}}$ oracle is really not too strong for our model learning if the time complexity is polynomial. So, we first recall an outcome from Tzeng (Reference Tzeng1992).

Let $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r) $ be the target MO-1QFA to be learned, where, as the case of learning PFA (Tzeng, Reference Tzeng1992), the learner is supposed to have the information of $Q, Q_a, Q_r$ , but the other parameters are to be learned by mean of querying the oracle for achieving an equivalent MO-1QFA (more concretely, for each $\sigma\in\Sigma$ , unitary matrix $V(\sigma)$ corresponding to $U(\sigma)$ needs to be determined, but it is possible that $V(\sigma)\not=U(\sigma)$ ). For any $x\in\Sigma^*$ , ${\boldsymbol{AD}}(x)$ can answer an amplitude distribution that is exactly equivalent to a state of superposition corresponding to the input string x, more exactly, ${\boldsymbol{AD}}(x)$ can answer the same state as $U(\sigma_k)U(\sigma_{k-1})\cdots U(\sigma_1)|\psi_0\rangle$ where $x=\sigma_1\sigma_2\cdots\sigma_k$ . From now on, we denote $U(x)=U(\sigma_k)U(\sigma_{k-1})\cdots U(\sigma_1)$ for $x=\sigma_1\sigma_2\cdots\sigma_k$ .

We outline the basic idea and method for designing the learning algorithm of MO-1QFA $\mathcal{M}$ . First, the initial state can be learned from ${\boldsymbol{AD}}$ oracle by querying empty string $\varepsilon$ . Then by using ${\boldsymbol{AD}}$ oracle we continue to search for a base of the Hilbert space spanned by $\{v^*=U(x)|\psi_0\rangle: x\in\Sigma^*\}$ . This procedure will be terminated since the dimension of the space is at most $|Q|$ . In fact, we can prove this can be finished in polynomial time. Finally, by virtue of the learned base and solving groups of linear equations we can conclude $V(\sigma)$ for each $\sigma\in\Sigma$ . We prove these results in detail following the algorithm and now present Algorithm 1 for learning MO-1QFA as follows.

Algorithm 1

Algorithm for learning MO-1QFA $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r) $

Next we prove the correctness of Algorithm 1 and then analyze its complexity. First we prove that Step 1 to Step 12 in Algorithm 1 can produce a set of vectors $\mathcal{B}$ consisting of a base of space spanned by $\{v^*(x)| x\in\Sigma^*\}$ , where $v^*(x)=\boldsymbol{AD}(x)$ is actually the vector replied by oracle $\boldsymbol{AD}$ for input string x, that is, $v^*(x)={\boldsymbol{AD}}(x)=U(\sigma_k)U(\sigma_{k-1})\ldots U(\sigma_1)|\psi_0\rangle$ , for $x=\sigma_1\sigma_2\ldots\sigma_k$ .

Proof. From the algorithm procedure we can assume that $\mathcal{B}=\{v^*(x_1), v^*(x_2),\ldots,v^*(x_m)\}$ for some m, where it is clear that some $x_i$ equals to $\varepsilon$ , and for any $x\in\Sigma^*$ , there are $x_j$ and $y\in\Sigma^*$ such that $x=x_jy$ . The rest is to show that $v^*(x)$ can be linearly represented by the vectors in $\mathcal{B}$ for any $x\in\Sigma^*$ . Let $x=x_jy$ for some $x_j$ and $y\in\Sigma^*$ . By induction on the length $|y|$ of y. If $|y|=0$ , i.e., $y=\varepsilon$ , then it is clear for $x=x_j$ . If $|y|=1$ , then due to the procedure of algorithm, $v^*(x_jy)$ is linearly dependent on $\mathcal{B}$ . Suppose that it holds for $|y|=k\geq 0$ . Then we need to verify it holds for $|y|=k+1$ . Denote $y=z\sigma$ with $|z|=k$ . Then with induction hypothesis we have $v^*(x_jz)= \sum_{k}c_kv^*(x_k)$ . Therefore, we have

(7) \begin{align}v^*(x)&=v^*(x_jz\sigma)\nonumber\\&=U(\sigma)v^*(x_jz)\nonumber\\&=U(\sigma)\sum_{k}c_kv^*(x_k)\nonumber\\&=\sum_{k}c_kv^*(x_k\sigma). \end{align}

Since $v^*(x_k\sigma)$ is linearly dependent on $\mathcal{B}$ for $k=1,2,\ldots,m$ , the proof is completed.

The purpose of Algorithm 1 is to learn the target MO-1QFA $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r)$ , so we need to verify $\mathcal{M}^*=(Q, |\psi_0^*\rangle,\{V(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r)$ obtained is equivalent to $\mathcal{M}$ . For this, it suffices to check $V(x)|\psi_0^*\rangle=U(x)|\psi_0\rangle$ for any $x\in\Sigma^*$ , where $V(x)=V(\sigma_s)V(\sigma_{s-1})\ldots V(\sigma_1)$ and $U(x)=U(\sigma_s)U(\sigma_{s-1})\ldots U(\sigma_1)$ for $x=\sigma_1\sigma_2\ldots\sigma_s$ .

Theorem 4. In Algorithm 1 for learning MO-1QFA, for any $x\in\Sigma^*$ ,

(8) \begin{equation} V(x)|\psi_0^*\rangle=U(x)|\psi_0\rangle. \end{equation}

For any $\sigma\in\Sigma$ and for any $ v^*(x) \in \mathcal{B}$ , according to Algorithm 1, we have $\ V(\sigma)v^*(x)=v^*(x\sigma)={\boldsymbol{AD}}(x\sigma)$ . In particular, taking $x=\varepsilon$ , then we have $\ V(\sigma)|\psi_0^*\rangle=v^*(\sigma)={\boldsymbol{AD}}(\sigma)=U(x)|\psi_0\rangle$ .

Suppose it holds for $|x|= k$ . The rest is to prove that it holds for $|x|= k+1$ . Denote $y=x\sigma$ where $|x|= k$ and $\sigma\in\Sigma$ . Due to Proposition 4, $v^*(x)$ can be linearly represented by $\mathcal{B}=\{v^*(x_1), v^*(x_2),\ldots,v^*(x_m)\}$ , i.e., $v^*(x)=\sum_{k}c_kv^*(x_k)$ for some $c_k\in \mathbb{C}$ . With the induction hypothesis, $V(x)|\psi_0^*\rangle=U(x)|\psi_0\rangle$ holds. Then by means of Algorithm 1, we have

(9) \begin{align}V(y)|\psi_0^*\rangle &=V(x\sigma)|\psi_0^*\rangle \nonumber\\&=V(\sigma)V(x)|\psi_0^*\rangle \nonumber\\&=V(\sigma)U(x)|\psi_0\rangle \nonumber\\&=V(\sigma)v^*(x)\nonumber\\&=V(\sigma)\sum_{k}c_kv^*(x_k)\nonumber\\&=\sum_{k}c_kV(\sigma)v^*(x_k)\nonumber\\&=\sum_{k}c_kv^*(x_k\sigma). \end{align}

On the other hand, since $v^*(z)={\boldsymbol{AD}}(z)=U(z)|\psi_0\rangle$ for any $z\in \Sigma^*$ , we have

(10) \begin{align}\sum_{k}c_kv^*(x_k\sigma)&=\sum_{k}c_kU(x_k\sigma)|\psi_0\rangle\nonumber\\&=\sum_{k}c_kU(\sigma)U(x_k)|\psi_0\rangle\nonumber\\&=\sum_{k}c_kU(\sigma)v^*(x_k)\nonumber\\&=U(\sigma)\sum_{k}c_kv^*(x_k)\nonumber\\&=U(\sigma)v^*(x)\nonumber\\&=U(x\sigma)|\psi_0\rangle\nonumber \\&=U(y)|\psi_0\rangle. \end{align}

So, the proof is completed.

From Theorem 4, it follows that Algorithm 1 returns an equivalent MO-1QFA to the target MO-1QFA $\mathcal{M}=(Q, |\psi_0\rangle,\{U(\sigma)\}_{\sigma\in \Sigma}, Q_a,Q_r)$ to be learned. Next we analyze the computational complexity of Algorithm 1.

Therefore, by combining (I) and (II) we have the complexity of Algorithm 1 is $O(n^5|\Sigma|)$ .

To illustrate Algorithm 1 for learning MO-1QFA, we give an example as follows.

Step 1 of Algorithm 1 yields

(11) \begin{equation}\begin{split}|\psi_0\rangle^*=&\textbf{AD}(\epsilon)\\=&U(\epsilon)|\psi_0\rangle\\=&I|\psi_0\rangle\\=&|q_0\rangle.\end{split}\end{equation}

The 1st iteration run of the while loop body in Algorithm 1 is given below, with the computation of each set.

Step 6 of Algorithm 1 yields

(12) \begin{equation}\begin{split}v^*(\epsilon)=&\textbf{AD}(\epsilon)\\=&U(\epsilon)|\psi_0\rangle\\=&I|\psi_0\rangle\\=&|q_0\rangle.\end{split}\end{equation}

Step 8 of Algorithm 1 yields

(13) \begin{equation}\begin{split}Nod=\{node(a)\}.\end{split}\end{equation}

Step 9 of Algorithm 1 yields

(14) \begin{equation}\begin{split}\mathcal{B}=\{|q_0\rangle\}.\end{split}\end{equation}

The 2nd iteration run of the while loop body in Algorithm 1 is given below, with the computation of each set.

Step 6 of Algorithm 1 yields

(15) \begin{equation}\begin{split}v^*(a)=&\textbf{AD}(a)\\=&U(a)|\psi_0\rangle\\=&U(a)|q_0\rangle\\=&\frac{|q_0\rangle+|q_1\rangle}{\sqrt{2}}.\end{split}\end{equation}

Step 8 of Algorithm 1 yields

(16) \begin{equation}\begin{split}Nod=\{node(aa)\}.\end{split}\end{equation}

Step 9 of Algorithm 1 yields

(17) \begin{equation}\begin{split}\mathcal{B}=\left\{|q_0\rangle,\frac{|q_0\rangle+|q_1\rangle}{\sqrt{2}}\right\}.\end{split}\end{equation}

The 3rd iteration run of the while loop body in Algorithm 3 is given below, with the computation of each set.

Step 6 of Algorithm 1 yields

(18) \begin{equation}\begin{split}v^*(aa)=&\textbf{AD}(aa)\\=&U(aa)|\psi_0\rangle\\=&U(a)U(a)|q_0\rangle\\=&|q_0\rangle.\end{split}\end{equation}

Since $v^*(x)$ belongs to $span(\mathcal{B})$ , the statements in the branch statement are not executed at this point. The set Nod is the empty set at this point, so Algorithm 1 exits from the while loop body.

Finally, let $V(a)=\begin{bmatrix}x_{11}(a) & x_{12}(a) \\x_{21}(a) & x_{22}(a) \\\end{bmatrix}$ , and according to steps 15 and 16 of Algorithm 1, we get

(19) \begin{equation}\begin{split}V(a)v^*(\epsilon)=&V(a)|q_0\rangle\\=&v^*(a)\\=&\textbf{AD}(a)\\=&\frac{|q_0\rangle+|q_1\rangle}{\sqrt{2}}.\end{split}\end{equation}

(20) \begin{equation}\begin{split}V(a)v^*(a)=&V(a)\left(\frac{|q_0\rangle+|q_1\rangle}{\sqrt{2}}\right)\\=&v^*(aa)\\=&\textbf{AD}(aa)\\=&|q_0\rangle.\end{split}\end{equation}

From Eqs. (19) and (20), the following system of equations is obtained

(21) \begin{equation}\begin{cases}\begin{bmatrix}x_{11}(a) & x_{12}(a) \\x_{21}(a) & x_{22}(a) \\\end{bmatrix}\begin{bmatrix}1 \\0 \\\end{bmatrix}=\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} \\\end{bmatrix},\\\begin{bmatrix}x_{11}(a) & x_{12}(a) \\x_{21}(a) & x_{22}(a) \\\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} \\\end{bmatrix}=\begin{bmatrix}1 \\0\\\end{bmatrix}.\end{cases}\end{equation}

Solving the system of Eq. (21) gives

(22) \begin{equation}\begin{split}V(a)=&\begin{bmatrix}x_{11}(a) & x_{12}(a) \\x_{21}(a) & x_{22}(a) \\\end{bmatrix}\\=&\begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\\end{bmatrix}.\end{split}\end{equation}

As a result, we can obtain $\mathcal{M}^*=(Q,|\psi_0\rangle^*,\{V(\sigma)\}_{\sigma\in\Sigma},Q_{a},Q_r)$ , where $Q=\{q_{0},q_{1}\}$ , $|\psi_0\rangle^*=|q_0\rangle$ , $Q_a=\{q_{1}\}$ , $Q_r=\{q_{0}\}$ , $ \Sigma=\{a\}$ , and $V(a)=\begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\\end{bmatrix}$ .

Therefore, the MO- ${\rm 1QFA} $ $\mathcal{M}^*$ , which is equivalent to MO- ${\rm 1QFA} $ $\mathcal{M}$ , can be obtained from Algorithm 1.

4. Learning MM-1QFA

In this section, we study learning MM-1QFA via ${\boldsymbol{AD}}$ oracle. Let $\mathcal{M}=(Q, |\psi_0\rangle, \{U(\sigma)\}_{\sigma\in \Gamma}, Q_a,Q_r,Q_g)$ be the target QFA to be learned, where $\Gamma=\Sigma\cup\{\$\}$ , and $\$\notin\Sigma$ is an end-maker. As usual, $Q, Q_a, Q_r, Q_g$ are supposed to be known, and the goal is to achieve unitary matrices $V(\sigma)$ for each $\sigma\in \Gamma$ in order to get an equivalent MM-1QFA $\mathcal{M}^*=(Q, |\psi_0^*\rangle, \{V(\sigma)\}_{\sigma\in \Gamma}, Q_a,Q_r,Q_g)$ . ${\boldsymbol{AD}}$ oracle can answer an amplitude distribution ${\boldsymbol{AD}}(x)$ for any $x\in\Gamma^*$ . MM-1QFA performs measuring after reading each input symbol, and then only the non-halting (i.e. going on) states continue to implement computing for next step, and the amplitude distribution for the superposition state after performing each unitary matrix needs to be learned from oracle.

Therefore, for any $x=\sigma_1\sigma_2\ldots\sigma_k\in\Gamma^*$ , since MM-1QFA $\mathcal{M}$ outputs the following state (un-normalized form) as the current state:

(23) \begin{equation}U(\sigma_k)P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle,\end{equation}

we require ${\boldsymbol{AD}}$ oracle can answer ${\boldsymbol{AD}}(x)=U(\sigma_k)P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle$ . In particular, ${\boldsymbol{AD}}(\varepsilon)=|\psi_0\rangle$ .

Before presenting the algorithm of learning MM-1QFA, we describe the main ideas and procedure.

First the initial state can be learned from ${\boldsymbol{AD}}$ oracle via querying empty string $\varepsilon$ .

Then by using ${\boldsymbol{AD}}$ oracle we are going to search for a base $\mathcal{B}$ of the Hilbert space spanned by $\{v^*(x): x\in\Sigma^*\}$ where for any $x=\sigma_1\sigma_2\ldots\sigma_k\in\Sigma^*$ ,

(24) \begin{equation}v^*(x)={\boldsymbol{AD}}(x)=U(\sigma_k)P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle.\end{equation}

This procedure will be terminated due to the finite dimension of the space (at most $|Q|$ ), and this can be completed with polynomial time.

Finally, by combining the base $\mathcal{B}$ and with groups of linear equations we can obtain $V(\sigma)$ for each $\sigma\in\Sigma$ . These results can be verified in detail after Algorithm 2, and we now present Algorithm 2 for learning MM-1QFA in the following.

Algorithm 2

Algorithm for learning MM-1QFA $\mathcal{M}=(Q, |\psi_0\rangle, \{U(\sigma)\}_{\sigma\in \Gamma}, Q_a,Q_r,Q_g)$

Next we first demonstrate that the algorithm can find out a base $\mathcal{B}$ for Hilbert space $span\{v^*(x)| x\in\Sigma^*\}$ .

Proof. Suppose that $\mathcal{B}=\{v^*(x_1), v^*(x_2),\ldots,v^*(x_m)\}$ , where it is clear that some $x_i$ equals to $\varepsilon$ . So, for any $x\in\Sigma^*$ , there are $x_j$ and $y\in\Sigma^*$ such that $x=x_jy$ . It suffices to show that $v^*(x)$ can be linearly represented by the vectors in $\mathcal{B}$ . By induction on the length $|y|$ of y. If $|y|=0$ , i.e., $y=\varepsilon$ , then it is obvious for $x=x_j$ . In addition, for $|y|=1$ , $v^*(x_jy)$ is linearly dependent on $\mathcal{B}$ in terms of the algorithm’s operation. Suppose that it holds for $|y|=k\geq 0$ . Then we need to verify it holds for $|y|=k+1$ . Denote $y=z\sigma$ with $|z|=k$ . Then by induction hypothesis $v^*(x_jz)= \sum_{k}c_kv^*(x_k)$ for some $c_k\in\mathbb{C}$ with $k=1,2,\ldots,m$ . Therefore, we have

(25) \begin{align}v^*(x)&=v^*(x_jz\sigma)\nonumber\\&=U(\sigma)P_nv^*(x_jz)\nonumber\\&=U(\sigma)P_n\sum_{k}c_kv^*(x_k)\nonumber\\&=\sum_{k}c_kU(\sigma)P_nv^*(x_k)\nonumber\\&=\sum_{k}c_kv^*(x_k\sigma). \end{align}

Since $v^*(x_k\sigma)$ is linearly dependent on $\mathcal{B}$ for $k=1,2,\ldots,m$ , $v^*(x)$ can be linearly represented by the vectors in $\mathcal{B}$ and the proof is completed.

Then we need to verify that the MM-1QFA $\mathcal{M}^*$ obtained in Algorithm 2 is equivalent to the target MM-1QFA $\mathcal{M}$ . This can be achieved by checking $V(\$)P_n|\psi_0^*\rangle=U(\$)P_n|\psi_0\rangle$ and for any $x=\sigma_1\sigma_2\ldots\sigma_k\in\Sigma^*$ ,

(26) \begin{equation}V(\sigma_k)P_nV(\sigma_{k-1})P_n\ldots V(\sigma_1)P_n|\psi_0^*\rangle=U(\sigma_k)P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle.\end{equation}

So we are going to prove the following theorem.

Theorem 5. In Algorithm 2 for learning MM-1QFA, we have

(27) \begin{equation} V(\$)P_n|\psi_0^*\rangle=U(\$)P_n|\psi_0\rangle;\end{equation}

and for any $x=\sigma_1\sigma_2\ldots\sigma_k\in\Sigma^*$ , Eq. (26) holds, where $|x|\geq 1$ .

Proof. Note $ v^*(\varepsilon) \in \mathcal{B}$ , by means of Step 15 in Algorithm 2 and taking $\sigma=\$ $ , we have

(28) \begin{equation}V(\$)P_nv^*(\varepsilon)=v^*(\$)={\boldsymbol{AD}}(\$)=U(\$)P_n|\psi_0\rangle.\end{equation}

Since $ v^*(\varepsilon)={\boldsymbol{AD}}(\varepsilon)=|\psi_0\rangle$ , and from Algorithm 2 we know $ {\boldsymbol{AD}}(\varepsilon)=|\psi_0^*\rangle$ , Eq. (27) holds.

Next we prove that Eq. (26) holds for any $x=\sigma_1\sigma_2\ldots\sigma_k\in\Sigma^*$ . We do it by induction method on the length of $|x|$ .

If $|x|=1$ , say $x=\sigma\in\Sigma$ , then with Step 15 in Algorithm 2 and taking $v^*(\varepsilon)$ , we have $V(\sigma)P_nv^*(\varepsilon)=v^*(\sigma)={\boldsymbol{AD}}(\sigma)=U(\sigma)P_n|\psi_0\rangle$ , so, Eq. (26) holds for $|x|=1$ due to $v^*(\varepsilon)=|\psi_0\rangle$ .

Assume that Eq. (26) holds for any $|x|=k\geq 1$ . The rest is to prove that Eq. (26) holds for any $|x|=k+1$ . Let $x=y\sigma$ with $y=\sigma_1\sigma_2\ldots\sigma_k$ . Suppose $v^*(y)=\sum_{i}c_iv^*(x_i)$ for some $c_k\in \mathbb{C}$ . For each i, by means of Step 15 in Algorithm 2, we have

(29) \begin{equation}V(\sigma)P_nv^*(x_i)=v^*(x_i\sigma)={\boldsymbol{AD}}(x_i\sigma)=U(\sigma)P_n{\boldsymbol{AD}}(x_i),\end{equation}

and therefore

(30) \begin{equation}V(\sigma)P_n\sum_{i}c_iv^*(x_i)=U(\sigma)P_n\sum_{i}c_i{\boldsymbol{AD}}(x_i).\end{equation}

Since $v^*(x_i)={\boldsymbol{AD}}(x_i)$ , we further have

(31) \begin{equation}V(\sigma)P_nv^*(y)=U(\sigma)P_nv^*(y).\end{equation}

By using $v^*(y)=U(\sigma_k)P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle$ , and the above induction hypothesis (i.e., Eq. (26) holds), we have

(32) \begin{equation}V(\sigma_{k+1})P_nV(\sigma_k)P_nV(\sigma_{k-1})P_n\ldots V(\sigma_1)P_n|\psi_0^*\rangle=U(\sigma_{k+1})P_nU(\sigma_{k-1})P_n\ldots U(\sigma_1)P_n|\psi_0\rangle.\end{equation}

Consequently, the proof is completed.

To conclude the section, we give the computational complexity of Algorithm 2.

5. Concluding Remarks

QFA are simple models of quantum computing with finite memory, but QFA have significant advantages over classical finite automata concerning state complexity (Ambainis and Yakaryilmaz, Reference Ambainis, Yakaryilmaz and Pin2021; Bhatia and Kumar, Reference Bhatia and Kumar2019; Say and Yakaryılmaz, 2014), and QFA can be realized physically to a considerable extent (Mereghetti et al., Reference Mereghetti, Palano and Cialdi2020). As a new topic in quantum learning theory and quantum machine learning, learning QFA via queries has been studied in this paper. As classical model learning (Vaandrager, Reference Vaandrager2017), we can term it as quantum model learning.

The main results we have obtained are that we have proposed two polynomial-query learning algorithms for measure-once one-way QFA (MO-1QFA) and measure-many one-way QFA (MM-1QFA), respectively. The oracle to be used is an ${\boldsymbol{AD}}$ oracle that can answer an amplitude distribution, and we have analyzed that a weaker oracle being only able to answer accepting or rejecting for any inputting string may be not enough for learning QFA with polynomial time.

Here a question is how to compare ${\boldsymbol{AD}}$ oracle with ${\boldsymbol{MQ}}$ oracle and ${\boldsymbol{EQ}}$ oracle? In general, ${\boldsymbol{MQ}}$ oracle and ${\boldsymbol{EQ}}$ oracle are together used in classical models learning with deterministic or nondeterministic transformation of states; ${\boldsymbol{AD}}$ oracle can return a superposition state for an input string in QFA, as ${\boldsymbol{SD}}$ oracle in Tzeng (Reference Tzeng1992) can return a distribution of state for an input string in PFA, so for learning DFA, ${\boldsymbol{AD}}$ oracle and ${\boldsymbol{SD}}$ oracle can return a state for each input string, not only accepting state as ${\boldsymbol{MQ}}$ oracle can do. Of course, the problem of whether both ${\boldsymbol{MQ}}$ oracle and ${\boldsymbol{EQ}}$ oracle together can be used to study QFA learning is still not clear. Furthermore, if ${\boldsymbol{AD}}$ oracle can return the weight of general weighted automata for each input string, then the problem of whether ${\boldsymbol{AD}}$ oracle can be used to study general weighted automata learning is worthy of consideration carefully.

However, we still do not know whether there is a weaker oracle $\mathcal{Q}$ than ${\boldsymbol{AD}}$ oracle but by using $\mathcal{Q}$ one can learn MO-1QFA or MM-1QFA with polynomial time. Furthermore, what is the weakest oracle to learn MO-1QFA and MM-1QFA with polynomial query complexity? These are interesting and challenging problems to be solved. Of course, for learning RFA, similar to learning DFA (Angluin, Reference Angluin1987), we can get an algorithm of polynomial time by using MQ together with EQ.

Another interesting problem is how to realize these query oracles physically, including ${\boldsymbol{SD}}$ oracle, ${\boldsymbol{AD}}$ oracle, and even ${\boldsymbol{MQ}}$ as well as ${\boldsymbol{EQ}}$ . In quantum query algorithms, for any given Boolean function f, it is supposed that a quantum query operator called an oracle, denoted by $O_f$ , can output the value of f(x) with any input x. As for the construction of quantum circuits for $O_f$ , there are two cases: (1) If a Boolean function f is in the form of disjunctive normal form and suppose that the truth table of f is known, then an algorithm for constructing quantum circuit to realize $O_f$ was proposed in Avron et al. (Reference Avron, Casper and Rozen2021). However, this method relies on the truth table of the function, which means that it is difficult to apply, since the truth table of the function is likely not known in practice. (2) If a Boolean function f is a conjunctive normal form, then a polynomial-time algorithm was designed in (Qiu et al., Reference Qiu, Luo and Xiao2022) for constructing a quantum circuit to realize $O_f$ , without any further condition on f.

As mentioned above, besides MO-1QFA and MM-1QFA, there are other one-way QFA, including Latvian QFA (Ambainis et al., Reference Ambainis, Beaudry, Golovkins, Kikusts, Mercer and Therien2006), QFA with control language (Bertoni et al., Reference Bertoni, Mereghetti and Palano2003), 1QFA with ancilla qubits (1QFA-A) (Paschen, Reference Paschen2000), one-way quantum finite automata together with classical states (1QFAC) (Qiu et al., Reference Qiu, Li, Mateus and Sernadas2015), and other 1QFA such as Nayak-1QFA (Na-1QFA), General-1QFA (G-1QFA), and fully 1QFA (Ci-1QFA). So, one of the further problems worthy of consideration is to investigate learning these QFA via queries.

Finally, we would like to analyze partial possible methods for considering these problems. In the present paper, we have used ${\boldsymbol{AD}}$ oracle as queries and quantum algorithms for determining the equivalence between 1QFA to be learned for learning both MO-1QFA and MM-1QFA. So, an algorithm for determining the equivalence between 1QFA to be learned is necessary in our method. In general, as we studied in Li and Qiu (Reference Li and Qiu2008), for designing an algorithm to determine the equivalence between 1QFA, we first transfer the 1QFA to a classical linear mathematical model, and then obtain the result by using the known algorithm for determining the equivalence between classical linear mathematical models. As pointed out in Ambainis and Yakaryilmaz (Reference Ambainis, Yakaryilmaz and Pin2021), the equivalence between 1QFA can be determined, though the equivalence problems for some of 1QFA still have not been studied carefully. Of course, some 1QFA also involve more parameters to be learned, for example, 1QFAC have classical states to be determined.