1 Introduction↩︎

State transition-based systems are an umbrella term to represent systems that change their internal states after receiving some inputs. These systems include, but are not limited to, hardware, software, mathematical, and biological systems. In general, state-transition-based systems must return to a particular initial (or consistent/safe) state to function correctly. This operation is known as the reset operation. In essence a reset operation defines the steps required to bring the system back to a particular initial or consistent state independent of its current state. Because of its role, resets are indispensable aspects of many systems. Some systems use reset circuits to carry out this operation. In case of lack of reset circuits, a reset operation is done by executing a sequence of inputs called reset sequence (RS) (also named as synchronizing sequence or a reset word).

In robotics, for example, RSs are crucial for multi-robot manipulation and transportation, where multiple robots must coordinate and recover from faults to ensure the system operates smoothly [1].

Automotive control systems also benefit from these sequences, as they help synchronize embedded systems in vehicles, maintaining safety and functionality in critical systems after unexpected failures [2].

In communication systems, RSs ensure the synchronization of protocol handlers after disruptions, enabling uninterrupted data flow and maintaining the integrity of communication networks [3].

RSs are also key in software engineering; namely, in conformance testing of reactive systems where many tests or input words are derived to detect errors or unexpected behaviour of a given implementation. The implementation needs to be reset before running each test [4], [5], Chow78?.

In bio-computing, a collection of automata work in parallel on different inputs and in order to start a new computation a RS is applied to reset the automata to their initial states. In  [6] for example, the researchers showed that in a controlled environment they ran \(3 * 10^{12}\) automata per microliter, performing \(6 * 10^{10}\) transitions per second, and in order to run these automata, we need to run reset words. The reader may also refer to other applications of RSs in robotics  [7], matrix theory [8], and Markov processes [9].

A Finite Automaton (FA) is a fundamental mathematical computation model used to describe state-transition-based systems’ behaviour. An FA consists of finite numbers of states, inputs, and transitions between states, and it can be in exactly one of its states at a given time and can transition from one state to another in response to inputs it receives. Depending on the underlying system, many FA classes exist, each having different properties. For example, if all system states share a common set of inputs, the system can be represented by a complete FA; otherwise, one can use a partial FA.

Automated RS derivation from FA is a long-standing problem. In 1990, Epsstein used a quadratic algorithm to find an RS from a complete FA [10]. Moreover, as the length of the RS is the time required to reset a given system, deriving one of the shortest RS is usually needed. In 1964, Černý conjectured that for every \(n\)-state complete FA having an RS, there is an RS of length at most \((n-1)^2\) [11], [12]. This conjecture is unproved yet. However, Eppstein also showed that for complete FA, finding the one of the shortest RS is an NP-Hard problem [10]. They also revealed that checking the existence of an RS of length \(l\) from a complete FA is NP-Complete.

For partial FA, which is the general case, the picture is more pessimistic as the length of the shortest RS is \(\Omega(3^{n/3})\) and the length of an RS is bounded by \(\Theta(n^2*4^{n/3})\)  [13]. Therefore, for such systems modelled by a partial FA, checking the existence of an RS is PSPACE-Complete [14]. Therefore, in the literature, there exists a line of research to investigate efficient algorithms for finding (checking existence, deriving, deriving shortest) RSs  [10], [15]–[29].

Quantum computers offer the promise of up to exponential speed-ups over classical computers. Recent advances in quantum computing hardware have resulted in quantum processors with more than 400 qubits [30], and there are claims that quantum superiority has been achieved on different quantum devices, including superconducting systems  [31] and photonic quantum devices  [32]. Quantum algorithms like Grover’s algorithm  [33] and amplitude amplification give polynomial speed-ups over corresponding classical algorithms. Yet, though these algorithms give comparably modest quadratic speed-up, they are widely applicable and thus give speed-ups for a wide range of problems  [34]. Some other algorithms like Shor algorithm [35] offer exponential speed-up.

Despite extensive efforts in designing classical algorithms for RS generation, the computational complexity of deriving shortest RSs remains a major challenge, especially for partial automata where classical methods are often infeasible due to their exponential time complexity.

While quantum algorithms have been successfully applied to a wide range of search and optimisation problems, their application to reset sequence generation remains unexplored. To the best of our knowledge, no formal method has yet been proposed for constructing quantum circuits that generate reset sequences for finite automata.

In this paper, we introduce a quantum RS generation algorithm. This is the first formal method to generate a quantum circuit to compute an RS from a given (complete/partial) FA. A high-level summary of the method is provided in the following section. A simple application example, the rules for transforming a transition function into a permutative one and a proof about the space complexity are provided in the online supplementary material provided in the appendix.

2 Background↩︎

A Finite Automata (FA) \(M = (S,X,\delta )\) has a finite set \(S\) of \(n\) states, a finite set \(X\) of \(k\) inputs, and a next-state transition function: \(\delta : S \times X \rightarrow S\). If \(M\) is at state \(p\) (can also be denoted by \(s_p\), \(p=0...n-1\)) and input \(x\) (inputs can also be denoted as \(x_i\), \(i\) \(\in\) \(0..k-1\)) is applied, then \(M\) moves to state \(q = \delta(p, x)\).

In quantum computing, the information is represented by quantum bits, qubits. A qubit represents the information in a complex Hilbert space by a set of orthonormal basis vectors in a wave equation. For a single qubit represented by a pair of orthonormal basis states \(\vert0\rangle = \begin{pmatrix} 1\\0 \end{pmatrix}\) and \(\vert1\rangle = \begin{pmatrix} 0\\1 \end{pmatrix}\), the corresponding wave equation \(\vert\psi\rangle = \alpha\vert 0\rangle + \beta\vert 1\rangle\), with \(\alpha, \beta\in\mathbb{C}\) are complex coefficients for each basis state of the wave equation such that \(\vert\alpha\vert^2+\vert\beta\vert^2 = 1\).

When using more than one qubit the multi-qubit quantum state is obtained using the Kronecker product \(\otimes\). Given two qubits \(\vert\psi\rangle\) and \(\vert\phi\rangle = \gamma\vert0\rangle + \delta\vert1\rangle\) their joint state obtianed by Kronecker product is shown in eq. 1 . \[\vert \rho\rangle = \vert\psi\rangle\otimes\vert\phi\rangle = \alpha\gamma\vert00\rangle+\alpha\delta\vert01\rangle+\beta\gamma\vert 10\rangle+\beta\delta\vert11\rangle\\ \label{eq:skron}\tag{1}\]

Kronecker product can be also applied to matrices in a similar manner as it is applied to quantum states. As an example, let \(H=\frac{1}{\sqrt{2}}\begin{pmatrix} 1&1\\1&-1 \end{pmatrix}\) be the Hadamard quantum gate used to put a quantum state in superposition. Let \(\vert\rho\rangle=\vert\psi\rangle\otimes\vert\phi\rangle =\vert0\rangle\otimes\vert1\rangle = \begin{pmatrix} 1\\0\end{pmatrix}\otimes\begin{pmatrix} 0\\1\end{pmatrix}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\). Then to apply the Hadamard transform to both qubit, first we need to create a two qubit Hadamard quantum gate using the kronecker product and then multiply it with the two-qubit state \(\vert\rho\rangle\) as shown in eq. 2 . \[\begin{align} H\otimes H\vert\rho\rangle &= \frac{1}{2}\begin{pmatrix} 1&1\\1&-1 \end{pmatrix}\otimes\begin{pmatrix} 1&1\\1&-1 \end{pmatrix}\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\nonumber=\frac{1}{2}\begin{pmatrix} 1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\ 1&-1&-1&1 \end{pmatrix}\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\nonumber\\& = \frac{1}{2}\left ( \vert00\rangle-\vert01\rangle+\vert10\rangle-\vert11\rangle\right )\label{eq:kron} \end{align}\tag{2}\]

Each complex coefficient in a quantum state represents the probability \(prob(q)\) of obtaining the state \(q\) from the superposition under the measurement. For instance, \(\vert\alpha\vert^2\) is the probability to measure the state \(\vert0\rangle\) . For instance in the state in equation 2 , each two qubit state is equiprobable under measurement with probability of observation being \(prob(q) = \frac{1}{4}\).

Finally, the tensor (Kronecker) product applied to a same state or the same gate \(k\)-times can also be written in a shortenned form. For instance \(\vert1\rangle^{\otimes^k}=\vert111\ldots 11\rangle\) represents a quantum register of \(k\) qubits all in the basis state \(1\). Similarly, \(H^{\otimes^k}=H\otimes \ldots\otimes H\otimes H\) represents \(k\) Hadamard gates multiplied by kronecker product.

The quantum register can be manipulated using unitary operators such as \(H\). A particular type of unitary operator is also called a permutative matrix. A permutative matrix is a a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. Thus a permutative matrix contains exactly \(n\) one’s and the rest are zeros for a matrix of size \(n\times n\).

3 The approach↩︎

3.1 High-level summary↩︎

Our approach has the following steps:

1) Represent a given FA in quantum space: We map the states and input symbols of the FA to quantum registers. To simulate the transition function \(\delta\) of the FA under an input symbol \(x\), we first construct a unitary matrix that encodes \(\delta(x)\). If this matrix is not permutative (i.e., not directly applicable in quantum computation), we transform it into a permutative unitary matrix \(\Delta_x\) by introducing ancillary (ancilla) registers. These ancilla registers allow the extension of the system’s Hilbert space so that the resulting matrix is reversible and unitary. A global permutative transition operator \(\Delta\) is then derived using all \(\Delta_x\) matrices.

2) Simulate an FA transition in quantum space: To simulate a transition from an initial FA state under a given input, we first construct a quantum total state (QTS) by taking the tensor product of: (i) the quantum encoding of the input symbol, (ii) its corresponding ancilla register, (iii) and the quantum state representing the current FA state.

We then apply the operator \(\Delta\) to this QTS. The resulting QTS represents: (i) the input symbol, (ii) the reached FA state (as a quantum state), (iii) and any garbage data left in the ancilla registers after the computation.

