摘要 - 绘制的Sparsifation是大量算法的基础，范围从剪切问题的近似算法到图形Laplacian中线性系统的求解器。以最强的形式“光谱尖峰”将边缘的数量减少到节点数量的接近线性，同时近似保留了图形的切割和光谱结构。Benczúr和Karger（Stoc'96）的突破性工作以及Spielman和Teng（Stoc'04）表明，在原始图的边缘数量中，Sparsifitation可以在接近线性的时间内最佳地完成Sparsifation。在这项工作中，我们证明了用于光谱尖峰及其许多应用的多项式量子加速。特别是，我们给出了一种量子算法，在给定带有n个节点和m边缘的加权图中，在sublinear时间e O（√mn/ϵ）中输出了对spectral sparsifier的经典描述。我们证明这对小数因素很紧张。The algorithm builds on a string of existing results, most notably sparsification algorithms by Spielman and Srivastava (STOC'08) and Koutis and Xu (TOPC'16), a spanner construction by Thorup and Zwick (STOC'01), a single-source shortest paths quantum algorithm by Dürr et al.（ICALP'04）和Christiani，Pagh和Thorup（Stoc'15）的有效的K-K-wise独立哈希结构。我们的算法意味着用于求解拉普拉斯系统的量子加速，并近似于一系列切割问题，例如切割和最稀少的切割。索引项 - Quantum Computing;量子算法；图理论