Sublinear Time Quantum Algorithm for Attention Approximation
Authors: Zhao Song
Jianfei Xue
Jiahao Zhang
Lichen Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: quantum computing
attention approximation
numerical linear algebra
Primary area: optimization
TL;DR: We develop the first quantum algorithm to approximate the attention matrix and output any row of the attention matrix in sublinear in context length time.

Abstract: Given the query, key and value matrices $Q, K, V\in \mathbb{R}^{n\times d}$, the attention matrix 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 matrix is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix $D^{-1}A$ incurs $\Omega(n^2)$, 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( \epsilon^{-1} n^{0.5} \left( s_\lambda^{2.5} + s_\lambda^{1.5} d + \alpha^{0.5} d \right) \right)$
time, where $\epsilon$ is the target accuracy, $s_\lambda$ is the $\lambda$-statistical dimension of the exponential kernel defined by $Q$ and $K$, and $\alpha$ 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_\lambda^2 + s_\lambda 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{\"o}m approximation of the exponential kernel, quantum multivariate mean estimation for computing $D$, and quantum leverage score sampling for the multiplication with $V$.

Published as a conference paper at ICLR 2026
SUBLINEAR TIME QUANTUM ALGORITHM FOR ATTEN- TION APPROXIMATION
Zhao Song
Jianfi Xue New York University jx8 9 weennn.eeeeeeeee edu
Simons Institute for the Theory of Computing, UC Berkeley magic. 1 @nuukde@gman com
Jiahao Zhang
Lichen Zhang
ml ma..jiahaachhang22gggg com
MIT CSAIL
1 lichenzecsail.co mit edu
ABSTRACT
Given the query, key and value matrices Q, K, V Rexd the attention module is defined as Aut(Q, K, V) DV where exp(QKT/ with exp(-) applied entrywise, D = diag(AIn)). The attention module is the backbone of modern transformers and large language models. but explicitly forming the softmax matrix D- A incurs (? time, motivating numerous approximation schemes that reduce runtime to (nd) via sparsity low-rank factorization.
We propose quantum data structure that approximates any of (tt(Q, K, V) using only row queries to Q, K, V. Our algorithm preprocesses these matrices in Ô (n 0.5 (s2
+ 5 + a d.) time, where is the target accuracy, 8x is the X-statistical dimension of the exponential kernel defined by Q and K, and a measures the row distortion of V that is at most d/srank( (V), the stable rank of V.
Each row query can be answered Ö(5² +sdd time.
To our knowledge, this the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to 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.
INTRODUCTION
Transformers (Vaswani et al., 2017) have emerged as one the most successful machine learning architectures recent years, revolutionizing fields such natural language processing (Devlin et al., 2019; Yang et al., 2019; Raffel et al., 2020; Brown et al., 2020; Jiao et al., 2020), computer vision (Carion al., 2020: Dosovitskiy et al., 2021; Guo al., 2022), speech recognition (Chorowski et al., 2015; Wang et al., 2021), robotics (Liu et al., 2022), and time series forecasting (Zhou et al., 2021). These models typically operate on sequences of length n, autoregressively predicting next most likely token to produce an output of length In applications like large language models (LLMs), it has been widely observed that increasing the sequence length n significantly enhances generative performance. However, this benefit comes at substantial computational cost: the core attention module has a quadratic time complexity in n, which severely limits both training and inference scalability.
Formally, let Q, K, V E xx denote the query, key, and value embeddings. The attention module is defined as
K,( AV E BRad
where = exp(QKT /Va) E R is computed entrywise. and D (Aig(AA,) E R2 The matrix A is referred to the attention matrix, and D A as the softmax matrix. Due to the size of A, much recent research has focused on reducing the quadratic complexity by approximating attention through baased sparse attention (Daras al., 2020; Kitaev et al., 2020; Roy et al.,

---

Published as a conference paper at ICLR 2026
2021; Sun et al., 2022; Child et al., 2019; Beltagy et al., 2020; Ainslic al., 2020; Zaheer et al., 2020), linearizing the kernel through feature mapping (Katharopoulos et al., 2020; Choromanski et al., 2021; Wang al., 2020; Peng et al.. 2021), or various algorithmic and data structure optimizations (Zandich et al., 2023; Alman & Song, 2023; Han et al., 2024; Kacham et al., 2024; Zandieh et al., 2024; van den Brand et al., 2024; Song al., 2024; Kannan et al., 2025; Chu al., 2024; Chen et al., 2025b; Indyk et al., 2025).
The theoretical goal in these efforts is to achieve runtime that scales nearly linearly with n. allowing some approximation error. This is natural target, since the input size to the attention module is n x d.
On a classical computer, any algorithm that approximates attention in time ((dd) is considered optimal. But could this process be accelerated further using a quantum computer?
If our objective is to output the entire n. x d matrix (t, K, V), then ((nd) time is unavoidable due to output size. However, in many transformer applications - particularly during inference (Pope et al., 2023; Brandon et al., 2024; Adnan et al., 2024; Zhang et al., 2024a; Feng et al., 2025: Liu et al., 2024b; Kumari et al., 2024; Behnam et al., 2025; Chen et al.. 2025a;e; Indyk et al., 2025) only now queries are needed. In this setting, we aim preprocess Q, K, V into a data structure such that, for any index i E [n]. the structure can return a vector T; E TRdd that approximates the i-th row of (Q, K, V). This model circumvents the (ndd) lower bound by focusing on partial output. Nonetheless, since each row of (t, K, V) is a convex combination of rows of V, achieving truly sublinear time in n still appears classically intractable.
In this work, we answer this question affirmatively. Specifically, we construct quantum data structure that preprocesses Q, K, V using only row queries, and does so in time' On poly (d. sx, a)). where 82 is the statistical dimension of the exponential kernel matrix associated with Q and K, and is measure of the row distortion of V (see Definition C.2). Given any index i E [ni], the data structure returns an approximation to the i-th row of (Q, V) in time O + sxd).
To our knowledge, this is the first quantum algorithm to implement the row query model in sublinear time. Prior works either require superlinear preprocessing time or impose structural assumptions (Gao et al., 2023). Our approach avoids both: it makes no assumptions on Q, K, V, making it broadly applicable in practice. Moreover, our construction is conceptually simple it combines quantum techniques such as Grover search (Grover, 1996). Nyström kernel approximation, and quantum multivariate mean estimation (Cornelissen et al., 2022) to approximate each component of the attention module: D, A, and V.
Quantum Computation Model. We follow the standard quantum computation framework as in Apers & De Wolf (2022); Apers & Gribling (2023). The model allows quantum subroutines using Olog n) qubits, quantum queries to the input, and access to quantun-read/classical (QRAM) of poly(n) bits. Each quantum read or classical write takes unit cost. We measure time complexity by the number of QRAM operations. and query complexity by the number of queries to the input. In our setting, we query rows of Q, K, and V. each requiring ((d) time classically. For simplicity, we assume Q and K have been scaled by 1/d!/4, /4, which can also be done via row queries in O(d) time.
RAM
2 PRELIMINARY
Notation. Given symmetric matrices A, B E Raxn use A- B > 0 to denote A B is a positive semidefinite (PSD) matrix, i.e., for any x E Ra xt (A B)x 2 Given a matrix M E Ronn we use eXp(MM to denote the entrywise exponentiation operation. We use tr[M] to denote the trace of M. For a real matrix A, we use Al to denote its Peooree pseudoinverse, and for a square, nonsingular real matrix M, we use M to denote its inverse. For two vectors x. y RR., we x y or (I, y) to denote the inner product of x and y. We use O,, and 1,, to denote all-O's and all-1's I's vector. For a vector I E TR"", we use ||>:||2 = v vx. to denote its E2 norm, || = maxte(x) |as] to denote its Eo norm. M a PSD matrix, then we use || = Vx Mr to denote the M-energy norm of x. For a matrix A, use || to denote its spectral norm and || llc to denote its max row l norm, and ||A||] f to denote its Frobenius norm. Throughout the paper, we will also exclusively
We use Ö(-) to suppress polylogarithmic factors in n, d, 8x, and 1/c.
2

---

Published as a conference paper at ICLR 2026
work with weighted sampling matrices, usually denoted by S R for where is the total number of samples taken, let i(j) be the index of the i-th sample, then the i-th column of S is vPj ej. where
Pj is the probability of choosing the index j. We use [[[] to denote the expectation of random variable X. We use [E] to denote the indicator of whether event E happens.
Numerical Linear Algebra. We rely on several primitives from numerical linear algebra for fast approximations and provable guarantees.
Definition 2.1 (Leverage score), Let A E R Raxd The i-th leverage score of A is defined as
:: A az.
A)-
where as is the i-th row of A. Equivalently, let A UEV be its SVD, then T; = ||u, 12. where u, is the i-th row of U.
We will also work exclusively with kernel matrices. Given dataset X = {x1.-... Ir S Rd, we define the exponential kernel matrix E' E g= by Ei,; = exp((x,, Although E generally full-rank, algorithm depends only on parameter called the X-statistical dimension of E, which may be much smaller than n.
Definition 2.2 (Statistical dimension (Zhang, 2005; Hastie al., 2009)). Let E Ra be a PSD matrix, and let X > O. The X-statistical dimension of E is defined as 5x(E) +r(E(E+A1)+) When is clear from context, we write 8x for simplicity.
Note that 8 is monotonically decreasing function of X, and closely related to the notion of ridge leverage scores.
Definition 2.3 (Ridge leverage score (Alaoui & Mahoney, 2015)). Let E E Ruxn be a kernel matrix and let À > 0. The X-ridge leverage score of the data point x; is defined
= (E(E + XT)
If E = BBT for some B E Raxx, then this can be equivalently written as
T 6, (B LBB++ BB
where by is the i-th row of B.
is easy to see that Ei= 7.A = 8x. Moreover, Musco & Musco (2017) shows that Nyström approximations (Williams & Seeger, 2000) based ridge leverage score sampling yield accurate spectral approximations to E.
Lemma 2.4 (Theorem 3 of Musco & Musco (2017)). Let s Oss, (o))s)))())/)). X> O. and e (0, 1). Let E RRxn be any kernel matrix. Let S E TR be the X-ridge leverage score sampling matrix. Then the Nyström approximation = ES(S ESy S satisfies < 3 Xl with probability at least 1 - 8.
Quantum Primitives. In this paper, we primarily leverage two quantum algorithmic primitives. The first is an efficient quantum sampling oracle based on Grover search.
Lemma 2.5 (Claim 3 in Apers & De Wolf (2022)). Let be a positive integer, and let (pi...., Pu. C [o, 1] be a list of probabilities. There exists a quantuu algorithm, QSAMPLE(P) that generates a list of indices where each is sampled independently with probability Pt, in time Ö ( T, where T denotes the time required to generate any individual Pt-
The second primitive is a quantum procedure for approximating matrix-vector products using quantum multivariate mean estimation.
Lemma 2.6 (Theorem 5.1 of Apers Gribling (2023)). Let e E (0,1), 1), and let A maxd and U E " Suppose we are given quantum query access to the rows of A and the entries of v. Then there exists a guantum algorithm EEATVEC(A, u. c) that outputs a vector jı E Rd such that, with
probability at least 1 - 1/poly(n). || - AT AlllCAa A)-1 S e, uuing Ö (1, 0 [[o])o) queries A and
3

---

Published as a conference paper at ICLR 2026
3 TECHNICAL OVERVIEW
In this section, we provide an overview on the algorithmic techniques we utilize to approximate A, D and V. in sublinear time.
3.1 APPROXIMATE THE ATTENTION MATRIX VIA QUANTUM NYSTRÓM
To approximate the attention matrix A. will make use of Nyström approximation (Williams & Seeger, 2000). However, recall that = exp(QK' ); for Q * K, the matrix itself is not even symmetric. This poses significant challenges for obtaining good approximation. On the other hand, we treat the queries and keys as the dataset, and form the exponential kernel matrix over them, then the resulting matrix indeed kernel matrix.
Specifically, let the dataset X = ((1..... In. k1, (i1....,k,,, ) and consider E E R2nx2n where =
exp(QKT T
O, 1.
then the attention matrix can be retrieved via PE
where P
exp(KK) e
Rax2n the matrix consisting of the first rows of the 2n identity matrix, which selects
the first rows of E. Thus, once obtain an approximation for E, automatically obtain an approximation for A.
It remains to compute a Nyström approximation of E, as at first glance it is not clear how to even generate the ridge leverage score sampling matrix S in sublinear time. Musco & Musco (2017) shows that classical computer, it is possible to compute generalized ridge leverage score sampling matrix using (nsx) evaluations of the kernel function and additional Ö(ns)) time, via a recursive sampling scheme:
Uniformly sample half of the data points, then recursively compute the weighted sampling matrix Smxx for the subset;
Compute the generalized ridge leverage score, defined as 7/ = (B S Al)ib. and set pt min F.A log(s>/8));
Output S as the weighted sampling matrix according to pt-
The key ingredients in their algorithm are (1) the generalized ridge leverage
be computed via kernel function evaluations instead of computing the factorization (see Definition A.4), and (2) sampling according generalized ridge leverage score only increases the sample size by constant factor, hence it does not affect the asymptotic runtime of the algorithm (see Lemma A.3).
For the simpler setting of leverage score sampling, Apers & Gribling (2023) shows that this recursive framework can benefit from quantum speedup, especially the Grover search sampler of Lemma 2.5, by noting that when sampling according the leverage score, is not necessary to compute or approximate all the scores; rather, it is enough to implement an oracle that can supply any approximate leverage score when needed.
For our application, however, this oracle is much more difficult to implement, as in the setting of Apers & Gribling (2023), one could directly query the row of B, which is not the case for the kernel setting. Nevertheless, we show how to implement such an oracle for generalized ridge leverage scores of kernels. The algorithm detailed in Algorithm 1. Throughout this section, we let denote the final sample size of the Nyström approximation.
The main idea is to utilize the identity 7,* = )E ES(S ES + - E)... where Es, involves a single kernel evaluation K K(r;, vr). and S ES requires only O(s2) kernel evaluations. Finally, the term (ES(ST ES X E);.; I; and the sampled points in S. weighted appropriately, which requires ((s) kernel evaluations. This shows that we can implement the oracle by precomputing (S" ES + X1) in O(s2). Tk + time, where Tk denotes the time for kernel evaluation and w RJ 2.37 is the matrix multiplication exponent (Duan et al., 2023; Williams et al., 2024; Alman et al., 2025). Each oracle query can then be answered in (ss) Tk + 2 time. By Lemma 2.5 the quantum sampler requires only 0.5055005 oracle calls, so the overall runtime is 0.5 (Tk 8) s²).. In our setting, the
be computed by evaluating the kernel between
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Quantum Nyström approximation via recursive generalized ridge leverage score sam- pling.
1: procedure QNYSTRÖMKERNELL b dái is the failure probability, is the ridge leverage score parameter.
E (Rd)", K IR x T2 + Rm 8 E (0, 1), E
(0, o0))
2:
s O(sx log(s>/6)) (o(s/\)0()))/)
3:
4: Let So C1/2 S1
C1/2 Sr [n]
> We use A C1/2 B to denote A is uniform
subset of half of the indices of B
5:
Mo < (t.
|oo
6:
Let Do E gnx[Sol be the sampling matrix of So
7:
for f- to do
8:
M
(M+
9:
>et K, (D,- (i) my)) E R for E St where D.-1 (f) is the weight corresponding to Ii specified by Dz-1
10:
Implement oracle for q: 2 (K(x,, (D. K.) b min 16g; log (2s/0)}
MDD,,, K.) for i St
11:
12:
D. +- QSAMPLE(P)
> D3 T
D. Ds, DD
De E Buxs
14:
M, + (i() K(r,,))))
> M4 E R
end for
16: return Dr
17: end procedure
kernel function K(z;, xT)) = On..5.1255 (d + 8) + ))), sublinear in
can be computed O(d) time, which gives a runtime of
remains to analyze the approximation guarantee. Sampling according to generalized ridge leverage scores ensures that N E 3 + AI, but this does not immediately imply a bound on the
B
B
A
approximation error for exp(QKT). To address this, let F = A
C and E. = A
C
Standard spectral approximation theory guarantees that B h B = B B+B AI and C C C XL. For the off dfigonal block we are interested in A, cannot get such strong spectral approximation guarantee; fact, one can show that the best we could hope for is symmetrization bound: A+A 1
Ā T < A + T + 2X7, On the other hand, a weaker and more handy bound can be exhibited:
||~ ^ < X and ||A A & Xyn, and we will show these bounds are sufficient to derive the final approximation guarantees our algorithm.
It is also worth noting that Algorithm merely computes the weighted sampling matrix S, which can be stored compactly by recording the sampled indices and corresponding weights, but does not explicitly form the Nyström approximation E ES(S ES) E. While (S ES) can be computed and stored in Os + s² time, forming F. would take 9(ns) time, which is prohibitive due to output size. In what follows, we show that this restricted representation of S is nonetheless sufficient to approximate D, V. and Att(Q, K)
We now compare our Nyström approximation scheme to related method known as Nyström- former (Xiong et al., 2021), which also integrates Nyström into the attention mechanism. Specifically,
X1 X₂
they consider the attention matrix A and partition it as = X3 X,
aiming to approximate X4
using the other three blocks. Given Nyström landmark points Q' and K' sampled from Q and K, they set X = exp((' K" X2 = exp(QK'T) and X; exp(Q' K Since the number of landmarks is small, these blocks are all low- diwddiinsiioal. Xiong et al. (2021) proves that X, can be efficiently approximated using X1, X2, and X3 in O(nmd) time, where is the number of landmarks. While Nyströmformer performs well in practice, guarantees convergence to the true attention matrix only when all rows of Q and K are included as landmarks. In contrast, our Nyström scheme operates
5

---

Published as a conference paper at ICLR 2026
the exponential kernel matrix formed from Q and K, and achieves spectral approximation guarantees as long as the sample size is sufficiently large without needing to include all data points.
3.2 APPROXIMATE THE NORMALIZATION FACTOR VIA QUANTUM MEAN ESTIMATION
Recall that D diag( AL,)), and each normalization factor only requires computing af I, where 0g the i-th row of A. If we have access to E, then the i-th normalization factor could be estimated as 0n la
However, discussed earlier, we cannot explicitly form F due to its size. To resolve this, we define U= ES E2 2 By the definition of the Nyström approximation, we have where U1, U2 E R=xx, and the U2
U1
E = UUT Moreover, U' also exhibits a block structure U
desired approximate A= U.U.J can be obtained via these blocks. Given any vector v E R", if we can compute approximate U22 v, then the normalization factor for the i-th row can be estimated as (U1),, (U2 u) where (U1),,. E IR is the i-th row of U1. Fortunately, we can implement row queries to U2. We first precompute (S" ES) in O(s²d + st) time, then each row (U2) of U2 is computed via kernel evaluations between Ti+n and the points in S, followed by matrix-vector multiplication with (5T ES) This takes O(s" + =dd time.
It remains to approximate U.1 v, which we cast as multivariate mean estimation problem. Define the random variable X = 2n 2 where E [n] is selected uniformly at random. It is easy to verify that [[X] = U.2 v, and the variance is bounded. Therefore, one can apply the quantum multivariate mean estimation procedure of Cornelissen et al. (2022) to approximate U2 To further reduce variance, Apers & Gribling (2023) proposes approximating the matrix-vector product in the (U, U2) (12)-"-nerrg) -enery norm. Following this idea, we apply Lemma 2.6 to output vector f R such that || U._ ulluu, U2) S c, using (n,51, g.5. [ row queries to U2 and v. In our application, we always have ||v||cc = 1, and as noted above, each row query to U takes O(s + sd) time. We present the full algorithm below in Algorithm 2.
For the approximation guarantee, we prove that for any vector I E R" if [| US) S e, then || S e || 2 ||. This is particularly useful for us, as we can set r U._ v --. in which case U1x = U U1 = Av - U1 and the upper bound becomes c || c ([]A|] + A). On the other hand, we can upper bound [I(A A)ull using the matrix infinity norm, defined as || A Allso max ||A., A,, A simple argument shows that I| Alloc S /n /| All >/nn A triangle inequality then yields the final approximation guarantee. If we define D = diag (A1,), diag(A1,)) the above analysis provides bound on | DII However, in forming the attention module, it is more desirable to control |||-,|| To achieve this, we prove a perturbation bound matrix inversion that relates || to D --1|
3.3 APPROXIMATE THE VALUE MATRIX VIA LEVERAGE SCORE SAMPLING
In preceding discussions, we have shown how construct the sampling matrix for Nyström ap- proximation and how to compute the normalization factor for any row i E [ni] It remains to approximate V in sublinear time. Prior classical algorithms, such as Zandieh et al. (2023), propose using importance sampling based on the joint row norm of V and D- A. Specifically, the sampling probability for the i-th row is set as P; 2 1/4. (lle,D> D-1 A 2 + + 1))pl)((((()
'A + IVV where = 11 / This method achieves a final sample size that is nearly linear in + srank( -D-1 A), where srank D A) | A All2 is the stable rank of the softmax matrix. While this approach is conceptually simple and easy implement, it requires estimating the Frobenius norms of both V and D A to constant-facto accuracy. This is straightforward if we are allowed to read all entries of V. but becomes particularly challenging in sublinear time. Our solution is to instead use leverage score sampling on the matrix V, which can be implemented in sublinear time (Apers& & Gribling, 2023).
Unlike the joint sampling distribution of Zandich et al. (2023), which yields a spectral norm approx- imate matrix multiplication guarantee of the form DD-ASSTT VII S - All ||V]], leverage

---

Published as a conference paper at ICLR 2026
Algorithm 2 Algorithm for estimating normalization factor.
1: data structure QROWNORM
2:
begin members
3: E N
4:
(IR2) 5: .N R
6: já E IR*
7:
end members
8:
9: procedure PREPROCESS(Q E Baxd d K E Ruxd X o0), (0,
10:
f- Ossx log(sın))
S QNYSTRÖMKERNELL(QU K, (I); +
Algorithm 1, is a list of sampled indices and weights
12:
N + (STES)
Implement row oracle (U2)j.- follows:
14:
(U2)s(H), < S5 (xpp((2)+m))) (I)+n;; Ak: E
& (U)) E R
15:
(U2),,- + N(U2),(k),
b S stores pairs indices and weights, Sp is the weight
corresponding to index k, (U2),,- E R
16:
Implement entry oracle for vector
1, R"
17:
I + QMATVEC (U, v,c)
D J E R Lemma 2.6
18: end procedure
19:
procedure QUERY(İ E [n])
21: b, + ((U1)s,..P))
> (U1),, is computed via row oracle
22: return
23: end procedure
end data structure
score sampling has two key limitations: (1) it requires that V have orthonormal columns (Clarkson Woodruff, 2017), and (2) it provides approximate matrix multiplication guarantees in Frobenius norm, i.e., 1DD1-AS V|[F ---ID--AA
[[V[[
To address the first limitation, we introduce a new parameter called the row distortion of V. defined d/I[V max;e[n] |///////T Intuitively, measures the mismatch between the row density and row importance. Specifically, the ratio ||,: quantifies how much row U; contributes in 22 norm, while T: / measures how linearly independent is compared to other rows via 7,
Our main result is that by sampling aa) rows of V according to its leverage score distribution, we obtain an approximate matrix multiplication guarantee in Frobenius norm. Note that a = if V has orthonormal columns, which recovers the result of Clarkson & Woodruff (2017). This sampling procedure can be implemented in Ö(E a time by making row queries V.
3.4 MAIN RESULT
Now that we have described how to approximate each of the matrices D, A, and V, we are in position to state our main result. We provide an overview our algorithm below Algorithm 3.
Theorem 3.1 (Informal version of Theorem D.2). Let Q,K.V E Baad be the query, key and value matrices. let e, O. Let E E R 2222n be the exponential kernel matrix on the dataset Q J K and 8x be the statistical dimension of E (Definition 2.2) and a be the row distortion of V (Definition C.2). Assume that ||D < quantum data structure that preprocesses Q, K, through only row queries to these matrices and maintains matrices D. A, V implicitly such that, with probability at least 1/ poly(n).
A and let B (e(
'TI There exists
- Att(Q, V)Il= < (8-11D-11) ([A]]F + +Avn) [[[]e
Moreover, the data structure has the specification
7

---

Published as a conference paper at ICLR 2026
Algorithm 3 Quantum data structure for attention row query.
1: data structure QATTENTION
Theorem 3.1
2:
begin members
3: SE, 8V EN
4: V. E Rd
5: N E R
6: L Re
7:
QROWNORM QRN
B Algorithm
8: end members
9:
procedure PREPROCESS(Q E Baxd Raxd Fexd,V VVV. Ruxd
/a >> 0,000,0000 0,a
11:
+ (FF
SV < O(c Ö(5x)
12:
13: PRN.PREPROCESSS e,),
D. Algorithm Sv Ruxev Lemma A.5
14:
Sy QLEVERAGHSSCOREVV.W
15:
V + -TV
V gd xd
16:
SE QNYSTRÖMKKERNE (1)) exp((x;, x3)), 1/ poly(n),
17:
Let 21.... D2n denote the dataset QUK
18:
M + (SE(1)SE(i) exp( 2,))
4> M E 12 X8B R ETE Ñ ROXXAv Rsxxd xd
R (Se(i)Sv()) exp( (o))Esss
R ReEKSY
20:
Ñ M
21:
+ NV
22:
end procedure
23:
24:
procedure QUERY(İ [n]
25:
b2 + QRN.QUERY
4 Algorithm Uj E IR
26: U1 + (SE(i) exp (2t, 23) hESS
27: return T. u//b/
28: end procedure
29: end data structure
It preprocesses K,K, in 0,,5,, row queries to Q, K and Ö(E ((5551))))03)))) row queries V, and Ö(E 0 0.5 (5 + 5 a a.5 time;
For any i E [n], it returns vector P. = 1- in Ö(5} + sxd) time.
We pause make remarks Theorem 3.1. The preprocessing time scales with 0-5 achieving a quadratic speedup with respect to n over any classical algorithm. Several parameters merit further discussion, in particular the statistical dimension 8 and the approximation factor for || |DD denoted by 3. We summarize their relationships as functions of X in Table 1. The row distortion factor also
VI affects the runtime, and Appendix C, we prove that a S srank(V) where srank(V) TV]j the stable rank V. This ensures a < d and becomes smaller the value matrix V has close stable rank. We empirically verify that (1) the assumption on |-|||| is easy satisfy with wide range of choices for (2) the Frobenius norm of A is only a small constant factor of its spectral norm, (3) the row distortion a O(1) and (4) the infinity norm of A is only small constant factor its spectral norm, implying in practice, the additive A/n term is likely to be O(A). We refer to Appendix E for more detailed section.
X
8A
A
+Ayn
8
Table 1: Parameters 8x, <| + and B as functions of X.
8

---

Published as a conference paper at ICLR 2026
Bit Complexity of Our Algorithm. Our discussions and results above are grounded in the assump- tion that arithmetic operations are performed in infinite precision, while this is usually adopted in the analysis of classical algorithms, QRAM model only allows O(log n) qubits and poly(n) bits. In Section F, we provide a preliminary bit complexity analysis of our algorithm, in particular centering around the matrix inversion and pseudoinversion operations. To the best of our knowledge, there is no prior work on studying the bit complexity of numerical linear algebra operations in the QRAM model, and we leave a comprehensive analysis of bit complexity as future direction.
4 RELATED WORK
Transformers and Attention Mechanism. Transformers (Vaswani et al., 2017) have been the driving force behind large language models (Devlin et al., 2019; Brown et al., 2020; Touvron et al., 2023; Bubeck et al., 2023; Team et al., 2023; Liu et al., 2024a). They are requence-to-sequene generative models, where the sequence length is typically denoted by The key architectural component that distinguishes transformers from earlier models is the attention mechanism, which computes softmax over the pairwise interactions of query-key vectors. However, computing the full softmax distribution requires (2n2)) time, due to the size of the attention matrix. This quadratic dependency renders transformers inefficient for long sequences, motivating rich body of work aimed at approximating attention in subquadratic time. These approaches can be broadly categorized into three main classes: (1) Pattern-based sparse atlention: only subset of attention matrix entries are computed, with the subset determined by predefined patterns, such as sliding windows or graph-baser sparsity structures (Daras et al., 2020; Kitaev et al., 2020; Roy al., 2021: Sun et al., 2022: Child et al., 2019; Beltagy et al., 2020; Ainslie et al., 2020; Zaheer et al., 2020). (2) Kernel-based linear attention: these methods attempt to linearize the kernel by exploiting the identity K(z,, (ő(x:), o(x,)) for a feature map á : IRd + Em When the kernel is exponential. exact computation requires m oo, sO many heuristic approximations for é have been proposed (Katharopoulos et al., 2020;
Choromanski et al., 2021; Wang et al., 2020; Peng et al., 2021) with m = (d). (3) Data structure- based attention: these works design specialized data structures for approximating various components of attention. Examples include estimating the normalization factor via kernel density estimation (KDE) (Zandich et al., 2023), using hashing to identify large entries (Han et al., 2024), applying polynomial approximation methods under bounded input conditions (Alman & Song, 2023), and other algorithmic innovations (Kacham al., 2024; Zandieh al., 2024; van den Brand et al., 2024; Song et al., 2024; Kannan et al., 2025; Chu et al., 2024; Chen et al., 2025b; Indyk et al., 2025). Our work falls into the third category, as we design quantum data structures to approximate each of the matrices involved in the attention computation.
Quantum Machine Learning. Given a machine learning problem, can we solve it faster on a quantum computer? The paradigm of using quantum mechanies to accelerate machine learning algorithms has sparked significant interest, leading to wide array of results across diverse problem domains, including clustering (Kerenidis et al., 2019; Xue et al., 2023), classification (Li et al., 2019), regression (Chen & de Wolf, 2023), training neural networks (Chakrabarti et al., 2019; Kerenidis et al., 2020), convex optimization (Chakrabarti et al., 2020; van Apeldoom et al., 2020a; Li & Zhang, 2022; Sidford & Zhang, 2023; Zhang et al., 2024b; Wang et al., 2024), mathematical program- ming (Brandão et al., 2019; van Apeldoor et al., 2020b; van Apeldoor & Gilyén, 2019; Kerenidis & Prakash, 2020; Kerenidis et al., 2021: van Apeldoorn et al., 2021; Apers & Gribling. 2023), graph sparsification (Apers & De Wolf, 2022), and recommender systems (Kerenidis & Prakash, 2017). Among the key quantum techniques, Grover search (Grover, 1996) plays foundational role. It provides a quadratic speedup for database search problems: given a function f: [M] + {0, 1}. the goal is list up to m indices i such that (ii 1. The Grover search algorithm requires oracle access to f and can produce these m indices using only O(y queries, in contrast to the ((n) queries required classically. Several variants of Grover search have been developed to suit different computational settings. In this paper, we use the probabilistic version: given a list of probabilities pı.....2 Pr E [0, 1), Grover search can be used to sample list of indices where each is selected independently with probability p;- By the standard analysis of Grover search, this sampling requires Ö( ((VnP) queries to the probability values P; where P Σi= P:. Before our work, Gao et al. (2023) also applied Grover search to accelerate attention computation. However, their method requires a structural assumption: for each query qi E Rd. the associated set S, [j E [m]
(gi, kj) 2 7) must

---

Published as a conference paper at ICLR 2026
have cardinality at most k. Under this assumption, their algorithm runs in time Ö(n'-5x0 20.5 nkd). Notably, if & = n, then their algorithm offers no speedup over the exact computation.
CONCLUSION
We consider the problem of approximating the attention module in the query model, where the goal is to return individual rows of the approximate attention matrix. We design a quantum data structure that preprocesses Q, K, and V in query in Os3 sxd) time. To the best of our knowledge, this is the first quantum algorithm to achieve sublinear dependence on n even in the row query model.
psly d, a)) time, and answers any row
Our work also has several limitations, which raises interesting open questions. (1) The emror guarantec we obtain is in Frobenius norm rather than spectral norm. While Frobenius norm bounds the sum of the squared l errors across all rows, the spectral norm provides worst-case guarantee that each row well approximated. Therefore, it would be desirable to strengthen the result to achieve a spectral norm guarantee. (2) The error bound obtain contains additive Xyn term, which stems from bounding the infinity norm of the error matrix by /ni times the spectral norm of it. This bound seems overly pessimistic, and it theoretically forces one to choose small value for X, hindering the advantage of small statistical dimension. It would be interesting to remove the vn factor in the additive term. (3) While we provide preliminary bit complexity analysis of our algorithm in Section F, we feel more comprehensive study of bit complexity of numerical linear algebra in the QRAM model is needed. We leave this as major future direction, as will significantly broaden the practicality of these quantum speedups. (4) Our algorithm in its current form can only compute the full attention without the causal mask, as using the Nyström approximation implicitly assumes the complete interactions between queries and keys. To implement causal masking, possibility is to design quantum kernel density estimation data structure as shown in Zandich et al. (2023) classically.
ETHICS STATEMENT
Our work is theoretical quantum framework to approximate the attention module in sublinear time. We don't 't' foresee any potential ethics concerns.
REPRODUCIBILITY STATEMENT
We include all the proofs in the appendix. For proofs of the exponential kernel, Section A, for proofs of estimating the normalization factor, see Section B. For proofs of the leverage score approximate matrix multiplication, see Section C. The final conclusion is proved in Section D. We provide empirical verifications on the assumptions of the parameters in Section E, and a preliminary bit complexity analysis of our algorithm in Section F.
ACKNOWLEDGMENT
We would like to thank anonymous for very helpful discussions, and Ruizhe Zhang for answering our questions on the QRAM model. Lichen Zhang supported by a Mathworks Fellowship and Simons Dissertation Fellowship in Mathematics.
REFERENCES
Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant Nair, llya Soloveychik, and Pu- rushotham Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference. In Proceedings of the 7th Conference on Machine Learning and Systems (MLSys), 2024.
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. ETC: Encoding long and structured inputs transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 268 284. Association for Computational Linguisties, 2020.
10

---

Published as a conference paper at ICLR 2026
Ahmed EI Alaoui and Michael W. Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Advances in Neural Information Processing Systems 28 (NeurIPS 2015), pP- 775-783, 2015.
Josh Alman and Zhao Song. Fast attention requires bounded entries. Advances in Neural Information Processing Systems, 36:63117-66115, 2023.
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2005-2039, 2025.
Simon Apers and Ronald De Wolf. Quantum speedup for graph sparsification, cut approximation, and laplacian solving. SIAM Journal Computing. 51(6):1703-1745 2022.
Simon Apers and Sander Gribling. Quantum speedups for linear programming via interior point methods. arXiv preprint arXiv:2311.0321,, 2023.
Payman Behnam, Yaosheng Fu, Ritchie Zhao, Po-An Tsai, Zhiding Yu, and Alexey Tumanov. Rocketkv: Accelerating long-context Ilm inference via two-stage kv cache compression. arXiv preprint arXiv:2502.1405/ 2025.
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer, 2020.
Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen- Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning. In 46th International Colloquium on Automala, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings Informatics (LIPIcs)) pp. 27:1-27:14. Schloss Leainl-Leebniii-Zeeen
für Informatik, 2019.
William Brandon, Mayank Mishra, Aniruddha Nrusimha, Rameswar Panda, and Jonathan Ragan- Kelley. Reducing transformer key-value cache size with cross-layer attention. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel VerrerrtVosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Eee Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with gpt-4, 2023. URL https: /awpivi.vvv////////i//...////av. org/ abs 22333...... 12712.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 213-229. Springer, 2020.
Shouvanik Chakrabarti, Yiming Huang, Tongyang Li, Soheil Feizi, and Xiaodi Wu. Quantum wasserstein generative adversarial networks. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019), pp. 6768-6779, 2019.
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020.
Bo Chen, Xiaoyu Li, Yekun Ke, Yingyu Liang, Zhenmei Shi, and Zhao Song. Exploring the limits of kv cache compression in visual autoregressive transformers. arXiv preprint 2rXiv:2503.1453 2025a.
11

---

Published as a conference paper at ICLR 2026
Bo Chen, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. HSR-enhanced sparse attention acceleration. In The Second Conference on Parsimony and Learning (Proceedings Track), 2025b.
URL
net. Lttp:////wwe..tttttooooooooooeee wtw.n/ddddooooopaaaaaa
Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPlcs), pp- 38:1-38:21. Schloss Dagstuhl- Leibnizz-Zentrum für Informatik, 2023.
Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yu Tian. Time and memory trade-off of kv-cache compression in tensor transformer decoding. arXiv preprint arXiv:2503.11008 2025c.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint 1904 2019.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio. Attention-based models for speech recognition. Advances in neural information processing systems, 28, 2015.
Timothy Chu, Josh Alman, Gary L Miller, Shyam Narayanan, Mark Sellke, and Zhao Song. Met- ric transforms and low rank representations of kemels for fast attention. Advances in Neural Information Processing Systems, 37:47014 47066, 2024.
Kenneth L Clarkson and David P Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6):1-43 2017.
Arjan Cornelissen, Yassine Hamoudi. and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 33 43, New York, NY, USA, 2022. Association for Computing Machinery.
Giannis Daras, Nikita Kitaev, Augustus Odena, and Alexandros G. Dimakis. Smyrf: Efficient attention using asymmetric clustering. In Advances Neural Information Processing Systems, volume 33, pp. 6470-6481, 2020.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguisties: Human Language Technologies (NAACL-HLT), pp. 4171-4188 Association for Computational Linguistics, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In FOCS, 2023.
Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S. Kevin Zhou Identify critical kv cache in Ilm inference from an output perturbation perspective. arXiv preprint arXiv:2502.03880. 2025.
Yeqi Gao, Zhao Song, Xin Yang, and Ruizhe Zhang. Fast quantum algorithm for attention computa- tion, 2023.
Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eights Annual ACM Symposium on Theory of Computing, STOC '96, pp. 212-219, New York. NY. USA, 1996. Association for Computing Machinery. ISBN 0897917855. doi: 10.1 00.11455237814223786 URL https: //doii////////// org. http://..1111///11 1ee.e1145228118 237866.
12

---

Published as a conference paper at ICLR 2026
Yuzhou Gu, Zhao Song. Junze Yin, and Lichen Zhang. Low rank matrix completion via robust alternating minimization nearly linear time. In The Tweifth International Conference on Learning Representations (ICLR), 2024.
Meng-Hao Guo, Tian-Xing Xu, Jiang-Jiang Liu, Zheng- Ning Liu, Peng-Tate Tao Jiang, Tai-Jiang Mu, Song-Hai Zhang, Ralph R Martin, Ming-Ming Cheng, and Shi-Min Hu. Attention mechanisms in computer vision: survey. Computational Visual Media, 8(3):331-368, 2022.
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In International Conference on Learning Representations (ICIR), 2024.
David Harvey and Joris van der Hoeven. Integer multiplication in time O(n log n). Annals of Mathematics, March 2021. doi: 1044077aamal, URL https::/hall....
ha1-02070778.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York, 2nd edition, 2009.
Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2 edition, 2002. ISBN 0-89871-521-0. doi: 10.1137/1. 9780898718027..
Piotr Indyk. Michael Kapralov, Kshiteej Sheth, and Tal Wagner. Improved algorithms for kernel matrix-vector multiplication under sparsity assumptions. In Proceedings of the International Conference on Learning Representations (ICLR), May 2025.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. TinyBERT: Distilling BERT for natural language understanding. Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 4163 4174. Association for Computational Linguistics, 2020.
Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketching polynomial kernels. Proceedings of the 41st International Conference on Machine Learning, 2024.
Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, and David P. Woodruff. Levatten- tion: Time, space, and streaming efficient algorithm for heavy attentions. In Proceedings of the International Conference on Learning Representations (ICLR), 2025.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers Fast autoregressive transformers with linear attention. In Proceedings of the 37th International Conference on Machine Learning, pp. 5156-5165. PMLR, 2020.
Lordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPles), pp. 49:1-49:21. Schloss Dagstuhl-Leibniz-zennrru für Informatik, 2017.
lordanis Kerenidis and Anupam Prakash. A quantum interior point method for lps and sdps. ACM
Transactions Quantum Computing, 1(1):1-32, 2020.
lordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. In Advances in Neural Information Processing Systems, volume 32, pp. 4134-4144, 2019.
Iordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep con- volutional neural networks. In Proceedings of the 8th International Conference on Learning Reprexentations (ICIRR, 2020.
Lordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi. Quantum algorithms for Second-Order Cone Programming and Support Vector Machines. Quantum, 5:427, 2021.
13

---

Published as a conference paper at ICLR 2026
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
Lilly Kumari, Shengjie Wang, Tianyi Zhou, Nikhil Sarda, Anthony Rowe, and Jeff Bilmes, Bumble- bee: Dynamic kv-cache streaming submodular summarization for infinite-context transformers, In Proceedings of the Conference on Learning for Molecules (COLM), 2024.
Tongyang and Ruizhe Zhang. Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits. In Advances in Neural Information Processing Systems, volume 35, pp. 19565-19577, 2022.
Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 3815-3824. PMLR, June 2019.
Aixin Liu, Bei Feng. Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437, 2024a.
Minghui Liu, Tahseen Rabbani, Tony O' O'Halloran, Ananth Sankaralingam, Mary-Anne Hartley, Brian Gravelle, Furong Huang, Cornelia Fermüller, and Yiannis Aloimonos. Hashevict: A pre-attention kv cache eviction strategy using locality-sensitive hashing. arXiv preprint arXiv: 16187, 2024b.
Xiaoyun Liu, Daniel Esser, Brandon Wagstaff, Anna Zavodni, Naomi Matsuura, Jonathan Kelly, and Eric Diller. Capsule robot pose and mechanism state detection in ultrasound using attention-based hierarchical deep learning. Scientific Reports, 12(1):21138) 130, 2022.
Cameron Musco and Christopher Musco. Recursive sampling for the nyström method. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 9836-3848, Red Hook, NY, USA, 2017. Curran Associates Inc.
Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the lanezos method for matrix function approximation. In Proceedings of the Twenty-Ninth Annual ACM-SIAN Symposium on Discrete Algorithms, SODA '18, pp. 1605-1624, USA, 2018. Society for Industrial and Applied Mathematics.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong, Random feature attention. Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. In Proceedings of the 6th Conference on Machine Learning and Systems (MLSys), 2023.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68. 68, 2021.
Rikhav Shah. Hermitian diagonalization in linear precision. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pp. 5599-5615,, 2025.
Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023). pp. 1-12, 2023.
14

---

Published as a conference paper at ICLR 2026
Aleksandros Sobezyk. Deterministic complexity analysis of hermitian eigenproblems. In Keren Censor-Hilled Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis (eds.). 52nd International Colloquiun Automata, Languages. and Programming. ICALP 2025, Aarhus. Denmark, July 8-11, 2025, volume 334 of LJPlcs, pp. 131:1-131:21. Informatik, 2025.
Schloss Dagstuhl Leibniz-7entrru für
Zhao Song. Junze Yin, and Lichen Zhang. Solving attention kernel regression problem via pre- conditioner. In International Conference Artificial Intelligence and Statistics, pp. 208-216 PMLR, 2024.
Zhiqing Sun, Yiming Yang, and Shinjae Yoo. Sparse attention with learning to hash. In International Conference on Learning Representations, 2022.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean- Sann-Bapisste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.1 /805, 2023.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.1397. 2023.
Joran van Apeldoom and András Gilyén. Improvements in quantum sdp-solving with applications. In 46th International Colloquium Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 99:1-99:15. Schloss
Pagstubl-Leibniz-Zeentre für Informatik, 2019.
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020a.
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald Wolf. Quantum sdp-solvers: Better upper and lower bounds. Quantum, 4:230, 2020b.
Joran van Apeldoom, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPlcs), pp. 110:1-110:17. Schloss Dagstuhl- Leibniz- Zentrum für Informatik, 2021.
Jan van den Brand, Zhao Song, and Tianyi Zhou Algorithm and hardness for dynamic attention maintenance in large language models. In International Conference on Machine Learning, pp. 19908-49022 PMLR, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Evan Pete Walsh, Luca Soldaini, Dirk Groeneveld, Kyle Lo, Shane Arora, Akshita Bhagia, Yuling Gu, Shengyi Huang, Matt Jordan, Nathan Lambert, Dustin Schwenk, Oyvind Tafjord, Taira Anderson, David Atkinson, Faeze Brahman, Christopher Clark, Pradeep Dasigi, Nouha Dziri, Allyson Ettinger, Michal Guerquin, David Heineman, Hamish Ivison, Pang Wei Koh, Jiacheng Liu, Saumya Malik, William Merrill, Lester James Validad Miranda, Jacob Morrison, Tyler Murray, Crystal Nam, Jake Poznanski. Valentina Pyatkin, Aman Rangapur, Michael Schmitz, Sam Skjonsberg, David Wadden, Christopher Wilhelm, Michael Wilson, Luke Zettlemoyer, Ali Farhadi, Noah A. Smith, and Hannanch Hajishirzi. 2 OLMo 2 furious (COLM's version). In Second Conference on Language Modeling, 2025.
Hao Wang, Chenyi Zhang, and Tongyang Li. Near-optimal quantum algorithm for minimizing the maximal loss. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
Sinong Wang. Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self- with linear complexity, 2020.
15

---

Published as a conference paper at ICLR 2026
Yuanchao Wang, Wenji Du, Chenghao Cai, and Yanyan Xu. Explaining the attention mechanism of end-to-end speech recognition using decision trees. arXiv preprint arXiv:2110.03879, 2021.
Christopher K. I. Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In Proceedings of the 14th International Conference on Neural Information Processing Systems, NIPS'00 (0,S'00,TT pp. 661-667, Cambridge, MA, USA, 2000. MIT Press.
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha omega. Proceedings of the 2024 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 3792-3835. SIAM, 2024.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung. Yin Li, and Vikas Singh. Nyströmformer: A nyström-based algorithm for approximating self-attention. In AAAL pp. 14138-1414 14148. AAAI Press, 2021.
Yecheng Xue, Xiaoyu Chen, Tongyang Li, and Shaofeng H.-C. Jiang. Near-optimal quantum coreset construction algorithms for clustering. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 38881-38911 PMLR, 2023.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. In Advances in Neural Information Processing Systems, volume 32, pp. 3754-5764, Curran Associates, Inc., 2019.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang. and Amr Ahmed. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, volume 33, pp. 17283-172977 2020.
Amir 7andieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 40605-40623, PMLR, 2023.
Amir Zandieh, Insu Han, Vahab Mirrokni, and Amin Karbasi. Subgen: Token generation in sublinear time and memory, arXiv preprint arXwv:2402.06082, 2024.
Rongzhi Zhang, Kuang Wang, Liyuan Liu, Shuohang Wang, Hao Cheng, Chao Zhang, and Yelong Shen. Lore: Low-rank compression for llms kv cache with progressive compression strategy. In NeurlPS 2024 Workshop on Model Compression, 2024a.
Tong Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 1709):2077-2098, 2005.
Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 12345-12356. PMLR, 2024b.
Haoyi Zhou, Shanghang Zhang, Jieqi Peng. Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11106-11115 AAAI Press, 2021.
16

---

Published as a conference paper at ICLR 2026
Appendix
Roadmap. In Section A, we describe the quantum algorithm for exponential kernels. In Section B, we discuss how to estimate the normalization factor. In Section C, we show the details on approx- imating matrix multiplication via leverage scores. In Section D, we combine things together and obtain the main result. In Section E, we empirically verify the assumptions on the parameters. In Section F, we discuss the bit complexity our algorithm.
A QUANTUM ALGORITHM FOR EXPONENTIAL KERNEL
this section, we give generic reduction from attention matrix to a kernel matrix. Given queries and keys = {g...... On J. K (ki...., Kn recall that where the (i. ()th entry is exp(q, k2), and this matrix is not a PSD kernel matrix. We show a reduction that first computes the exponential kernel K(x, y) cxp((x; (xx y)) over the dataset Q U K, then we can effectively extract certain blocks of the kernel matrix E that approximates exp(QK) well. We start with lemma on block approximation.
interested in the matrix exp(QKK
B
A
Lemma A.I. Let E 222x2n be PSD matrix and F
where each block is of size
AT
C
n x n.. Suppose there exists matrix E E 2nx22n such that E R
E
3
E AI for > 0 and let
B
A
E
then we have
A
| - Al S and A|- S AVn.
Proof. We let U E R" be the vector that realizes the spectral norm A A, consider the augmented
0,,
vector
then we see that
0n 0
(A - Ā)u
(E
E)
(C C)e
= |[ - Ayull + |I( - E)ull
S x2
where the last step is by || - -El < X and our test vector is unit norm. As [I - C'ull3 trivially non-negative, we conclude that [[AA A)ull2 = ||A Āll < x, as desired. To obtain Frobenius norm bound, note that ||A All I Vn ||A - All < AVT..
Our plan is to form the kernel matrix over the dataset Q QU K implicitly via Nyström approximation, then extract corresponding blocks to approximate exp(QKT)
Corollary A.2. Let Q, K Ruxd and let F, E 222xx2n be the exponential kernel matrix the dataset Q U K, suppose there exists an E 222nx2n such that I E E AI for some X > then there exists A R such that
Ä exp(QKT) and exp(exxp(KK]) )) S AVT.
Proof. The result is consequence of Lemma A.1 by identifying that
E (exp(QQ) eeppl K (QT)
exp(QKT) exp(KK)
and E contains proper approximations for the desired blocks.
remains to give an efficient algorithm to approximate the exponential kernel matrix E. A popular scheme is via Nyström approximation (Williams & Seeger, 2000): the algorithm selects subset of
17

---

Published as a conference paper at ICLR 2026
"landmark" points, and constructs E through these landmarks, Musco & Musco (2017) recursive ridge leverage score sampling to generate such an approximation efficiently. Musco Musco (2017) presents an algorithm that uses (ss (o)( kernel function evaluations and Ö(ns log(1/ ( additional runtime to compute approximation K satisfying K K N K XI with probability at least 5. We restate their main result here for the sake of completeness.
Lemma A.3 (Theorem of Musco Musco (2017)). Let $ = (ogxo0(()1/0)) there ex- ists a weighted sampling matrix S E Raxs, such that the Nyström approximation of E, E ES(S S satisfies
E E
holds with probability at least 1 8. Moreover, S can be computed using ((ns) kernel evaluations and (nns²) additional time.
Our main contribution quantum algorithm that generates the approximation in sublinear time. Before introducing the algorithm, recall several key concepts.
Lemma A.3 relies on approximating the ridge leverage score on sample, which can be captured by the notion of generalized ridge leverage score.
Definition A.4 (Generalized ridge leverage score, Musco & Musco (2017)). Let E E Raxx be kernel matrix, let > O. and let [Rax* be any weighted sampling matrix, the X-generalized ridge leverage score with respect to S, is defined for any i [n].
(E - ES(S ES + S E)...
let B E RRxx be any factorization of E =BB it can be equivalently defined as
by (B SB - b..
where b, is the i-th row of B.
We also need procedure introduced in Apers & Gribling (2023) that generates a spectral approxima- matrix, given only queries its rows, using quantum leverage score sampling. We record it here.
tion of an
Lemma A.5 (Theorem 3.1 of Apers & Gribling (2023)). Let U E Rxdd e, E (0, 1). There exists quantum algorithm that computes weighted sampling matrix S Raxs with O(E such that with probability at least 1 - 8,
(1- SUSTST U 31
The quantum algorithm uses 065 row queries U, and takes time 1.b. ) Moreover, if the leverage score sampling matrix contains $ I rows, then the algorithm uses On55 g0.5) row queries to U and it takes time 0 3 0.5 denote this procedure that produces leverage score sampling matrix E Roxs
We use QLEVERAGESCORE(U;
We prove the key algorithmic result of this section.
Theorem A.6. Let {Z1,..., In) C Rd be dataset, K Rd Rd R. be kernelffunctinn À 0 and 8 E (0, 1). Let E. be the kernel matrix where Fi,j = K K(ri, x.). Suppose 8 = O(8x log(sx/6), then Algorithm I computes weighted sampling matrix S B such that with probability at least 1
E E-
where È - ES(S ST E. Moreover, S can be computed in 0.5 row queries to Q, K and in time 0.5 (Tk + s) 3²), where Tk is the time to evaluate the kernel function.
Proof. We note that the major differences between Algorithm and the algorithm in Musco & Musco (2017)
18

---

Published as a conference paper at ICLR 2026
Musco & Musco (2017) algorithm is recursive, algorithm unrolls the recursion and iteratively constructs the weighted sampling matrix;
Musco & Musco (2017) computes all p;'s classically, while we use QSAMPLE to generate samples.
Hence, the correctness is automatically satisfied. It remains to give a bound on the running time.
Computing Mo: Mo E I contains the values of kernel functions over s² pairs, forming it takes (s²)) Tk time;
Computing M: we maintain the invariant that M, Raxs for all & [2], therefore
computing M is inverting an s x 8 matrix, which takes (())) time;
Computing KG this operation involves computing s weighted kernel function evalua- tions, given D stores list of indices together with weights, can be done in O(s) TK time;
Oracle for qı: for any fixed i, note that we need to form D K; using 0(s) Tk time, and computing the quadratic form takes (s²) time. Thus each oracle call takes Oss)-T(( +0(3) time;
Computing D.: this step requires to compute at most n probabilities, and each probability can be computed via oracle call in ((s) TT + Os²²) time, remains to give a bound on the sum of probabilities. By the definition of p..
pi 16 (2660g((s/))
2 4i
and the sum of qa 's is
Σ 9:
(K(I,, 24) - M.D,
5
(E - ED. ED, + -
= 5. Σ 7M
by Theorem of Musco & Musco (2017), the sum of X X-generalized ridge leverage score with sampling matrix D,-1 is at most (s8 log(s>/6) = 8, thus the runtime is ".5 (Tk s)).
Finally, note that the loop dominated by the last iteration, and at each iteration, the number of points consider is divided by half, we conclude the overall runtime of Algorithm 1
055 1.5 (Tk + 8) + s"),
as desired.
We can then apply Theorem A.6 to exponential kernel function and the dataset Q U K to compute Nyström sampling matrix S.
Corollary A.7. Let Q, K E R X > O and ā E (0,1). Define the datasel X = Rdd where for E [n), 24 q and for i {n + I...., 2n), I; ki- Let E be the kernel matrix where Eig = xx, Suppose s = log(sx))))))) then there exists an algorithm that computes a weighted sampling matrix S E RRaxx such that, let E = ESSIST ES)* ST E, then with probability at least 1 - 8, E x E x E + XI. Moreover, S can be computed in 0(n 5. (d+ s) + 5 time.
Proof. Apply Theorem A.6 to the kernel function K(z,; = exp (a,, x,,) and note that the kernel function can be computed in (dd) time.
19

---

Published as a conference paper at ICLR 2026
B ESTIMATING THE NORMALIZATION FACTOR
Given a sublinear quantum algorithm to approximate the matrix exp(QK' 1), our next step is to estimate the normalization factor exp(QK' )1,, compute the softmax matrix. We first show that given a Nyström approximation to the 2n x 2n kernel matrix E, how to compute the normalization factor and the approximate guarantees.
Lemma B.1. Let M gnxa be symmetric matrix, then we have
|| S vn. ||M]].
Proof. Fix any E [n]. examine the row Mi set the test vector to be 2j
+1, if Mr 2 then 11, otherwise.
| M,,.o
(Me,,))
S Me |||||
S M| || ||ا||
vn |M
The conclusion can be achieved by noting that this bound works for any row
There major issues for estimating the normalization factor:
Corollary A.7 only allows us to compute the sampling matrix in sublinear time, explicitly forming the Nyström approximation F. however, would require Qm)) time since the matrix is of size n X n
Even though we are given the explicit factorization É UUT where U E 2 would have to compute n normalization factors, which would require 2(n) time.
In other words, because the output has size (nn). one cannot expect any quantum algorithm to run in o(n) time. Instead, we design quantum data structure with preprocessing time o(n) time, and can support query to compute the normalization factor to any row efficiently.
In particular, are interested in the following algorithmic task: given query access to the rows of matrix U TR= and vector e E TR. output vector j E IR such that 1/ UT ell(u S c, 1. However, we are interested in which can be solved via Lemma 2.6. For our application, ||e|| U v) How would bound on the the quantity UUT v so we need to measure the error |[ ( be useful? We prove structural lemma below.
Lemma B.2. Let E R and U2 E Tgax satisfying ( U.) S e for some E (0, ler U1 E Raxx, we have
|Uar|| S CU I|.
Proof. We define the vector y = (U, -1) and : = U2y then
|| U.T U2y
(U,2 -1
|1 ( U2)-1
moreover, the vector of interest is U1 which is
U = U (U, U2)y
(U.U, U2y
20

---

Published as a conference paper at ICLR 2026
subsequently its lg norm can be bounded (U112) )
||U|ø||2 - |1 || -112122
sc. 11
as desired.
Corollary B.3. Let E (0.1), U2 E _x where == U1U, v E R", suppose there exists vector pi E R with || U2 v (2) I c. then we have
|| Ar - 1 S 6 1
Proof. We will apply Lemma B.2 by setting x = - v and by noting that U1z U U1ū - Av.
We are now in the position to state our formal theorem, which provides end-to-end guarantee on estimating the normalization factor. For simplicity, we will prove the statement with high probability guarantee, i... the success probability is 1 1/ poly(n).
Theorem B.4. Let Q, K E Raxd, À > 0 and c E (0, Let s (sx)) where 82 is the statistical dimension of the exponential kernel on K. There exists a data structure (Algorithm 2) with the following specification:
Preprocessing in 0.5 (e)
/e) row queries Q K and time Ö(n d)/e )n);
For any i E [n), outputs an approximate normalization factor for row in time
Moreover, with probability at least - 1/ poly(n), it holds that for any i [pi], the output by satisfies
lb. exp(x,, )1m1 I O([|A|| + Avn).
Aya T < 1, then the bound can be further simplified to
1b. exp(q; K )mm1 ) 5(AVM),
and the preprocessing time simplifies to
(s+ s*).
Given Q, K, let E 2nx2n be the associated exponential kernel matrix. We will first invoke Corollary A.7 compute sampling matrix R2axa where s O(s)) such that E. = =ES(ST 5T E approximates F, in time 0.. (.55 + Set U = ES(S FSS)
Proof.
Ui
we have that E = UUT for U
with U1, U2 IR and our desired approximate block for U22
A is A UUU.T. Note that forming U explicitly would take M(x) time, so instead implement a row oracle for U2. Since U2 E x we only need to compute entries for each row, and let N = = ESS) we see that (U2)j.- = N(ES) and (ES) contains values in the form of Sk exp(
xx)) for k S. N can be computed in O(s²d + 3h)) time, and row oracle for any E [n] can be implemented in O(sd + s?) time. By Lemma 2.6, j be computed in O(.0.511 + d)/e) time. To query the normalization factor for row i, note that can be computed via (U,7), ((U)).., mi), which can be computed using row oracle, in O + d)) time. Thus, the overall runtime of our procedure can be summarized as
Preprocessing time 06.55.1.55 + d)/e + s²));
Query time O(s(s d))-
21

---

Published as a conference paper at ICLR 2026
It remains to give an approximation guarantee. With probability at least 1/ poly(n), have ||A All X, and observe that
a In - exp((;K
1nm ml 1 11(AA A)oiloo
I E Ell
||0
Avn
where the second step is by the matrix infinity norm is the induced norm of vector loe norm, and the last step is by Lemma B.1. On the other hand, our final output bq is an approximation to a In Let U1j5 by Corollary B.3, we have
| 2 e ||A],
this holds with probability at least 1 - 8, conditioning on this event, note that by Lemma A.I, we have that ||||| < ||||| + X. Thus, we conclude our final result by
16: exp(g,
)m,1 )),l
S 16: ";1nج + ब 1, -ex((x
I ||Áu 7l2 + A/nn
$ c (A ||||]) + Avn.
Now, suppose Avñ S ||A]], then we could set
AVT the error bound simplifies to O(Ayn). T
C APPROXIMATE MATRIX MULTIPLICATION VIA LEVERAGE SCORE
remains handle the value matrix, and we will do so via machinery called approximate matrix multiplication.
Definition C.1 (Approximate matrix multiplication, Clarkson & Woodruff (2017)). Let A E Raxd B Raxm and let C A Rddmm. The approximate matrix multiplication prob- lem asks to design random matrix S E 12xx such that
Pr[lIAT SS B - Cllr S <=]AA|]>|BB||]]2
21
where e, 1). We call such S satisfying 6MMMM.
To generate the random matrix S, our strategy will be performing leverage score sampling over V. However, standard proof (see, e.g., Clarkson & Woodruff (2017)) requires V to have orthonormal columns. We provide proof for the case where V does not have orthonormal columns (albeit it requires extra factors in blowups). Before doing so, we define a parameter that quantifies this blowup which we call distortion.
Definition C.2 (Row distortion). Let A E Raxd foxdfoor d, we define the row distortion of A, denoted by ((A), as
10
a(A)
TAIZ
max (E(R)
where a; the i-th row of A and Ti is the i-th leverage score of A (Definition 2.1). When A is clear from context, we use as an abbreviation.
Lemma C.3. Let A E ga with n 2 d. then the row distortion of A satisfies
d
a(A)
srank(A)
||||| [[ is the stable rank of A.
where srank(A)
Proof. We derive an upper bound on ||a: 11,, let A UEVT be its SVD, then
||.
||e TUTTVTI
112
22

---

Published as a conference paper at ICLR 2026
S <|uu:112 | 1 1
тΙ |UEV 11? = Tj ||||1
where the third step is by the definition of leverage score and spectral norm is unitary invariant. We thus obtain the following bound on a(A):
|a,l12
a(4)
= |
max (E
d
Ti
||
< ||
max KE(m)
T5.
d ||
||
F
d
srank (A)
|| ||
where we recall that srank(A)
We are now ready to prove a generalized approximate matrix multiplication based on leverage score sampling, when the matrix does not have orthonormal columns.
Lemma C.4. Let A E Raxd B E R"xm, let S E Raxs be the leverage score sampling matrix of A with (o for e, 10, and a is the row distortion of (Definition C.2). Then, S is an (c, 6..MMMM.
Proof. For the sampling matrix S, is a scaled submatrix of the permutation matrix, where for any E [s]. Sm,.m /spm where Pm 2 Eg and 2m i with probability p,. Let a, bj denote the i-th and j-th row of and B, respectively. We can write
(l i -1).
A B A 8
Σ mE(n),meld
a
Pi
taking expectation, we obtain
BIATSST B A
Σ
a,b;
Pi
-1
pi
=0,
bound the second moment of ||AT SST B AT Bli P, we first expand the definition of Frobenius norm square:
Etr Etr((A SS B - (A SS B B-ATDA ATBB]
11)
[[2m = 5] -1)
[[ = i
E
tr
b,ae byaJa,b a,b,
$2
Pj
P;
tr
b,a, abb - -B AATA B
P
tr
bya T a.b.
BT AAT B
Pe
| 14
BT AAT B)
Pi
[11
B1
<
23

---

Published as a conference paper at ICLR 2026
< ah
where the first step is by definition of S, the second step is by applying expectation and use
E[A SS B A B 0, the fourth step is by tr(b,a, abd ||a,b 1 I 111bb the
fifth step is by Ps 2 d. therefore
d
||
|
||a:112
||
T
|| I
| 11
where the last step is by the definition of a. By Chebyshev's inequality, we can choose (a/e²) so that the approximate matrix multiplication holds with constant probability, and one could boost the success probability to 5 by either taking log(1/5) independent copies via Chernoff bound, or directly through Bernstein inequality.
We are ready to state our final result on approximating the value matrix V.
Theorem C.5. Let V TRaxd 6 E 1) and a be the row distortion of V. There exists quantum algorithm that computes weighted sampling matrix E R with Ō such that for any fixed matrix B Raxm S is an 1/1l/ -AMM. Moreover, S can be computed using Ō(E 'n 0.3 0.5) row queries to and Ö(E 0.5 a 0.5 + d²)) time.
0.5)
Proof. The proof is by composing Lemma A.5 and Lemma C.4, and note that for Ō(c-2a) rows, the sum of leverage scores most
D PUT THINGS TOGETHER
We are now ready to state our final algorithm and its guarantee. Recall that, we define D exp(QKT)L and D' = exp(KQT)LL We use D, D' to denote their approximations.
We prove simple inequality that quantifies the perturbation the inverse. D
Lemma D.1. Let C E Raxx, if D is nonsingular and ||C DII S e, and ||- < 1/e, then C is also nonsingular and ||C-||| < I-e ||-'||
Proof. We will make use of Neumann series, which states that for ||||| < 1, (T- A) admits the expansion
(I (T- -)- Σ *
k=0
this leads to bound on the norm:
(I- A)
k=0
|
||
(1)
|||
24

---

Published as a conference paper at ICLR 2026
now, to prove our desired bound, write C D + E where E is the perturbation, then C = E), and we will apply Eq. (1) to -D
| E || |||
-1
< c/c.c
=1,
therefore
10- |1 -
$ || -
D--1
$ |
||D
| D-
||-
1 c. DD
this completes the proof.
Rand be the query, key and value matrices for attention, let x >>>>0 O. Let E E 2n be the exponential kernel matrix with the dataset Q QUK, and let S be the statistical dimension of E (Definition 2.2), a be the row distortion of V (Definition C.2). There exists quantum data structure (Algorithm 3) thut preprocesses Q. K, V only through row queries to these matrices and with probability least 1 - 1/ poly(n), for any [n]) outputs vector & Rd where
Theorem D.2 (Formal version of Theorem 3.1). Let Q,
7=
If in addition, have ||0-1|| < +|| then the approximations D, A and V satisfy that
1D- - - D-1AV Se. Se- ([IAl)= + AVT) [V[|E,
where B = 1-(e|| D- Moreover, the algorithm has the following runtime specification:
Preprocesses 0.3 row queries to Q, K and Ö(e (35 row queries to V, and 02.5 (s2 + 1 d a d. + d= + 8 + c 2sxad) time;
For any i E [n]. it outputs T; in ( + sxd) time.
By Theorem C.5, know that with probability at least 1 poly(n), the following bound holds:
Proof.
| ASv s |D- |[
S [ [D-1 |[]| I|V
where the second step is by |ÍD-AAlle < | [|| By Theorem B.4, we know that
| D| < <||AA] + +AvR,
note that as long as the error satisfies that || < -|A then by Lemma D.1, we obtain
bound on D-11|:
||-
| - [e||A|| + A/ T D-11
Finally, by Corollary A.2, we have
Ā < ||
For the runtime, it suffices to combine Corollary A.7, Theorem B.4 and Theorem C.5, and the only additional runtime term is the -2 add which is the time form matrix R and T..
n
25

---

Published as a conference paper at ICLR 2026
E EMPIRICAL VERIFICATIONS ON PARAMETERS
In this section, we empirically verify the assumptions on the parameters. In particular, we focus on the following metrics:
|D & AA we specifically check that what is the maximum possible e so that Dー न|
TA this is important as our emor guarantee is in terms of Frobenius norm rather than the more typical spectral norm (Zandieh et al., 2023; Han et al., 2024), verify that this ratio is small.
||||
[V this similar the above test, verify that this ratio close to vd.
[V]
arank(V) this quantity serves as an upper bound of (VV), we verify that this quantity is small constant rather than the upper bound d.
[| in our enror analysis, we have pay extra vni factor when converting the spectral norm to matrix infinity norm, empirically show that this ratio is small constant rather than the /n scaling.
To conduct our experiment, we use the OLMo2-1B and OLMc2 models, in particular their st stagel pretraining checkpoints (Walsh et al., 2025). We list the model architecture in the following.
Sequence length
Value dimension d Number of layers
Number of heads H
OLMo2-1B
4096
128
16
16
OLMo2-7B
4096
128
32
32
Table 2: Model architecture for OTMo2-18 and OTMo2-7B.
compute the corresponding attention modules D, using the pretraining datasets for these models, with batch size 2 and 16 batches, We then compute the statistics for each head and each layer, then aggregate the statistics over layers. We report the mean of these statistics.
A
V
A
Emax
A
V
srank(V]
[A
OLMo 1B
0,1708
1.3769
11.3137
1.7126
2.7439
OLMo2273 7B
0.1685
1.3586
11.3137
2.1345
2.7439
Table 3: Mean statistics across all heads and all layers. Cmax is the maximum such that |D-1| || s |||
Through these verifications, we make the following preliminary observations:
To satisfy the || S
a|[Ai| assumption, it enough pick c S 0.17, which is larger than common choice of e =s 0.1. This gives us enough room to tune the parameter e to achieve good balance between efficiency and accuracy.
The ratio |Alee is a constant smaller than 2, much smaller than the worst case / predicted |||l|
by the theory (recall that 4096 and vn 64). This suggests that we don't 't need to scale down by a factor of ( to recover the spectral norm error guarantee.
The ratio ||V le 11 is roughly Vd as d 128, this confirms the theory, but it does not [[V
impair the sublinear scaling in n of our algorithm: we could simply scale down by factor of Vd to absorb this blowup and increase the runtime by factor of Vd.
The ratio srank[V] is small constant, recall that srank(V)) can be small as 1, causing the ratio to d, our experiment shows that a(V) is close small constant rather than d.
The ratio || is constant smaller than 3, check this quantity in proving the [[|
approximation guarantee for D, we make of the fact that ||ol S Vn. ||A]], this again
26

---

Published as a conference paper at ICLR 2026
shows that instead of the worst case vn scaling, this distortion is only by constant factor, implying the Xv additive error term is more likely O()) in practice. This greatly enlarges the range of choice for À to achieve better speedup.
F BIT COMPLEXITY OF OUR ALGORITHM
In this section, we give preliminary analysis on the bit complexity of our algorithm, in particular the bit complexity of matrix inversion operation. We will make use of the following standard algorithm for backward stable matrix inversion.
Lemma F.1 (Higham (2002); Harvey & van der Hoeven (2021)). Let A E R be nonsingular, there exists an algorithm that computes B-1 such that
|B - All s 5.- 5.ss s k(A))loRs ||A-
for absolute constant C' O with bit complexity ((s).M(b) where b ((lo((((A)) +og) and M (b) = (b lolg b).
We note that the backward stable error guarantee is exactly what has been analyzed in Gu al. (2024):
Lemma F.2 (Lemma G.3 Gu (2024)). Let A, E Raxx be matrices such that || Bl| then
(T:(A) T, (B) S (A).
This means that by setting 8 = 1/ (x])), we can approximate the leverage scores well, and the number bits b (()g((x(A))) Note that we apply matrix inversions for two type of matrices:
S ES + AI, where S' is the ridge leverage score sampling matrix for E; VTV, where V is the value matrix.
In the latter case, we only need to pay the (V))))(VV)) factor, which practice, very small: in our experiments, we see that on average, the log of the condition number is smaller than 4 and the largest log of the condition number smaller than 20. The interesting part is the former case.
To analyze <(ST ES + XT), we upper bound the spectral norm and lower bound the smallest cigenvalue. First, observe that S ES 0, so trivially we have S ES AI y Al, thus the smallest eigenvalue is at least X. To bound ||S ES + A/]I, we note that
S| ES X7 S |SS ES|| + +
|| ||T|| + X
we bound the two spectral norms respectively. For ||S|| bound it probabilistically: let if is sampled with probability P: and consider the matrix SS note that by definition, SST
1,
0, otherwise
diagonal matrix with
(SS )1, 6
note that as 6; Bernoulli random variable with probability Pe, we have TF/c:] and
hence E
c
P
||||S||
E
max x
Ci
P:
E
Pj
i=1
C2
Pt
1=1
27

---

Published as a conference paper at ICLR 2026
n,
hence by Markov's inequality, with constant probability (say 0.99), we have that ||s|| O(n). Condition on this event, we analyze EE|: let R max(max |1 max; [1 then
|| v tr[F]
Σ exp(1l9:11 + exp(1k:1/Vaa)
S 2n exp( (xp(R/vd))
combining the above, we obtain a final (probabilistic) upper bound on the condition number of S ES AI:
|| |E 1+1++
+
<(S +
A
Cn exp(R/Vd)
51+
A
this gives the final bound on log(k((T ES + XI)):
log(k(S* ES + AT) & R/Va log(n/A).
In practice, the data-dependent parameter R/vd is small: for both OLMo2-IB and OLMo2-7B models, these values are 20.1 147 and 21.2227 respectively. Hence, the final bit complexity is (d-001 R + log()<V)) log(n/A))).
When performing leverage score sampling over V, we need to compute the inverse (VTV)- thus is mandatory to obtain an upper bound on the condition number of V. To compute such upper bound, we note that the algorithm computes leverage score sampling matrix S with O -2 log d) rows, and the matrix SV E R= "d dxd Computing the condition number and spectral norm of SV can be done classically, in poly (d) time.
To establish relation between the conditioning of V and SV, observe that S provides a subspace embedding property:
cVVTV = V SV I (1 + VV this implies that x(SV) s
Its k(V) I (1 +1+00 O(d) x(V). This ensures that the bit complexity b depends only on I-c (Vog(.(V)).
V
Finally, to compute the spectral norms and condition numbers required by the algorithms, we could the algorithms in Musco et al. (2018); Shah (2025); Sobezyk (2025).
LLM USAGE DISCLOSURE
LLMs were used only to polish language, such grammar and wording. These models did not contribute to idea creation or writing, and the authors take full responsibility for this paper's content.
28


Reviews:
[{"review_id": "FDcq4OC0zm", "reviewer": "Reviewer_ppDN", "summary": "The paper proposes a quantum data structure for approximating the Transformer attention mechanism under the row query model, where only individual rows of the attention output are queried. The key contribution is a theoretical framework that achieves sublinear preprocessing time complexity of $\\tilde{O}(\\epsilon^{-1} n^{0.5}(s_\\lambda^{2.5} + s_\\lambda^{1.5} d + \\alpha^{0.5} d))$, providing a quadratic speedup over the best known classical algorithms.\nThe method embeds the non-symmetric attention matrix $A = \\exp(QK^\\top / \\sqrt{d})$ into a larger symmetric exponential kernel matrix over the combined dataset $(Q, K)$, and applies a combination of quantum Nyström approximation, quantum multivariate mean estimation, and quantum leverage score sampling to approximate the attention normalization factor, kernel matrix, and value multiplication components, respectively.\nThe resulting data structure allows approximating any attention row in time $\\tilde{O}(s_\\lambda^2 + s_\\lambda d)$, without assumptions on $Q, K, V$. This is, to the authors’ knowledge, the first quantum algorithm achieving sublinear dependence on sequence length $n$ for attention approximation. The authors also provide theoretical guarantees in Frobenius norm for the symmetrized attention matrix $(A + A^\\top)/2$, along with detailed parameter dependence on the kernel’s statistical dimension $s_\\lambda$ and value distortion factor $\\alpha$.", "questions": "Q1:Regarding Empirical Validation (W1):\nCould the authors provide any empirical or simulated evidence to illustrate the practical implications of the proposed algorithm? For example, could a small-scale classical simulation or synthetic experiment demonstrate the expected sublinear scaling behavior or approximation quality?\n\nQ2:Regarding Symmetrization Limitation (W2):\nThe current framework provides guarantees only for the symmetrized attention matrix $(A + A^\\top)/2$. Do the authors believe the same quantum speedup could be achieved without this symmetrization? If not, could they elaborate on the fundamental technical barriers that make direct approximation of the asymmetric attention matrix more challenging?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1: High Originality and Theoretical Significance: This work, to the best of my knowledge, is the first to propose a sublinear-time quantum algorithm for approximating the standard Transformer attention mechanism in the row-query setting. Achieving a preprocessing complexity of $\\tilde{O}(n^{0.5})$, the method provides a potential quadratic speedup over classical algorithms. This represents a meaningful theoretical advance and offers a new perspective on overcoming the quadratic bottleneck in large-scale attention computation.\n\nS2: Sophisticated Theoretical Framework: The paper demonstrates strong technical depth by systematically combining several advanced quantum tools—Nyström kernel approximation, multivariate mean estimation, and leverage score sampling—into a coherent data structure for attention approximation. The approach of embedding the non-symmetric attention matrix into a symmetric exponential kernel over the joint query–key space is both elegant and conceptually novel. Moreover, the framework is general, requiring no structural assumptions on $Q$, $K$, or $V$, which enhances its theoretical robustness and potential applicability.", "weaknesses": "W1: Lack of Empirical Validation: The paper is entirely theoretical and does not provide any numerical simulation or small-scale experiment to illustrate the potential practical impact of the proposed method. While this is acceptable for a theoretical contribution, even a simple empirical demonstration (e.g., simulated quantum runtime scaling or synthetic kernel approximation) would help substantiate the claimed sublinear advantages.\n\nW2: Symmetrization Limitation: Because the algorithm approximates the attention matrix through a symmetric kernel on the combined $(Q, K)$ dataset, it effectively provides guarantees only for the symmetrized form $(A + A^\\top)/2$. This design choice limits its direct interpretability as an approximation to the true attention matrix, and it remains unclear whether the same speedup can be achieved without this symmetrization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "70IbOKd9R9", "reviewer": "Reviewer_ojWR", "summary": "The goal of the paper is to study approximation algorithms for self-attention computation in the transformer architecture. The inputs to self-attention are $Q,K,V \\in \\mathbb{R}^{n\\times d}$ and the goal is to output $Att(Q,K,V) = D^{-1}A V$ where $A= exp(QK^T/\\sqrt{d})$ and $D^{-1} = diag(A\\mathbb{1})$. Past works for provable attention approximation need at least $\\Omega(nd)$ time, which is the input and output size, and the paper focuses on quantum algorithms that can achieve a better runtime. If one insists on outputting the entire $Att(Q,K,V)$ matrix, $\\Omega(nd)$ time is inevitable, however this can be avoided by formulating the problem as a data structure problem. In particular the goal is preprocess $Q,K,V$ into a data structure that then allows, for any index $i\\in [n]$, the return an approximation to the $i^{th}$ row of $Att(Q,K,V)$. Even then since each row of $Att(Q,K,V)$ is a convex combination of rows of $V$, achieving sublinear in $n$ time is hard. \n\nTheir main contribution is a quantum data structure that access the input matrices only using row queries, performs preprocessing in $\\widetilde{O}(\\epsilon^{-1} n^{0.5} poly(d,s_{\\lambda},\\alpha)$ time, and answers output row queries in time $\\widetilde{O}(s_{\\lambda}^2 + s_{\\lambda}d)$ (here $s_{\\lambda}$ is the statistical dimension of $exp(QK^T/\\sqrt{d})$. Their approach uses techniques such as Grover search, Quantum Nystrom approximation, and Quantum multivariate mean estimation.", "questions": "The first question is that the authors make a statement that achieving sublinear in $n$ dependence for the row query model seems intractable for classical algorithms since each row of the output is a convex combination of rows of $V$. Is there a formal claim to show this ? If yes then since there are past works on attention approximation that make structural assumptions on the input matrices, is it possible to prove classical sublinear in $n$ guarantees under plausible assumptions ?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength of the paper is to present a sublinear time algorithm that answers row queries for attention approximation in the quantum model. The techniques are very interesting and conceptually simple.", "weaknesses": "Perhaps one minor weakness is that there are few previous works on attention approximation that achieve spectral norm approximation guarantees and it would be to prove such a guarantee here as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7PhIPzUwmO", "reviewer": "Reviewer_eeim", "summary": "This paper proposes a quantum data structure for approximating rows of the attention matrix in sublinear time with respect to the sequence length n. The method combines quantum Nyström approximation, multivariate mean estimation, and leverage score sampling to approximate the components of the attention mechanism. This is the first quantum algorithm to achieve sublinear dependence on n in the row-query model without structural assumptions.", "questions": "1. Can you give numberical experiments to show the time cost, errors and the assumptions on parameters.\n2. How does the statistical dimension s behave in practice for typical transformer inputs, and does it remain small enough to yield meaningful speedups?\n3. Is the row distortion parameter α bounded in real-world value matrices, and are there cases where it becomes large enough to negate the sublinear advantage?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The work is the first to achieve sublinear-in-n row queries for attention approximation using quantum methods.\n2. The approach makes no  structural assumptions making it widely applicable.", "weaknesses": "1. Parameter dependence: The runtime depends on s  and α , which may be large in practice, limiting practical speedups.\n2. Norm of D−1 assumption: The guarantee requires ∥D−1∥<(ϵ∥E∥+λn)−1, which may not hold in all settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LB4mcYJhXY", "reviewer": "Reviewer_zcdq", "summary": "This paper studies quantum algorithms (in the QRAM model) to approximate attention in transformers. Given query-key-value matrices $Q,K,V$ of sizes $n\\times d,d\\times n,$ and $n\\times d$, respectively, the goal is to approximate the attention matrix $A=softmax(QK^\\top)V$. This is achieved by constructing a data structure that, given any index $i\\in[n]$, it returns $\\widetilde r_i\\in\\mathbb{R}^{d}$, which approximates the  $i$-th row of $A$. The total complexity to construct the data structure  depends on $n,d$ and other parameters such as the accuracy, statistical dimension, and row-distortion, and Frobenius norms (I expand further below). If the additional parameters besides $n,d$ are treated as constants, then the proposed approach provides quadratic speed-up with respect to the large dimension $n$, against known algorithms for the problem at hand. Importantly, the complexity guarantees are also accompanied with approximation bounds.", "questions": "My current assessment is slightly leaning towards reject, due to the two main concerns that I raised above. At this stage it is not clear to me if the final, end-to-end complexity achieves the reported sublinear time, or, if it does, what are the corresponding parameter regimes. My recommendation is not final. I will take into consideration the authors responses as well as the comments from the other reviewers.\nHere I mention some questions that I would like answered to help me clarify my understanding of the paper and provide the additional evidence for my final assessment.\n### Questions\n1) Regarding concern 1): What is the \"classical\" model of computation followed here? Is it \"compatible\" with QRAM? Could you provide references/discussion on the precise complexity / approximation guarantees of the assumed classical subroutines?\n2) Regarding concern 2): Could you provide a small paragraph discussing further how the choice of the different parameters affects the total complexity? If someone wants spectral-norm bounds, how can they be achieved?\n3) Can we replace QRAM with something simpler (e.g., QROM)? Which parts are currently the \"bottleneck\"? \n4) Are there any quantum / classical lower bounds for Frobenius-norm type of approximations, e.g., in similar spirit to [2] below. I do not expect the authors to prove lower bounds at this stage, but a relevant discussion would be helpful.\n5) If we were to use the proposed algorithms to  approximate the entire attention matrix, what would be the complexity and how does it compare with existing attention algorithms? I think that the $\\Omega(n^2)$ lower bounds of [2] leave quite some room for improvements. E.g., if the final complexity of the proposed algorithm is $O(n^{1.5})$ to achieve the same (or similar) bound as [2], then this would already be a nice improvement, and would significantly strengthen the presentation. Could you provide some insights? \n6) Could the authors comment on how to choose the $\\lambda$ parameter?\n\n### Additional Feedback\nHere I provide additional feedback with the aim to improve the paper. These points are here to help, and not necessarily part of the decision assessment.\n\n- The main result, Theorem 3.1, is in page 7. It would be nice to either move it earlier, e.g., in the introduction, or at least a more explicit statement of the main result in the introduction.\n- A table with the main result compared to existing algorithms could be helpful. E.g., to compare complexity, approximation guarantees (if any), the model of computation, or other properties that the authors consider important (again, this is not a request for the rebuttal, just potentially nice-to-have)\n- Some paragraphs are a bit long, e.g., the first paragraph of Section 3.3. \n- Using colored references can be helpful, and I think it is allowed by ICLR template.\n- In line 206, $O(s^2)\\cdot \\mathcal{T}_K+s^\\omega$ should be $O(s^2\\cdot \\mathcal{T}_K+s^\\omega)$. The hidden constants in fast matrix product are quite large. There might be other places in the paper where this applies.\n- When mentioning algorithms/subroutines with $O(n^\\omega)$  complexity, a reference or proof should be given. I know that some theory papers tend to take them for granted, but often they are highly non-trivial to prove, or even to find the corresponding bibliography.\n- Between lines 368-369: The sentence \"...achieving a quadratic speedup over any classical algorithm\" should probably be \"...achieving a quadratic speedup with respect to $n$ over any classical algorithm that we know of\". \n- In line 372, it is mentioned \"when $a=o(n)$\". Based on Definition C.2 in the Appendix, I think $a(V)$ is always at most $d$. Take the SVD of $V=U\\Sigma W^\\top$, and let $v_i$ be the $i$-th row of $V$. It holds that \n$||v_i||_{2}^{2}=||e_i^{\\top}U\\Sigma W^{\\top}||_2^2\\leq  ||e_i^{\\top} U||_2^2||\\Sigma W^\\top||_2^2=\\tau_i||V||_2^2.$ Replacing this in Definition C.2 gives \n$\\frac{d}{||V||_F^2}\\cdot \\max_i\\frac{||v_i||_2^2}{\\tau_i} \\leq d$.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is well-written and concise, which makes it enjoyable to read. \n2) It targets one of the currently most popular computational problems in deep learning, the \"quadratic curse\" of attention.\n3) It provides a novel approach to the problem, combining (non-trivially) techniques from random Linear Algebra and quantum computing.\n4) It achieves a complexity that scales as $\\sqrt{n}$, with respect to the large dimension $n$. This is impressive, even if it only holds for certain parameter regimes. To my knowledge, classical algorithms require $\\Omega(n^2)$ time to achieve sharp element-wise approximations (ref [2] below), or $\\Omega(n)$ for less strict approximations. \n5) The related work discussion is thorough.\n6) The mathematical analysis is very rigorous. I did not read all the details in the proofs, but I was not able to \"break\" any of them, they seem correct, and well-written.\n\n### References\n- [1] Demmel, James, Ioana Dumitriu, and Olga Holtz. \"Fast linear algebra is stable.\" Numerische Mathematik 108.1 (2007): 59-91.\n- [2] Alman, Josh, and Zhao Song. \"Fast attention requires bounded entries.\" Advances in Neural Information Processing Systems 36 (2023): 63117-63135.", "weaknesses": "I have only two \"major concerns\" to raise at this stage. Below in \"Questions\" I provide specific questions that would help me understand the details better and clarify these points.\n1) **Classical model of computation**: From what I understand, there are subroutines in the main algorithm that rely on classical computations. For example, line 274 assumes a subroutine to compute the pseudoinverse in $O(n^\\omega)$. How? From what I know, finite precision algorithms can only return approximate solutions (see e.g. ref [1] below). Things might be easier in \"exact arithmetic\", but I am not sure that infinite-precision is compatible with QRAM.\n2) **Approximation/complexity trade-off**: I am a bit sceptical about the complexity / approximation trade-off. In Theorem 3.1, line 362, there is a $\\sqrt{n}$ term, and two more \"hidden\" in the Frobenius norms. The former can be absorbed by setting e.g. $\\lambda=1/\\sqrt{n}$, but it is a bit unclear how this affects complexity. Now, if we were to upper bound the $||\\cdot||_F$-norms with $||\\cdot||_2$-norms, which is commonly the desired type of bound, they would intruduce another $\\sqrt{n}$ factor. This factor would have to be absorbed inside $\\epsilon$, e.g., by setting $\\epsilon'=\\epsilon/\\sqrt{n}$. But they this would introduce an additional $\\sqrt{n}$ factor in the complexity of line 365, and therefore it would no longer be sublinear in $n$.\n\n**Minor concerns:**\nI have the following two minor comments (but they did not influence my recommendation).\n\n- The QRAM model is mostly of theoretical interest (at least at the time of this writing). This might be a limitation for practical implementations in the future. \n- The authors recognize in line 377 that the reported approximation guarantee is for a \"symmetrized version\" rather than the classic norm-wise approximation. I think this is fine, I am more concerned with the Frobenius-versus-spectral norm topic, as I mentioned above. But it certainly speaks in favor of the authors that they explicitly mention this topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)