3) Simulate the application of an input sequence: We extend the previous step to simulate the effect of an input sequence of length \(l\). We apply the operator \(\Delta\) iteratively \(l\) times, denoted \(\Delta^l\), to the tensor product of: (i) the quantum encoding of the full input sequence, (ii) the associated ancilla registers, and (iii) the initial FA state. The final QTS reflects the FA state reached after applying the entire input sequence.

4) Simulate the application of all input sequences: To simulate the application of all input sequences of length \(l\) simultaneously, we initialize the system in a uniform superposition over all possible input sequences of that length. The QTS is constructed as the tensor product of: (i) the superposition of all input sequences, (ii) the corresponding ancilla registers, and (iii) the initial FA state.

Applying \(\Delta^l\) in this setting results in a quantum state that contains, for each sequence, the corresponding reached FA state and ancillary outputs.

5) Simulate the application of all input sequences starting from all FA states: We extend step (4) by simulating, in superposition, the effect of all input sequences of length \(l\) on all FA states. The initial quantum state now encodes all FA states, and the total quantum state (QTS) is formed by the tensor product of this encoding with all input sequences of length \(l\) and their ancilla registers. For each sequence, the resulting QTS captures all quantum states reached when that sequence is applied to every FA state.

6) Use Grover algorithm to search for an intended RS: The construction in (5) groups together the FA states that evolve into identical quantum states in addition to having the input sequences that reach such identical states. Grover’s algorithm is then used to find such sequences—those that map all FA states to the same final state yielding an RS. For partial FAs, the FA is first completed by adding a “don’t care” state with self-loops for all inputs and for each FA state with an undefined input, a transition under the input is added connecting the state to the don’t care state. The added state is included in the quantum search.

3.2 Representing FA states and inputs and transition function in quantum space↩︎

Representing the FA states and inputs:

Each orthonormal basis \(\vert0\rangle\), \(\vert1\rangle\),... can be mapped to a state of the FA. Therefore, the \(n\) states of an FA can be directly mapped to the \(n\) basis vectors represented in a quantum state using \(\log_2 n\) qubits. Accordingly, we define:

• The \(\nu\)-qubit register is used to represent the state \(\vert\mathcal{S}\rangle =\vert w_{\nu-1}\ldots w_0\rangle\), with \(\nu = \log_2n\), and the basis states \(\vert \mathcal{S}_0\rangle\), \(\vert \mathcal{S}_1\rangle\), ..., \(\vert \mathcal{S}_{n-1}\rangle\).

Similarly, for an FA with \(k\) inputs, the inputs can be represented in quantum space using \(\log_2 k\) qubits. Accordingly, we define:

• A \(\kappa\)-qubit register representing the input \(\vert\mathcal{X}\rangle =\vert\xi_{\kappa-1}\ldots \xi_0\rangle\), with \(\kappa = \log_2k\), and the basis states \(\vert \mathcal{X}_0\rangle\), \(\vert \mathcal{X}_1\rangle\), ...,\(\vert \mathcal{X}_{k-1}\rangle\)

Representing FA transition function: The state change of an FA is defined by the state transition function \(\delta\). To achieve the mapping of \(\delta\) from state \(s_i\) (\(\vert\mathcal{S_{i}}\rangle\)) and input \(x\) leading to state \(s_j\) (\(\vert\mathcal{S_{j}}\rangle\)), we first map \(\delta\) to a unitary square binary matrix \(\bar{\Delta}_x\) which has exactly one entry equals to \(1\) in each row (specifies next-quantum state) and in each column (current quantum state), and \(0\) elsewhere. Namely, if \(\delta_x(s_i,x)=s_j\), then 1 is placed in the intersection of the column representing \(\vert \mathcal{S}_i\rangle\) and the row representing \(\vert \mathcal{S}_j\rangle\). The matrix \(\bar{\Delta_x}\) must be permutative so that it can be directly mapped to a quantum implementation (required by the implementation limitations of reversible and quantum computing). However, if for certain input \(x\), the corresponding unitary matrix that encodes \(\delta(x)\) is not permutative, then \(\bar{\Delta}_x\) is transformed into a permutative matrix by introducing \(\mu\) ancilla qubits register denoted by \(\vert\mathcal{A}\rangle\).

In fact, we define the following:

• A \(\mu\)-qubit register representing ancilla \(\vert\mathcal{A}\rangle =\vert a_{\mu-1}\ldots a_0\rangle\) with \(\mu = \log_2m\) with basis states \(\vert\mathcal{A}_0\rangle\ldots\vert\mathcal{A}_{m-1}\rangle\).

Note, first, for each input \(x\) with a non-permutative \(\bar{\Delta}_{x_i}\), we determine \(\mu'\) the ancillae necessary to create the corresponding unitary permutative matrix. The total number of required ancillae over all inputs \(x\) is computed as \(\mu = \arg\max_{\mu'}\max(\mu')\). Then, considering \(\mu\), for every input \(x\), FA embedding can be used to derive the corresponding permutative \(\Delta_{x}\) using the general approaches for embedding reversible automata or functions  [36].

In our case, the columns and rows of \(\Delta_{x}\) are labeled by the basis vectors of the tensor product \(\vert\mathcal{A}\mathcal{S}\rangle = \vert\mathcal{A}\rangle\otimes\vert\mathcal{S}\rangle\).

By construction of a \(\Delta_{x_i}\), for each transition \(\delta(s_k, x_i)=s_l\), \({\Delta}_{x_i}[\vert\mathcal{A}_?\mathcal{S}_? \rangle][\vert\mathcal{A}_?\mathcal{S}_?\rangle]=1\).

Then we define \(\Delta\) representing the \(\delta\) next-state function under all \(x\in X\) as a block-diagonal (permutative) matrix where for each \(x\) there is a corresponding \(\Delta_x\). Namely, we place in the diagonal of \(\Delta\), the individual \(\Delta_{x}\) operators ordered in the natural order of the elements in \(X\). The first operator will be \(\Delta_{x_0}\), then \(\Delta_{x_1}\) and so on, as shown in eq. 4 . All other elements of the matrix are set to zeros.

\[\Delta = \begin{pNiceMatrix}[margin=3pt,create-medium-nodes,first-row,first-col] &\vert \mathcal{X}_0\mathcal{E}\rangle&\vert \mathcal{X}_1\mathcal{E}\rangle&\Cdots&\vert \mathcal{X}_{k-1}\mathcal{E}\rangle\\ \vert \mathcal{X}_0\mathcal{E}\rangle&\Delta_{x_0}&0&\Cdots&0\\\vert \mathcal{X}_1\mathcal{E}\rangle&0&\Ddots&\Ddots&\Vdots\\\Vdots&\Vdots&\Ddots&&0\\\vert \mathcal{X}_{k-1}\mathcal{E}\rangle&0&\Cdots&0&\Delta_{x_{k-1}}\\ \CodeAfter \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wuhkixbc.png}\tag{3}\end{figure} \end{pNiceMatrix} \tag{4}\]

To conveniently represent the combinations of the basis states of \(\vert\mathcal{A}\rangle\) and \(\vert\mathcal{S}\rangle\) we use \(\vert\mathcal{E}\rangle =\vert\mathcal{A}\rangle\otimes\vert\mathcal{S}\rangle=\vert\mathcal{A}_0\mathcal{S}_0\rangle+\ldots+\vert\mathcal{A}_{m-1}\mathcal{S}_{n-1}\rangle\) to annotate the rows and columns of the matrix \(\Delta\). Therefore, each term \(\vert\mathcal{X}_i\mathcal{E}\rangle\) can be expanded as a vector \(\vert\mathcal{X}_i\mathcal{A}_0\mathcal{S}_0\rangle \ldots\vert\mathcal{X}_i\mathcal{A}_{m-1}\mathcal{S}_{n-1}\rangle\). We use \(\vert\mathcal{Q}\rangle\), referred to as Quantum Total State (QTS), to represent the tensor product of the three defined registers \(\vert\mathcal{X}\rangle\), \(\vert\mathcal{A}\rangle\), and \(\vert\mathcal{S}\rangle\), respectively, as shown in eq. 5 .

\[\vert\mathcal{Q}\rangle = \vert\mathcal{X}\rangle\vert\mathcal{A}\rangle\vert\mathcal{S}\rangle \label{eq:genstate}\tag{5}\]

Each square (\(\Delta_{x_i}\)) in eq. 4 shows one specific operator mapping \(\mathcal{A}\times \mathcal{S}\rightarrow \mathcal{A}\times \mathcal{S}\) for a specific input value \(x_i\). Thus, for an input encoded in \(\vert\mathcal{X}\rangle\), using the \(\Delta\) operator, we transform \(\vert\mathcal{Q}\rangle\) from eq. 5 to the next-quantum state \(\vert\mathcal{Q}\rangle^1\) as shown in eq. 6 . The ancilla \(\vert\mathcal{A}\rangle\) is always set as \(\vert\mathcal{A}\rangle=\vert\mathcal{A}_0\rangle =\vert0\rangle^{\otimes \mu}\) before the \(\Delta\) operation is applied. Observe that the application of \(\Delta\) transforms the ancillae \(\vert\mathcal{A}\rangle\) into garbage \(\vert\mathcal{G}\rangle^1\). The garbage indicates that it should be discarded because it is used and its value is unknown. We note that both the used garbage and the resulting quantum state \(\vert\mathcal{S}\rangle^1\) are indexed by a superscript indicating the application of one input. The circuit representing the application an FA input encoded by \(\vert\mathcal{X}\rangle\) to an FA state encoded by \(\vert\mathcal{S}\rangle\) according to \(\Delta\) leading to the FA state encoded by \(\vert\mathcal{S}\rangle^1\) is shown in Figure 1.

\[\Delta \vert\mathcal{Q}\rangle = \vert\mathcal{Q}\rangle^1 = \Delta\vert\mathcal{X} \rangle \vert\mathcal{A}_0\rangle\vert\mathcal{S}\rangle = \vert\mathcal{X} \rangle \vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^1 \label{eq:genstate1}\tag{6}\]

