Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

• URL: http://arxiv.org/abs/2508.21002v1
• Date: Thu, 28 Aug 2025 17:04:18 GMT
• Title: Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
• Authors: Almudena Carrera Vazquez, Aleksandros Sobczyk,
• Abstract summary: In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>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.
• Score: 47.600794349481966
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Approximating 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 success 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.

Related papers

• Sublinear Time Quantum Algorithm for Attention Approximation [13.665266438908533]
  We propose a quantum data structure that approximates any row of $mathrmAtt(Q, K, V)$ using only row queries to $Q, K, V$.<n>Our algorithm preprocesses these matrices in $widetildeOleft( -1 n0.5 left( s_2.5 + s_1.5 d + 0.5 d right)$ time, where $$ is the target accuracy, $s_$ is the $$-statistical dimension of the exponential kernel
  arXiv  Detail & Related papers  (2026-01-31T19:33:52Z)
• Quantum speed-ups for solving semidefinite relaxations of polynomial optimization [3.1798318618973362]
  We study quantum algorithms for approximating Lasserre's hierarchy values for optimization.<n>We give a quantum algorithm based on matrix multiplicative weights that approximates $_k$ to accuracy.<n>We show how to implement the required block encodings without QRAM.
  arXiv  Detail & Related papers  (2025-11-18T11:48:33Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.<n>Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.<n>Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
  arXiv  Detail & Related papers  (2023-08-16T06:46:37Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  We show that any algorithm requires $Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods. Our lower bound addresses Open Question 1WooWoo14, providing evidence for the lack of progress on algorithms for Spectral LRA.
  arXiv  Detail & Related papers  (2023-04-06T16:15:19Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  In this paper, we investigate the sample complexity of policy evaluation in offline reinforcement learning. Under the low distribution shift assumption, we show that there is an algorithm that needs at most $Oleft(maxleft fracleftVert thetapirightVert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$ samples to approximate the
  arXiv  Detail & Related papers  (2021-03-17T18:18:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.