搜索

x
中国物理学会期刊

基于奇异值分解的矩阵低秩近似量子算法

CSTR: 32037.14.aps.70.20210411

Matrix low-rank approximate quantum algorithm based on singular value decomposition

CSTR: 32037.14.aps.70.20210411
PDF
HTML
导出引用
  • 在大数据时代, 高效的数据处理至关重要, 量子计算具有平行计算能力, 为方便处理数据提供了新的解决途径. 本文提出了一个基于奇异值分解的矩阵低秩近似量子算法, 复杂度为O\log(pq). 在核磁共振量子计算系统完成了算法的原理演示, 选择一个8\times8维的图像矩阵, 实现共振跃迁算法的哈密顿量\mathcalH的时间演化, 用量子态层析法分别读出密度矩阵的不同成分, 对密度矩阵进行重构, 保真度为99.84%, 在误差范围内验证了本文提出的矩阵低秩近似量子算法的正确性. 而通过奇异值分解计算低秩矩阵的经典算法的复杂度是O\mathrmpoly(p q), 量子算法与经典算法相比, 实现了指数加速.

     

    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 O\rmpoly(p q). We conduct the principle demonstration of the algorithm in the NMR quantum computing system. In the experiment, ^13\rm C labeled cromaric acid is used as a four-bit sample, dissolved in d6-acetone, and ^1 \rm H 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 8\times8-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 \mathcalH 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 O\rmpoly(p q) to solve the low-rank matrix on the classical computer. Compared with the classical algorithm, the quantum algorithm achieves exponential acceleration.

     

    目录

    /

    返回文章
    返回