The number of qubits to encode inputs (states) is obtained directly from \(log_2\) of the total number of input values (FA states).

Working example: As an application example, consider the FA given in Table  1. The FA has three states \(S = \{s_0,s_1,s_2\}\), two inputs \(X = \{x_0,x_1\}\), and four transitions. First, we map the states \(s_0 \rightarrow \vert0\rangle = \begin{pmatrix}1\\0\\0\end{pmatrix}=\vert\mathcal{S}_0\rangle\), \(s_1\rightarrow \vert1\rangle = \begin{pmatrix}0\\1\\0\end{pmatrix} =\vert\mathcal{S}_1\rangle\) and \(s_2\rightarrow \vert2\rangle = \begin{pmatrix}0\\0\\1\end{pmatrix} =\vert\mathcal{S}_2\rangle\). We decide to encode the states by qutrits (quantum bits with three basis states). The input values are encoded each by a single qubit \(\vert\mathcal{X}_0\rangle = \vert0\rangle=\begin{pmatrix}1\\0\end{pmatrix}\) and \(\vert\mathcal{X}_1\rangle = \vert1\rangle=\begin{pmatrix}0\\1\end{pmatrix}\).

Considering the input \(x_1\), we transform the state transition function (Table 1) into a the matrix \(\bar{\Delta}_{x_1}\) shown in eq. 7 . \[\bar{\Delta}_{x_1}=\begin{pNiceMatrix}[first-row,first-col,create-medium-nodes] &\vert \mathcal{S}_0\rangle&\vert \mathcal{S}_1\rangle&\vert \mathcal{S}_2\rangle\\ \vert \mathcal{S}_0\rangle&1&0&0\\ \vert \mathcal{S}_1\rangle&0&0&0\\ \vert \mathcal{S}_2\rangle&0&1&1\\ \end{pNiceMatrix} \label{eq:nonunit}\tag{7}\] where if \(\delta(s_i,x_1) = s_j\) then \(1\) is placed at intersection of column \(\vert \mathcal{S}_i\rangle\) and row \(\vert \mathcal{S}_j\rangle\) denoted as \(\bar{\Delta}_{x_1}[\vert\mathcal{S}_j\rangle][\vert\mathcal{S}_i\rangle]=1\).

Note that as \(\delta(s_0,x_1) = s_0\), we have in eq. 7 \(\bar{\Delta}_{x_1}[\vert\mathcal{S}_0\rangle][\vert\mathcal{S}_0\rangle]=1\). In addition, observe that as \(\delta(s_1,x_1) =\delta(s_2,x_1) = s_3\), the matrix \(\bar{\Delta}_{x_1}\) is non-permutative. This is shown by \(\bar{\Delta}_{x_1}[\vert\mathcal{S}_2\rangle][\vert\mathcal{S}_1\rangle]=1\) and \(\bar{\Delta}_{x_1}[\vert\mathcal{S}_2\rangle][\vert\mathcal{S}_2\rangle]=1\). For the input \(x_2\), we observe that \(\bar{\Delta}_{x_2}\) is permutative as \(\delta(s_0,x_0) \neq \delta(s_1,x_0) \neq \delta(s_2,x_0)\). Thus, In order to transform \(\bar{\Delta}_{x_1}\) into a permutative \(\Delta_{x_1}\), we need one ancilla qubit because \(m=2\); in this FA there are at maximum two state transitions leading to the same successor state. And for the input \(x_2\). The ancillae qubit is thus represented by a wave equation with two basis states: \(\vert\mathcal{A}\rangle = \frac{1}{\sqrt{2}}(\vert\mathcal{A}_0\rangle+\vert\mathcal{A}_1\rangle)\) with basis vectors \(\vert \mathcal{A}_0\rangle=\begin{pmatrix} 1\\0 \end{pmatrix}\) and \(\vert \mathcal{A}_1\rangle=\begin{pmatrix} 0\\1 \end{pmatrix}\). Then using tensor product we create \(\vert\mathcal{A}\mathcal{S}\rangle = \vert\mathcal{A}\rangle\otimes\vert\mathcal{S}\rangle = \frac{1}{\sqrt{6}}(\vert\mathcal{A}_0\mathcal{S}_0\rangle+\vert\mathcal{A}_0\mathcal{S}_1\rangle+\vert\mathcal{A}_0\mathcal{S}_2\rangle+\vert\mathcal{A}_1\mathcal{S}_0\rangle+\vert\mathcal{A}_1\mathcal{S}_1\rangle+\vert\mathcal{A}_1\mathcal{S}_2\rangle)\). The unitary matrix \(\Delta_{x_1}\) will have the rows and columns labeled by the basis vectors of \(\vert\mathcal{A}\mathcal{S}\rangle\). To construct \(\Delta_{x_1}\), for each state transition \(\delta(s_k,x_1) = s_l\) we place a 1 in column labeled by \(\vert\mathcal{A}_0\mathcal{S}_k\rangle\) and any empty row that contains \(\vert\mathcal{S}_l\rangle\) in the label. Using this rule we map \(\delta(s_0,x_1) = s_0\) to \({\Delta}_{x_1}[\vert\mathcal{A}_0\mathcal{S}_0\rangle][\vert\mathcal{A}_0\mathcal{S}_0\rangle]=1\), \(\delta(s_1,x_1) = s_2\) to \({\Delta}_{x_1}[\vert\mathcal{A}_0\mathcal{S}_2\rangle][\vert\mathcal{A}_0\mathcal{S}_1\rangle]=1\) and \(\delta(s_2,x_1) = s_2\) to \({\Delta}_{x_1}[\vert\mathcal{A}_1\mathcal{S}_2\rangle][\vert\mathcal{A}_0\mathcal{S}_2\rangle]=1\). For all the columns that contain \(\vert\mathcal{A}_1\rangle\) put a 1 in the remaining empty rows. An example of such a constructed unitary matrix is shown in eq. 9 .

\[{!}{ \Delta_{x_1} =\begin{pNiceMatrix}[first-row,first-col,create-medium-nodes] &\vert \mathcal{A}_0 \mathcal{S}_0\rangle&\vert \mathcal{A}_0\mathcal{S}_1\rangle&\vert \mathcal{A}_0\mathcal{S}_2\rangle&\vert \mathcal{A}_1 \mathcal{S}_0\rangle&\vert \mathcal{A}_1\mathcal{S}_1\rangle&\vert \mathcal{A}_1\mathcal{S}_2\rangle\\ \vert \mathcal{A}_0 \mathcal{S}_0\rangle&1&0&0&0&0&0\\\vert \mathcal{A}_0\mathcal{S}_1\rangle&0&0&0&1&0&0\\\vert \mathcal{A}_0\mathcal{S}_2\rangle&0&1&0&0&0&0\\\vert \mathcal{A}_1 \mathcal{S}_0\rangle&0&0&0&0&1&0\\\vert \mathcal{A}_1\mathcal{S}_1\rangle&0&0&0&0&0&1\\\vert \mathcal{A}_1\mathcal{S}_2\rangle&0&0&1&0&0&0 \CodeAfter \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/pqadbtmi.png}\tag{8}\end{figure} \end{pNiceMatrix} \tag{9} }\]

For the input \(x_0\), as \(\bar{\Delta}_{x_0}\) is permutative, there is no need to embed \(\bar{\Delta}_{x_0}\) with additional ancillae. Thus, we when constructing \(\Delta_{x_0}\), we consider the ancilla qubit used for \(\Delta_{x_1}\), and accordingly, we obtain \(\Delta_{x_0}\) shown in equation  11 constructed using the same rules as \(\Delta_{x_1}\).

\[\Delta_{x_0} =\begin{pNiceMatrix}[first-row,first-col,create-medium-nodes] &\vert \mathcal{A}_0 \mathcal{S}_0\rangle&\vert \mathcal{A}_0\mathcal{S}_1\rangle&\vert \mathcal{A}_0\mathcal{S}_2\rangle&\vert \mathcal{A}_1 \mathcal{S}_0\rangle&\vert \mathcal{A}_1\mathcal{S}_1\rangle&\vert \mathcal{A}_1\mathcal{S}_2\rangle\\ \vert \mathcal{A}_0 \mathcal{S}_0\rangle&0&0&1&0&0&0\\\vert \mathcal{A}_0\mathcal{S}_1\rangle&1&0&0&0&0&0\\\vert \mathcal{A}_0\mathcal{S}_2\rangle&0&1&0&0&0&0\\\vert \mathcal{A}_1 \mathcal{S}_0\rangle&0&0&0&0&1&0\\\vert \mathcal{A}_1\mathcal{S}_1\rangle&0&0&0&0&0&1\\\vert \mathcal{A}_1\mathcal{S}_2\rangle&0&0&0&1&0&0 \CodeAfter \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/nkyiqfdr.png}\tag{10}\end{figure} \end{pNiceMatrix} \tag{11}\] The obtained \(\Delta\) contains both matrices \(\Delta_{x_0}\) and \(\Delta_{x_1}\) as block matrices on the diagonal as shown in eq. 12 . To represent clearly matrix \(\Delta\) we used \(\vert\mathcal{E}\rangle =\vert\mathcal{A}\rangle\otimes\vert\mathcal{S}\rangle =\vert\mathcal{A}_0\mathcal{S}_0\rangle+\vert\mathcal{A}_0\mathcal{S}_1\rangle+\vert\mathcal{A}_0\mathcal{S}_2\rangle+\vert\mathcal{A}_1\mathcal{S}_0\rangle+\vert\mathcal{A}_1\mathcal{S}_1\rangle+\vert\mathcal{A}_1\mathcal{S}_2\rangle\) to indicate all combinations of the ancillae and the FA states.

