量子科技中心_量科网

该研究团队针对矩阵谱和（如对数行列式）的估计问题提出了新的去量子化方法和计算难度结论。近期量子算法已证明，对于稀疏、良条件、正定矩阵的行列式对数，可在与维度N的多对数时间（即poly(log(N), s, κ, 1/ε)时间内，其中s为稀疏度，κ为条件数）实现ε相对精度近似。我们发展了一种能保持维度多对数依赖性的简单去量子化技术，其经典算法运行时间为polylog(N)·s^O(√κlog κ/ε)，在特定参数区间内相对先前经典算法实现指数级加速。 通过建立𝖣𝖰𝖢𝟣完全性结果，我们证明了对于对数局部哈密顿量的特定谱和（如逆矩阵迹和矩阵幂迹）估计问题，其参数缩放与已知量子算法一致。在假设𝖡𝖯𝖯≠𝖣𝖰𝖢𝟣前提下，该结果排除了具有相同缩放因子的经典算法存在性，同时解决了Cade与Montanaro(TQC 2018)关于Schatten-p范数估计复杂度的核心开放问题。 在块编码输入模型分析中，研究人员证明：当给定矩阵的块编码而非经典稀疏描述时，对于任意满足f与f⁻¹充分光滑条件的函数，估计tr[f(A)]问题在𝖣𝖰𝖢𝟣意义下具有普适完全性。最终工作还给出了高精度对数行列式估计的𝖡𝖰𝖯困难性和𝖯𝖯完全性结论。