关键词: quantum algorithm, matrix operation, digital and analog-encoded states, quantum computing

Abstract: 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({\rm poly} \log(mn/\epsilon))$ and the matrix product with a time complexity of $O({\rm poly} \log (mnl/ \epsilon))$, 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} \sqrt{mn} \cdot {\rm poly} \log(mn/\epsilon))$ and the matrix product with a time complexity of $O(k_{2} \sqrt{l} \cdot {\rm poly} \log (mnl/ \epsilon))$, 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.

Key words: quantum algorithm, matrix operation, digital and analog-encoded states, quantum computing