\[{!}{ \Delta =\begin{pNiceMatrix}[first-row,first-col,create-medium-nodes] &&\vert \mathcal{X}_0\rangle\vert\mathcal{E}\rangle&&&\vert \mathcal{X}_1\rangle\vert\mathcal{E}\rangle&\\ &\Block{3-3}<\Large>{\Delta_{x_0}}&&&0&\Cdots&0\\ \vert \mathcal{X}_0\rangle\vert\mathcal{E}\rangle&&&&\Vdots&&\\ &&&&&&\Vdots\\ &&&&0&\Cdots&0\\ &0&\Cdots&0&\Block{3-3}<\Large>{\Delta_{\mathcal{X}_1}}&\\ \vert \mathcal{X}_1\rangle\vert\mathcal{E}\rangle&\\ &\Vdots&&\Vdots&&&\\ &0&\Cdots&0&&& \end{pNiceMatrix}} \label{eq:exdelta}\tag{12}\]

To simulate the application of \(x_1\) to the FA starting from \(s_1\), we use the input \(\vert\mathcal{X}_1\rangle = \vert1\rangle\), with \(\vert\mathcal{S}\rangle = \vert \mathcal{S}_1\rangle = \vert1\rangle\) and \(\vert\mathcal{A}\rangle = \vert\mathcal{A}_0\rangle =\vert0\rangle\), and apply \(\Delta\) to the QTS \(\vert\mathcal{Q}\rangle = \vert 100\rangle\) as shown in eq. 13 . The obtained QTS \(\vert\mathcal{S}\rangle^1=\vert0\rangle=\vert S_0\rangle\) and \(\vert\mathcal{G}\rangle^1=\vert1\rangle=\vert\mathcal{A}_1\rangle\).

\[\begin{gather} \Delta \vert\mathcal{Q}\rangle = \vert\mathcal{Q}\rangle^1 =\Delta \vert \mathcal{X}_1\mathcal{A}_0\mathcal{S}_1\rangle\\ = \Delta \vert 101\rangle= \Delta\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}1\\0\end{pmatrix}\otimes\begin{pmatrix}0\\1\\0\end{pmatrix}=\Delta \begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}0\\1\\0\\0\\0\\0\end{pmatrix}=\Delta \begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\1\\0\\0\\0\\0\end{pmatrix} =\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\0\\1\\0\\0\\0\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}0\\0\\1\\0\\0\\0\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}1\\0\end{pmatrix}\otimes\begin{pmatrix}0\\0\\1\end{pmatrix}\\=\vert1\rangle \vert02\rangle= \vert\mathcal{X}_1\rangle \vert\mathcal{A}_0\rangle^1\vert\mathcal{S}_1\rangle^1=\vert\mathcal{X}_1\rangle \vert\mathcal{G}\rangle\vert\mathcal{S}_2\rangle \label{eq:exgenstate} \end{gather}\tag{13}\]

If we apply the sequence \(x^2\) starting from the initial FA state \(s_0\); i.e. \(\vert S\rangle = \vert\mathcal{S}_0\rangle\), then \(\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^1=\vert0\rangle\vert\mathcal{S}_1\rangle=\vert0\rangle\vert1\rangle\) and \(\vert\mathcal{S}\rangle^2=\vert\mathcal{S}_2\rangle=\vert2\rangle\) and \(\vert\mathcal{G}\rangle^2=\vert0\rangle\).

3.3 Executing an input sequence starting from a quantum state↩︎

We use \(x^l = x_j.....x_i\) to denote an input sequence of length \(l\); \(i,j \in \{0...k-1\}\). We map the inputs of \(x^l\) to \(\vert\mathcal{X}^l_j\rangle\ldots\vert\mathcal{X}^1_i\rangle\), where the superscripts are used to denote the first to the \(l\)-th inputs of the sequence. For each input \(\vert\mathcal{X}_i^r\rangle\) where \(r=1\ldots l\) and \(i\in 0\ldots k-1\), we define an \(\mu\)-qubit register to represent ancillae \(\vert \mathcal{A}_0\rangle=\vert0\rangle^{\otimes \mu}\). We create \(l\) ancillae \(\vert\mathcal{A}_0\rangle^l\ldots\vert\mathcal{A}_0\rangle^1\) for the \(x_j....x_i\) inputs of \(x^l\). The quantum state register \(\vert \mathcal{S}\rangle\) contains \(\log_2n\) qubits so that it can represent FAs with up to \(n\) states by its basis states. Accordingly, we define the QTS \(\vert\mathcal{Q}\rangle\) as the Kronecker product shown in eq. 14 \[\vert\mathcal{Q}\rangle = \vert \mathcal{X}^l_j\ldots\mathcal{X}^1_i\rangle\vert\mathcal{A}_0\rangle^l\ldots\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle \label{eq:qsatatepg}\tag{14}\]

The application of the \(l\)-consecutive inputs of \(\vert\mathcal{X}^l_j\rangle\cdots\vert\mathcal{X}^1_i\rangle\) starting from QTS \(\vert\mathcal{Q}\rangle\) according to the \(\Delta\) function leads to QTS \(\vert\mathcal{Q}\rangle^l\) as shown in eq. 15 . We denote by \(\vert\mathcal{A}_0\rangle^r\) and \(\vert\mathcal{G}\rangle^r\), \(1\leq r\leq l\), the ancilla and their corresponding garbage registers obtained by the \(r-\)times application of \(\Delta\) (depicted as \(\Delta^r\)). Similarly, we denote the resulting (reached) quantum state by \(\vert\mathcal{S}\rangle^r\).

\[\Delta^l\vert\mathcal{Q}\rangle=\vert\mathcal{Q}\rangle^l =\Delta(\ldots(\Delta\vert \mathcal{X}^l_j\rangle\ldots\vert\mathcal{X}^1_i\rangle\vert\mathcal{A}_0\rangle^l\ldots\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle))= \vert \mathcal{X}^l_j\rangle\ldots\vert\mathcal{X}^1_i\rangle\vert \mathcal{G}\rangle^l\ldots\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^l \label{eq:evolutions3}\tag{15}\]

The circuit representing the application of an input sequence \(\vert\mathcal{X}^l_j\rangle\ldots\vert\mathcal{X}^1_i\rangle\) to an FA state encoded by \(\vert\mathcal{S}\rangle\) leading to the FA state encoded by \(\vert\mathcal{S}\rangle^l\) is shown in Figure 2. Namely, this denotes the \(l-\)times application of \(\Delta\) starting from QTS \(\vert\mathcal{Q}\rangle\) and leading to QTS \(\vert\mathcal{Q}\rangle^l\).

Working example: Consider the input sequence \({x}^2= x_0 x_1\) of length \(l=2\). We map the sequence \({x}^2\) onto \(\vert\mathcal{X}^2_1\rangle\vert\mathcal{X}^1_0\rangle=\vert10\rangle\). We require two ancillae, \(\vert\mathcal{A}_0\rangle^2\mathcal{A}_0\rangle^1=\vert00\rangle\) one for each application of \(\Delta\) and one qutrit to represent the starting machine state as \(\vert\mathcal{S}\rangle\). Accordingly, we create the initial QTS shown in eq. 16 . \[\vert\mathcal{Q}\rangle = \vert\mathcal{X}_1^2\mathcal{X}_0^1\rangle\vert\mathcal{A}_0\rangle^2\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle \label{eq:qts0}\tag{16}\]

Performing a state change, starting from the QTS in eq. 16 and using the input sequence \(x^2\) is shown in eq. 17 .

\[\Delta^2\vert \mathcal{Q}\rangle=\vert\mathcal{Q}\rangle^2=\Delta\Delta\vert \mathcal{X}^2_1\rangle\vert\mathcal{X}^1_0\rangle\vert \mathcal{A}_0\rangle^2\mathcal{A}_0\rangle^1\mathcal{S}\rangle=\Delta\vert \mathcal{X}^2_1\rangle\vert\mathcal{X}^1_0\rangle\vert \mathcal{A}_0\rangle^2\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^1=\vert \mathcal{X}^2_1\rangle\vert\mathcal{X}^1_0\rangle\vert \mathcal{G}\rangle^2\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^2 \label{eq:evolutions2}\tag{17}\]

If we apply the sequence \(x^2\) starting from the initial FA state \(s_0\); i.e. \(\vert S\rangle = \vert\mathcal{S}_0\rangle\), then \(\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^1=\vert0\rangle\vert\mathcal{S}_1\rangle=\vert0\rangle\vert1\rangle\) and \(\vert\mathcal{S}\rangle^2=\vert\mathcal{S}_2\rangle=\vert2\rangle\) and \(\vert\mathcal{G}\rangle^2=\vert0\rangle\).

3.4 Executing all possible input sequences starting from a single quantum state↩︎

Here we generalize equation  14 considering the application of all input sequences of length \(l\) to an initial QTS encompassing an initial FA state encoded by \(\vert\mathcal{S}\rangle\).

We recall that the inputs, ancillae, and the quantum states are defined on \(\kappa=\log_2 k\), \(\mu=\log_2 m\) and \(\nu =\log_2 n\) qubits respectively. Let’s start by a sequence length of \(l\), with each input of the sequence \(\vert\mathcal{X}_j^l\rangle...\vert\mathcal{X}_i^1\rangle\) being encoded on \(\kappa\) qubits encoding \(k\) input values. There will be all together \(l\kappa\) qubits used to encode an input sequence of \(l\) inputs. We create a superposition of all (the \(k^l\)) input sequences of length \(l\) and with \(k\) possible input values defined as in eq. 18 . \[\begin{gather} \vert\prescript{l}{k}{\mathcal{X}}\rangle=H^{\otimes^{l\kappa}}\vert\mathcal{X}_0^l\rangle\otimes\ldots\otimes\vert\mathcal{X}^1_0\rangle\\=H^{\otimes^{\kappa}}\vert\mathcal{X}_0^l\rangle\otimes\ldots\otimes H^{\otimes^{\kappa}}\vert\mathcal{X}^1_0\rangle=\underbrace{H^{\otimes^{\kappa}}\vert0\rangle^{\otimes^{\kappa}}\otimes\ldots \otimes H^{\otimes^{\kappa}}\vert0\rangle^{\otimes^{\kappa}}}_{l}\\=\underbrace{H\vert0\rangle\otimes\ldots\otimes H\vert0\rangle}_{H^{\otimes^\kappa}\mathcal{X}^l_0}\otimes\ldots\otimes \underbrace{H\vert0\rangle\otimes\ldots\otimes H\vert0\rangle}_{H^{\otimes^\kappa}\mathcal{X}^1_0}=\underbrace{\frac{1}{\sqrt{k^l}}(\vert0\rangle+\vert1\rangle)\otimes (\vert0\rangle+\vert1\rangle)\otimes\ldots\otimes(\vert0\rangle+\vert1\rangle)}_{kl}\\=\frac{1}{\sqrt{k^l}}\left (\underbrace{\underbrace{\vert0\ldots0\rangle}_{\mathcal{X}^l_0}\ldots\underbrace{\vert0\ldots0\rangle}_{\mathcal{X}^1_0}}_l+\ldots+\underbrace{\underbrace{\vert1\ldots1\rangle}_{\mathcal{X}_{k-1}^l}\ldots\underbrace{\vert1\ldots1\rangle}_{\mathcal{X}_{k-1}^1}}_l \right)=\frac{1}{\sqrt{k^l}}\left (\vert\mathcal{X}_0^l\rangle\ldots\vert\mathcal{X}^1_0\rangle+\ldots+\vert\mathcal{X}_{k-1}^l\rangle\ldots\vert\mathcal{X}^1_{k-1}\rangle \right) \label{eq:super} \end{gather}\tag{18}\]

