logo

SCIENCE CHINA Information Sciences, Volume 63 , Issue 9 : 192501(2020) https://doi.org/10.1007/s11432-019-2706-9

Quantum algorithms of state estimators in classical control systems

More info
  • ReceivedJun 29, 2019
  • AcceptedOct 24, 2019
  • PublishedAug 13, 2020

Abstract

In this paper, quantum algorithms are applied to the design of state estimators in classical control systems under the condition that quantum algorithms can be physically implemented. We demonstrate that the design of state estimators can be solved by quantum algorithms, which may achieve significant acceleration in comparison to traditional classical algorithms.The time complexity can be reduced from $O(n^6)$ to $O(qn)$ when the system matrix is sparse and the condition number $\kappa$ and the reciprocal of precision $\epsilon$ are small in size $O$(poly log$(n)$), where $n$ is the dimension of state $x(t)$ and $q$ is the dimension of input $u(t)$.Our research will provide an entire quantum scheme of constructing state estimators and can be regarded as an attempt to widen application scope of quantum computation.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61673389, 61273202).


Supplement

Appendix

The impact of the inaccuracy of quantum measurement on the state estimator

The design goal of the state estimator is to make the state estimator's output $\hat{x}(t)$ as close as possible to the system state $x(t)$. Therefore, we make the steady state error $J=\lim_{t\rightarrow+\infty}\|\hat{T}(\hat{x}(t)-x(t))\|$ as a measure of the quality of the state observer constructed by matrices $\hat{T}$ and $\hat{L}$. Suppose there are $N$ measured quantum states, then the measurement error $\delta=O(\frac{1}{N})$.

After measuring quantum states $|T\rangle$ and $|L\rangle$, we get the normalized matrices $\hat{T_0}$ and $\hat{L_0}$. Because of the inaccuracy of quantum measurement, there is a deviation between the real values $T_0,~L_0$ and measured values $\hat{T_0},~\hat{L_0}$. Therefore, the coefficients $\hat{C_1}$ and $\hat{C_2}$ obtained based on $\hat{T_0},~\hat{L_0}$ also deviate from the true values $C_1$ and $C_2$, \begin{equation}T=C_1T_0, \hat{T}=\hat{C_1}\hat{T_0}=\hat{C_1}\bigg(T_0+\Delta\bigg(\frac{1}{N}\bigg)\bigg), \tag{35}\end{equation} \begin{equation}L=C_2L_0, \hat{L}=\hat{C_2}\hat{L_0}=\hat{C_2}\bigg(L_0+\Delta\bigg(\frac{1}{N}\bigg)\bigg), \tag{36}\end{equation} where $T,~L$ are the expected target matrices, $\hat{T},~\hat{L}$ are the corresponding matrices with errors and $\Delta(\frac{1}{N})$ is a set of matrices whose element $\delta_{ij}$ satisfies $\delta_{ij}=O(\frac{1}{N})$. The matrices $T_0$ and $L_0$ are normalized, so $C_1=\|T\|$ and $C_2=\|L\|$. Substituting $\hat{T}$ into (4), we get \begin{equation}\begin{aligned} &\hat{C_1}\bigg(FT_0+F\Delta\bigg(\frac{1}{N}\bigg)-T_0A-\Delta\bigg(\frac{1}{N}\bigg)A\bigg)_{11}=(GC)_{11} \\ &\mapsto\hat{C_1}\bigg(\frac{1}{C_1}GC+F\Delta\bigg(\frac{1}{N}\bigg)-\Delta\bigg(\frac{1}{N}\bigg)A\bigg)_{11}=(GC)_{11} \\ &\mapsto\hat{C_1}\bigg(\frac{1}{C_1}V_{11}+\lambda(f_1)O\bigg(\frac{1}{N}\bigg)-\sum_ia_{i1}O\bigg(\frac{1}{N}\bigg)\bigg)=V_{11}, \end{aligned} \tag{37}\end{equation} where $V_{11}=(GC)_{11}$ is the first element of matrix $GC$, $a_{i1}$ is the non-zero element of the first column of $A$, the matrix $F$ is a diagonal matrix constructed based on eigenvalue $\lambda(f_i)~(\lambda(f_i)<0)$ and $A$ is a sparse matrix. According to (37), there is \begin{equation}\hat{C_1}=\frac{V_{11}}{V_{11}+(\lambda(f_1)-\sum_ia_{i1})C_1O(\frac{1}{N})}C_1. \tag{38}\end{equation} The value of $N$ is big enough, so $\hat{C_1}\approx~C_1=\|T\|$. Based on the equation $\hat{L}=\hat{T}B$, we can get \begin{equation}\begin{aligned} &\hat{C_2}\|\hat{L_0}\|=\|C_1\bigg(T_0+\Delta\bigg(\frac{1}{N}\bigg)\bigg)B\|, \\ & \hat{C_2}=\|L+C_1\Delta\bigg(\frac{1}{N}\bigg)B\|\approx\|L\|. \end{aligned} \tag{39}\end{equation}

