量智信息中心_量科网

将经典矩阵分解为泡利字符串的线性组合，是近期量子算法端到端实现的主要瓶颈。该研究考虑了该泡利分解问题的一个承诺版本，其中矩阵被保证仅在 \(k = \mathsf{poly}(n)\) 个泡利字符串上有支持，并通过经典稀疏查询方式给出。现有的泡利分解算法针对通用稠密问题设计，并未充分利用这种承诺的稀疏性，因此这些方法所需时间随 \(n\) 呈指数增长。该团队提出了一种经典的随机算法，该算法利用了这种稀疏性，并能以至少 \(1 - δ\) 的成功概率恢复精确的泡利分解，适用于任意 \(δ\)。在所声明的访问模型下，该算法的查询和运行时复杂度关于 \(n\)、\(k\) 和 \(\log(1/δ)\) 呈多项式级。这些结果表明，尽管对一般矩阵而言寻找泡利分解是指数级困难的，但对于已知在泡利基下稀疏的矩阵（这是操作结构化经典输入的近期量子算法所相关的场景），该问题变得高效可解。