Research map / Learning theory and algorithms / Matrix and tensor methods

Sublinear Time Quantum Sensitivity Sampling

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a quantum sensitivity-sampling framework (Grover-based recursive halving) that builds coresets in sublinear time for clustering, lp regression, and low-rank approximation.

Problem

Constructing coresets via sensitivity sampling is typically at least linear in input size nd; the paper asks whether it can be done in sublinear time with quantum algorithms, independent of input representation and data-dependent parameters.

Approach

Recursively halve the points, approximate sensitivities against the small coreset of the half, and sample with Grover-based quantum sampling in roughly sqrt(n s) oracle queries; extended to approximator-based weights (leverage, ridge leverage, Lewis weights) and to tensor and clustering settings.

Key results

• Quantum coreset for k-median/k-means in time O~(n^0.5 d k^2.5 poly(1/eps)), improving on the prior n^0.5 d^1.5 k^0.5 bound of Xue et al.
• lp regression coreset in time O~_p(n^0.5 d^{max(0.5,p/4)+1}(eps^-3+d^0.5)), improving Apers and Gribling for p in (0,2) U (2,22]
• First quantum sublinear-time Frobenius low-rank approximation without data-dependent parameters, in O~(n d^0.5 k^0.5 eps^-1) time

Surprising findings

• Sampling tensor response rows directly from A_1 fails, but ridge leverage score sampling still yields a (2+eps)-approximate solution for tensor regression.

Limitations

• Clustering sensitivities are only upper bounds, so the recursive framework does not directly apply (two-sided approximation is open).
• Tensor low-rank approximation achieves only a (4+eps) multiplicative approximation for 3rd order tensors.
• Results are theoretical; no empirical evaluation and the quantum model assumes QRAM access.

Experimental setup

Metrics: query complexity time complexity (QRAM operations)

Baselines: Xue et al. ICML'23 clustering coreset Apers and Gribling QIP'24 Frobenius low-rank quantum algorithm PSD low-rank approximation tensor low-rank approximation (bicriteria)

Builds on: sensitivity sampling leverage score sampling quantum algorithm (Apers and Gribling) Lewis weights sampling Grover search

Closest papers by meaning

• Quantum (Inspired) $D^2$-sampling with Applications (ICLR 2025 · similarity 0.88)
• Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.87)
• A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.87)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.87)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing (CVPR 2024 · similarity 0.86)
• Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.86)