56-dequantized-recommendation-sampling

Dequantised recommendation: Tang's ℓ²-sampling algorithm against truncated and randomised SVD at practical sizes

Abstract. Kerenidis and Prakash's quantum recommendation algorithm and Tang's classical dequantisation of it rest on one premise — sample-and-query (SQ) access through binary trees of squared norms — and differ by a polynomial in k, 1/ε and ‖A‖_F/σ_k. We build that structure with every operation counted, run Tang's full pipeline (ModFKV row and column sampling, median-of-means inner products, rejection-sampled recommendations) against exact truncated SVD, randomized SVD, popularity and an equal-budget uniform-sampling control, and score precision@10 on held-out users in ten seeded user–item configurations (500–20 000 users, 200–2 000 items, rank 5–20, density 0.05–1, heavy-tailed rows, ‖A‖_F/σ_k = 6–174). At r = c = 1 000 sampled rows Tang's top-10 list is 0.04–0.44 below randomized SVD's (rank 10: 0.736 against 0.966), the loss splitting into the sampled subspace (≤ 0.30), the sampled inner products (≤ 0.023) and turning 30 samples into a list (0.04–0.18, a step the quantum output shares). Precision collapses where the additive FKV error exceeds the k-th direction's share σ_k²/‖A‖_F² by 4–11×, ℓ² sampling beats the uniform control on 5 configurations and ties on 3, and the FKV-type sufficient size 16k(‖A‖_F/σ_k)⁴ is 10⁵–10¹¹ rows against the 10³ that work in practice. Once the trees exist Tang's cost is flat in the number of users (0.07 s subspace + 5 ms per user at r = 1 000), so one user's list undercuts a full randomized SVD beyond 9.2·10³ users (r = 1 000) or 1.5·10⁵ (r = 4 000, read-out within 0.06 of rSVD), and charging the tree build, 24× cheaper per nonzero than rSVD, moves those points by < 10 %. But each served user costs 570–2 300× randomized SVD's amortised per-user cost, so the dequantised speed-up is a single-query latency effect — one randomized SVD is cheaper as soon as 19–335 users need recommendations at 2·10⁵ users — and a quantum sampler on the same SQ access would have to undercut randomized SVD's per-user cost, not Tang's.

1. Background & gap

The quantum claim. Kerenidis & Prakash (arXiv:1603.08675) gave a quantum recommendation algorithm: if the user–item matrix is stored in a qRAM-addressable binary tree of squared norms, a quantum computer can return an item for user u drawn from (approximately) row u of a rank-k projection of the observed matrix in time poly(k)·polylog(mn), under the assumption that the matrix is well approximated at rank k. The classical recommenders it was compared with run in time polynomial in m and n, so the claim was an exponential speed-up for a practical machine-learning task.

Dequantisation. Tang (arXiv:1807.04271) showed that the same data structure, read classically as sample-and-query (SQ) access, supports a classical algorithm with the same output and running time poly(k, 1/ε, ‖A‖_F/σ)·polylog(mn): the exponential gap closes and a polynomial one remains. The algorithm is Frieze–Kannan–Vempala length-squared row and column sampling (FKV, J. ACM 2004) with a modification that keeps the approximate singular vectors implicit, plus sampled inner products and rejection sampling. Gilyén, Lloyd & Tang (arXiv:1811.04909) did the same for low-rank linear systems, and Chia, Gilyén, Li, Lin, Tang & Wang (arXiv:1910.06151) turned the toolbox into a general framework with lower exponents; Chepurko, Clarkson, Horesh, Lin & Woodruff (ICML 2022) lowered them further with randomized-numerical-linear-algebra sketches. The exponents in the original analysis are large, and the bounds are worst-case.

Practice. Arrazola, Delgado, Bardhan & Lloyd (arXiv:1905.10415) implemented the dequantised linear-system and recommendation algorithms and found that on very large, low-rank, well-conditioned matrices they need far fewer samples than the bounds require, but degrade quickly with rank and condition number. The classical alternative at practical sizes is not "polynomial in m and n" in any painful sense: randomized SVD (Halko, Martinsson & Tropp, arXiv:0909.4061) costs a few passes over the nonzeros, and ARPACK computes the exact top-k singular vectors at similar cost.

Gap. We have not found an end-to-end measurement, at the sizes recommenders have (10³–10⁵ users, 10²–10³ items), of the whole dequantised pipeline — SQ build, ModFKV, sampled inner products, rejection-sampled output — against exact truncated SVD and randomized SVD at matched accuracy, on held-out users, with an equal-budget uniform-sampling control that removes the ℓ² structure, with the number of SQ operations counted, and with the wall-clock crossover (including the SQ preprocessing the quantum algorithm also assumes) located. That is this experiment.

2. Problem formulation

Data (data.py). Ground-truth preferences T = X diag(s) Yᵀ ∈ ℝ₊^{m×n}, X_u ~ Dirichlet(0.3·1_k), Y_i ~ Gamma(0.5, 2)^k, so T is non-negative and has rank k. Observed matrix A = mask ∘ (T + σ_noise·sd(T)·G), G standard normal. Training users form A ∈ ℝ^{m_train×n}; 100–200 further users are held out, folded in through their observed row a_u, and judged on their unobserved items: the relevant set R_u is the top 10 % of T_u among the items u has not observed. Four families: lowrank (flat strengths s = 1, uniform mask, noise 0.1); illcond (s_t = 100^{−(t−1)/(k−1)}, complete training matrix, noise 0.02, held-out users 30 % observed — the only way to get large ‖A‖_F/σ_k, since masking noise otherwise floors σ_k); noisy (noise 3: the spectrum beyond k is a flat bulk that carries 94 % of ‖A‖_F²); powerlaw (training mask Poissonised from user activity 1 + Pareto(1) and item exposure ∝ rank^−0.8, so heavy rows dominate ‖A‖_F²; held-out users 20 % observed).

SQ access (sq.py; Tang 2018 §2). For a vector x ∈ ℝⁿ: query x_i, sample i with probability x_i²/‖x‖², norm ‖x‖. For a matrix: SQ access to every row A_i and to the vector of row norms (‖A_1‖, …, ‖A_m‖). Both are served by binary trees whose leaves hold squared magnitudes and whose nodes hold sums: one tree over the m squared row norms, one over the nnz squared entries in row-major order (each row is a contiguous leaf range, sampled by a prefix walk and a descent). A sample costs O(log m) or O(log nnz) node reads, an update O(log nnz), a norm one read; building both trees is one O(nnz) pass. This is the structure Kerenidis–Prakash assume in qRAM. Every operation is counted.