Combining the superposed input sequences with the ancillae and the state registers, we derive the QTS \(\vert\bar{\mathcal{Q}}\rangle=\vert\prescript{l}{k}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^l\ldots \vert \mathcal{A}_0\rangle^1\vert \mathcal{S}\rangle\). The application of all input sequences of length \(l\) to \(\vert\bar{\mathcal{Q}}\rangle\) is shown in equation. 19 .

\[\begin{gather} \Delta^l\vert\bar{\mathcal{Q}}\rangle =\vert\bar{\mathcal{Q}}\rangle^l =\Delta^l\vert\prescript{l}{k}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^l\ldots \vert \mathcal{A}_0\rangle^1\vert \mathcal{S}\rangle\\=\Delta^l\frac{1}{\sqrt{{k^l}}}\left (\vert\mathcal{X}^l_0\ldots \mathcal{X}^1_0\rangle\vert \mathcal{A}_0\rangle^l\ldots \vert\mathcal{A}_0\rangle^1\vert \mathcal{S}\rangle+\ldots+\vert\mathcal{X}^l_{k-1}\ldots \mathcal{X}^1_{k-1}\rangle\vert \mathcal{A}_0\rangle^l\ldots \vert\mathcal{A}_0\rangle^1\vert \mathcal{S}\rangle\right ) \\=\frac{1}{\sqrt{k^{l}}}\left (\vert\mathcal{X}^l_0\ldots \mathcal{X}^1_0\rangle\vert \mathcal{G}\rangle^{l,0}\ldots \vert\mathcal{G}\rangle^{1,0}\vert \mathcal{S}\rangle^{l,0}+\ldots+\vert\mathcal{X}^l_{k-1}\ldots \mathcal{X}^1_{k-1}\rangle\vert \mathcal{G}\rangle^{l,k^l-1}\ldots \vert\mathcal{G}\rangle^{1,k^l-1}\vert \mathcal{S}\rangle^{l,k^l-1}\right ) \label{eq:ginitq3} \end{gather}\tag{19}\]

Let \(\sigma\) denote the \(0... k^r-1\) possible input sequences, over the FA input alphabet, of length \(r=1...l\). Each input sequence in the superposition of input sequences creates a superposition of the resulting garbage ancillae qubits. We denote by \(\vert\mathcal{G}\rangle^{r,\sigma}\ldots\vert\mathcal{G}\rangle^{1,\sigma}\) the garbage qubits resulting from the application of the \(\sigma^\text{th}\) input sequence of length \(r\) to state \(\vert\mathcal{S}\rangle\). Similarly, we use \(\vert\mathcal{S}\rangle^{r,\sigma}\) to denote the quantum state reached after the application of the \(\sigma^\text{th}\) input sequence of length \(r\).

The circuit representing the whole process of putting inputs in superposition, creating all input sequences of length \(l\), applying all these input sequences to the FA state encoded by \(\vert\mathcal{S}\rangle\) reaching the collection FA states encoded by \(\vert\mathcal{S}\rangle^l\) is shown in Figure  3.

Each quantum state \(\vert\mathcal{G}\rangle^{r}....\vert\mathcal{G}\rangle^1\vert\mathcal{S}\rangle^{r} = \sum_{\sigma=0}^{k^r-1}\vert\mathcal{G}\rangle^{r,\sigma}....\vert\mathcal{G}\rangle^{1,\sigma}\vert\mathcal{S}\rangle^{r,\sigma}\) contains the FA states encoded by \(\vert\mathcal{S}\rangle^{r}\) reached by the application of all the input sequences of length \(r\) to the FA state encoded by \(\vert\mathcal{S}\rangle\). Figure 3 however represents the succession of the QTS evolution in a step by step manner. For instance, \(\vert\mathcal{G}\rangle^{1}\vert\mathcal{S}\rangle^{1}\) \(=\sum_{\sigma=0}^{k-1}\vert\mathcal{G}\rangle^{1,\sigma}\vert\mathcal{S}\rangle^{1,\sigma}\), represents the states \(\vert\mathcal{S}\rangle^1\) reached by the application of the input sequences (denoted by \(\sigma=0..k^1-1\)) of length \(r=1\) to the initial QTS encoded by \(\vert\mathcal{S}\rangle\) and the related garbage encoded in \(\vert\mathcal{G}\rangle^1\).

Observe that in the circuit of Figure 3 each box marked indicates \(H^{\otimes^\kappa}\) applied to the qubits encoding each input such as \(\vert\mathcal{X}_0^1\rangle =\vert0\ldots0\rangle\).

Working example: Considering the initial QTS \(\vert\mathcal{Q}\rangle = \vert\mathcal{X}_0^2\mathcal{X}_1^1\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\mathcal{S}\rangle = \vert1100\mathcal{S}\rangle\), we create \(\vert\bar{\mathcal{Q}}\rangle\) by setting the input qubits to \(0\) and then apply one hadamard quantum gate for each input qubit. The input superposition creation is shown in eq. 20 , \[\begin{gather} \vert\prescript{2}{2}{\mathcal{X}}\rangle=H^{\otimes 2}\vert\mathcal{X}_0^2\mathcal{X}_0^1\rangle=H\vert\mathcal{X}_0^2\rangle\otimes H\vert\mathcal{X}_0^1\rangle=H\vert0\rangle\otimes H\vert0\rangle\\= \frac{1}{\sqrt{2^2}}\left (\vert0\rangle+ \vert1\rangle\right )\left\vert0\rangle+\vert1\rangle\right )= \frac{1}{\sqrt{2^2}}\left (\vert00\rangle+ \vert01\rangle+\vert10\rangle+\vert11\rangle\right )\\= \frac{1}{\sqrt{2^2}}\left (\vert\mathcal{X}^2_0\mathcal{X}^1_0\rangle+ \vert\mathcal{X}^2_0\mathcal{X}^1_1\rangle+\vert\mathcal{X}^2_1\mathcal{X}^1_0\rangle+\vert\mathcal{X}^2_1\mathcal{X}^1_1\rangle\right ) \label{eq:exqbar} \end{gather}\tag{20}\] and the resulting QTS \(\vert\bar{\mathcal{Q}}\rangle\) is shown in eq. 21 . \[\begin{gather} \vert\bar{\mathcal{Q}}\rangle = \vert\prescript{2}{2}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle=\frac{1}{\sqrt{2^2}}\left (\vert\mathcal{X}^2_0\mathcal{X}^1_0\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle+ \vert\mathcal{X}^2_0\mathcal{X}^1_1\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle\right .\\\left .+\vert\mathcal{X}^2_1\mathcal{X}^1_0\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle+\vert\mathcal{X}^2_1\mathcal{X}^1_1\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle\right ) \label{eq:exqbar1} \end{gather}\tag{21}\] Then evolve the initial QTS using all input sequences of length \(l=2\). The result is shown in eq. 22 . \[\begin{gather} \Delta^2\vert\bar{\mathcal{Q}}\rangle=\vert\bar{\mathcal{Q}}\rangle^2=\Delta^2\vert\prescript{2}{2}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert \mathcal{S}\rangle \\= \Delta^2\frac{1}{\sqrt{2^2}}\left (\vert\mathcal{X}^2_0\mathcal{X}^1_0\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle+ \vert\mathcal{X}^2_0\mathcal{X}^1_1\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle+\vert\mathcal{X}^2_1\mathcal{X}^1_0\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle+\vert\mathcal{X}^2_1\mathcal{X}^1_1\rangle\vert\mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1\vert\mathcal{S}\rangle\right )\\= \frac{1}{\sqrt{2^2}} \left (\vert\mathcal{X}^2_0\mathcal{X}^1_0\rangle\vert\mathcal{G}\rangle^{2,1}\vert\mathcal{G}\rangle^{1,1}\vert\mathcal{S}\rangle^{2,1}+\vert\mathcal{X}^2_0\mathcal{X}^1_1\rangle\vert\mathcal{G}\rangle^{2,2}\vert\mathcal{G}\rangle^{1,2}\vert\mathcal{S}\rangle^{2,2}+\vert\mathcal{X}^2_1\mathcal{X}^1_0\rangle\vert\mathcal{G}\rangle^{1,3}\vert\mathcal{G}\rangle^{1,3}\vert\mathcal{S}\rangle^{2,3}+\vert\mathcal{X}^2_1\mathcal{X}^1_1\rangle\vert\mathcal{G}\rangle^{2,4}\vert\mathcal{G}\rangle^{1,4}\vert\mathcal{S}\rangle^{2,4} \right) \label{eq:init26} \end{gather}\tag{22}\] Similarly to eq. 17 , here let \(\vert \mathcal{A}_0\rangle^2\vert\mathcal{A}_0\rangle^1 = \vert 00\rangle\) and \(\vert \mathcal{S}\rangle=\vert \mathcal{S}_0\rangle\) . Then \(\vert\mathcal{G}\rangle^{2,1}\vert\mathcal{G}\rangle^{1,1}=\vert00\rangle\), \(\vert\mathcal{G}\rangle^{2,2}\vert\mathcal{G}\rangle^{1,2}=\vert00\rangle\), \(\vert\mathcal{G}\rangle^{2,3}\vert\mathcal{G}\rangle^{1,3}=\vert00\rangle\), \(\vert\mathcal{G}\rangle^{2,4}\vert\mathcal{G}\rangle^{1,4}=\vert00\rangle\) and \(\vert\mathcal{S}\rangle^{2,1}=\vert\mathcal{S}_2\rangle\), \(\vert\mathcal{S}\rangle^{2,2}=\vert\mathcal{S}_1\rangle\), \(\vert\mathcal{S}\rangle^{2,3}=\vert\mathcal{S}_2\rangle\) and \(\vert\mathcal{S}\rangle^{2,4}=\vert\mathcal{S}_0\rangle\). The corresponding quantum circuit to eq. 22 is shown in Figure 3.

