Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.16801

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David Paul Woodruff, Lichen Zhang

Published Sep 20, 2025• 1 citation
arXivHTMLPDF

Abstract

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume $n,d\geq\mathrm{poly}(k/ε)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $ε$-coreset of input points of size $\tilde O(k^{4/3}ε^{-2})$ (resp. $\tilde O(k^{3/2}ε^{-2})$) in time $\tilde O(ε^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(ε^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/ε$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geqΩ(k^{7/3})$ (resp. $Ω(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $ε$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}ε^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})$ time with factored output (plus $\tilde O(nk^2ε^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $ε$-coreset of size $o(\sqrt{nS})$ needs $Ω(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(ε^{-1},\log n)$ and VC-dimension factors.

DOI
10.48550/arxiv.2509.16801

Related papers

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li +1 more

$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for $k$-clustering in $\mathbb{R}^d$ with $\tilde{O}(\sqrt{nk}d^{3/2})$ query complexity. Our coreset reduces the input size from $n$ to $\mathrm{poly}(kε^{-1}d)$, so that existing $α$-approximation algorithms for clustering can run on top of it and yield $(1 + ε)α$-approximation. This eventually yields a quadratic speedup for various $k$-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make $Ω(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation for $k$-clustering.

arXiv:2306.02826•Jun 5, 2023•1 citation

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

quant-pharXiv:2609.40302•Oct 1, 2026•0 citations

Accelerating Regression Tasks with Quantum Algorithms

C. L. Liu, Zhengfeng Ji

Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attracted considerable attention, most existing work has focused on linear regression, leaving many more complex yet practically important variants unexplored. In this work, we present a unified quantum framework for accelerating a broad class of regression tasks -- including linear and multiple regression, Lasso, Ridge, Huber, $\ell_p$-, and $δ_p$-type regressions -- achieving up to a quadratic improvement in the number of samples $m$ over the best classical algorithms. This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al. (STOC'24) using several quantum techniques, including quantum leverage score approximation (Apers &Gribling, 2024) and the preparation of many copies of a quantum state (Hamoudi, 2022). For problems of dimension $n$, sparsity $r < n$, and error parameter $ε$, our algorithm solves the problem in $\widetilde{O}(r\sqrt{mn}/ε+ \mathrm{poly}(n,1/ε))$ quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.

arXiv:2509.24757•Sep 29, 2025•1 citation

Sublinear Time Quantum Algorithm for Attention Approximation

Zhao Song, Jianfei Xue, Jiahao Zhang +1 more

Given the query, key and value matrices $Q, K, V\in \mathbb{R}^{n\times d}$, the attention module is defined as $\mathrm{Att}(Q, K, V)=D^{-1}AV$ where $A=\exp(QK^\top/\sqrt{d})$ with $\exp(\cdot)$ applied entrywise, $D=\mathrm{diag}(A{\bf 1}_n)$. The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix $D^{-1}A$ incurs $Ω(n^2)$ time, motivating numerous approximation schemes that reduce runtime to $\widetilde O(nd)$ via sparsity or low-rank factorization. We propose a quantum data structure that approximates any row of $\mathrm{Att}(Q, K, V)$ using only row queries to $Q, K, V$. Our algorithm preprocesses these matrices in $\widetilde{O}\left( ε^{-1} n^{0.5} \left( s_λ^{2.5} + s_λ^{1.5} d + α^{0.5} d \right) \right)$ time, where $ε$ is the target accuracy, $s_λ$ is the $λ$-statistical dimension of the exponential kernel defined by $Q$ and $K$, and $α$ measures the row distortion of $V$ that is at most $d/{\rm srank}(V)$, the stable rank of $V$. Each row query can be answered in $\widetilde{O}(s_λ^2 + s_λd)$ time. To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to $n$. Our approach relies on a quantum Nyström approximation of the exponential kernel, quantum multivariate mean estimation for computing $D$, and quantum leverage score sampling for the multiplication with $V$.

quant-pharXiv:2602.00874•Feb 3, 2026•0 citations

Quantum (Inspired) $D^2$-sampling with Applications

Poojan Shah, Ragesh Jaiswal

$D^2$-sampling is a fundamental component of sampling-based clustering algorithms such as $k$-means++. Given a dataset $V \subset \mathbb{R}^d$ with $N$ points and a center set $C \subset \mathbb{R}^d$, $D^2$-sampling refers to picking a point from $V$ where the sampling probability of a point is proportional to its squared distance from the nearest center in $C$. Starting with empty $C$ and iteratively $D^2$-sampling and updating $C$ in $k$ rounds is precisely $k$-means++ seeding that runs in $O(Nkd)$ time and gives $O(\log{k})$-approximation in expectation for the $k$-means problem. We give a quantum algorithm for (approximate) $D^2$-sampling in the QRAM model that results in a quantum implementation of $k$-means++ that runs in time $\tilde{O}(ζ^2 k^2)$. Here $ζ$ is the aspect ratio (i.e., largest to smallest interpoint distance), and $\tilde{O}$ hides polylogarithmic factors in $N, d, k$. It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(\log{k})$ approximation guarantee. Further, we show that our quantum algorithm for $D^2$-sampling can be 'dequantized' using the sample-query access model of Tang (PhD Thesis, Ewin Tang, University of Washington, 2023). This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + \tilde{O}(ζ^2k^2d)$, where the $O(Nd)$ term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-$k$-means++ on large datasets with bounded aspect ratio. Finally, we use our quantum $D^2$-sampling with the known $ D^2$-sampling-based classical approximation scheme (i.e., $(1+\varepsilon)$-approximation for any given $\varepsilon>0$) to obtain the first quantum approximation scheme for the $k$-means problem with polylogarithmic running time dependence on $N$.

arXiv:2405.13351•May 22, 2024•0 citations

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim +1 more

Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.

quant-pharXiv:2610.42069•Nov 2, 2026•0 citations
We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume n,d≥poly(k/ε)n,d\geq\mathrm{poly}(k/ε)n,d≥poly(k/ε) and, for regression, n≥poly(d)n\geq\mathrm{poly}(d)n≥poly(d): - kkk-median/kkk-means: For nnn points in Rd\mathbb{R}^dRd, we build an εεε-coreset of input points of size O~(k4/3ε−2)\tilde O(k^{4/3}ε^{-2})O~(k4/3ε−2) (resp. O~(k3/2ε−2)\tilde O(k^{3/2}ε^{-2})O~(k3/2ε−2)) in time O~(ε−1n0.5dk1.67)\tilde O(ε^{-1}n^{0.5}dk^{1.67})O~(ε−1n0.5dk1.67) (resp. O~(ε−1n0.5dk1.75)\tilde O(ε^{-1}n^{0.5}dk^{1.75})O~(ε−1n0.5dk1.75)). Our better ddd- and linear 1/ε1/ε1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3)d\geqΩ(k^{7/3})d≥Ω(k7/3) (resp. Ω(k2.5)Ω(k^{2.5})Ω(k2.5)). - ℓp\ell_pℓp​ regression: For min⁡x∥Ax−b∥p\min_x\|Ax-b\|_pminx​∥Ax−b∥p​, A∈Rn×dA\in\mathbb{R}^{n\times d}A∈Rn×d, we build an εεε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})O~p​(dmax{1,p/2}ε−2) in time O~p(n0.5d1.5ε−1)\tilde O_p(n^{0.5}d^{1.5}ε^{-1})O~p​(n0.5d1.5ε−1) for p≤2p\leq 2p≤2 and O~p(n0.5dp/4+1(ε−1+d0.5))\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))O~p​(n0.5dp/4+1(ε−1+d0.5)) for p>2p>2p>2, matching [Liu and Ji, ICML'26] for p≤2p\leq 2p≤2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2p>2p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-kkk approximation of A∈Rd×nA\in\mathbb{R}^{d\times n}A∈Rd×n free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5)\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})O~(n0.5dk0.5ε−0.5) time with factored output (plus O~(nk2ε−2)\tilde O(nk^2ε^{-2})O~(nk2ε−2) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity SSS, any quantum algorithm outputting an εεε-coreset of size o(nS)o(\sqrt{nS})o(nS​) needs Ω(nS)Ω(\sqrt{nS})Ω(nS​) queries, so our query complexity is optimal up to poly(ε−1,log⁡n)\mathrm{poly}(ε^{-1},\log n)poly(ε−1,logn) and VC-dimension factors.
kkk-Clustering in Rd\mathbb{R}^dRd (e.g., kkk-median and kkk-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality nnn, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for kkk-clustering in Rd\mathbb{R}^dRd with O~(nkd3/2)\tilde{O}(\sqrt{nk}d^{3/2})O~(nk​d3/2) query complexity. Our coreset reduces the input size from nnn to poly(kε−1d)\mathrm{poly}(kε^{-1}d)poly(kε−1d), so that existing ααα-approximation algorithms for clustering can run on top of it and yield (1+ε)α(1 + ε)α(1+ε)α-approximation. This eventually yields a quadratic speedup for various kkk-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Ω(nk)Ω(\sqrt{nk})Ω(nk​) queries in order to achieve even O(1)O(1)O(1)-approximation for kkk-clustering.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O~(n+m)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.
Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attracted considerable attention, most existing work has focused on linear regression, leaving many more complex yet practically important variants unexplored. In this work, we present a unified quantum framework for accelerating a broad class of regression tasks -- including linear and multiple regression, Lasso, Ridge, Huber, ℓp\ell_pℓp​-, and δpδ_pδp​-type regressions -- achieving up to a quadratic improvement in the number of samples mmm over the best classical algorithms. This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al. (STOC'24) using several quantum techniques, including quantum leverage score approximation (Apers &Gribling, 2024) and the preparation of many copies of a quantum state (Hamoudi, 2022). For problems of dimension nnn, sparsity r<nr < nr<n, and error parameter εεε, our algorithm solves the problem in O~(rmn/ε+poly(n,1/ε))\widetilde{O}(r\sqrt{mn}/ε+ \mathrm{poly}(n,1/ε))O(rmn​/ε+poly(n,1/ε)) quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.
Given the query, key and value matrices Q,K,V∈Rn×dQ, K, V\in \mathbb{R}^{n\times d}Q,K,V∈Rn×d, the attention module is defined as Att(Q,K,V)=D−1AV\mathrm{Att}(Q, K, V)=D^{-1}AVAtt(Q,K,V)=D−1AV where A=exp⁡(QK⊤/d)A=\exp(QK^\top/\sqrt{d})A=exp(QK⊤/d​) with exp⁡(⋅)\exp(\cdot)exp(⋅) applied entrywise, D=diag(A1n)D=\mathrm{diag}(A{\bf 1}_n)D=diag(A1n​). The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix D−1AD^{-1}AD−1A incurs Ω(n2)Ω(n^2)Ω(n2) time, motivating numerous approximation schemes that reduce runtime to O~(nd)\widetilde O(nd)O(nd) via sparsity or low-rank factorization. We propose a quantum data structure that approximates any row of Att(Q,K,V)\mathrm{Att}(Q, K, V)Att(Q,K,V) using only row queries to Q,K,VQ, K, VQ,K,V. Our algorithm preprocesses these matrices in O~(ε−1n0.5(sλ2.5+sλ1.5d+α0.5d))\widetilde{O}\left( ε^{-1} n^{0.5} \left( s_λ^{2.5} + s_λ^{1.5} d + α^{0.5} d \right) \right)O(ε−1n0.5(sλ2.5​+sλ1.5​d+α0.5d)) time, where εεε is the target accuracy, sλs_λsλ​ is the λλλ-statistical dimension of the exponential kernel defined by QQQ and KKK, and ααα measures the row distortion of VVV that is at most d/srank(V)d/{\rm srank}(V)d/srank(V), the stable rank of VVV. Each row query can be answered in O~(sλ2+sλd)\widetilde{O}(s_λ^2 + s_λd)O(sλ2​+sλ​d) time. To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to nnn. Our approach relies on a quantum Nyström approximation of the exponential kernel, quantum multivariate mean estimation for computing DDD, and quantum leverage score sampling for the multiplication with VVV.
Quantum (Inspired) D2D^2D2-sampling with Applications
D2D^2D2-sampling is a fundamental component of sampling-based clustering algorithms such as kkk-means++. Given a dataset V⊂RdV \subset \mathbb{R}^dV⊂Rd with NNN points and a center set C⊂RdC \subset \mathbb{R}^dC⊂Rd, D2D^2D2-sampling refers to picking a point from VVV where the sampling probability of a point is proportional to its squared distance from the nearest center in CCC. Starting with empty CCC and iteratively D2D^2D2-sampling and updating CCC in kkk rounds is precisely kkk-means++ seeding that runs in O(Nkd)O(Nkd)O(Nkd) time and gives O(log⁡k)O(\log{k})O(logk)-approximation in expectation for the kkk-means problem. We give a quantum algorithm for (approximate) D2D^2D2-sampling in the QRAM model that results in a quantum implementation of kkk-means++ that runs in time O~(ζ2k2)\tilde{O}(ζ^2 k^2)O~(ζ2k2). Here ζζζ is the aspect ratio (i.e., largest to smallest interpoint distance), and O~\tilde{O}O~ hides polylogarithmic factors in N,d,kN, d, kN,d,k. It can be shown through a robust approximation analysis of kkk-means++ that the quantum version preserves its O(log⁡k)O(\log{k})O(logk) approximation guarantee. Further, we show that our quantum algorithm for D2D^2D2-sampling can be 'dequantized' using the sample-query access model of Tang (PhD Thesis, Ewin Tang, University of Washington, 2023). This results in a fast quantum-inspired classical implementation of kkk-means++, which we call QI-kkk-means++, with a running time O(Nd)+O~(ζ2k2d)O(Nd) + \tilde{O}(ζ^2k^2d)O(Nd)+O~(ζ2k2d), where the O(Nd)O(Nd)O(Nd) term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-kkk-means++ on large datasets with bounded aspect ratio. Finally, we use our quantum D2D^2D2-sampling with the known $ D^2$-sampling-based classical approximation scheme (i.e., (1+ε)(1+\varepsilon)(1+ε)-approximation for any given ε>0\varepsilon>0ε>0) to obtain the first quantum approximation scheme for the kkk-means problem with polylogarithmic running time dependence on NNN.
Quantum algorithms for linear algebra that access a matrix AAA through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to AAA, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm ρ=∥A∥F/∥A∥ρ=\|A\|_F/\|A\|ρ=∥A∥F​/∥A∥ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use O~(ρ)\widetilde O(ρ)O(ρ) queries, whereas the best dequantized algorithms use O~(ρ4)\widetilde O(ρ^4)O(ρ4). We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant κ0>1κ_0>1κ0​>1, we construct dense linear systems with condition number at most κ0κ_0κ0​ for which sampling from the solution within a sufficiently small constant total variation distance requires Ω(ρ4/log⁡ρ)Ω(ρ^4/\logρ)Ω(ρ4/logρ) classical queries but only Θ(ρ)Θ(ρ)Θ(ρ) quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.