Given the query, key and value matrices $Q, K, V\in \mathbb{R}^{n\times d}$, the attention module is defined as $\mathrm{Att}(Q, K, V)=D^{-1}AV$ where $A=\exp(QK^\top/\sqrt{d})$ with $\exp(\cdot)$ applied entrywise, $D=\mathrm{diag}(A{\bf 1}_n)$. The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix $D^{-1}A$ incurs $Ω(n^2)$ time, motivating numerous approximation schemes that reduce runtime to $\widetilde O(nd)$ via sparsity or low-rank factorization.
We propose a quantum data structure that approximates any row of $\mathrm{Att}(Q, K, V)$ using only row queries to $Q, K, V$. Our algorithm preprocesses these matrices in $\widetilde{O}\left( ε^{-1} n^{0.5} \left( s_λ^{2.5} + s_λ^{1.5} d + α^{0.5} d \right) \right)$ time, where $ε$ is the target accuracy, $s_λ$ is the $λ$-statistical dimension of the exponential kernel defined by $Q$ and $K$, and $α$ measures the row distortion of $V$ that is at most $d/{\rm srank}(V)$, the stable rank of $V$. Each row query can be answered in $\widetilde{O}(s_λ^2 + s_λd)$ time.
To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to $n$. Our approach relies on a quantum Nyström approximation of the exponential kernel, quantum multivariate mean estimation for computing $D$, and quantum leverage score sampling for the multiplication with $V$.
AI Summary
The paper studies whether individual rows of transformer attention, $D^{-1}AV$ with $A=\exp(QK^\top/\sqrt d)$, can be approximated with preprocessing sublinear in sequence length $n$. It assumes coherent row-query access to $Q,K,V\in\mathbb R^{n\times d}$ and a quantum-read/classical-write RAM model, and returns classical row vectors rather than the entire attention output.
The proposed data structure has leading preprocessing time $\widetilde O(\epsilon^{-1}\sqrt n(s_\lambda^{5/2}+s_\lambda^{3/2}d+\sqrt\alpha\,d))$ and row-query time $\widetilde O(s_\lambda^2+s_\lambda d)$. Here $s_\lambda$ is the statistical dimension of the exponential kernel on the combined query/key dataset, and $\alpha\le d/\mathrm{srank}(V)$ measures value-row distortion. The formal runtime additionally includes $d^\omega+s_\lambda^\omega+\epsilon^{-2}s_\lambda\alpha d$. The construction embeds the nonsymmetric attention matrix into a PSD kernel matrix, applies quantum recursive ridge-leverage sampling for an implicit Nyström approximation, estimates normalization factors using quantum multivariate mean estimation, and approximates multiplication by $V$ through leverage-score sampling.
The stated high-probability error guarantee is a global Frobenius-norm bound, scaled by $\|D^{-1}\|$, $\|A\|_F$, and $\|V\|_F$, under the stability condition $(\epsilon\|A\|+\lambda\sqrt n)\|D^{-1}\|<1$. Sublinear scaling therefore depends on the other parameters remaining sufficiently small. Reported model statistics examine several error-bound parameters, but not the statistical dimension. Stated limitations include the Frobenius rather than spectral guarantee, the additive $\lambda\sqrt n$ normalization error and its tradeoff with statistical dimension, incomplete finite-precision analysis, and lack of support for causal masking.
Little sign of AI-generated textOverclaimsStrong assumptionsMissing comparisonPossible error
Central claim may not hold: The abstract's preprocessing bound omits d^ω and ε⁻²sλαd terms retained in the formal theorem, without restrictions ensuring that they are dominated.
The attention-error guarantee requires a normalization-stability condition and data-dependent norm factors that are not specified in the abstract.
Sublinear preprocessing requires sufficiently small statistical dimension at a regularization parameter compatible with accuracy, a regime the paper does not establish generally.
The stated Nyström guarantee has the wrong Loewner-order direction: the defined approximation always satisfies Ē⪯E, so the asserted E⪯Ē would require exact reconstruction.
The main proof controls only value-sampling error and omits kernel and normalization errors, leaving its claimed end-to-end ε-dependent attention-error bound unsupported.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Given the query, key and value matrices Q,K,V∈Rn×d, the attention module is defined as Att(Q,K,V)=D−1AV where A=exp(QK⊤/d) with exp(⋅) applied entrywise, D=diag(A1n). The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix D−1A incurs Ω(n2) time, motivating numerous approximation schemes that reduce runtime to O(nd) via sparsity or low-rank factorization.
We propose a quantum data structure that approximates any row of Att(Q,K,V) using only row queries to Q,K,V. Our algorithm preprocesses these matrices in O(ε−1n0.5(sλ2.5+sλ1.5d+α0.5d)) time, where ε is the target accuracy, sλ is the λ-statistical dimension of the exponential kernel defined by Q and K, and α measures the row distortion of V that is at most d/srank(V), the stable rank of V. Each row query can be answered in O(sλ2+sλd) time.
To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to n. Our approach relies on a quantum Nyström approximation of the exponential kernel, quantum multivariate mean estimation for computing D, and quantum leverage score sampling for the multiplication with V.
The paper studies whether individual rows of transformer attention, D−1AV with A=exp(QK⊤/d), can be approximated with preprocessing sublinear in sequence length n. It assumes coherent row-query access to Q,K,V∈Rn×d and a quantum-read/classical-write RAM model, and returns classical row vectors rather than the entire attention output.
The proposed data structure has leading preprocessing time O(ϵ−1n(sλ5/2+sλ3/2d+αd)) and row-query time O(sλ2+sλd). Here sλ is the statistical dimension of the exponential kernel on the combined query/key dataset, and α≤d/srank(V) measures value-row distortion. The formal runtime additionally includes dω+sλω+ϵ−2sλαd. The construction embeds the nonsymmetric attention matrix into a PSD kernel matrix, applies quantum recursive ridge-leverage sampling for an implicit Nyström approximation, estimates normalization factors using quantum multivariate mean estimation, and approximates multiplication by V through leverage-score sampling.
The stated high-probability error guarantee is a global Frobenius-norm bound, scaled by ∥D−1∥, ∥A∥F, and ∥V∥F, under the stability condition (ϵ∥A∥+λn)∥D−1∥<1. Sublinear scaling therefore depends on the other parameters remaining sufficiently small. Reported model statistics examine several error-bound parameters, but not the statistical dimension. Stated limitations include the Frobenius rather than spectral guarantee, the additive λn normalization error and its tradeoff with statistical dimension, incomplete finite-precision analysis, and lack of support for causal masking.
We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation. Our contributions include: * k-median and k-means clustering: For n points in d-dimensional Euclidean space, we give an algorithm that constructs an ε-coreset in time O(n0.5dk2.5poly(ε−1)) for k-median and k-means clustering. Our approach achieves a better dependence on d and constructs smaller coresets that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * ℓp regression: For ℓp regression problems, we construct an ε-coreset of size Op(dmax{1,p/2}ε−2) in time Op(n0.5dmax{0.5,p/4}+1(ε−3+d0.5)), improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all p∈(0,2)∪(2,22], including the widely studied least absolute deviation regression (ℓ1 regression). * Low-rank approximation with Frobenius norm error: We introduce the first quantum sublinear-time algorithm for low-rank approximation that does not rely on data-dependent parameters, and runs in O(nd0.5k0.5ε−1) time. Additionally, we present quantum sublinear algorithms for kernel low-rank approximation and tensor low-rank approximation, broadening the range of achievable sublinear time algorithms in randomized numerical linear algebra.
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n×n matrices with at most m non-zero entries and with ℓ2-error ε=Θ(1/m) must make Ω(m) queries to the matrix, even when the success probability is exponentially small in n. Additionally, we show that for ε∈[1/n,1/2], any quantum algorithm capable of producing 100ε-ℓ1-approximations of the row-sum vector of a (dense) normalized matrix uses Ω(n/ε) queries, and that there exists a constant ε0>0 for which this problem takes Ω(n1.5) queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an ε-ℓ1-scaling in time O(n1.5/ε2), whereas the best previously known bounds were O(n2polylog(1/ε)) (classical) and O(n1.5/ε3) (quantum).
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O(n+m) dependence on matrix dimension n and constraint number m. Compared with the O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs.
Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let s denote the the input matrix sparsity and γ:=Rr/ε capture dependence on the primal (R) and dual (r) radii as well as target accuracy (ε). When γ2≤min{m,n/s}, our solver runs in time O(nsγ4.5+msγ2). For γ=O(1), this is O((n+m)s) and sublinear in the O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to m and n, up to logarithmic factors. This implies that, with respect to dimensions m and n, there is no super-quadratic quantum advantage for generic sparse SDP solving.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
Suppose a matrix A∈Rm×n of rank r with singular value decomposition A=UAΣAVAT, where UA∈Rm×r, VA∈Rn×r are orthonormal and ΣA∈Rr×r is a diagonal matrix. The statistical leverage scores of a matrix A are the squared row-norms defined by ℓi=∥(UA)i,:∥22, where i∈[m], and the matrix coherence is the largest statistical leverage score. These quantities play an important role in machine learning algorithms such as matrix completion and Nyström-based low rank matrix approximation as well as large-scale statistical data analysis applications, whose usual algorithm complexity is polynomial in the dimension of the matrix A. As an alternative to the conventional approach, and inspired by recent development on dequantization techniques, we propose a quantum-inspired algorithm for approximating the statistical leverage scores. We then analyze the accuracy of the algorithm and perform numerical experiments to illustrate the feasibility of our algorithm. Theoretical analysis shows that our novel algorithm takes time polynomial in an integer k, condition number κ and logarithm of the matrix size.
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(ε1logm), where m is the number of variables and ε is the target precision, without dependence on the sparsity s, and could possibly be without explicit dependence on condition number κ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most s nonzero entries, we obtain the circuit depth O(ε1logs) using extra O(s) ancilla qubits, so the depth grows only logarithmically with sparsity s. When the sparsity s grows as O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.