The obtained QTS has the sub-QTSs that include the quantum states \(\vert \mathcal{S}\rangle^{2,1}\), \(\vert \mathcal{S}\rangle^{2,2}\), \(\vert \mathcal{S}\rangle^{2,3}\) and \(\vert \mathcal{S}\rangle^{2,4}\). If the initial QTS contains the quantum state \(\vert \mathcal{S}\rangle = \vert\mathcal{S}_0\rangle\), then \(\vert \mathcal{S}\rangle^1 = \frac{1}{\sqrt{2}}\left (\vert\mathcal{S}\rangle^{1,1}+\vert\mathcal{S}\rangle^{1,2}\right )= \frac{1}{\sqrt{2}}\left (\vert\mathcal{S}_1\rangle+\vert\mathcal{S}_0\rangle\right )\) and \(\vert \mathcal{S}\rangle^2=\frac{1}{{2}}\left (\vert\mathcal{S}\rangle^{2,1}+\vert\mathcal{S}\rangle^{2,2}+\vert\mathcal{S}\rangle^{2,3}+\vert\mathcal{S}\rangle^{2,4}\right )=\frac{1}{{2}}\left (\vert\mathcal{S}_2\rangle+\vert\mathcal{S}_1\rangle+\vert\mathcal{S}_2\rangle+\vert\mathcal{S}_0\rangle\right ) = \frac{\sqrt{2}}{{2}}\vert\mathcal{S}_2\rangle+ \frac{1}{{2}}\vert\mathcal{S}_1\rangle+ \frac{1}{{2}}\vert\mathcal{S}_0\rangle\).

The \(\Delta\) operator takes only three inputs: the input, the ancilla and the state. Therefore the \(\Delta\) operators used when a input sequence are compound operators as shown in circuit in Figure 5.

3.5 Executing all possible input sequences starting from all quantum states↩︎

In eq. 19 we show how to execute all possible inputs of certain length \(l\) starting from one state of the FA and here we generalize the approach considering the simultaneous application of all input sequences starting from each state of the FA. To this end, we map the states of the FA to the corresponding quantum states \(\vert\mathcal{S}_n\ldots\mathcal{S}_1\rangle\).

To simultaneously evolve the \(n\) FA states, we need \(n\) sets of \(l\) ancillae indexed by a subscript from \(0\) to \(n-1\), \(\vert\mathcal{A}_0\rangle^{l}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{1}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{l}_0\ldots\vert\mathcal{A}_0\rangle^{1}_0\). Putting together the superposed input sequences \(\vert\prescript{l}{k}{\mathcal{X}}\rangle\) encoded on \(l\kappa\) qubits , the ancillae \(\vert\mathcal{A}_0\rangle^{l}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{1}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{l}_0\ldots\vert\mathcal{A}_0\rangle^{1}_0\) encoded on \(l\nu\mu\) qubits, and the states \(\vert\mathcal{S}_{n-1}\ldots\mathcal{S}_0\rangle\) encoded on \(n\nu\) qubits, we create the QTS, which contains all the \(n\) states of the FA, \(\vert\bar{\mathcal{Q}_n}\rangle =\vert\prescript{l}{k}{\mathcal{X}}\rangle\vert\mathcal{A}_0\rangle^{l}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{1}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{l}_0\ldots\vert\mathcal{A}_0\rangle^{1}_0\vert\mathcal{S}_n\ldots\mathcal{S}_1\rangle\).

Then we apply, in parallel, \(l\) times in a series the \(\Delta\) operator representing the execution of the first, second, to the \(l\)-th input of each input sequence starting from the initial states of \(\vert\bar{\mathcal{Q}_n}\rangle\) as shown in eq. 23 . Because the result is a superposition of all input sequences and all reached FA states, the garbage qubits have been indexed as \(\vert\mathcal{G}\rangle_{p}^{l,k^{r}-1}\ldots\vert\mathcal{G}\rangle_{p}^{1,k^{r}-1}\), \(r=1..l; p=0...n-1; \sigma=0..k^r-1\). This indexing reflects the fact that the garbage qubits have been obtained by the application of the \(\sigma\) input sequence starting from \(\vert\mathcal{S}_{p}\rangle\) FA state. Similarly, the reached FA states \(\vert\mathcal{S}_{n-1}\ldots\mathcal{S}_0\rangle^{l,k^r-1}\) are indexed so as to reflect that they have been reached by \(\sigma\) sequence of length \(l\) from the initial states \(\vert\mathcal{S}_{n-1}\ldots\mathcal{S}_0\rangle\).

\[\begin{gather} \Delta^l\vert\bar{\mathcal{Q}_n}\rangle =\vert\bar{\mathcal{Q}_n}\rangle^l =\Delta^l\vert\prescript{l}{k}{\mathcal{X}}\rangle\vert\mathcal{A}_0\rangle^{l}_{n-1}\ldots\vert\mathcal{A}_0\rangle^{1}_{n-1}\vert\mathcal{S}_{n-1}\rangle\vert\mathcal{A}_0\rangle^{l}_{n-2}\ldots\vert\mathcal{A}_0\rangle^{1}_{n-2}\vert\mathcal{S}_{n-2}\rangle\ldots\vert\mathcal{A}_0\rangle^{l}_{0}\ldots\vert\mathcal{A}_0\rangle^{1}_{0}\vert\mathcal{S}_0\rangle \\=\frac{1}{\sqrt{k^l}}\left (\vert\mathcal{X}^l_0\ldots\mathcal{X}^1_0\rangle\vert\mathcal{G}\rangle^{l,0}_{n-1}\ldots\vert\mathcal{G}\rangle_{n-1}^{1,0}\vert\mathcal{S}_{n-1}\rangle^{l,0}\dots \vert\mathcal{G}\rangle_0^{l,0}\ldots\vert\mathcal{G}\rangle_{0}^{1,0}\vert\mathcal{S}_{0}\rangle^{l,0} \right .\\\left .\ldots +\vert\mathcal{X}^l_{k^l-1}\ldots\mathcal{X}^1_{k^l-1}\rangle \vert\mathcal{G}\rangle_{n-1}^{l,k^l-1}\ldots\vert\mathcal{G}\rangle_{n-1}^{1,k^l-1}\vert\mathcal{S}_{n-1}\rangle^{l,k^l-1}\dots \vert\mathcal{G}\rangle_0^{l,k^l-1}\ldots\vert\mathcal{G}\rangle_{0}^{1,k^l-1}\vert\mathcal{S}_{0}\rangle^{l,k^l-1}\right ) \label{eq:result3} \end{gather}\tag{23}\]

The circuit corresponding to eq. 23 is shown in Figure 6. Each quantum state \(\vert\mathcal{G}\rangle_p^{r}\ldots\vert\mathcal{G}\rangle^1_p\vert\mathcal{S}_p\rangle^{r} = \sum_{\sigma=0}^{k^r-1}\vert\mathcal{G}\rangle_{p}^{r,\sigma} \ldots\vert\mathcal{G}\rangle_{p}^{1,\sigma}\vert\mathcal{S}_p\rangle^{r,\sigma}\) contains the FA states encoded by \(\vert\mathcal{S}_p\rangle^{r}\), reached by the application of all input sequences of length \(r\) to the FA states encoded by \(\vert\mathcal{S}_p\rangle\).

Working example: The example FA has two states and thus the initial TQS for such a FA is shown in eq. 24 . \[\vert\mathcal{Q}_2\rangle =\vert\mathcal{X}_0^2\mathcal{X}_0^1\rangle\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_2\mathcal{S}_1\mathcal{S}_0\rangle \label{eq:init351}\tag{24}\] We index the ancillae by a subscript \(q=0,1\) such that \(\vert\mathcal{A}^l_0\rangle_q\) represents an ancilla that will be used with the \(q^{th}\) initial FA state \(\vert\mathcal{S}_q\rangle\).

Following eq. 20 , we put the inputs in eq. 24 in superposition resulting in the quantum state \(\vert\bar{\mathcal{Q}}\rangle\) shown in eq. 25 . \[\begin{gather} \vert\bar{\mathcal{Q}}_2\rangle =\vert\prescript{2}{2}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_2\mathcal{S}_1\mathcal{S}_0\rangle\\=\vert\prescript{2}{2}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle \label{eq:init35} \end{gather}\tag{25}\]

The two consecutive applications of \(\Delta\) (similar to eq. 22 ) to \(\vert \bar{Q}\rangle\) from eq. 25 are shown in eq. 26 .

