Solving Lyapunov equation by quantum algorithm
Tóm tắt
Lyapunov equation is one of the most basic and important equations in control theory, which has various applications in, e.g., stability analysis and robust analysis of linear control systems. Inspired by the recent progresses of quantum algorithms, we find that solving Lyapunov equation can be exponentially accelerated by quantum algorithms rather than traditional classical algorithms. Our algorithm is more efficient especially when the system matrix is sparse and has a low condition number. The results presented in this paper open up new dimensions of research in controlling classical system by quantum information processors, which has rarely been considered in the existing literature.
Tài liệu tham khảo
P. H. Petkov, N. D. Christov, M. M. Konstantinov. Computational Methods for Linear Control Systems. Hertfordshire: Prentice-Hall, 1991.
B. N. Datta. Numerical Methods for Linear Control Systems. Boston: Elsevier Acadamic Press, 2004.
V. Sima. Algorithms for Linear-quadratic Optimization. New York: Marcel Dekker, 1996.
N. R. Sandell, P. Varaiya, M. Athans, et al. Survey of decentralized control methods for large scale systems. IEEE Transactions on Automatic Control, 1978, 23(2): 108–128.
P. Benner. Solving large-scale control problems. IEEE Control Systems, 2004, 24(1): 44–59.
P. Benner, J. R. Li, T. Penzl. Numerical solution of largescale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numerical Linear Algebra with Applications, 2008, 15(9): 755–777.
M. A. Nielsen, I. L. Chuang. Quantum Computation and Quantum Information. Cambrige: Cambridge University Press, 2000.
R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 1982, 21(6): 467–488.
P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 1994: 124–134.
P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303–332.
L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on Theory of Computing. Philadelphia: ACM, 1996: 212–219.
S. Hallgren. Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. Journal of the ACM, 2007, 54(1): 1–19.
S. Hallgren. Fast quantum algorithms for computing the unit group and class group of a number field. Proceedings of the 37th ACM Symposium on Theory of Computing, New York: ACM, 2005: 468–474.
C. Dürr, M. Heiligman, P. Hoyer, et al. Quantum query complexity of some graph problems. SIAM Journal on Computing, 2004, 35(6): 1310–1328.
A. Ambainis, A. M. Childs, Y. K. Liu. Quantum property testing for bounded-degree graphs. Proceedings of RANDOM 2011: Lecture Notes in Computer Science 6845. Princeton: Springer, 2011: 365–376.
F. Magniez, M. Santha, M. Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 2007, 37(2): 413–424.
N. Wiebe, A. Kapoor, K. M. Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation, 2014, 15(3): 318–358.
S. Lloyd, S. Garnerone, P. Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature Communications, 2016, 7: DOI 10.1038/ncomms10138.
S. Lloyd, M. Mohseni, P. Rebentrost. Quantum principal component analysis. Nature Physics, 2014, 10(9): 631–633.
D. S. Abrams, S. Lloyd. Simulation of many-body Fermi systems on a universal quantum computer. Physical Review Letters, 1997, 79(13): 2586–2589.
I. Kassal, S. P. Jordan, P. J. Love, et al. Quantum algorithms for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(48): 18681–18686.
L. A. Wu, M. S. Byrd, D. A. Lidar. Polynomial-time simulation of pairing models on a quantum computer. Physical Review Letters, 2002, 89(5): DOI 10.1103/PhysRevLett.89.057904.
A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 2009, 15(103): DOI 10.1103/PhysRevLett.103.150502.
D. W. Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 2014, 47(10): DOI 10.1088/1751-8113/47/10/ 105301.
S. K. Leyton, T. J. Osborne. A quantum algorithm to solve nonlinear differential equations. arXiv, 2008: arXiv:0812.4423.
Y. D. Cao, A. Papageorgiou, I. Petras, et al. Quantum algorithm and circuit design solving the Poisson equation. New Journal of Physics, 2013, 15(1): DOI 10.1088/1367-2630/15/1/013021.
N. Wiebe, D. Braun, S. Lloyd. Quantum algorithm for data fitting. Physical Review Letters, 2012, 109(5): DOI 10.1103/ PhysRevLett.109.05050.
P. Rebentrost, M. Mohseni, S. Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 2014, 113(13): DOI 10.1103/PhysRevLett.113.130503.
X. D. Cai, C. Weedbrook, Z. E. Su, et al. Experimental quantum computing to solve systems of linear equations. Physical Review Letters, 2013, 110(23): DOI 10.1103/PhysRevLett.110.230501.
J. Pan, Y. D. Cao, X. W. Yao, et al. Experimental realization of quantum algorithm for solving linear systems of equations. Physical Review A, 2014, 89(2): DOI 10.1103/PhysRevA.89. 022313.
S. J. Hammarling. Numerical solution of the stable, non-negative definite Lyapunov equation. IMA Journal of Numerical Analysis, 1982, 2(3): 303–323.
L. Grover, T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv, 2002: arXiv:quant-ph/0208112.
A. Luis, J. Peřina. Optimum phase-shift estimation and the quantum description of the phase difference. Physical Review A, 1996, 54(5): 4564–4570.
D. W. Berry, G. Ahokas, R. Cleve, et al. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 2007, 270(2): 359–371.