Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms

Abstract

We study the differential privacy (DP) of the quantum recommendation algorithm of Kerenidis--Prakash and its quantum-inspired classical counterpart. Under standard low-rank and incoherence assumptions on the preference matrix, we show that the randomness already present in the algorithms' measurement/${\ell }_2$-sampling steps can act as a privacy-curating mechanism, yielding $(\epsilon ,\hat{I}´)$-DP without injecting additional DP noise through the interface. Concretely, for a system with $m$ users and $n$ items and rank parameter $k$, we prove $\epsilon =\mathcal{O}(\sqrt{k/n})$ and $\hat{I}´=\mathcal{O}(k^2/{\min }^2\{m,n\})$; in the typical regime $k=\mathrm{polylog}(m,n)$ this simplifies to $\epsilon =\tilde{\mathcal{O}}(1/\sqrt{n})$ and $\hat{I}´=\tilde{\mathcal{O}}(1/{\min }^2\{m,n\})$. Our analysis introduces a perturbation technique for truncated SVD under a single-entry update, which tracks the induced change in the low-rank reconstruction while avoiding unstable singular-vector comparisons. Finally, we validate the scaling on real-world rating datasets and compare against classical DP recommender baselines.

18 pages, 3 figures in total(including appendix)