Research On Quantum Algorithms For Structured Matrices Computation And Related Privacy Protection Issues

Structured matrices have a very wide range of applications in scientific and engineering computing.In the field of cryptography,linear feedback shift register,an important part of stream cipher,involves the computation of Toeplitz matrices;many block cipher algorithms,such as AES,involve the computation of circulant matrices.With the development of technology and society,the data that needs to be processed is increasing explosively.The performance of classical algorithms will suffer enormous challenges when solving computational problems related to structured matrices.On the other hand,in the era of big data led by the Internet,machine learning has greatly promoted the development of productivity and economy by mining valuable information from massive data.Many machine learning algorithms also involve the computation of structured matrices.However,running these machine learning algorithms and publishing the relevant results directly may lead to the risk of privacy leakage.How to protect the private information of individuals while preserving the benefits of machine learning is a common concern.Quantum computing is a new computing paradigm based on the basic principles of quantum mechanics,which shows a huge speed advantage over classical computing when solving certain problems.This dissertation is dedicated to designing quantum algorithms with significant speedup compared to classical algorithms for the computation of several common structured matrices.Moreover,this dissertation studies the application of quantum algorithms for structured matrices in machine learning,and designs privacy-preserving quantum machine learning algorithms to respond to people’s concerns about computing speed and privacy protection in the era of big data.These quantum algorithms will also promote the integration and development of cryptography,privacy technology and quantum machine learning.Specifically,this study includes the following four aspects:1.A quantum algorithm is proposed for solving a class of Toeplitz systems generated by the discretization of continuous functions.The basic idea of the algorithm is to approximate the Toeplitz matrices with tractable circulant matrices,and then solve the Toeplitz systems by solving the systems of linear equations with the circulant matrices.The result shows that when the generating function is a strictly positive continuous real-valued function,the complexity of the proposed quantum algorithm is O(κpolylog n),where κ and n are the condition number and dimension of coefficient Toeplitz matrices,respectively.This means that for the well-conditioned(κ=O(polylog n)Toeplitz systems,the proposed quantum algorithm has an exponential speedup compared to the corresponding classical algorithm.2.A quantum algorithm is proposed for solving the linear systems with common displacement structures.Specifically,by decomposing n × n dense matrices into linear combinations of displacement matrices,parametric representations of the matrices with displacement structures are derived.With such representations,block-encodings of these structured matrices are then constructed in two different data access models,i.e.,the black-box model and the QRAM data structure model.Finally,based on the constructed block coding,the quantum algorithms for various common linear systems with displacement structures are given,including the Toeplitz systems in Wiener class,the circulant systems with bounded spectral norm and some Toeplitz/Hankel-like linear systems.It is shown the linear system solvers provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model.As an application,one of the quantum linear system solvers is applied to the linear prediction of time series.3.A privacy-preserving quantum algorithm is proposed for linear least squares filter.The data matrix of least square filter is a(n-d+1)× d Toeplitz matrix,where n is the number of time series data and d is the order of the filter.By improving the method of constructing block-encoding of skewed matrix,a quantum least squares filter with improved dependence on parameter d is proposed.In addition,the sampling sensitivity of filter coefficients is calculated by amplitude estimation,and a quantum least squares filter that satisfies random differential privacy is proposed by combining the classical output perturbation strategy.The complexity of the proposed algorithm is O(poly(log n,d,κ,1/?)),where κ is the maximum condition number of all sampled data matrices and ? is the desired precision of the output.For wellconditioned skewed(d=O(polylog n))data matrices,the proposed quantum algorithm has an exponential speedup relative to the classical algorithm.4.A quantum algorithm is proposed for a class of linear regression models with differential privacy.The algorithm solves a regression model with a noise perturbation term in the objective function.For many classes of data matrices,when adding reasonable noise,the complexity of privacy-preserving quantum algorithms is slightly higher than that of non-privacy-preserving quantum algorithms,but have the same order of magnitude of speedup compared to classical algorithms.In addition,for a typical feature selection algorithm with differential privacy,a modified version is given,and the corresponding quantum algorithm is designed.The proposed quantum feature selection algorithm satisfying differential privacy can be used as a preprocessing step of the linear regression algorithm to improve the prediction performance of the model.