Task. For user u, output items j drawn from P(j) ∝ ŵ_j² with ŵ ≈ a_u V_k V_kᵀ (the rank-k fold-in), or a top-10 list built from such draws.

Tang's algorithm (tang.py), parameters (k, r, c, N, N_rec):

1. ModFKV. Draw r rows i_t ~ ‖A_i‖²/‖A‖F² and set S_t = A{i_t}·‖A‖F/(√r‖A{i_t}‖) (so E SᵀS = AᵀA and ‖S‖F = ‖A‖F). Draw c columns by picking t uniformly and then j ~ S_tj²/‖S_t‖² — which is exactly j ~ ‖S{:,j}‖²/‖S‖F² — and set W{:,l} = S{:,j_l}·‖S‖F/(√c‖S{:,j_l}‖). With (U, Σ) the top-k left singular pairs of the r × c matrix W, the approximate right singular vectors are V̂ = SᵀUΣ⁻¹, stored as the r × k coefficient matrix UΣ⁻¹: one entry v̂_j costs r queries. Cost: r + c samples, r·c queries, an r × c SVD; nothing depends on m or n except through log factors.
2. Inner products. λ_i = ⟨a_u, v̂^(i)⟩ is estimated by drawing j ~ a_uj²/‖a_u‖² and averaging Z = ‖a_u‖² v̂_j / a_uj, which is unbiased with Var Z ≤ ‖a_u‖²‖v̂‖²; the median of 5 means of N/5 draws has additive error ε‖a_u‖‖v̂‖ with probability 1 − δ for N = O(ε⁻² log 1/δ). Cost: N samples, N·r queries.
3. Sampling a recommendation. ŵ = V̂λ̂ = Sᵀz with z = UΣ⁻¹λ̂ is a combination of the r′ distinct sampled rows. Propose t ∝ z_t²‖S_t‖², then j ~ S_tj²/‖S_t‖² (an SQ sample in row i_t), accept with probability ŵ_j²/(r′ Σ_t z_t² S_tj²) ≤ 1 (Cauchy–Schwarz); accepted samples are exactly ∝ ŵ_j². The acceptance rate is ‖Sᵀz‖²/(r′ Σ_t z_t²‖S_t‖²); each trial costs one sample and r′ queries. Items the user already observed are discarded (one query each) until N_rec items are collected; the top-10 list is the 10 distinct sampled items with the largest ŵ_j.

What the theory says. (i) Row stage (Drineas, Kannan & Mahoney 2006, LinearTimeSVD applied to Aᵀ): with V_S the top-k right singular vectors of S, E‖A − AV_SV_Sᵀ‖_F² ≤ ‖A − A_k‖_F² + 2√(k/r)‖A‖_F². (ii) Column stage: E‖WWᵀ − SSᵀ‖_F² ≤ ‖S‖_F⁴/c. (iii) For exactly rank-k A we derive, per draw, V̂V̂ᵀ = V_S M V_Sᵀ with M = Σ_S G⁻¹Σ_S, G = U_SᵀWWᵀU_S, hence ‖A − AV̂V̂ᵀ‖_F ≤ ‖A‖_F‖I − M‖₂ ≤ ‖A‖_F·σ₁(S)e / (σ_k(S)(σ_k(S)² − e)) with e = ‖WWᵀ − SSᵀ‖₂ < σ_k(S)² — the condition number enters even when A is exactly low rank (tested in tests/). (iv) For the additive error ε‖A‖_F² to resolve the k-th direction one needs ε‖A‖_F² ≲ σ_k², i.e. ε ≈ (σ_k/‖A‖_F)²/2, and (i) then asks for r_DKM = 4k/ε² = 16k(‖A‖_F/σ_k)⁴ rows — the dequantised constant that ‖A‖_F/σ_k controls. Tang's theorem has the same shape with larger exponents; Kerenidis–Prakash assume ‖A‖_F/σ_k = O(√k) to make poly(k) hold.

3. Method

