Efficient implementation of fundamental matrix operations on quantum computers,such as matrix products and Hadamard operations,holds significant potential for accelerating machine learning algorithms.A critical prereq...Efficient implementation of fundamental matrix operations on quantum computers,such as matrix products and Hadamard operations,holds significant potential for accelerating machine learning algorithms.A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states.We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations,including the matrix product,matrix sum,matrix Hadamard product and division.Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O(poly log(mn/ε))and the matrix product with a time complexity of O(poly log(mnl/ε)),achieving an exponential speedup in contrast to the classical methods of O(mn)and O(mnl).Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O(k_(1)√mn·poly log(mn/ε))and the matrix product with a time complexity of O(k_(2)√1·poly log(mnl/ε)),where k_(1)and k_(2)are coefficients correlated with the elements of the matrix,achieving a square speedup in contrast to the classical counterparts.As applications,we construct an oracle that can access the trace of a matrix within logarithmic time,and propose several algorithms to respectively estimate the trace of a matrix,the trace of the product of two matrices,and the trace inner product of two matrices within logarithmic time.展开更多
基金Project supported by the National Natural Science Foundation of China(Grant No.61573266)the Natural Science Basic Research Program of Shaanxi(Grant No.2021JM-133)the Fundamental Research Funds for the Central Universities and the Innovation Fund of Xidian University(Grant No.YJSJ25009)。
文摘Efficient implementation of fundamental matrix operations on quantum computers,such as matrix products and Hadamard operations,holds significant potential for accelerating machine learning algorithms.A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states.We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations,including the matrix product,matrix sum,matrix Hadamard product and division.Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O(poly log(mn/ε))and the matrix product with a time complexity of O(poly log(mnl/ε)),achieving an exponential speedup in contrast to the classical methods of O(mn)and O(mnl).Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O(k_(1)√mn·poly log(mn/ε))and the matrix product with a time complexity of O(k_(2)√1·poly log(mnl/ε)),where k_(1)and k_(2)are coefficients correlated with the elements of the matrix,achieving a square speedup in contrast to the classical counterparts.As applications,we construct an oracle that can access the trace of a matrix within logarithmic time,and propose several algorithms to respectively estimate the trace of a matrix,the trace of the product of two matrices,and the trace inner product of two matrices within logarithmic time.
