Quantum Matrix Multiplier

Quantum computing has the characteristics of superposition and entanglement, which make quantum computers have natural parallelism and be faster and more efficient than classical computers. The quantum matrix multiplier proposed in this paper improves the efficiency of matrix multiplication algorithms, and also meets the needs of many quantum algorithms that use matrix multiplication as an intermediate step. In our scheme, the data of two matrices are superimposed and stored in the basis state of quantum states respectively. Quantum multipliers and quantum comparators are used to make up the quantum output matrix. When a M × N matrix and a N × S matrix are multiplied, the time complexity is reduced from classical O(MNS) to quantum O(MSlog2N)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(MS\log _{2} N)$\end{document}, and the space complexity is reduced from classical O(MN + NS + MS) to quantum O(1). Moreover, unlike the existing quantum matrix multiplication algorithms, our calculation results are directly stored in the basis state, without having to rely on measurement to get the result, and can be used as an intermediate module of complex quantum algorithms.