\[\begin{gather} \Delta^{2}\vert\bar{\mathcal{Q}}_2\rangle=\vert\bar{\mathcal{Q}}_2\rangle^2= \Delta^{2}\vert\prescript{2}{2}{\mathcal{X}}\rangle\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle\\= \frac{1}{\sqrt{2^2}}\left [ \Delta\Delta\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle +\Delta\Delta\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle \right . \\ \left .+\Delta\Delta\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle \vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle \Delta\Delta\vert \mathcal{A}_0\rangle^2_2\vert\mathcal{A}_0\rangle^1_2\vert\mathcal{S}_2\rangle\vert \mathcal{A}_0\rangle^2_1\vert\mathcal{A}_0\rangle^1_1\vert\mathcal{S}_1\rangle\vert\mathcal{A}_0\rangle^2_0\vert\mathcal{A}_0\rangle^1_0\vert\mathcal{S}_0\rangle\right ]\\= \frac{1}{\sqrt{2^2}}\left [ \vert \mathcal{X}_0^2\mathcal{X}_0^1\rangle\vert \mathcal{G}\rangle_2^{2,1}\vert\mathcal{G}\rangle_2^{1,1}\vert\mathcal{S}_2\rangle^{2,1}\vert \mathcal{G}\rangle_1^{2,1} \vert\mathcal{G}\rangle_1^{1,1}\vert\mathcal{S}_1\rangle^{2,1}\vert\mathcal{G}\rangle_0^{2,1}\vert\mathcal{G}\rangle_0^{1,1}\vert\mathcal{S}_0\rangle^{2,1} \right . \\ \left .+\vert \mathcal{X}_0^2\mathcal{X}_1^1\rangle\vert \mathcal{G}\rangle_2^{2,2}\vert\mathcal{G}\rangle_2^{1,2}\vert\mathcal{S}_2\rangle^{2,2}\vert \mathcal{G}\rangle_1^{2,2} \vert\mathcal{G}1\rangle_1^{1,2}\vert\mathcal{S}_1\rangle^{2,2}\vert\mathcal{G}\rangle_0^{2,2}\vert\mathcal{G}\rangle_0^{1,2}\vert\mathcal{S}_0\rangle^{2,2} \right . \\ \left .+\vert \mathcal{X}_1^2\mathcal{X}_0^1\rangle\vert \mathcal{G}\rangle_2^{2,3}\vert\mathcal{G}\rangle_2^{1,3}\vert\mathcal{S}_2\rangle^{2,3}\vert \mathcal{G}\rangle_1^{2,3} \vert\mathcal{G}\rangle_1^{1,3}\vert\mathcal{S}_1\rangle^{2,3}\vert\mathcal{G}\rangle_0^{2,3}\vert\mathcal{G}\rangle_0^{1,3}\vert\mathcal{S}_0\rangle^{2,3} \right . \\ \left .+\vert \mathcal{X}_1^2\mathcal{X}_1^1\rangle\vert \mathcal{G}\rangle_2^{2,4}\vert\mathcal{G}\rangle_2^{1,4}\vert\mathcal{S}_2\rangle^{2,4}\vert \mathcal{G}\rangle_1^{2,4} \vert\mathcal{G}\rangle_1^{1,4}\vert\mathcal{S}_1\rangle^{2,4}\vert\mathcal{G}\rangle_0^{2,4}\vert\mathcal{G}\rangle_0^{1,4}\vert\mathcal{S}_0\rangle^{2,4} \right ]\label{eq:init4} \end{gather}\tag{26}\]

with \(\vert \mathcal{G}\rangle_2^{2,1}\vert\mathcal{G}\rangle_2^{1,1}\vert\mathcal{S}_2\rangle^{2,1}=\vert 00\rangle\vert\mathcal{S}_1\rangle\), \(\vert \mathcal{G}\rangle_1^{2,1}\vert\mathcal{G}\rangle_1^{1,1}\vert\mathcal{S}_1\rangle^{2,1}=\vert 00\rangle\vert\mathcal{S}_0\rangle\), \(\vert\mathcal{G}\rangle_0^{2,1}\vert\mathcal{G}\rangle_0^{1,1}\vert\mathcal{S}_0\rangle^{2,1}=\vert00\rangle\vert\mathcal{S}_2\rangle\), \(\vert\mathcal{G}\rangle_2^{2,2}\vert\mathcal{G}\rangle_2^{1,2}\vert\mathcal{S}_2\rangle^{2,2}=\vert01\rangle\vert\mathcal{S}_0\rangle\), \(\vert\mathcal{G}\rangle_1^{2,2}\vert\mathcal{G}\rangle_1^{1,2}\vert\mathcal{S}_1\rangle^{2,2}=\vert00\rangle\vert\mathcal{S}_0\rangle\), \(\vert\mathcal{G}\rangle_0^{2,2}\vert\mathcal{G}\rangle_0^{1,2}\vert\mathcal{S}_0\rangle^{2,2}=\vert00\rangle\vert\mathcal{S}_1\rangle\), \(\vert\mathcal{G}\rangle_2^{2,3}\vert\mathcal{G}\rangle_2^{1,3}\vert\mathcal{S}_2\rangle^{2,3}=\vert00\rangle\vert\mathcal{S}_0\rangle\), \(\vert\mathcal{G}\rangle_1^{2,3}\vert\mathcal{G}\rangle_1^{1,3}\vert\mathcal{S}_1\rangle^{2,3}=\vert10\rangle\vert\mathcal{S}_2\rangle\), \(\vert\mathcal{G}\rangle_0^{2,3}\vert\mathcal{G}\rangle_0^{1,3}\vert\mathcal{S}_0\rangle^{2,3}=\vert00\rangle\vert\mathcal{S}_2\rangle\), \(\vert \mathcal{G}\rangle_2^{2,4}\vert\mathcal{G}\rangle_2^{1,4}\vert\mathcal{S}_2\rangle^{2,4}=\vert 11\rangle\vert\mathcal{S}_2\rangle\), \(\vert \mathcal{G}\rangle_1^{2,4}\vert\mathcal{G}\rangle_1^{1,4}\vert\mathcal{S}_1\rangle^{2,4}=\vert 10\rangle\vert\mathcal{S}_2\rangle\), \(\vert\mathcal{G}\rangle_0^{2,4}\vert\mathcal{G}\rangle_0^{1,4}\vert\mathcal{S}_0\rangle^{2,4}=\vert00\rangle\vert\mathcal{S}_0\rangle\). However to the shortest resetting sequence has length \(l=4\). To save space we show only their resulting QTS with the input sequences and the state collections while omitting the garbage qubits.

\[\begin{gather} \frac{1}{\sqrt{2^4}}\left ( \vert \mathcal{X}_0^4\mathcal{X}_0^3\mathcal{X}_0^2\mathcal{X}_0^1\rangle\vert\mathcal{S}_0\rangle\vert\mathcal{S}_1\rangle\vert\mathcal{S}_2\rangle+[\vert \mathcal{X}_0^4\mathcal{X}_0^3\mathcal{X}_0^2\mathcal{X}_1^1\rangle+\vert \mathcal{X}_0^4\mathcal{X}_1^3\mathcal{X}_0^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_0^4\mathcal{X}_1^3\mathcal{X}_1^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_0^4\mathcal{X}_1^3\mathcal{X}_1^2\mathcal{X}_1^1\rangle]\vert\mathcal{S}_0\rangle\vert\mathcal{S}_0\rangle\vert\mathcal{S}_1\rangle\right . \\ \left .+[\vert \mathcal{X}_0^4\mathcal{X}_0^3\mathcal{X}_1^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_0^4\mathcal{X}_0^3\mathcal{X}_1^2\mathcal{X}_1^1\rangle]\vert\mathcal{S}_1\rangle\vert\mathcal{S}_1\rangle\vert\mathcal{S}_2\rangle +\vert \mathcal{X}_0^4\mathcal{X}_1^3\mathcal{X}_0^2\mathcal{X}_1^1\rangle\vert\mathcal{S}_0\rangle\vert\mathcal{S}_1\rangle\vert\mathcal{S}_1\rangle \right . \\ \left .+(\vert \mathcal{X}_1^4\mathcal{X}_0^3\mathcal{X}_0^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_1^4\mathcal{X}_1^3\mathcal{X}_0^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_1^4\mathcal{X}_1^3\mathcal{X}_1^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_1^4\mathcal{X}_1^3\mathcal{X}_1^2\mathcal{X}_1^1\rangle)\vert\mathcal{S}_0\rangle\vert\mathcal{S}_2\rangle\vert\mathcal{S}_2\rangle\right . \\ \left .+\vert \mathcal{X}_1^4\mathcal{X}_0^3\mathcal{X}_0^2\mathcal{X}_1^1\rangle\vert\mathcal{S}_2\rangle\vert\mathcal{S}_2\rangle\vert\mathcal{S}_2\rangle +[\vert \mathcal{X}_1^4\mathcal{X}_0^3\mathcal{X}_1^2\mathcal{X}_0^1\rangle+\vert \mathcal{X}_1^4\mathcal{X}_0^3\mathcal{X}_1^2\mathcal{X}_1^1\rangle+\vert \mathcal{X}_1^4\mathcal{X}_1^3\mathcal{X}_0^2\mathcal{X}_1^1\rangle] \vert\mathcal{S}_0\rangle\vert\mathcal{S}_0\rangle\vert\mathcal{S}_2\rangle\right ) \label{eq:init8} \end{gather}\tag{27}\]

which concretely results in

\[\begin{gather} \frac{1}{\sqrt{2^4}}\left ( \vert 0000\rangle\vert 012\rangle +(\vert 0001\rangle+\vert 0100\rangle+\vert 0110\rangle+\vert 0111\rangle)\vert 001\rangle +(\vert 0010\rangle+\vert 0011\rangle)\vert 112\rangle+\vert 0101\rangle\vert 011\rangle \right . \\ \left .+(\vert 1000\rangle+\vert 1100\rangle+\vert 1110\rangle+\vert 1111\rangle)\vert 022\rangle+\vert 1001\rangle\vert 222\rangle +(\vert 1010\rangle+\vert 1011\rangle+\vert 1101\rangle)\vert 002\rangle\right ) \label{eq:init85} \end{gather}\tag{28}\]

The corresponding circuit is shown in Figure 6.

3.6 Extracting a resetting sequence↩︎

