Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms

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/ℓ2-sampling steps can act as a privacy-curating mechanism, yielding (varepsilon,δ)-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 varepsilon=mathcal O(√k/n) and δ= mathcal Obig(k2/min2m,nbig); in the typical regime k=polylog(m,n) this simplifies to varepsilon=tildemathcal O(1/√ n) and δ=tildemathcal Obig(1/min2m,nbig). 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.