Quantum algorithms for spectral sums

Abstract

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({\lambda }_j)$, where ${\lambda }_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.

References in corpus (13)

• Quantum algorithm for solving linear systems of equations
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum speedup of Monte Carlo methods
• A simple and practical algorithm for differentially private data release
• Statistical-mechanical approach to subgraph centrality in complex networks
• Quantum gradient descent for linear systems and least squares
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse
• Large-scale Log-determinant Computation through Stochastic Chebyshev Expansions
• Quantum algorithms for training Gaussian Processes
• Stochastic determination of matrix determinants
• Compiling basic linear algebra subroutines for quantum computers