{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreic5xsirhz5yc5kauuzixxsksmx3u7w53wglwidtcy3mqcvs7eo324",
    "uri": "at://did:plc:cx57fsir6oyzywdd4jafsdsw/app.bsky.feed.post/3mjl3u6zjz572"
  },
  "path": "/papers/q-2026-04-15-2067/",
  "publishedAt": "2026-04-15T07:23:18.000Z",
  "site": "https://quantum-journal.org",
  "tags": [
    "Paper",
    "https://doi.org/10.22331/q-2026-04-15-2067"
  ],
  "textContent": "Quantum 10, 2067 (2026).\n\nhttps://doi.org/10.22331/q-2026-04-15-2067\n\nApproximating the $k$-th spectral gap $\\Delta_k=|\\lambda_k-\\lambda_{k+1}|$ and the corresponding midpoint $\\mu_k=\\frac{\\lambda_k+\\lambda_{k+1}}{2}$ of an $N\\times N$ Hermitian matrix with eigenvalues $\\lambda_1\\geq\\lambda_2\\geq\\ldots\\geq\\lambda_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 $\\epsilon\\Delta_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}{\\epsilon^{2}\\Delta_k^2}\\mathrm{polylog}\\left( N,\\frac{1}{\\Delta_k},\\frac{1}{\\epsilon},\\frac{1}{\\delta}\\right)\\right)$, where $\\epsilon,\\delta\\in(0,1)$ are the accuracy and the failure probability, respectively. For large gaps $\\Delta_k$, this provides a speed-up against the best-known complexities of classical algorithms, namely, $O \\left( N^{\\omega}\\mathrm{polylog} \\left( N,\\frac{1}{\\Delta_k},\\frac{1}{\\epsilon}\\right)\\right)$, where $\\omega\\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 $\\Omega(N^2)$ query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.",
  "title": "Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation"
}