Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

Abstract

Approximating the $k$-th spectral gap $\hat{I}{”}_k=|\hat{I}{»}_k-\hat{I}{»}_{k+1}|$ and the corresponding midpoint $\hat{I}{¼}_k=\frac{\hat{I}{»}_k+\hat{I}{»}_{k+1}}{2}$ of an $N\times N$ Hermitian matrix with eigenvalues $\hat{I}{»}_1\ge \hat{I}{»}_2\ge \dots \ge \hat{I}{»}_N$, is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error $\hat{I}\mu \hat{I}{”}_k$ using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by $O\left(\frac{N^2}{\hat{I}{\mu }^2\hat{I}{”}_k^2}\mathrm{polylog}\left(N,\frac{1}{\hat{I}{”}_k},\frac{1}{\hat{I}}\mu ,\frac{1}{\hat{I}}´\right)\right)$, where $\hat{I}\mu ,\hat{I}´\in (0,1)$ are the accuracy and the failure probability, respectively. For large gaps $\hat{I}{”}_k$, this provides a speed-up against the best-known complexities of classical algorithms, namely, $O\left(N^{\ddot{I}}‰\mathrm{polylog}\left(N,\frac{1}{\hat{I}{”}_k},\frac{1}{\hat{I}}\mu \right)\right)$, where $\ddot{I}‰\lesssim 2.371$ is the matrix multiplication exponent. A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold, while maintaining a quadratic complexity in $N$. In the black-box access model, we also report an $\hat{I}\text{c◯}(N^2)$ query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.

Published in Quantum Journal