论文标题
光谱总和的量子算法
Quantum algorithms for spectral sums
论文作者
论文摘要
我们提出了新的量子算法，用于估计阳性半明确（PSD）矩阵的光谱总和。用于函数$ f $的PSD矩阵$ a $的光谱总和定义为$ \ text {tr} [f（a）] = \ sum_j f（λ_j）$，其中$λ_j$是$ a $的特征值。频谱总和的典型示例是von Neumann熵，$ a^{ - 1} $的痕迹，log-determinant和schatten $ p $ -Norm，后者不需要矩阵为PSD。估计这些数量的当前最佳经典随机算法的运行时至少在矩阵的非零条目和二次误差中的非零条目中线性线性。假设访问矩阵的块编码，我们的算法在矩阵大小中是亚线性的，最多取决于其他参数，例如条件数和近似错误，因此可以与大多数随机和分布式的经典算法竞争，并在文献中提出的相同的量子脉冲，并在其他问题中提出了相同的量子。我们展示了这项工作中使用的算法和技术如何应用于光谱图理论中的三个问题：近似三角形的数量，有效的电阻和图中的跨越树的数量。
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. The spectral sum of an PSD matrix $A$, for a function $f$, is defined as $ \text{Tr}[f(A)] = \sum_j f(λ_j)$, where $λ_j$ are the eigenvalues of $A$. Typical examples of spectral sums are the von Neumann entropy, the trace of $A^{-1}$, the log-determinant, and the Schatten $p$-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees within a graph.