For an input sequence \(c\) of length \(l\) and the \(n\) states of an FA, encoded in initial quantum states \(\vert\mathcal{S}_{n-1}\rangle....\vert\mathcal{S}_{0}\rangle\), let \(\bar{\vert\mathcal{S}}\rangle^{l,c}\) denote the collection (orederd list) of \(n\) FA states, encoded in quantum states \(\vert\mathcal{S}_{n-1}\rangle^l....\vert\mathcal{S}_{0}\rangle^l\) reached after the application of \(c\) to the initial quantum states as indicated in equation eq. 23 . Similarly, for input sequence \(c\), consider the related collection \(\bar{\vert\mathcal{S}}\rangle^{l,c}\). These collections are considered to be the same (equivalent) if the following holds:

\[\bar{\vert\mathcal{S}}\rangle^{l,c} = \bar{\vert\mathcal{S}}\rangle^{l,d} \implies (\vert\mathcal{S}_p\rangle^{l,c}=\vert\mathcal{S}_p\rangle^{l,d},\forall p=0...n-1). \label{eq:resss1}\tag{29}\]

Then Eq. 29 can factor eq. 23 as shown in eq. 30 . \[\begin{align} \Delta^l\vert\bar{\mathcal{Q}_n}\rangle &=\vert\bar{\mathcal{Q}_n}\rangle^l\nonumber \\ &=\frac{1}{\sqrt{k^l}}\left (\vert\mathcal{X}^l_0\ldots\mathcal{X}^1_0\rangle\vert\mathcal{G}\rangle^{l,0}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,0}_{n-1}\vert\mathcal{S}_{n-1}\rangle^{l,0}\ldots\vert\mathcal{G}\rangle_0^{l,0}\ldots\vert\mathcal{G}\rangle^{1,0}_{0}\vert\mathcal{S}_{0}\rangle^{l,0} +\ldots+\vert\mathcal{X}^l_{i}\ldots\mathcal{X}^1_{h}\rangle\vert\mathcal{G}\rangle^{l,c}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,c}_{n-1}\vert\mathcal{S}_{n-1}\rangle^{l,c}\nonumber \right .\\&\left .\ldots\vert\mathcal{G}\rangle^{l,c}_{0}\ldots\vert\mathcal{G}\rangle^{1,c}_{0}\vert\mathcal{S}_{0}\rangle^{l,c}+\ldots+\vert\mathcal{X}^l_{m}\ldots\mathcal{X}^1_{l}\rangle\vert\mathcal{G}\rangle^{l,d}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,d}_{n-1}\vert\mathcal{S}_{n-1}\rangle^{l,d}\ldots\vert\mathcal{G}\rangle^{l,d}_{0}\ldots\vert\mathcal{G}\rangle^{1,d}_{0}\vert\mathcal{S}_{0}\rangle^{l,d}\nonumber \right .\\&\left .+\ldots+\vert\mathcal{X}^l_{k-1}\ldots\mathcal{X}^1_{k-1}\rangle\vert\mathcal{G}\rangle^{l,k^l-1}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,k^l-1}_{n-1}\vert\mathcal{S}_{n-1}\rangle^{l,k^l-1}\ldots\vert\mathcal{G}\rangle^{l,k^l-1}_{0}\ldots\vert\mathcal{G}\rangle^{1,k^l-1}_{0}\vert\mathcal{S}_{0}\rangle^{l,k^l-1} \right )\tag{30} \\&=\frac{1}{\sqrt{k^l}}\left (\vert\mathcal{X}^{1}_0\ldots\mathcal{X}^{1}_0\rangle\vert\mathcal{G}\rangle^{l,0}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,0}_{0}\vert\bar{\mathcal{S}}\rangle^{l,0}+\ldots+\tikzmark{M1}\left [\vert\mathcal{X}^l_{i}\ldots\mathcal{X}^1_{h}\rangle\vert\mathcal{G}\rangle^{l,c}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,c}_{0}+\vert\mathcal{X}^l_{m}\ldots\mathcal{X}^1_{l}\rangle\vert\mathcal{G}\rangle^{l,d}_{n-1}\ldots\vert\mathcal{G}\rangle^{1,d}_{0}\right ]\tikzmark{M2}\tikzmark{M3}\vert\bar{\mathcal{S}}\rangle^{l,c}\tikzmark{M4}\nonumber \right .\\ &\left .+\ldots+\vert\mathcal{X}^l_{k-1}\ldots\mathcal{X}^1_{k-1}\rangle\vert\mathcal{G}\rangle^{k^l-1}_{n-1}\ldots\vert\mathcal{G}\rangle^{k^l-1}_{0}\vert\bar{\mathcal{S}}\rangle^{l,k^l-1} \right )\nonumber \tag{31} \end{align}\]

Equation 30 thus naturally factors into a form that includes both all input sequences with the associated garbage qubits (in Box B in eq. 30 ) such that these sequences lead to the same collection of quantum states; here, \(\vert\bar{\mathcal{S}}\rangle^{l,c}\) (in Box A in eq. 30 ).

Using Grover algorithm on eq. 30 , with the oracle searching for the qubits representing a factored collection say \(\bar{\vert\mathcal{S}}{\rangle^{l,c}}\) such that all quantum states of the collection correspond to the same FA state ; i.e., the following holds: eq. 32 . \[\vert\mathcal{S}_p\rangle^{l,c}= \vert\mathcal{S}_{p+1}\rangle^{l,c}, p=0..n-2 \label{eq:synch}\tag{32}\]

We apply the Grover algorithm [33] with oracle searching for a collection where all its elements correspond to the same FA state. Finally upon measurement we identify a collection which is a solution and we obtain all input sequences (RSs) that reach that solution. In general, in the worst-case, we reach \(M=k^l\) collections; where the upper bound on \(k^l\) is \(n^n\). Let \(M'\) be the number of collections with the same FA state, where the upper bound on \(M'\) is \(n\). Then the number of iterations required for the amplitude amplification to find a solution is \(\sqrt{\frac{M}{M'}}\). Therefore, before applying the Grover algorithm, we first search for \(M'\) using the Quantum Counting algorithm [37]. Then if \(M'< (M/2)\), which is always the case as the \(n\) is much smaller than \(M/2\), we apply the Grover algorithm [33].

The resulting state from eq. 28 is thus searched using the Grover algorithm on the qubits representing the quantum states. For instance, after three iterations of Grover algorithm, the quantum state from eq. 28 would results in the quantum state shown in eq. 33 .

\[\begin{gather} \sqrt{\frac{1}{4}}\left ( \vert 0000\rangle\vert 012\rangle +(\vert 0001\rangle+\vert 0100\rangle+\vert 0110\rangle+\vert 0111\rangle)\vert 001\rangle +(\vert 0010\rangle+\vert 0011\rangle)\vert 112\rangle+\vert 0101\rangle\vert 011\rangle \right . \\ \left .+(\vert 1000\rangle+\vert 1100\rangle+\vert 1110\rangle+\vert 1111\rangle)\vert 022\rangle +(\vert 1010\rangle+\vert 1011\rangle+\vert 1101\rangle)\vert 002\rangle\right )+\sqrt{\frac{3}{4}}\vert 1001\rangle\vert 222\rangle \label{eq:grovex} \end{gather}\tag{33}\] Such state would result with a probability of 75% in measuring the the state \(\vert222\rangle\) and thus indicating that the synchronizing sequence is \(\vert1001\rangle\). The algorithm can be parameterized more precisely to give more dependable results after measurement.

4 Space complexity of finding a RS using our approach↩︎

4.1 Complexity↩︎

The space complexity of the classical brute-force depth-first-search algorithm for an \(n\)-state FA for finding a resetting sequence is of polynomial order \(n\log(n)+n\) [10]. In the presented quantum framework, for an \(n\)-state FA, the space complexity for finding a resetting sequence is linear. A related proof is given in the supplementary material.

For finding an RS, in a classical brute-force algorithm, one has to generate and evaluate all the \(M=k^l\) input sequences in the worst case. Thus, the time complexity is exponentially given by \(O(k^l)\). In the proposed method, the time complexity of simulating and generating all state combinations by applying the \(l\) sequences to all states of the FA is of order \(O(l)\).

In addition, in a classical algorithm, each generated combination \(x'\) is evaluated by a comparator. However, in the proposed quantum algorithm, the target combination needs to be searched using the amplitude amplification algorithm. The complexity of such a search is \(\sqrt{\frac{M}{M'}}\). The solutions are the input sequences that lead to the same set of states as defined in Eq. 32 . When the number of target solutions is \(1\), the amplitude amplification algorithm is equivalent to the Grover algorithm [33]. Thus, the gain over a classical brute-force algorithm is quadratic. In addition, the speed of convergence of the amplitude amplification algorithm (Grover algorithm with multiple solutions) accelerates for \(M'>1\). Note that while the classical algorithm generates \(k^l\) collections of states, the quantum algorithm generates at most \(n^n\) distinct collections. According to eq. 30 , collections with the same quantum states combine together. As a result, the amplitude amplification algorithm searches at a maximum of \(n^n\) states. This also implies that while the gain of the proposed model is in the linear steps of generating all the collections of states \(l\) versus \(k^l\), the number of searched state collections is a relative gain \(n^n\) versus \(k^l\) when \(k^l < n^n\). Moreover, when the quantum algorithm searches for \(l: k^l<n^n\), the number of searched state collections is \(k^l\).

5 Conclusion↩︎

Finite state transition systems (FA) are used to represent hardware, software, mathematical, biological, and many other systems. We consider a well-known problem used in various domains which relates to finding an input sequence, called resetting sequence, which can bring the system to a known or safe state independent of its current state. In general the problem is exponential; and accordingly we solve the problem using a quantum model. To this end, we use a proper representation of a given state machine in quantum space, and we search for an intended solution by exploring the behavior of the machine under all input sequences in superposition followed by a proper Grover search throughout the states reached by these sequences. A quadratic gain is provided by our approach over the exponential complexity of a traditional brute-force method, which is the only method that can be applied to a general FA class. A simulator is given online as a proof of concept.

The proposed approach paves the way for utilizing the work in various related domains; and in particular, we focus now on adapting and extending the work in FSM-based testing [5], [38], where many types of input sequences, in addition to resetting sequences, are used in test derivation.

6 Appendices↩︎

References↩︎