# Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms

arXiv: https://arxiv.org/abs/2502.04758 · HTML: https://mlsanity.com/paper/2502.04758/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 41 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 5 of 5)

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Quantum Differential Privacy: An Information Theory Perspective](https://mlsanity.com/paper/2202.10717/) (2022)
- [Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems](https://mlsanity.com/paper/2306.13054/) (2023)

## Abstract (arXiv)

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.