王芙蓉 杨帆 张亚 李世中 王鹤峰

1) (中北大学机电工程学院, 太原 030051)

2) (清华大学物理系, 北京 100084)

3) (西安交通大学理学院, 西安 710049)

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

1 引 言

随着互联网的技术不断提高, 大数据时代正在到来.矩阵作为处理大数据的基本工具之一, 常被用于解决许多实际问题.大多数情况下, 矩阵表示在空间和时间复杂度上会随着数据的规模呈二次方增长, 这导致数据处理困难.因此, 去除冗杂信息, 只保留有用的信息, 构造低秩矩阵, 快速高效地近似一个目标矩阵, 可提高机器学习和数据管理的效果.目前, 低秩矩阵已被广泛用于模式识别[1]、图像压缩和检测[2,3]、图像处理[4,5]、人脸识别[6]等应用领域.

矩阵的低秩近似是一种稀疏表示形式, 可以在保持原矩阵的诸多性质同时, 减少冗余和噪声, 降低了数据的存储空间和……