量子科技中心_量科网

该团队研究非正交、过完备字典中的量子稀疏恢复问题：给定对某个态和向量字典的相干量子访问，目标是使用尽可能少的向量来以ℓ₂误差重构该态。该工作首先证明了广义恢复问题是NP难问题，排除了完全通用情况下存在高效精确算法的可能性。 为克服这一困难，该团队引入了量子正交匹配追踪（QOMP），这是经典OMP贪婪算法的首个量子类似物。QOMP结合了用于内积估计、最大值查找和块编码投影的量子子程序，并采用避免迭代间误差累积的误差重置设计。在标准互不相干性和良好条件稀疏性假设下，QOMP能够在多项式时间内确切恢复K稀疏态的支持集。 作为应用，该工作首次提出了在ℓ₂范数下使用非正交字典进行稀疏量子层析的框架，在有利条件下实现了查询复杂度Õ(√N/ε)，并将层析简化为仅需估计K个系数而非N个振幅。特别地，对于具有m=O(N)个字典向量且在良好条件子字典上稀疏度为K=Õ(1)的纯态层析，该框架通过同时利用稀疏性和非正交性，规避了在稠密正交字典设置下成立的Õ(Ω(N/ε))下界，且不存在矛盾。 除层析外，该研究还在QRAM模型中分析了QOMP，发现其相比经典OMP实现能带来多项式加速，并提供了估计m个向量字典互不相干性的量子算法，查询复杂度为O(m/ε)，优于确定性和量子启发的经典方法。