Matrix low-rank approximate quantum algorithm based on singular value decomposition
Authors: Wang Fu-Rong , Yang Fan , Zhang Ya , Li Shi-Zhong , Wang He-Feng ,   School of Mechatronics Engineering, North University of China, Taiyuan 030051, China,   Department of Physics, Tsinghua University, Beijing 100084, China,   Department of Applied Physics, Xi’an Jiaotong University, Xi’an 710049, China
Published: June 2021

In the era of big data, efficient data processing is crucial. Quantum computing has the capability of parallel computing, which provides a new solution for convenient data processing. We propose a matrix low-rank approximate quantum algorithm based on singular value decomposition with a complexity of <inline-formula><tex-math id="M5">\begin{document}$O[{\rm{poly}}(p q)]$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M5.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M5.png"/></alternatives></inline-formula>. We conduct the principle demonstration of the algorithm in the NMR quantum computing system. In the experiment, <inline-formula><tex-math id="M6">\begin{document}$^{13}{\rm C}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M6.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M6.png"/></alternatives></inline-formula> labeled cromaric acid is used as a four-bit sample, dissolved in d6-acetone, and <inline-formula><tex-math id="M7">\begin{document}$^1 {\rm H }$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M7.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M7.png"/></alternatives></inline-formula> is decoupled in the whole process. In the case of a large number of bits, quantum principal component analysis, quantum recommendation algorithm, and other quantum algorithms can achieve the same goal, and their time complexities are basically the same. In this paper, the resonance transition algorithm is used to effectively replace the phase estimation algorithm in this kind of problem, which greatly reduces the need of auxiliary bits. Only one auxiliary bit is used and a singular value is retained to better restore the image, which is currently unable to be achieved by other algorithms based on phase estimation. Firstly, an <inline-formula><tex-math id="M8">\begin{document}$8\times8$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M8.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M8.png"/></alternatives></inline-formula>-dimensional image matrix is selected, and the pseudo-pure state is prepared by using the spatial averaging method. The quantum state reaches the target state by using gradient descent pulse to complete the preparation of the initial state. Then the shape pulse is used to apply the time-evolution operator to the initial state several times to realize the time evolution of the Hamiltonian <inline-formula><tex-math id="Z-20210720111312-1">\begin{document}$ \mathcal{H} $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_Z-20210720111312-1.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_Z-20210720111312-1.png"/></alternatives></inline-formula> of the resonance transition algorithm. Finally, the quantum state chromatography is used to read out the different components of the density matrix and reconstruct the density matrix. The experimental results are analyzed by quantum state chromatography, and the experimental values are in agreement with the theoretical ones. The fidelity is 99.84%, and the error comes mainly from the experimental equipment and the gradient pulse’s optimization algorithm. This verifies the correctness of the matrix low-rank approximate quantum algorithm proposed in this paper within the error range. For the classical algorithm, it usually takes <inline-formula><tex-math id="M9">\begin{document}$O[{\rm{poly}}(p q)]$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M9.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="15-20210411_M9.png"/></alternatives></inline-formula> to solve the low-rank matrix on the classical computer. Compared with the classical algorithm, the quantum algorithm achieves exponential acceleration.