量子推荐算法自带隐私保护，无需额外加噪即可实现差分隐私。
Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms
- 利用测量和ℓ₂采样中的固有随机性作为隐私保护机制。
- 在典型场景下，隐私参数ε≈1/√n，δ≈1/min²{m,n}。
- 适用于关注隐私的推荐系统研发者，尤其对量子启发类算法感兴趣者。
我们研究了Kerenidis--Prakash量子推荐算法及其量子启发的古典对应算法的差分隐私（DP）性质。在偏好矩阵满足低秩与非相干性假设的前提下，证明算法中已有的测量/ℓ₂采样步骤所引入的随机性可自然充当隐私保护机制，无需通过接口注入额外的DP噪声。具体地，对于具有m个用户、n个物品及秩参数k的系统，我们得到ε=O(√(k/n))，δ=O(k²/min²{m,n})；在典型情形k=polylog(m,n)下，简化为ε=~O(1/√n)，δ=~O(1/min²{m,n})。分析中提出一种针对截断SVD在单条目更新下的扰动技术，能有效追踪低秩重构的变化，避免不稳定的奇异向量比较。最后，我们在真实评分数据集上验证了该尺度，并与经典DP推荐基线进行对比。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。