arm	what it computes
exact truncated SVD	top-k right singular vectors V_k (LAPACK if m·n ≤ 4·10⁶, else ARPACK svds, tol = 0); fold-in a_uV_kV_kᵀ; the Eckart–Young optimum and the referee
rSVD q = 7 / q = 2	Halko–Martinsson–Tropp Alg. 4.4, oversampling 10, q power iterations with re-orthonormalisation (q = 7 is scikit-learn's default for k < 0.1·min(m, n))
Tang (ℓ²), top-10 of samples	the three stages above with r = c = 1 000 (200 on small), N = 1 000 (median of 5 means), N_rec = 30 accepted unobserved samples, ≤ 50 000 trials
Tang read-out	rank all unobserved items by ŵ = V̂λ̂ (not sublinear in n; isolates the loss from building a list out of samples)
ℓ² rows + exact projection	the same V̂ draw, λ = a_uV̂ computed exactly (isolates the inner-product sampling error; a user row has 50–500 nonzeros, so this is also cheaper)
uniform control	identical pipeline and budget (r, c, N, N_rec) with uniform rows, uniform columns and uniform-over-observed inner-product samples, seeded per instance
exact A_k, top-10 of N samples	the sampling output model applied to the exact fold-in: the best a perfect quantum or dequantised sampler could return from N draws
popularity / random	Σ_u A_ui over training users / uniformly random unobserved items (seeded per instance)

Metrics. precision@10 and recall@10 against R_u; P(relevant) of a single ℓ² sample; Frobenius excess (‖A − AV̂V̂ᵀ‖_F² − ‖A − A_k‖_F²)/‖A‖_F², the quantity FKV and Tang bound by ε (V̂ is used as returned, not orthonormalised); preference-row errors ‖ŵ − a_uV_kV_kᵀ‖/‖a_uV_kV_kᵀ‖ and against the algorithm's own target a_uV̂V̂ᵀ; mean |entry error| over the row RMS; SQ samples, queries and node reads; wall-clock of each stage.

Studies. (a) the main grid of ten configurations; (b) a sweep r = c ∈ {20, …, 4 000} on five of them, ℓ² vs uniform; (c) a sweep of N ∈ {25, …, 25 600} at r = 1 000; (d) wall-clock against m ∈ {10³, …, 10⁵} at n = 1 000, density 0.05, k = 10, with the SQ build, rSVD (q = 7 and q = 2), exact SVD and Tang (subspace + one user) timed as the best of 3 (2 for Tang's subspace); (e) the crossover, from straight-line fits t = a + b·nnz over the larger sizes, of rSVD's whole factorisation against Tang's one-user latency, with the SQ build assumed free, with the trees charged, and with CSR canonicalisation plus trees charged.

Statistics. Three instance seeds per configuration, two algorithm seeds per instance for the sampled arms; 95 % bootstrap CIs (qcore.stats.bootstrap_ci, 1 000 resamples) over pooled held-out users × instance seeds × algorithm seeds for ranking metrics and over (instance, algorithm-seed) pairs for errors and costs; the Tang-vs-rSVD precision gap is paired per user.

4. Experimental setup

config	family	m_train × n	k	density nominal (realised)	held-out density	nnz (train)	‖A‖_F/σ_k	σ_1/σ_k	‖A−A_k‖_F/‖A‖_F	top-1 % rows' share of ‖A‖_F²	r = c	eval users / inst.
small	lowrank	500 × 200	5	0.2 (0.201)	0.2	20 114	6.1	2.4	0.844	0.027	200	100
lowrank_k5	lowrank	5000 × 1000	5	0.2 (0.200)	0.2	999 046	8.0	3.0	0.886	0.020	1000	200
lowrank_k10	lowrank	5000 × 1000	10	0.2 (0.200)	0.2	1 000 597	12.3	4.7	0.883	0.019	1000	200
lowrank_k20	lowrank	5000 × 1000	20	0.2 (0.200)	0.2	1 000 616	17.7	7.1	0.875	0.017	1000	200
dense_d0.5	lowrank	5000 × 1000	10	0.5 (0.500)	0.5	2 500 810	9.0	5.4	0.701	0.017	1000	200
sparse_d0.05	lowrank	5000 × 1000	10	0.05 (0.050)	0.05	250 410	14.1	2.8	0.951	0.026	1000	200
powerlaw	powerlaw	5000 × 1000	10	0.1 (0.043)	0.2	184 999	10.5	4.7	0.799	0.175	1000	200
illcond	illcond	5000 × 1000	10	1.0 (0.973)	0.3	5 000 000	174.1	154.9	0.016	0.096	1000	200
noisy	noisy	5000 × 1000	10	0.2 (0.200)	0.2	1 000 597	19.8	3.6	0.970	0.014	1000	200
large	lowrank	20000 × 2000	10	0.05 (0.050)	0.05	2 000 160	18.2	3.5	0.964	0.023	1000	200

m_train excludes the held-out users; "realised" density is nnz/(m·n) of the whole matrix (the powerlaw mask collides on heavy cells, and illcond's 0.973 mixes the complete training block with the 30 %-observed held-out rows). ‖A‖_F/σ_k, σ_1/σ_k and the tail ‖A − A_k‖_F/‖A‖_F are means over the three instance seeds of the training matrix; the masked families have ‖A‖_F/σ_k ≈ 6–20 however low their rank, because masking noise is a full-rank bulk.

item	value
seeds	--seed 0; instance seeds 0, 1, 2 per configuration; algorithm seeds 0, 1 per instance for Tang and the uniform control; every RNG stream is keyed by (seed, instance, algorithm seed, arm)
Tang / control	r = c = 1 000 (200 on small), N = 1 000 inner-product samples (median of 5 means), N_rec = 30 accepted unobserved samples, ≤ 50 000 trials per user
r sweep	r = c ∈ {20, 50, 100, 200, 500, 1 000, 2 000, 4 000} on five configurations (instance seed 0), 100 held-out users, 2 algorithm seeds
inner-product sweep	N ∈ {25, 100, 400, 1 600, 6 400, 25 600} at r = 1 000 on lowrank_k10, 50 users, 2 algorithm seeds
scaling	lowrank, n = 1 000, density 0.05, k = 10, m_train ∈ {10³, 2·10³, 5·10³, 10⁴, 2·10⁴, 5·10⁴, 10⁵, 2·10⁵}, 100 held-out users; r ∈ {1 000, 4 000}; exact SVD up to 5·10⁴
timing	time.perf_counter; scaling: best of 3 (SQ, rSVD), best of 2 (Tang subspace), median over 20 users (Tang per user); main grid: single measurement
backend	none — classical NumPy/SciPy (--backend accepted and recorded as aer (unused))
hardware	Apple M1 Pro (10 cores, 16 GiB), macOS 27, Python 3.13, NumPy/SciPy with Accelerate BLAS, qcore 0.1.0
wall-clock	full run 631 s while other agents' experiments loaded the machine (load average 10–25); peak RSS 1.6 GiB; --quick ≈ 7 s; pytest -q ≈ 8 s (12 tests)

5. Results

All numbers below are copied from results/results.json (seed 0); brackets are 95 % bootstrap CIs. "Tang top-10 of 30 samples" is the algorithm's actual output; "read-out" and "exact projection" are diagnostics that give up sublinearity in n to locate the loss.

5.1 Precision on held-out users

config	exact SVD	rSVD q=7	rSVD q=2	ℓ² rows + exact proj.	Tang read-out	Tang top-10 of 30 samples [CI]	exact A_k, top-10 of 30 samples	uniform ctrl, top-10 of 30 samples	popularity	random
small	0.614	0.615	0.619	0.533	0.532	0.482 [0.469, 0.496]	0.538	0.486	0.511	0.107
lowrank_k5	0.994	0.994	0.994	0.984	0.980	0.917 [0.910, 0.923]	0.958	0.816	0.643	0.093
lowrank_k10	0.966	0.966	0.947	0.899	0.894	0.736 [0.726, 0.747]	0.859	0.631	0.604	0.093
lowrank_k20	0.840	0.834	0.740	0.583	0.571	0.393 [0.384, 0.403]	0.640	0.356	0.517	0.104
dense_d0.5	0.999	0.999	0.999	0.995	0.993	0.911 [0.904, 0.917]	0.954	0.887	0.559	0.095
sparse_d0.05	0.562	0.552	0.522	0.479	0.482	0.394 [0.384, 0.403]	0.435	0.393	0.603	0.094
powerlaw	0.749	0.748	0.735	0.705	0.697	0.547 [0.537, 0.557]	0.582	0.449	0.219	0.097
illcond	1.000	1.000	1.000	0.997	0.996	0.957 [0.952, 0.963]	0.971	0.958	0.618	0.097
noisy	0.831	0.829	0.693	0.532	0.509	0.391 [0.383, 0.400]	0.702	0.376	0.605	0.093
large	0.717	0.718	0.634	0.548	0.549	0.407 [0.397, 0.417]	0.570	0.387	0.621	0.099

config	Tang sampled − rSVD precision [CI]	recall@10 rSVD	recall@10 Tang sampled	recall@10 popularity	one ℓ² sample of exact A_k: P(relevant)	Tang: first 10 samples, P(relevant)	ℓ² rows + exact proj.: P(relevant)
small	-0.133 [-0.147, -0.118]	0.384	0.301	0.319	0.420	0.380	0.376
lowrank_k5	-0.077 [-0.084, -0.071]	0.124	0.115	0.080	0.599	0.567	0.561
lowrank_k10	-0.229 [-0.239, -0.219]	0.121	0.092	0.076	0.469	0.395	0.387
lowrank_k20	-0.441 [-0.451, -0.429]	0.104	0.049	0.065	0.331	0.212	0.209
dense_d0.5	-0.089 [-0.095, -0.082]	0.200	0.183	0.112	0.514	0.484	0.489
sparse_d0.05	-0.158 [-0.171, -0.144]	0.058	0.041	0.064	0.272	0.249	0.245
powerlaw	-0.201 [-0.212, -0.190]	0.094	0.068	0.027	0.324	0.307	0.307
illcond	-0.042 [-0.048, -0.037]	0.143	0.137	0.088	0.567	0.555	0.563
noisy	-0.437 [-0.449, -0.425]	0.104	0.049	0.076	0.396	0.228	0.226
large	-0.310 [-0.325, -0.297]	0.038	0.021	0.033	0.313	0.235	0.235

Randomized SVD at scikit-learn's default q = 7 matches the exact truncated SVD everywhere (≤ 0.010 apart); q = 2 loses 0.14 on noisy and 0.08–0.10 on large and lowrank_k20, the configurations where the rank-k structure is weakest relative to the noise bulk. Tang's sampled output is below rSVD on every configuration — paired gaps from −0.04 (illcond) to −0.44 (noisy, lowrank_k20), all CIs excluding 0 — and below popularity on five (small, lowrank_k20, sparse_d0.05, noisy, large). On sparse_d0.05 popularity beats every low-rank method, the exact SVD included: with 50 observations per user a rank-10 fold-in has little to work with.

5.2 Where the loss comes from

Reading the table across a row splits Tang's loss into three steps. (a) Sampled subspace: exact SVD → ℓ² rows + exact projection costs 0.003–0.30 (lowrank_k10: 0.966 → 0.899; noisy: 0.831 → 0.532). (b) Sampled inner products at N = 1 000: exact projection → read-out costs ≤ 0.023 everywhere. (c) A list from samples: read-out → top-10 of 30 samples costs 0.04–0.18 (lowrank_k10: 0.894 → 0.736). Step (c) is not specific to dequantisation; it is the output model of Kerenidis–Prakash — a sample from a row, not a ranked list — and it costs as much on the exact answer:

config	exact A_k deterministic top-10	one sample P(relevant)	top-10 of 10 samples	of 30	of 100	of 300	of 1000
small	0.614	0.420	0.329	0.538	0.608	0.614	0.614
lowrank_k5	0.994	0.599	0.546	0.958	0.991	0.994	0.994
lowrank_k10	0.966	0.469	0.447	0.859	0.953	0.965	0.965
lowrank_k20	0.840	0.331	0.319	0.640	0.805	0.838	0.840
dense_d0.5	0.999	0.514	0.486	0.954	0.999	0.999	0.999
sparse_d0.05	0.562	0.272	0.266	0.435	0.539	0.557	0.562
powerlaw	0.749	0.324	0.309	0.582	0.715	0.750	0.749
illcond	1.000	0.567	0.537	0.971	0.999	1.000	1.000
noisy	0.831	0.396	0.371	0.702	0.818	0.830	0.831
large	0.717	0.313	0.293	0.570	0.686	0.717	0.718

A single ℓ² sample of the exact rank-k row is relevant with probability 0.27–0.60, and 100–300 samples are needed before a top-10 list built from them matches the deterministic top-10. Step (b) behaves as the estimator's variance says:

N (samples / user)	‖λ̂ − a_uV̂‖/‖a_uV̂‖ [CI]	row err vs a_uV̂V̂ᵀ	row err vs a_uV_kV_kᵀ	read-out p@10 [CI]	queries / user
25	0.510 [0.479, 0.540]	0.469	0.559	0.723 [0.680, 0.766]	2.5·10^4
100	0.289 [0.271, 0.307]	0.265	0.421	0.808 [0.766, 0.845]	1·10^5
400	0.153 [0.144, 0.162]	0.140	0.360	0.845 [0.815, 0.874]	4·10^5
1600	0.078 [0.074, 0.083]	0.072	0.340	0.859 [0.826, 0.890]	1.6·10^6
6400	0.040 [0.037, 0.042]	0.036	0.335	0.874 [0.846, 0.900]	6.4·10^6
25600	0.019 [0.018, 0.020]	0.017	0.334	0.872 [0.843, 0.899]	2.6·10^7

The coefficient error falls as N^−1/2 (0.51 → 0.019 over a 1 024-fold range of N), but the preference-row error against the exact fold-in levels off at 0.33 from N ≈ 1 600: beyond that the subspace, not the inner products, is the error. At this row sparsity the estimator is also the expensive way to compute λ: N·r = 10⁶ queries per user at N = 1 000, while the exact projection a_uV̂ needs nnz(a_u)·r ≈ 2·10⁵ (mean nnz 202 per held-out row).

5.3 ℓ² sampling against the equal-budget uniform control

config	ℓ²: top-10 of samples [CI]	uniform: top-10 of samples [CI]	ℓ²: exact proj.	uniform: exact proj.	ℓ² excess	uniform excess	ℓ² excess / (σ_k/‖A‖_F)²	uniform excess / (σ_k/‖A‖_F)²
small	0.482 [0.469, 0.496]	0.486 [0.473, 0.499]	0.533	0.539	0.0412	0.0723	1.53	2.69
lowrank_k5	0.917 [0.910, 0.923]	0.816 [0.806, 0.826]	0.984	0.926	0.0067	0.0245	0.43	1.55
lowrank_k10	0.736 [0.726, 0.747]	0.631 [0.620, 0.643]	0.899	0.836	0.0183	0.0283	2.77	4.28
lowrank_k20	0.393 [0.384, 0.403]	0.356 [0.348, 0.365]	0.583	0.543	0.0359	0.0408	11.32	12.86
dense_d0.5	0.911 [0.904, 0.917]	0.887 [0.879, 0.894]	0.995	0.994	0.0104	0.0132	0.85	1.07
sparse_d0.05	0.394 [0.384, 0.403]	0.393 [0.383, 0.403]	0.479	0.486	0.0225	0.0304	4.47	6.03
powerlaw	0.547 [0.537, 0.557]	0.449 [0.438, 0.460]	0.705	0.586	0.0149	0.0788	1.62	8.61
illcond	0.957 [0.952, 0.963]	0.958 [0.953, 0.964]	0.997	0.999	0.0083	0.0122	250.71	370.59
noisy	0.391 [0.383, 0.400]	0.376 [0.367, 0.386]	0.532	0.532	0.0165	0.0164	6.46	6.41
large	0.407 [0.397, 0.417]	0.387 [0.378, 0.397]	0.548	0.539	0.0195	0.0227	6.50	7.56

At equal r, c, N and N_rec, ℓ² sampling beats uniform sampling with non-overlapping CIs on five configurations (lowrank_k5/k10/k20, dense_d0.5, powerlaw; +0.02 to +0.11), edges it on two (noisy, large) and ties on three (small, sparse_d0.05, illcond). The heavy-row family is the best case for ℓ² against uniform, not the worst: uniform rows miss the heavy users that carry the spectrum (uniform excess 5× larger). The last two columns are the excess in units of the k-th direction's share of the Frobenius norm, (σ_k/‖A‖_F)²: precision collapses where this ratio is large (lowrank_k20 11, noisy 6.5, large 6.5, sparse 4.5) and holds where it is below 1 (lowrank_k5 0.4, dense_d0.5 0.8) — with one exception, illcond, where the excess is 250× the k-th direction's energy and precision stays at 0.96, because the weak tastes the sampler cannot resolve do not change anyone's top 10.

5.4 Error against the number of sampled rows

config	arm	r = 20	r = 50	r = 100	r = 200	r = 500	r = 1000	r = 2000	r = 4000	reference
lowrank_k10	Tang read-out	0.405	0.498	0.593	0.635	0.782	0.871	0.945	0.946	rSVD 0.973
	Tang top-10 of 30 samples	0.329	0.391	0.433	0.466	0.607	0.702	0.822	0.822	exact A_k sampled 0.848
	uniform top-10 of 30 samples	0.318	0.377	0.375	0.399	0.508	0.626	0.707	0.807
sparse_d0.05	Tang read-out	0.283	0.317	0.357	0.443	0.448	0.469	0.491	0.496	rSVD 0.569
	Tang top-10 of 30 samples	0.262	0.296	0.305	0.358	0.347	0.390	0.396	0.399	exact A_k sampled 0.449
	uniform top-10 of 30 samples	0.241	0.305	0.306	0.323	0.386	0.357	0.376	0.371
powerlaw	Tang read-out	0.425	0.382	0.464	0.534	0.673	0.739	0.724	0.740	rSVD 0.752
	Tang top-10 of 30 samples	0.357	0.352	0.373	0.445	0.534	0.559	0.569	0.570	exact A_k sampled 0.542
	uniform top-10 of 30 samples	0.179	0.357	0.301	0.381	0.381	0.428	0.536	0.537
illcond	Tang read-out	0.801	0.968	0.982	0.915	0.987	0.996	0.994	0.996	rSVD 0.999
	Tang top-10 of 30 samples	0.219	0.761	0.735	0.766	0.849	0.927	0.940	0.962	exact A_k sampled 0.975
	uniform top-10 of 30 samples	0.545	0.853	0.791	0.906	0.927	0.951	0.945	0.955
noisy	Tang read-out	0.204	0.271	0.347	0.411	0.449	0.494	0.531	0.612	rSVD 0.857
	Tang top-10 of 30 samples	0.167	0.219	0.245	0.328	0.329	0.377	0.402	0.492	exact A_k sampled 0.698
	uniform top-10 of 30 samples	0.141	0.190	0.266	0.284	0.329	0.380	0.415	0.439

config	arm	r = 20	r = 50	r = 100	r = 200	r = 500	r = 1000	r = 2000	r = 4000	rSVD q=7
	DKM bound 2√(k/r)	1.414	0.894	0.632	0.447	0.283	0.200	0.141	0.100
lowrank_k10	Tang (ℓ²)	0.1245	0.0757	0.0648	0.0560	0.0332	0.0170	0.0082	0.0043	0.00000
	uniform	0.2658	0.0871	0.0726	0.0650	0.0479	0.0312	0.0157	0.0074
sparse_d0.05	Tang (ℓ²)	0.0649	0.0603	0.0527	0.0424	0.0280	0.0221	0.0112	0.0069	0.00015
	uniform	0.6073	0.0654	0.0599	0.0532	0.0422	0.0329	0.0200	0.0168
powerlaw	Tang (ℓ²)	0.1401	0.1132	0.0947	0.0650	0.0284	0.0176	0.0062	0.0039	0.00000
	uniform	65.4238	0.3575	0.1862	0.1474	0.1132	0.0616	0.0369	0.0300
illcond	Tang (ℓ²)	1.1876	0.1604	0.0813	0.1158	0.0237	0.0093	0.0052	0.0016	-0.00000
	uniform	11.8257	0.5063	0.4643	0.2491	0.1055	0.0255	0.0106	0.0026
noisy	Tang (ℓ²)	0.0417	0.0374	0.0308	0.0245	0.0194	0.0163	0.0146	0.0085	0.00017
	uniform	0.0472	0.0369	0.0315	0.0259	0.0196	0.0166	0.0128	0.0103

config	‖A−A_k‖_F/‖A‖_F	Tang excess [CI]	uniform excess [CI]	rSVD q=7 excess	rSVD q=2 excess	DKM 2√(k/r)	‖V̂ᵀV̂ − I‖₂	row err vs a_uV_kV_kᵀ	row err vs a_uV̂V̂ᵀ	mean abs entry err / row RMS
small	0.844	0.0412 [0.0348, 0.0483]	0.0723 [0.0673, 0.0771]	0.00001	0.00122	0.316	0.408	0.485	0.054	0.259
lowrank_k5	0.886	0.0067 [0.0058, 0.0076]	0.0245 [0.0192, 0.0308]	0.00000	0.00007	0.141	0.178	0.208	0.065	0.122
lowrank_k10	0.883	0.0183 [0.0169, 0.0196]	0.0283 [0.0270, 0.0294]	0.00001	0.00177	0.200	0.365	0.362	0.090	0.220
lowrank_k20	0.875	0.0359 [0.0343, 0.0378]	0.0408 [0.0389, 0.0430]	0.00026	0.00495	0.283	0.584	0.473	0.108	0.296
dense_d0.5	0.701	0.0104 [0.0087, 0.0128]	0.0132 [0.0114, 0.0151]	0.00000	0.00001	0.200	0.199	0.178	0.104	0.125
sparse_d0.05	0.951	0.0225 [0.0194, 0.0259]	0.0304 [0.0283, 0.0324]	0.00016	0.00321	0.200	0.508	0.553	0.067	0.251
powerlaw	0.799	0.0149 [0.0130, 0.0167]	0.0788 [0.0555, 0.1174]	0.00000	0.00103	0.200	0.257	0.281	0.110	0.148
illcond	0.016	0.0083 [0.0071, 0.0102]	0.0122 [0.0092, 0.0153]	0.00000	0.00000	0.200	0.529	0.167	0.104	0.122
noisy	0.970	0.0165 [0.0159, 0.0170]	0.0164 [0.0158, 0.0169]	0.00019	0.00406	0.200	0.616	0.630	0.157	0.436
large	0.964	0.0195 [0.0184, 0.0211]	0.0227 [0.0204, 0.0254]	0.00010	0.00223	0.200	0.608	0.508	0.065	0.227

The ℓ² excess falls as r^−0.3 (noisy) to r^−1 (illcond) and stays 4–62× below the DKM bound 2√(k/r) for every r ≥ 50 and below it at r = 20 (the bound is for the row stage with an exact SVD of S; ModFKV's V̂ is not orthonormal, which the uniform control shows can matter: its excess reaches 11.8 on illcond and 65 on powerlaw at r = 20). Precision converges far more slowly than the Frobenius error suggests: within 0.02 of rSVD by read-out the sweep reaches only powerlaw (r = 1 000) and illcond (r = 100); lowrank_k10 stops at 0.946 against 0.973 at r = 4 000, sparse_d0.05 at 0.496 against 0.569, noisy at 0.612 against 0.857. The sampled output reaches the exact-A_k sampled ceiling within 0.02 on powerlaw (r = 500) and illcond (r = 4 000) only.

5.5 What each stage costs

config	distinct rows	V̂ build [ms]	λ̂ per user [ms]	sampling per user [ms]	trials / accepted	users short of 30	queries V̂	queries λ̂ / user	queries sampling / user	exact SVD [ms]	rSVD q=7 [ms]	rSVD q=2 [ms]	SQ trees [ms]	SQ [MiB]
small	162	4.2	0.38	1.0	14.7	0.0	4·10^4	2·10^5	1.7·10^5	8	4	1	0.2	0.7
lowrank_k5	898	44.4	1.35	3.8	20.5	0.0	1·10^6	1·10^6	1·10^6	66	147	55	7.3	27.6
lowrank_k10	899	80.1	1.45	6.0	33.7	0.0	1·10^6	1·10^6	1.5·10^6	112	178	54	8.6	27.6
lowrank_k20	904	109.6	1.47	6.4	37.5	0.0	1·10^6	1·10^6	1.6·10^6	238	201	74	12.6	27.6
dense_d0.5	898	94.3	1.79	8.8	20.1	0.0	1·10^6	1·10^6	1.3·10^6	203	328	114	23.8	92.8
sparse_d0.05	898	114.9	1.57	13.2	67.1	0.0	1·10^6	1·10^6	2.8·10^6	47	48	18	1.9	7.0
powerlaw	724	59.9	1.18	6.8	56.2	0.0	1·10^6	1·10^6	2.1·10^6	27	42	15	1.3	6.3
illcond	762	42.2	1.30	29.4	246.9	5.3	1·10^6	1·10^6	9.2·10^6	232	564	229	62.2	185.4
noisy	907	104.5	1.14	8.7	68.7	0.0	1·10^6	1·10^6	3·10^6	139	118	44	5.9	27.6
large	973	86.8	1.09	9.9	57.7	0.0	1·10^6	1·10^6	2.4·10^6	299	286	104	16.6	55.5

Logical cost per user at r = 1 000 is 10⁶ queries for λ̂ and 1.0–9.2·10⁶ for the 30 samples (20–250 rejection trials per accepted sample, each reading the r′ ≈ 720–970 distinct sampled rows); the subspace costs r·c = 10⁶ queries plus a 1 000 × 1 000 SVD. None of these counts depends on m. On illcond 5.3 of the 200 users per run hit the 50 000-trial cap before collecting 30 samples (acceptance ≈ 1/250); their shorter lists count as misses. Main-grid wall-clock is a single measurement per instance on a loaded machine; §5.6 is the controlled measurement.

5.6 Wall-clock against the number of users, and the crossover

m_train	nnz	SQ trees [ms]	CSR + trees [ms]	SQ [MiB]	rSVD q=7 [ms]	rSVD q=2 [ms]	exact SVD [ms]	Tang V̂ r=1000 [ms]	Tang per user r=1000 [ms]	Tang V̂ r=4000 [ms]	Tang per user r=4000 [ms]	p@10 rSVD	p@10 rSVD q=2	p@10 Tang read-out r=1000	p@10 Tang read-out r=4000
1 000	50 095	0.3	0.4	2	10	4	11	55	3.7	1156	7.0	0.512	0.489	0.447	0.482
2 000	99 703	0.6	0.8	3	18	7	17	59	4.2	1326	11.3	0.499	0.508	0.460	0.500
5 000	250 515	1.4	1.8	7	45	17	46	73	5.6	1491	15.8	0.506	0.517	0.476	0.505
10 000	500 233	2.9	3.7	14	77	29	90	64	3.5	1177	18.6	0.536	0.484	0.460	0.494
20 000	998 190	5.9	7.5	28	147	56	122	71	4.4	1174	20.4	0.600	0.542	0.509	0.568
50 000	2 500 538	23.4	23.2	94	349	131	427	70	4.6	1267	20.3	0.598	0.562	0.480	0.590
100 000	5 001 125	33.6	41.1	188	780	287	—	69	4.9	1033	17.1	0.620	0.553	0.513	0.608
200 000	9 996 811	65.8	80.0	376	1565	594	—	68	5.2	1408	18.9	0.612	0.539	0.510	0.557

r	rSVD	Tang V̂ [s]	Tang per user [ms]	Tang one-user latency [s]	crossover users, SQ free	… trees charged	… CSR + trees charged	SQ at crossover [MiB]	rSVD / tree cost per nnz	Tang per user / rSVD per user	break-even users at largest m	rSVD at 10⁶ users, extrapolated [s]	break-even users at 10⁶ users
1000	q=7	0.069	4.5	0.074	9.2·10^3 (measured)	9.8·10^3	1·10^4	17	24.3	571	335	7.9	1746
1000	q=2	0.069	4.5	0.074	2.5·10^4 (measured)	2.9·10^4	2.9·10^4	47	9.2	1507	117	3.0	651
4000	q=7	1.222	17.9	1.241	1.5·10^5 (measured)	1.6·10^5	1.6·10^5	283	24.3	2286	19	7.9	372
4000	q=2	1.222	17.9	1.241	4.2·10^5 (extrapolated)	4.7·10^5	4.8·10^5	786	9.2	6027	none (rSVD < V̂)	3.0	98

Once the trees exist Tang's cost does not grow with m: from 10³ to 2·10⁵ training users the subspace stays at 0.055–0.073 s (r = 1 000) and 1.0–1.5 s (r = 4 000) and the per-user cost at 3.5–5.6 ms and 7–20 ms, while the SQ build, randomized SVD and the exact SVD grow linearly in nnz. Counting from the measured points, a full randomized SVD (q = 7) costs more than Tang's one-user latency (subspace plus one user's λ̂ and 10 samples) from 9.2·10³ training users at r = 1 000 and from 1.5·10⁵ at r = 4 000; both crossings lie inside the measured range, the second at an SQ footprint of ≈ 280 MiB. Charging the tree build moves them only to 9.8·10³ and 1.6·10⁵, because the trees cost 24× less per nonzero than rSVD; against rSVD at q = 2 the crossings are 2.5·10⁴ users (measured) and 4.2·10⁵ (extrapolated). The accuracies behind those latencies are not equal: Tang's read-out is 0.00–0.06 below rSVD at r = 4 000 and 0.03–0.12 below at r = 1 000 on these instances, and its sampled output is lower still (§5.2). Beyond the crossing Tang stays ahead only while it serves few users: per user served it costs 571× (r = 1 000) and 2 286× (r = 4 000) rSVD's amortised per-user cost at 2·10⁵ users, so a single rSVD is the cheaper way to serve more than 335 or 19 users at that size, and more than 1 746 or 372 users at 10⁶ users (rSVD time extrapolated).

5.7 The dequantised constants at their stated size

config	‖A‖_F/σ_k	r_DKM = 16k(‖A‖_F/σ_k)⁴	W at r_DKM [GiB]	fits 16 GiB	V̂ build extrapolated [s]	r used
small	6.1	1.1·10^5	95	no	4.5·10^2	200
lowrank_k5	8.0	3.2·10^5	7.8·10^2	no	3.2·10^3	1000
lowrank_k10	12.3	3.7·10^6	1·10^5	no	2.8·10^5	1000
lowrank_k20	17.7	3.2·10^7	7.5·10^6	no	1.5·10^7	1000
dense_d0.5	9.0	1.1·10^6	8.3·10^3	no	2.8·10^4	1000
sparse_d0.05	14.1	6.3·10^6	3·10^5	no	7.7·10^5	1000
powerlaw	10.5	1.9·10^6	2.7·10^4	no	8.4·10^4	1000
illcond	174.1	1.5·10^11	1.7·10^14	no	9.6·10^13	1000
noisy	19.8	2.4·10^7	4.5·10^6	no	9.4·10^6	1000
large	18.2	1.8·10^7	2.4·10^6	no	5.2·10^6	1000

The FKV-type sufficient size r_DKM = 16k(‖A‖_F/σ_k)⁴ is 1.1·10⁵ rows on the smallest instance and 1.5·10¹¹ on illcond; the r × r matrix W alone would need 95 GiB to 1.7·10¹⁴ GiB, and the measured subspace time (t ∝ r^1.85 over r = 1 000–4 000) extrapolates to 4.5·10² s – 10¹⁴ s. Tang's own theorem has the same shape with higher exponents. The r actually used in the main grid (200–1 000) is 320 to 1.5·10⁸ times below r_DKM and gives everything in §5.1–5.4.

6. Discussion & limitations

1. Randomized SVD is the answer at these sizes. It reproduces the exact truncated SVD's precision on every configuration (≤ 0.010 apart), its Frobenius excess is ≤ 3·10⁻⁴, and it factorises 2·10⁵ users × 1 000 items (10⁷ nonzeros) in 1.6 s, or 0.6 s at q = 2. ARPACK's exact top-k costs about the same up to 5·10⁴ users (0.43 s against 0.35 s). Nothing in the dequantised pipeline is more accurate than either on any instance.
2. Tang's error is the additive FKV error, and it bites exactly when ‖A‖_F/σ_k is large relative to what the rank-k structure contributes. Rank 20, a noise bulk or 5 % density push the excess to 4–11× σ_k²/‖A‖_F², and the top-10 list falls 0.16–0.44 below rSVD. The guarantee's poly(‖A‖_F/σ_k) is therefore not a technicality: it is the regime map. The ill-conditioned family shows the converse — a Frobenius guarantee 250× too weak for the k-th direction can still give the right top-10 — so the Frobenius error is a proxy for the ranking objective, and a loose one in both directions.
3. The sampling output is lossy on its own. Kerenidis–Prakash and Tang both return a sample from a preference row. On the exact answer, one sample is relevant with probability 0.27–0.60 and a top-10 list needs 100–300 samples; at 30 samples Tang's list loses 0.04–0.18 against its own read-out. Any quantum version inherits this step.
4. The crossover is a single-query effect, and it comes from FKV, not from the sampled inner products. Once the trees exist, Tang's cost is independent of m and the single-user latency undercuts a full randomized SVD from 9.2·10³ (r = 1 000) or 1.5·10⁵ (r = 4 000) users; charging the tree build hardly moves the point, because building the trees is one pass over the nonzeros, 24× cheaper per nonzero than rSVD at q = 7 and 9× at q = 2. But rSVD serves every user at once, and per user served Tang costs 571–2 286× rSVD's amortised cost (1 507–6 027× against q = 2). The part of Tang's pipeline that buys the m-independence is length-squared row sampling (FKV 2004); the inner-product estimator is less accurate than, and five times as many queries as, the exact projection of a user row with ≈ 200 nonzeros.
5. Implication for the quantum recommendation claim. The quantum algorithm assumes the same tree (in qRAM), returns the same kind of sample, and can only improve on Tang in the poly(k, 1/ε, ‖A‖_F/σ_k) factors. At the sizes measured here those factors amount to 0.06–1.5 s per subspace and 1–31 ms per user on a laptop, against an amortised randomized-SVD cost of ≈ 8 µs per user at 2·10⁵ users (1.565 s / 2·10⁵), and the classical preprocessing that both assume costs a twenty-fourth of one rSVD per nonzero. An exponential separation was never available at these sizes once rSVD is the baseline; the polynomial one is measured in milliseconds per user and is reversed as soon as 19–335 users need recommendations at 2·10⁵ users (372–1 746 at 10⁶).
6. Limitations. Synthetic non-negative low-rank data with one taste model (real rating matrices have item and user biases and heavier tails); one implementation (vectorised NumPy; a compiled implementation would lower every arm's constants, Tang's subspace step is already a LAPACK SVD); the r × n dense cache of sampled rows (fine at n ≤ 2 000, not sublinear in n); one rule for turning samples into a list (top-10 of 30 by estimated value) and one relevance definition (top 10 % of true preferences among unobserved items); main-grid timings are single measurements on a machine loaded by concurrent experiments; the q = 2 crossover at r = 4 000 is extrapolated beyond the largest measured m; no quantum resource model (qRAM access cost, phase-estimation precision) — the quantum algorithm is discussed, not simulated.

Checklist (docs/04 §5). (1) strongest baseline: exact truncated SVD (the Eckart–Young optimum), rSVD at two iteration counts, popularity; (2) proxy audit: Frobenius excess reported next to precision, and the two disagree in both directions (illcond, sparse); (6) the arm is classical by construction — the claim is about the dequantised constants, not about quantum hardware; (7) three instance seeds × two algorithm seeds, bootstrap CIs, paired gaps, and the uniform-sampling control that removes the ℓ² structure; (8) equal budget: the control spends the same r, c, N, N_rec, and random items are seeded per instance; (10) the exact solver's time is measured up to 5·10⁴ users (ARPACK) and rSVD's up to 2·10⁵. Items 3, 4, 5 and 9 do not apply (no encoding, no repair, no inherited input, no lossy pre-processing, no structural novelty claim).

7. Reproduce

cd experiments/56-dequantized-recommendation-sampling
uv sync
uv run pytest -q                 # 12 tests (SQ trees, estimators, FKV/Tang bounds, metrics, smoke run), ≈ 8 s
uv run python run.py --quick     # 4 configurations at 1 200 × 300, one seed, ≈ 7 s
uv run python run.py             # everything in §4–§5, wall-clock in §4

Outputs: results/results.json (every number in §5; per-instance records under instances), results/run.log, results/precision_by_family.png, results/error_vs_r.png, results/ip_samples.png, results/walltime_vs_users.png. Code: src/dequant_rec/sq.py (SQ trees and counters), tang.py (ModFKV, inner products, rejection sampler, uniform control), baselines.py, metrics.py, data.py, experiment.py. Classical numerics only: --backend is accepted and recorded for the contract, and no circuit is built.

References

• Kerenidis, I., Prakash, A. "Quantum recommendation systems", ITCS 2017; arXiv:1603.08675.
• Tang, E. "A quantum-inspired classical algorithm for recommendation systems", STOC 2019; arXiv:1807.04271.
• Frieze, A., Kannan, R., Vempala, S. "Fast Monte-Carlo algorithms for finding low-rank approximations", J. ACM 51(6), 2004.
• Drineas, P., Kannan, R., Mahoney, M. W. "Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix", SIAM J. Comput. 36(1), 2006.
• Chia, N.-H., Gilyén, A., Li, T., Lin, H.-H., Tang, E., Wang, C. "Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning", STOC 2020; arXiv:1910.06151.
• Gilyén, A., Lloyd, S., Tang, E. "Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension"; arXiv:1811.04909.
• Arrazola, J. M., Delgado, A., Bardhan, B. R., Lloyd, S. "Quantum-inspired algorithms in practice", Quantum 4, 307 (2020); arXiv:1905.10415.
• Chepurko, N., Clarkson, K. L., Horesh, L., Lin, H., Woodruff, D. P. "Quantum-inspired algorithms from randomized numerical linear algebra", ICML 2022.
• Halko, N., Martinsson, P.-G., Tropp, J. A. "Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions", SIAM Review 53(2), 2011; arXiv:0909.4061.
• Achlioptas, D., McSherry, F. "Fast computation of low-rank matrix approximations", J. ACM 54(2), 2007 (the subsampled-matrix model Kerenidis–Prakash build on).
• Lehoucq, R. B., Sorensen, D. C., Yang, C. ARPACK Users' Guide, SIAM 1998 (the exact truncated SVD via scipy.sparse.linalg.svds).
• Experiments 13 and 31 of this repository (quantum-inspired low-rank compression against SVD; recommendation-flavoured selection against greedy and popularity).