Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910033250353152 |
|---|---|
| author | Li, Chenjian Ying, Mingsheng Guan, Ji |
| author_facet | Li, Chenjian Ying, Mingsheng Guan, Ji |
| contents | 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 $(\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(\sqrt{k/n})$ and $δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)$; in the typical regime $k=\mathrm{polylog}(m,n)$ this simplifies to $\varepsilon=\tilde{\mathcal O}(1/\sqrt n)$ and $δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04758 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms Li, Chenjian Ying, Mingsheng Guan, Ji Quantum Physics Cryptography and Security Emerging Technologies Machine Learning 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 $(\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(\sqrt{k/n})$ and $δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)$; in the typical regime $k=\mathrm{polylog}(m,n)$ this simplifies to $\varepsilon=\tilde{\mathcal O}(1/\sqrt n)$ and $δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)$. 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. |
| title | Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms |
| topic | Quantum Physics Cryptography and Security Emerging Technologies Machine Learning |
| url | https://arxiv.org/abs/2502.04758 |