Author name cluster

Changpeng Shao

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

AAAI Conference 2026 Conference Paper

Quantum Algorithms for Spectral Sums

Alessandro Luongo
Changpeng Shao

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.

PDF Details DOI

STOC Conference 2024 Conference Paper

Quantum and Classical Query Complexities of Functions of Matrices

Ashley Montanaro
Changpeng Shao

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) (deg 2ε ( 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.

Details