论文标题
量子匹配追求：稀疏表示的量子算法
Quantum matching pursuit: A quantum algorithm for sparse representations
论文作者
论文摘要
用稀疏向量的信号具有广泛的应用，范围从图像和视频编码到形状表示和健康监测。在许多具有实时需求的应用或处理高维信号的应用中，发现稀疏表示形式的编码器的计算复杂性起着重要作用。量子计算最近显示了许多表示学习任务中有希望的加速。在这项工作中，我们提出了众所周知的匹配追求算法的量子版本。假设有易于故障的量子随机访问存储器的可用性，我们的量子匹配追击降低了其多项式因子的经典对应物的复杂性，以计算内部产物的一定错误，从而实现了高维信号的稀疏表示。除了证明我们新算法的计算复杂性外，我们还提供了数值实验，这些实验表明其误差在实践中可以忽略不计。这项工作为进一步研究量子算法开辟了道路，以查找稀疏表示形式，显示了信号处理中合适的量子计算应用。
Representing signals with sparse vectors has a wide range of applications that range from image and video coding to shape representation and health monitoring. In many applications with real-time requirements, or that deal with high-dimensional signals, the computational complexity of the encoder that finds the sparse representation plays an important role. Quantum computing has recently shown promising speed-ups in many representation learning tasks. In this work, we propose a quantum version of the well-known matching pursuit algorithm. Assuming the availability of a fault-tolerant quantum random access memory, our quantum matching pursuit lowers the complexity of its classical counterpart of a polynomial factor, at the cost of some error in the computation of the inner products, enabling the computation of sparse representation of high-dimensional signals. Besides proving the computational complexity of our new algorithm, we provide numerical experiments that show that its error is negligible in practice. This work opens the path to further research on quantum algorithms for finding sparse representations, showing suitable quantum computing applications in signal processing.