Let $\delta~T=\hat{T}-T,~\delta~L=\hat{L}-L$, then we may know $\delta~T\subseteq\Delta(\frac{1}{N})\|T\|,~\delta~L\subseteq\Delta(\frac{1}{N})\|L\|$. Let $e(t)=\hat{T}(\hat{x}(t)-x(t))$ and we obtain \begin{align}\dot{e}(t)&=\dot{z}(t)-\hat{T}\dot{x}(t) =Fe(t)+(F\hat{T}+GC-\hat{T}A)x(t)+(\hat{L}-\hat{T}B)u(t) \\ &=Fe(t)+(F\delta T-\delta TA)x(t)+(\delta L-\delta TB)u(t). \tag{40} \end{align} Set $\delta~U=F\delta~T-\delta~TA\subseteq\|U\|\Delta(\frac{1}{N})$ and $\delta~V=\delta~L-\delta~TB\subseteq\|V\|\Delta(\frac{1}{N})$, then we get \begin{equation}\|U\|\leq(\lambda(f)+a)\|T\|, \|V\|\leq(\|L\|+nb\|T\|), \tag{41}\end{equation} where $\lambda(f)=\text{max}(|\lambda(f_i)|)$, $a=\text{max}(|a_{ij}|)$ and $b=\text{max}(|b_{ij}|)$.

Therefore, we can obtain \begin{equation} \dot{e}(t)=Fe(t)+\delta Ux(t)+\delta Vu(t). \tag{42}\end{equation} Therefore, Eq. (42) can be transformed into \begin{equation}\dot{e_i}(t)=\lambda(f_i)e_i(t)+\sum_{j=1}^n{\delta U_{ij}x_j(t)}+\sum_{j=1}^q{\delta V_{ij}u_j(t)}, \tag{43}\end{equation} and \begin{equation} e_i(t)=E_i{\rm e}^{\lambda(f_i)t}+{\rm e}^{\lambda(f_i)t}\int{{\rm e}^{-\lambda(f_i)t}\left(\sum_{j=1}^n{\delta U_{ij}x_j(t)}+\sum_{j=1}^q{\delta V_{ij}u_j(t)}\right)}\text{d}t. \tag{44}\end{equation}

Let $y_i(t)=\sum_{j=1}^n{\delta~U_{ij}x_j(t)}+\sum_{j=1}^q{\delta~V_{ij}u_j(t)}$, then we may infer \begin{align}|y_i(t)|&=\left|\sum_{j=1}^n{\delta U_{ij}x_j(t)}+\sum_{j=1}^q{\delta V_{ij}u_j(t)}\right| \\ &\leq \left| \sum_{j=1}^n{\delta U_{ij}x_j(t)}\right|+\left|\sum_{j=1}^q{\delta V_{ij}u_j(t)}\right| \\ &\leq nx_m\|U\|O\bigg(\frac{1}{N}\bigg)+qu_m\|V\|O\bigg(\frac{1}{N}\bigg), \tag{45} \end{align} where $x_m=\text{max}(|x_{j}(t)|)$ and $u_m=\text{max}(|u_{j}(t)|)$.

