We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. For a matrix A and a function f, the spectral sum is the trace of f(A), equivalently the sum over eigenvalues of A of f applied to each eigenvalue. Typical examples of spectral sums are the von Neumann entropy, the trace of the inverse of A, 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 in a graph.

Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating i f(A) j. We show that for any continuous function f(x):[−1,1]→ [−1,1], the quantum query complexity of computing i f(A) j± ε/4 is lower bounded by Ω(degε(f)). The upper bound is at most quadratic in degε(f) and is linear in degε(f) under certain mild assumptions on A. Here the approximate degree degε(f) is the minimum degree such that there is a polynomial of that degree approximating f up to additive error ε in the interval [−1,1]. We also show that the classical query complexity is lower bounded by Ω((s/2)(deg2ε(f)−1)/6) for any s≥ 4. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.

Computing eigenvalues of matrices is ubiquitous in numerical linear algebra problems. Currently, fast quantum algorithms for estimating eigenvalues of Hermitian and unitary matrices are known. However, the general case is far from fully understood in the quantum case. Based on a quantum algorithm for solving linear ordinary differential equations, we show how to estimate the eigenvalues of diagonalizable matrices that only have real eigenvalues. The output is a superposition of the eigenpairs, and the overall complexity is polylog in the dimension for sparse matrices. Under an assumption, we extend the algorithm to diagonalizable matrices with complex eigenvalues.

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

Straightening is the most fundamental symbolic manipulation in bracket algebra. Young's classical algorithm and White's more recent algorithm have poor performance in straightening bracket polynomials of degree >4. Rota's straightening algorithm based on Capelli operator is generally superior to the former two in speed, but still performs badly when the degree reaches 5. In this paper, a new operator is defined in bracket algebra based on tableau manipulations, and is simpler than Capelli operator. A new straightening algorithm is then proposed, and is superior to the above three algorithms by a speedup of two order of magnitude on average by testing over 500 examples in the past two years.

In this paper, we propose an SL(n)-invariant division of SL(n)-invariant polynomials by establishing an admissible order among the invariant polynomials in normal form. The invariant division leads to an invariant Gröbner basis theory.