Dequantization: what survived and what didn't
In 2016 Iordanis Kerenidis and Anupam Prakash published a quantum algorithm for recommendation systems, the kind that suggests films and products, that ran exponentially faster than any known classical method. It was widely cited as one of the clearest exponential quantum speedups for a practical machine-learning task. Two years later Ewin Tang, an 18-year-old undergraduate at the University of Texas working with Scott Aaronson, found a classical algorithm that matched it up to polynomial factors. The exponential speedup was gone. The lesson was not that quantum machine learning is hopeless, but that the classical competitor must be given the same assumptions.
On the plate: approximating a large matrix from a handful of its rows, sampled by their size.
The hidden assumption
Quantum linear-algebra algorithms need the data loaded so that you can prepare states whose amplitudes are proportional to the entries, typically through a data structure that also stores partial sums of squared entries. Tang’s insight: give a classical computer the same data structure, and it can sample an index with probability proportional to the square of its entry, and query any entry. This sample-and-query access is the classical analogue of quantum state preparation, and it is surprisingly powerful. Established
Length-squared sampling
Alan Frieze, Ravi Kannan and Santosh Vempala showed in 1998 that if a matrix is close to low rank, sampling rows with probability proportional to their squared length, then working only with those rows, gives a good low-rank approximation. Sample 3 rows of a 40 × 40 matrix that is rank 3 plus noise, and . The error of projecting onto the sampled rows falls quickly toward the best possible rank-3 error, computed here exactly by SVD, without ever touching most of the matrix. Recommendation systems rest on exactly such low-rank structure.
What fell, and what survived
After Tang, Nai-Hui Chia and colleagues built a general framework in 2020: any quantum algorithm that applies a smooth function to the singular values of a low-rank, sample-accessible matrix (Chapter 119) can be matched classically with polynomial overhead. Proposed exponential speedups for recommendation, principal component analysis, low-rank regression and supervised clustering were dequantized. Sevag Gharibian and François Le Gall showed in 2022 that some quantum algorithms for estimating properties of sparse Hamiltonians can also be dequantized in certain regimes, but not all.
What survives: problems where the matrix is sparse and high-rank, given implicitly by a formula rather than as stored data; and Hamiltonian simulation, where the input is a physical system, not a dataset. Those are where to look for exponential advantage. Established for the dequantized results; Debated where the boundary finally lies.
What you now have
The Kerenidis–Prakash algorithm and Tang’s dequantization, sample-and-query access, length-squared sampling for low-rank approximation, the general dequantization framework, and which kinds of speedup survive.
· · ·
Three questions to carry with you.
And one to work out. A row has squared length 4; the whole matrix has squared Frobenius norm 100. With what probability is that row sampled?
Sources: I. Kerenidis and A. Prakash, Proc. ITCS 2017, 49. E. Tang, Proc. 51st ACM STOC, 217 (2019). A. Frieze, R. Kannan and S. Vempala, J. ACM 51, 1025 (2004) (FOCS 1998). N.-H. Chia et al., Proc. 52nd ACM STOC, 387 (2020). S. Gharibian and F. Le Gall, Proc. 54th ACM STOC (2022). Checked by code: for a 40 × 40 rank-3 + noise matrix, mean projection error falls from 0.69 (1 row) to 0.30 (3 rows) to 0.16 (8 rows), against a best rank-3 error of 0.149.