According to (44), it follows: \begin{align}\lim_{t\rightarrow+\infty}|e_i(t)|&\leq\lim_{t\rightarrow+\infty}|{\rm e}^{\lambda(f_i)t}\int{{\rm e}^{-\lambda(f_i)t}y_i(t)}\text{d}t| \\ &\leq-\frac{nx_m}{\lambda(f_i)}\|U\|O\bigg(\frac{1}{N}\bigg)-\frac{qu_m}{\lambda(f_i)}\|V\|O\bigg(\frac{1}{N}\bigg) \\ &\leq-\frac{nx_m(\lambda(f)+a)}{\lambda(f_i)}\|T\|O\bigg(\frac{1}{N}\bigg)-\frac{qu_m}{\lambda(f_i)}(\|L\|+nb\|T\|)O\bigg(\frac{1}{N}\bigg), \tag{46} \end{align} and the steady state error of state estimator $J=\lim_{t\rightarrow+\infty}\|\hat{T}(\hat{x(t)}-x(t))\|$ satisfies \begin{align}J&=\lim_{t\rightarrow+\infty}\|e(t)\| \\ &\leq\sqrt{\sum_{i=1}^{n}\bigg(\frac{nx_m(\lambda(f)+a)}{\lambda(f_i)}\|T\|O\bigg(\frac{1}{N}\bigg)+\frac{qu_m}{\lambda(f_i)}(\|L\|+nb\|T\|)O\bigg(\frac{1}{N}\bigg)\bigg)^2}. \tag{47} \end{align} When all eigenvalues of the system matrix $A$ are negative, the original linear system $\Sigma_1$ is stable, $\lim_{t\rightarrow+\infty}x(t)=x$ and \begin{align}J&\leq\sqrt{\sum_{i=1}^{n}\bigg(\frac{nx_m(\lambda(f)+a)}{\lambda(f_i)}\|T\|O\bigg(\frac{1}{N}\bigg)+\frac{qu_m}{\lambda(f_i)}(\|L\|+nb\|T\|)O\bigg(\frac{1}{N}\bigg)\bigg)^2} \\ &\approx O\bigg(\frac{\sqrt{n}n^2q}{N}\bigg). \tag{48} \end{align} With the increase of the number $N$ of measured quantum states, the steady state error $J$ of state estimator decreases. We can simulate the error in Figure A1.

In addition, when the system matrix $A$ has positive eigenvalues, the $\Sigma_1$ is an unstable system. With the increase of $x(t)$, the steady state error $J$ increases. For the unstable system $\Sigma_1$, the inaccuracy of quantum measurement will seriously affect the state estimator.


References

[1] M. A. Nielsen, I. L. Chuang. Quantum Computation and Quantum Information. Cambrige: Cambridge University Press, 2000. Google Scholar

[2] Pfaff W, Hensen B J, Bernien H. Unconditional quantum teleportation between distant solid-state quantum bits. Science, 2014, 345: 532-535 CrossRef PubMed ADS arXiv Google Scholar

[3] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994: 124-134. Google Scholar

[4] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Rev, 1999, 41: 303-332 CrossRef ADS Google Scholar

[5] L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on Theory of Computing ACM, 1996: 212-219. Google Scholar

[6] Harrow A W, Hassidim A, Lloyd S. Quantum Algorithm for Linear Systems of Equations. Phys Rev Lett, 2009, 103: 150502 CrossRef PubMed ADS arXiv Google Scholar

[7] Benner P, Li J R, Penzl T. Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numer Linear Algebra Appl, 2008, 15: 755-777 CrossRef Google Scholar

[8] Sun H, Zhang J. Solving Lyapunov equation by quantum algorithm. Control Theor Technol, 2017, 15: 267-273 CrossRef Google Scholar

[9] H. Sun, J. Zhang, R. B. Wu, et al. Optimal control protocols can be exponentially accelerated by quantum algorithms. IEEE Conference on Decision and Control, 2016: 2777-2782. Google Scholar

[10] C. P. Shao. Quantum algorithms to matrix multiplication,. arXiv Google Scholar

[11] P. H. Petkov, N. D. Christov, M. M. Konstantinov. Computational Methods for Linear Control Systems. Hertfordshire: Prentice-Hall, 1991. Google Scholar

[12] C. T. Chen. Linear System Theory and Design. New Tork Oxford: Oxford University Press, 1999. Google Scholar

