Supervisory Control of Quantum Discrete Event Systems

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}.$$

We get $(A\otimes B)(C\otimes D)=AC\otimes BD$ if the operations $AC$ and $BD$ can be done in terms of multiplication of matrices.

Matrix $M\in\mathbb{C}^{n\times n}$ is said to be unitary if $MM^{\dagger}=M^{\dagger}M=I$, 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 denoted by $||x||$ is defined as $||x||=\big{(}\sum_{i=1}^{n}x_{i}x_{i}^{*}\big{)}^{\frac{1}{2}}$, where symbol $*$ denotes conjugate operation. Unitary matrices preserve the norm, i.e., $||xM||=||x||$ for each $x\in\mathbb{C}^{1\times n}$ and unitary matrix $M\in\mathbb{C}^{n\times n}$.

Any quantum system can be described by a state of Hilbert space. More specifically, for a quantum system with a finite basic state set $Q=\{q_{1},\dots,q_{n}\}$, every basic state $q_{i}$ can be represented by an $n$-dimensional row vector $\langle q_{i}|=(0\dots 1\dots 0)$ having only 1 at the $i$th 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}^{n}c_{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 the Hilbert space ${\cal H}_{Q}$ spanned by the base $\{|q_{i}\rangle:i=1,2,\dots,n\}$, i.e. ${\cal H}_{Q}=\text{span}\{|q_{i}\rangle:i=1,2,\dots,n\}$.

The evolution of quantum system’s states complies with unitarity. More exactly, suppose the current state of system is $|\phi\rangle$. If it is acted on by some unitary matrix $M_{1}$, then the system’s state is changed to the new current state $M_{1}|\phi\rangle$; the second unitary matrix, say $M_{2}$, is acted on $M_{1}|\phi\rangle$, the state is further 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_{k}M_{k-1}\cdots M_{1}|\phi\rangle$.

If we want to get some information from a quantum system, then a measurement is made 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 ${\cal O}=c_{1}P_{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 ${\cal O}$ has result set $\{c_{i}\}$ and projector set $\{P_{i}\}$. For example, given state $|\psi\rangle$ is made by the measurement ${\cal 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\|}$.

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$. First we recall the definitions of deterministic finite automata (DFA) and probabilistic finite automata (PFA).

In order to study the decision of controllability condition, in this subsection we introduce the method of how to determine the equivalence between 1QFAC, and the details are referred to [36, 37, 28].

Associated to a BLM, the word function

$$L_{\mathcal{M}}:\Sigma^{\ast}\longrightarrow\mathbb{C}$$

(7)

is defined in the way:

$$L_{\mathcal{M}}(w)=\eta M(w_{m})M(w_{m-1})\ldots M(w_{1})\pi,$$

(8)

where $w=w_{1}w_{2}\ldots w_{m}\in\Sigma^{\ast}$. In particular, when $L_{\cal M}(w)\in\mathbb{R}$ for every $w\in\Sigma^{*}$, ${\cal M}$ is called a real-valued bilinear machine (RBLM).

The following proposition determines the equivalence between BLM (RBLM) [40, 41, 42, 43].

The following proposition [36, 37] is also useful in this paper.

By means of Lemma 1 and Proposition 1, we have the following theorem.

In this subsection, we briefly review some basic concepts concerning DES [1, 2]. A DES is modeled and represented as a nondeterministic finite automaton $G$, described by $G=(Q,\Sigma,\delta,q_{0},Q_{m})$, where $Q$ is the finite set of states; $\Sigma$ is the finite set of events; $\delta:Q\times\Sigma\rightarrow{\cal P}(Q)$ is the transition function (In what follows, ${\cal P}(X)$ represents the power set of set $X$.); $q_{0}\in Q$ is the initial state; and $Q_{m}\subseteq Q$ is called the set of marked states. Indeed, transition function $\delta$ can be naturally extended to $Q\times\Sigma^{*}$ in the following manner: For any $q\in Q$, any $s\in\Sigma^{*}$ and $\sigma\in\Sigma$, $\delta(q,\epsilon)=\epsilon,\hskip 5.69054pt{\rm and}\hskip 5.69054pt\delta(q,s\sigma)=\delta(\delta(q,s),\sigma),$ where we define $\delta(A,\sigma)=\bigcup_{q\in A}\delta(q,\sigma)$ for any $A\in{\cal P}(Q)$.

In particular, when $\delta$ is a map from $Q\times\Sigma$ to $Q$, then it is a DFA, as we depict it in Fig. 1.

In fact, in $G$ we can represent $q_{i}$ by vector $s_{i}=(0\hskip 5.69054pt\cdots\hskip 5.69054pt1\hskip 5.69054pt\cdots\hskip 5.69054pt0)^{T}$ where 1 is in the $i$th place and the dimension equals $n$ ($T$ denotes transpose); for $\sigma\in\Sigma$, $\sigma$ is represented as a 0-1 matrix $(a_{ij})_{n\times n}$ where $a_{ij}\in\{0,1\}$, and $a_{ij}=1$ if and only if $q_{j}\in\delta(q_{i},\sigma)$. Analogously, vector $(0\hskip 5.69054pt\cdots\hskip 5.69054pt1\hskip 5.69054pt0\hskip 5.69054pt\cdots\hskip 5.69054pt1\hskip 5.69054pt\cdots\hskip 5.69054pt0)^{T}$ in which 1 is in the $i$th and $j$th places, respectively, means that the current state may be $q_{i}$ or $q_{j}$.

For a DES modeled by finite automaton $G=(Q,\Sigma,\delta,q_{0},Q_{m})$, $L(G)=\{x\in\Sigma^{*}:\delta(q_{0},x)\in Q\}$ represents all feasible input strings in DES $G$, and $L_{m}(G)=\{x\in\Sigma^{*}:\delta(q_{0},x)\in Q_{m}\}$ is called the language marked by $G$.

In order to define and better understand parallel composition of quantum finite automata, we reformulate the parallel composition of crisp finite automata [1, 2]. For finite automata $G_{i}=(Q_{i},\Sigma_{i},\delta_{i},q_{0i},Q_{mi})$, $i=1,2$, we reformulate the parallel composition in terms of the following fashion:

$\displaystyle G_{1}\|G_{2}=(Q_{1}\otimes Q_{2},\Sigma_{1}\cup\Sigma_{2},\delta_{1}\|\delta_{2},q_{10}\otimes q_{20},Q_{m1}\otimes Q_{m2}).$

(14)

Here, $Q_{1}\otimes Q_{2}=\{q_{1}\otimes q_{2}:q_{1}\in Q_{1},q_{2}\in Q_{2}\}$, and symbol $``\otimes"$ denotes tensor product. For event $\sigma\in\Sigma_{1}\cup\Sigma_{2}$, we define the corresponding matrix of $\sigma$ in $G_{1}\|G_{2}$ as follows:

(i) If event $\sigma\in\Sigma_{1}\cap\Sigma_{2}$, then $\sigma=\sigma_{1}\otimes\sigma_{2}$ where $\sigma_{1}$ and $\sigma_{2}$ are the matrices of $\sigma$ in $G_{1}$ and $G_{2}$, respectively.

(ii) If event $\sigma\in\Sigma_{1}\backslash\Sigma_{2}$, then $\sigma=\sigma_{1}\otimes I_{2}$ where $\sigma_{1}$ is the matrix of $\sigma$ in $G_{1}$, and $I_{2}$ is unit matrix of order $|Q_{2}|$.

(iii) If event $\sigma\in\Sigma_{2}\backslash\Sigma_{1}$, then $\sigma=I_{1}\otimes\sigma_{2}$ where $\sigma_{2}$ is the matrix of $\sigma$ in $G_{2}$, and $I_{1}$ is unit matrix of order $|Q_{1}|$.

In terms of the above (i-iii) regarding the event $\sigma\in\Sigma_{1}\cup\Sigma_{2}$, we can define $\delta_{1}\|\delta_{2}$ as: For $q_{1}\otimes q_{2}\in Q_{1}\otimes Q_{2}$, $\sigma\in\Sigma_{1}\cup\Sigma_{2}$,

		$\displaystyle(\delta_{1}\|\delta_{2})(q_{1}\otimes q_{2},\sigma)$		(15)
	$\displaystyle=$	$\displaystyle\left\{\begin{array}[]{lll}(\sigma_{1}\otimes\sigma_{2})\times(q_{1}\otimes q_{2}),&{\rm if}&\sigma\in\Sigma_{1}\cap\Sigma_{2},\\ (\sigma_{1}\otimes I_{2})\times(q_{1}\otimes q_{2}),&{\rm if}&\sigma\in\Sigma_{1}\backslash\Sigma_{2},\\ (I_{1}\otimes\sigma_{2})\times(q_{1}\otimes q_{2}),&{\rm if}&\sigma\in\Sigma_{2}\backslash\Sigma_{1},\end{array}\right.$		(19)

where $\times$ is the usual product between matrices, and, as indicated above, symbol $\otimes$ denotes tensor product of matrices.

In the interest of completeness, in this subsection, we would recall the automata model for probabilistic discrete event systems (PDES). Formally, there are two definitions concerning PDES, and we name them PDES-I and PDES-II respectively.

PDES-II are defined in light of PFA in [39] that are from [44, 45, 46] as follows.

However, the problems of state complexity in PDES-I and PDES-II still need to be studied.

As in [31], a quantum language over finite input alphabet $\Sigma$ is defined as a function mapping words to probabilities, i.e., a function from $\Sigma^{\ast}$ to $[0,1]$.

For any 1QFA ${\cal M}$ (MO-1QFA,1QFAC) with finite input alphabet $\Sigma$, the accepting probability $L_{\cal M}(x_{1}\dots x_{n})$ for any $x_{1}\dots x_{n}\in\Sigma^{*}$ is defined as before. Therefore ${\cal M}$ generates a quantum language $L_{{\cal M}}$ over finite input alphabet $\Sigma$.

For any two quantum languages $f_{1}$ and $f_{2}$ over finite input alphabet $\Sigma$, denote $f_{2}\subseteq f_{2}$ if and only if $f_{2}(w)\leq f_{2}(w)$ for any $w\in\Sigma^{*}$.

Denote

$$L_{{\cal M}}^{\lambda}=\{x\in\Sigma^{\ast}:f_{\cal M}(x)>\lambda\},$$

(22)

where $0\leq\lambda<1$. Then $L_{{\cal M}}^{\lambda}$ is called the language recognized by ${\cal M}$ with cut-point $\lambda$.

A language, denoted by $L_{{\cal M}}^{\lambda,\rho}\subseteq\Sigma^{\ast}$, is recognized by ${\cal M}$ with some cut-point $\lambda$ isolated by some $\rho>0$, if for any $x\in L_{{\cal M}}^{\lambda,\rho}$, $f_{{\cal M}}(x)\geq\lambda+\rho$ and for any $x\notin L_{{\cal M}}^{\lambda,\rho}$, $f_{{\cal M}}(x)\leq\lambda-\rho$. In fact, if a language $L$ is recognized by a 1QFA ${\cal M}$ with some cut-point $\lambda$ isolated by some $\rho>0$, then $L$ is also called to be recognized by a 1QFA ${\cal M}$ with bounded error.

In DES, the event set (input alphabet) $\Sigma$ is partitioned into two disjoint subsets $\Sigma_{c}$ (controllable events) and $\Sigma_{uc}$ (uncontrollable events), and a specification language $K\subset\Sigma^{\ast}$ is given. It is assumed that controllable events can be disabled by a supervisor. To solve the supervisory control problem we need to find a supervisor for performing a feedback control with the plant that is described by an automaton. Formally, supervisor $S$ is defined as a function:

$$S:L(G)\rightarrow{\cal P}(\Sigma).$$

It is interpreted that for each $s\in L(G)$, $S(s)\cap\{\sigma:s\sigma\in L(G)\}$ represents the set of enabled events after the occurrence of $s$. Furthermore, it is required that for any $s\in L(G)$,

$$\Sigma_{uc}\cap\{\sigma\in\Sigma:s\sigma\in L(G)\}\subseteq S(s),$$

(23)

which means that after the occurrence of any physically possible string of events, the physically possible uncontrollable events are not allowed to be disabled by $S$. The condition described by Eq. (23) is called admissible for $S$ [1, 2].

A QDES is a quantum system (called a quantum plant) described by a 1QFA ${\cal M}$ together with the event set $\Sigma=\Sigma_{c}\cup\Sigma_{uc}$ and simulated as the quantum language generated by this 1QFA ${\cal M}$ (sometimes simulated as the quantum language recognized by this 1QFA ${\cal M}$ with some cut-point $\lambda$ or with some cut-point $\lambda$ isolated by some $\rho>0$).

A quantum supervisor ${\cal S}$ for controlling ${\cal M}$ is defined formally as a function ${\cal S}:\Sigma^{\ast}\rightarrow[0,1]^{\Sigma}$, where for any $s\in\Sigma^{\ast}$, ${\cal S}(s)$ is a quantum language over $\Sigma$. Intuitively, after inputting $s$ in QDES ${\cal M}$, for any $\sigma\in\Sigma$, ${\cal S}(s)(\sigma)$ denotes the degree to which $\sigma$ is enabled.

Therefore, we require that quantum supervisor ${\cal S}$ logically satisfies: $\forall\sigma\in\Sigma_{uc}$, $\forall s\in\Sigma^{\ast}$,

$$L_{{\cal M}}(s\sigma)\leq{\cal S}(s)(\sigma),$$

(24)

which denotes that both $s$ and $s\sigma$ being feasible in the quantum plant for uncontrollable event $\sigma$ results in $\sigma$ being enabled after quantum supervisor ${\cal S}$ controlling $s$. Equation (24) is called quantum admissible condition.

The feedback loop of supervisory control of QDES ${\cal M}$ controlled by quantum supervisor ${\cal S}$ can be depicted as Fig. 4.

In classical DES, given a DES modeled by finite automaton $G$ and admissible supervisor $S$, the resulting controlled system denoted by $S/G$ that means $S$ controlling $G$, is also a DES modeled by a language $L(S/G)$ defined recursively as follows [1, 2]: $\epsilon\in L(S/G)$ and $s\sigma\in L(S/G)\Longleftrightarrow s\in L(S/G)$ and $s\sigma\in L(G)$ and $\sigma\in S(s)$.

Naturally, we denote by ${\cal S}/{\cal M}$ the controlled system by ${\cal S}$, and $L_{{\cal S}/{\cal M}}$ is defined as a function from $\Sigma^{\ast}$ to $[0,1]$ as follows:

First, it is required that $L_{{\cal S}/{\cal M}}(\epsilon)=1$ (i.e., the starting state is an accepting state) and then recursively, $\forall s\in\Sigma^{\ast}$, $\forall\sigma\in\Sigma$, the following equation holds

$$L_{{\cal S}/{\cal M}}(s\sigma)=\min\{L_{{\cal S}/{\cal M}}(s),L_{{\cal M}}(s\sigma),{\cal S}(s)(\sigma)\}.$$

(25)

By intuitive the above equation logically implies that $s\sigma$ can be performed by the controlled system ${\cal S}/{\cal M}$ if and only if $s$ can be performed by the controlled system ${\cal S}/{\cal M}$ and $s\sigma$ is feasible in the quantum plant as well as $\sigma$ is enabled by the quantum supervisor ${\cal S}$ after the event string $s$ occurs.

In classical DES and automata theory, the prefix-closure $pr(L)$ of a language $L$ over alphabet $\Sigma$ is defined as: for any $s\in\Sigma^{\ast}$, $s\in pr(L)$ if and only if $st\in L$ for some $t\in\Sigma^{\ast}$. Naturaly, if ${\cal K}$ is a quantum language over alphabet $\Sigma$, then logically we define the quantum language of its prefix-closure $pr({\cal K})$ as follows: $\forall s\in\Sigma^{\ast}$,

$\displaystyle pr({\cal K})(s)=\sup_{t\in\Sigma^{\ast}}{\cal K}(st).$

(26)

Let two QDES with the same finite event set (input alphabet) $\Sigma$ be described by two 1QFAC ${{\cal M}_{i}}=(S_{i},Q_{i},\Sigma,s_{0}^{(i)},|\psi_{0}^{(i)}\rangle,\delta_{i},\mathbb{U}_{i},{\cal P}_{i})$, $i=1,2.$ Then the parallel composition of QDES ${{\cal M}_{1}}$ and ${{\cal M}_{2}}$ is their tensor operation, that is the 1QFAC ${{\cal M}_{1}}\otimes{{\cal M}_{2}}$ as follows.

	$\displaystyle{{\cal M}_{1}}\otimes{{\cal M}_{2}}=(S_{1}\otimes S_{2},Q_{1}\otimes Q_{2},\Sigma,(s_{0}^{(1)},s_{0}^{(2)}),$
	$\displaystyle|\psi_{0}^{(1)}\rangle\otimes|\psi_{0}^{(2)}\rangle,\delta_{1}\otimes\delta_{2},\mathbb{U}_{1}\otimes\mathbb{U}_{2},{\cal P}_{1}\otimes{\cal P}_{2}),$		(27)

where

• •

  $S_{1}\otimes S_{2}=\{(s_{1},s_{2}):s_{i}\in S_{i},i=1,2\}$;

• •

  $Q_{1}\otimes Q_{2}$ means the set $\{|q_{1,i}\rangle\otimes|q_{2,j}\rangle:q_{1,i}\in Q_{1},q_{2,j}\in Q_{2}\}$;

• •

  $\mathbb{U}_{1}\otimes\mathbb{U}_{2}=\{U_{s_{i}\sigma}\otimes U_{s_{j}\sigma}:(s_{i},s_{j})\in S_{1}\otimes S_{2},U_{s_{i}\sigma}\in\mathbb{U}_{1},U_{s_{j}\sigma}\in\mathbb{U}_{2},\sigma\in\Sigma\}$;

• •

  ${\cal P}_{1}\otimes{\cal P}_{2}=\{{\cal P}_{(s_{i},s_{j})}:(s_{i},s_{j})\in S_{1}\otimes S_{2}\}$ and ${\cal P}_{(s_{i},s_{j})}=\{P_{(s_{i},s_{j}),a},P_{(s_{i},s_{j}),r}\}$;

• •

  $\delta_{1}\otimes\delta_{2}((s_{1},s_{2}),\sigma)=(\delta_{1}(s_{1},\sigma),\delta_{2}(s_{2},\sigma))$.

It is easy to check that for any $s=x_{1}x_{2}\ldots x_{n}\in\Sigma^{\ast}$,

		$\displaystyle L_{{{\cal M}_{1}}\otimes{{\cal M}_{2}}}(s)$
	$\displaystyle=$	$\displaystyle\|P_{(\mu_{1}(s),\mu_{2}(s)),a}v_{1}(s)\otimes v_{2}(s)|\psi_{0}^{(1)}\rangle\otimes|\psi_{0}^{(2)}\rangle\|^{2}$		(28)
	$\displaystyle=$	$\displaystyle\|P_{\mu_{1}(s),a}v_{1}(s)|\psi_{0}^{(1)}\rangle\|^{2}\|P_{\mu_{2}(s),a}v_{2}(s)|\psi_{0}^{(2)}\rangle\|^{2}$		(29)
	$\displaystyle=$	$\displaystyle L_{{\cal M}_{1}}(s)L_{{\cal M}_{2}}(s),$		(30)

where

	$\displaystyle v_{i}(s)=$	$\displaystyle U_{\mu_{i}(x_{1}\cdots x_{n-2}x_{n-1})x_{n}}U_{\mu_{i}(x_{1}\cdots x_{n-3}x_{n-2})x_{n-1}}\cdots$
		$\displaystyle U_{\mu_{i}(x_{1})x_{2}}U_{s_{0}^{(i)}x_{1}},$		(31)

and $\mu_{i}(s)=\delta_{i}^{*}(s_{0}^{(i)},s)$, $i=1,2.$