Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms

We study the potential utility of classical techniques of spectral sparsification of graphs as a preprocessing step for digital quantum algorithms, in particular, for Hamiltonian simulation. Our results indicate that spectral sparsification of a graph with $n$ nodes through a sampling method, e.g.\ as in \cite{Spielman2011resistances} using effective resistances, gives, with high probability, a locally computable matrix $\tilde H$ with row sparsity at most $\mathcal{O}(\text{poly}\log n)$. For a symmetric matrix $H$ of size $n$ with $m$ non-zero entries, a one-time classical runtime overhead of $\mathcal{O}(m||H||t\log n/ε)$ expended in spectral sparsification is then found to be useful as a way to obtain a sparse matrix $\tilde H$ that can be used to approximate time evolution $e^{itH}$ under the Hamiltonian $H$ to precision $ε$. Once such a sparsifier is obtained, it could be used with a variety of quantum algorithms in the query model that make crucial use of row sparsity. We focus on the case of efficient quantum algorithms for sparse Hamiltonian simulation, since Hamiltonian simulation underlies, as a key subroutine, several quantum algorithms, including quantum phase estimation and recent ones for linear algebra. Finally, we also give two simple quantum algorithms to estimate the row sparsity of an input matrix, which achieve a query complexity of $\mathcal{O}(n^{3/2})$ as opposed to $\mathcal{O}(n^2)$ that would be required by any classical algorithm for the task.