[13] R. E. Kalman. Mathematical Description of Linear Dynamical systems. SIAM Journal on Control 1963, 1(2): 152-192. Google Scholar

[14] G. F. Franklin, A. Emami-Naeini, J. D. Powell. Feedback Control of Dynamic Systems. Addison-Wesley, 2002, 1(10): 157-175. Google Scholar

[15] Krener A J, Isidori A. Linearization by output injection and nonlinear observers. Syst Control Lett, 1983, 3: 47-52 CrossRef Google Scholar

[16] Darouach M, Zasadzinski M, Hayar M. Reduced-order observer design for descriptor systems with unknown inputs. IEEE Trans Automat Contr, 1996, 41: 1068-1072 CrossRef Google Scholar

[17] Yue D, Han Q L, Peng C. State Feedback Controller Design of Networked Control Systems. IEEE Trans Circuits Syst II, 2004, 51: 640-644 CrossRef Google Scholar

[18] Luis A, Pe?ina J. Optimum phase-shift estimation and the quantum description of the phase difference. Phys Rev A, 1996, 54: 4564-4570 CrossRef PubMed ADS Google Scholar

[19] Berry D W, Ahokas G, Cleve R. Efficient Quantum Algorithms for Simulating Sparse Hamiltonians. Commun Math Phys, 2007, 270: 359-371 CrossRef ADS arXiv Google Scholar

[20] G. Emily, H. Mark. Quantum Computing: Progress and Prospects. The National Academy press, 2018. Google Scholar

[21] Solving large-scale control problems. IEEE Control Syst, 2004, 24: 44-59 CrossRef Google Scholar

[22] Wossnig L, Zhao Z, Prakash A. Quantum Linear System Algorithm for Dense Matrices. Phys Rev Lett, 2018, 120: 050502 CrossRef PubMed ADS arXiv Google Scholar

[23] Luenberger D G. Observing the State of a Linear System. IEEE Trans Mil Electron, 1964, 8: 74-80 CrossRef Google Scholar

  • Figure 1

    The system diagram about state estimator. $\Sigma_1$ is the original linear system, $\Sigma_2$ is the state estimator to be designed, and state feedback $K$ is the coefficient matrix.

  • Figure 2

    The flow chart of quantum algorithms of constructing state estimators. Information of the matrices $T$ and $L$ is stored in quantum registers.

  • Figure 3

    Quantum circuit for phase estimation. There are two registers in the circuit, one for storing state $|v\rangle$ and the other named M for storing the eigenvalues. Initialize M to $|0\rangle^{\bigotimes~m}$. And the bottom half of the picture is a Fourier transform. The $x_i$ is the representation of qubits of eigenvalue. Accuracy is reserved to four decimal places.

  • Figure 4

    Quantum circuit for the quantum state transition. Convert the output of the HHL algorithm to the input of the quantum algorithms of matrix multiplication. The position information of the quantum state $|x\rangle$ is stored in the register G, which controls the number of rows of the quantum state $|T\rangle$ in the register N. Where X is the NOT gate.

  • Table 1  

    Table 1The time complexity comparison between classical algorithms and our scheme

    Time complexity Our scheme when Our scheme when
    Step of classical quantum states can be quantum states cannot
    algorithms efficiently prepared be efficiently prepared
    Select $F$ and $G$ 0 0 0
    Preparing states $|\nu\rangle$ and $|B\rangle$ $/$ $O(\log(n)/\epsilon^2)$[10] $O(n^2)$[21]
    $H|r\rangle=|\nu\rangle$ $O(n^6)$ $O(\kappa_1^2\log(n)/\epsilon)$[6,8] $O(\kappa_1^2\log(n)/\epsilon)$[6,8]
    $|L\rangle=|TB\rangle$ $O(n^2q)$ $O(\kappa_2\sqrt{n}/\epsilon+nq)$[10] $O(\kappa_2\sqrt{n}/\epsilon+nq)$[10]
    Sum $O(n^6)$ $O(\kappa_2\sqrt{n}/\epsilon+nq)$ $O(\kappa_2\sqrt{n}/\epsilon+n^2)$

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号