Parameter estimation of a linear regression model by extending least square method based on quantum computing

Document Type : Original Article

Authors

1 Department of Mathematics, Tafresh University, Tafresh, Iran

2 Department of Electrical Engineering, Tafresh University, Tafresh, Iran

Abstract

The least square error method, despite its simplicity, yields acceptable results in system identification. The process of parameter estimation in system identification leads to solving the linear equation Ax=b. The important point is that the normal method of solving the above problem has a computational complexity of O(n3) for a n×n matrix. In solving this problem, the computational complexity increases with the increase of n (the size of the data matrix). On the other hand, availability of more samples leads to better modeling of the system. In the practical problems of system identification, when the number of input data is large, the computational complexity increases greatly. In this article, the goal is to present the developed quantum algorithm for solving the problem of least square error identification. In this article, two classical-quantum and all-quantum methods are presented. Unlike conventional HHL methods, the proposed methods in this article are able to calculate unbiased parameters with non-Hermitian matrices, and color noise. The proposed classical-quantum method has a computational complexity of of O(n2 log n) and the all-quantum method has an order of O(polylog n) in relation to the size of the data matrix. The results and comparisons show that the methods proposed in the article have less complexity and limitations than classical methods (with O(n3) complexity).

Keywords

Main Subjects

References

[1] P. Eykhoff, “Identification theory: Practical implications and limitations,” Measurement, vol. 2, no. 2, pp. 75-85, 1984, doi: 10.1016/0263-2241(84)90036-8.
[2] L. Ljung, “System Identification,” Signal Anal. Predict., pp. 163-173, 1998, doi: 10.1007/978-1-4612-1768-8_11.
[3] A. Ghanbari Sorkhi, H. Hassanpour, and M. Fateh, “Regions Proposal Selection in Objects Detection and Recogntion Systems,” Soft Comput. J., vol. 5, no. 2, pp. 34-47, 2016, dor: 20.1001.1.23223707.1395.5.2.4.1 [In Persian]
[4] J.J. Vyas, B. Gopalsamy, and H. Joshi, “System Identification,” SpringerBriefs Appl. Sci. Technol., pp. 47-51, 2018, doi: 10.1007/978-981-13-2547-2_4.
[5] M. Karari, System Identification, 4th ed., Amirkabir University of Technology Press, 2013 [In Persian].
[6] M. Mohagheghi, “An approach to accelerate policy iteration for probabilistic model checking of Markov decision processes using machine learning,” Soft Comput. J., vol. 11, no. 2, pp. 134-148, 2023, doi: 10.22052/scj.2023.243360.1029 [In Persian]
[7] S. Kalantari and M.J. Abdollahifard, “Optimization-based multiple-point geostatistics: A sparse way,” Comput. Geosci., vol. 95, pp. 85-98, 2016, doi: 10.1016/j.cageo.2016.07.006.
[8] S. Kalantari, A. Madadi, M. Ramezani, and A. Hajati, “Controlling the Ground Particle Size and Ball Mill Load Based on Acoustic Signal, Quantum Computation Basis, and Least Squares Regression, Case Study: Lakan Lead-Zinc Processing Plant,” Int. J. Ind. Electron. Control Optim., vol. 6, no. 3, pp. 205-218, Sep. 2023, doi: 10.22111/ieco.2023.45981.1488.
[9] S. Kalantari, A. Madadi, and M. Ramezani, “Reconstruction of geological images based on an adaptive spatial domain filter: an example to introduce quantum computation to geosciences,” Int. J. Min. Geo-Eng., vol. 57, no. 2, pp. 183-194, 2023, doi: 10.22059/IJMGE.2023.352048.595007.
[10] M. Khosravi and M. Zekri, “A review of quantum neural networks,” Soft Comput. J., vol. 1, no. 1, pp. 46-55, 2012, dor: 20.1001.1.23223707.1391.1.1.113.0 [In Persian].
[11] Y. Liu and S. Zhang, “Fast quantum algorithms for least squares regression and statistic leverage scores,” Theor. Comput. Sci., vol. 657, pp. 38-47, 2017, doi: 10.1016/j.tcs.2016.05.044.
[12] A.W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems of equations,” Phys. Rev. Lett., vol. 103, no. 15, 2009, doi: 10.1103/physrevlett.103.150502.
[13] I. Kerenidis and A. Prakash, “Quantum Recommendation Systems,” 2016, arXiv:1603.08675, [Online]. Available: https://arxiv.org/abs/1603.08675.
[14] K. Li et al., “Quantum Linear System Algorithm for General Matrices in System Identification,” Entropy, vol. 24, no. 7, p. 893, 2022, doi: 10.3390/e24070893.
[15] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge Univ. Press, 2010, doi: 10.1017/CBO9780511976667.
[16] S. Kalantari, M. Ramezani, and A. Madadi, “Introducing a New Hybrid Adaptive Local Optimal Low Rank Approximation Method for Denoising Images,” Int. J. Ind. Electron. Control Optim., vol. 3, no. 2, pp. 173-185, 2020, doi: 10.22111/ieco.2019.31245.1199.
[17] S. Kalantari, M. Ramezani, A. Madadi, and V.V. Estrela, “Reduction AWGN from Digital Images Using a New Local Optimal Low-Rank Approximation Method,” Smart Innov. Syst. Technol., 2020, doi: 10.1007/978-3-030-57548-9_5.
[18] G.H. Golub, A. Hoffman, and G.W. Stewart, “A generalization of the Eckart-Young-Mirsky matrix approximation theorem,” Linear Algebra Appl., vol. 88-89, pp. 317-327, 1987, doi: 10.1016/0024-3795(87)90114-5.
[19] S.A. Goreinov, I. Oseledets, D. Savostyanov, E.E. Tyrtyshnikov, and N.L. Zamarashkin, “How to Find a Good Submatrix,” Matrix Methods Theory Alg. Appl., pp. 247-256, 2010, doi: 10.1142/9789812836021_0015.
[20] N.K. Kumar and J. Schneider, “Literature survey on low rank approximation of matrices,” Linear Multilinear Algebra, vol. 65, no. 11, pp. 2212-2244, 2016, doi: 10.1080/03081087.2016.1267104.
[21] L. Grover and T. Rudolph, “Creating superpositions that correspond to efficiently integrable probability distributions,” 2002, arXiv:quant-ph/0208112, [Online]. Available: https://arxiv.org/abs/quant-ph/0208112
[22] L. Wossnig, Z. Zhao, and A. Prakash, “Quantum Linear System Algorithm for Dense Matrices,” Phys. Rev. Lett., vol. 120, no. 5, 2018, doi: 10.1103/physrevlett.120.050502.
[23] Y. Cao, A. Daskin, S. Frankel, and S. Kais, “Quantum Circuit Design for Solving Linear Systems of Equations,” Mol. Phys., vol. 110, no. 15-16, pp. 1675-1680, 2012, doi: 10.1080/00268976.2012.668289.
Soft Computing Journal
Volume 13, Issue 2 - Serial Number 26
February 2025
Pages 154-169

Files

History

  • Receive Date: 18 July 2023
  • Revise Date: 06 November 2023
  • Accept Date: 16 January 2024

Share

How to cite

Statistics