Title: Dequantization and Hardness of Spectral Sum Estimation Show Chinese title

Title: 去量化与谱和估计的难度

Abstract: We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time $\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension. Our classical algorithm runs in time $\mathrm{polylog}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. We complement our classical upper bound with $\mathsf{DQC1}$-completeness results for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers for log-local Hamiltonians, with parameter scalings analogous to those of known quantum algorithms. Assuming $\mathsf{BPP}\subsetneq\mathsf{DQC1}$, this rules out classical algorithms with the same scalings. It also resolves a main open problem of Cade and Montanaro (TQC 2018) concerning the complexity of Schatten-$p$ norm estimation. We further analyze a block-encoding input model, where instead of a classical description of a sparse matrix, we are given a block-encoding of it. We show $\mathsf{DQC}1$-completeness in a very general way in this model for estimating $\mathrm{tr}[f(A)]$ whenever $f$ and $f^{-1}$ are sufficiently smooth. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results for high-accuracy log-determinant estimation. Show Chinese abstract

Abstract: 我们给出了对矩阵谱和估计的新去量化和难度结果，例如对数行列式。最近的量子算法表明，稀疏、条件良好、正定矩阵的行列式的对数可以在维度$N$的多项对数时间内以$\varepsilon$相对精度近似，具体时间复杂度为$\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$，其中$s$是稀疏性，$\kappa$是输入矩阵的条件数。我们提供了一种简单的这些技术的去量化方法，该方法保留了与维度的多项对数依赖关系。我们的经典算法运行时间为$\mathrm{polylog}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$，这在某些参数范围内相对于之前的经典算法有指数级的改进。我们通过针对特定谱和估计的$\mathsf{DQC1}$完全性结果来补充我们的经典上界，例如对数局部哈密顿量的逆矩阵迹和矩阵幂迹，其参数缩放与已知量子算法的参数缩放类似。 假设$\mathsf{BPP}\subsetneq\mathsf{DQC1}$，这排除了具有相同缩放比例的经典算法。 它还解决了 Cade 和 Montanaro（TQC 2018）关于 Schatten-$p$范数估计复杂性的主要开放问题。 我们进一步分析了一种块编码输入模型，在这种模型中，我们不是获得稀疏矩阵的经典描述，而是获得它的块编码。 我们在这个模型中以一种非常普遍的方式证明了$\mathsf{DQC}1$完全性，当$\mathrm{tr}[f(A)]$、$f$和$f^{-1}$具有足够的平滑性时。 我们最后得出高精度对数行列式估计的$\mathsf{BQP}$-难性和$\mathsf{PP}$-完全性结果。