论文标题
量子差异私人稀疏回归学习
Quantum Differentially Private Sparse Regression Learning
论文作者
论文摘要
各种高级量子算法的资格是否不能保证隐私。为了填补这一知识差距，在这里，我们设计了一个有效的量子差异私有（QDP）套索估计器来解决稀疏回归任务。具体而言，给定$ n $ $ d $ d $二维数据点带有$ n \ ll d $，我们首先证明了最佳的经典和量子非私有性套件需要$ω（n+d）$和$ω（\ sqrt {n}+\ \ \ \ \ \ \ \ \ sqrt {d}）$ Runtime。接下来，我们证明QDP套索的运行时成本为\ textIt {dimension ipperdent}，即$ o（n^{5/2}）$，这意味着QDP套索可以比最佳的古典和量子非proventum nontrivate lasso更快。最后，我们表明，QDP Lasso获得了近乎最佳的实用程序限制的$ \ tilde {o}（n^{ - 2/3}）$，并提供隐私保证，并讨论了在具有优势的近期量子芯片上实现它的机会。
The eligibility of various advanced quantum algorithms will be questioned if they can not guarantee privacy. To fill this knowledge gap, here we devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Concretely, given $N$ $d$-dimensional data points with $N\ll d$, we first prove that the optimal classical and quantum non-private Lasso requires $Ω(N+d)$ and $Ω(\sqrt{N}+\sqrt{d})$ runtime, respectively. We next prove that the runtime cost of QDP Lasso is \textit{dimension independent}, i.e., $O(N^{5/2})$, which implies that the QDP Lasso can be faster than both the optimal classical and quantum non-private Lasso. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $\tilde{O}(N^{-2/3})$ with privacy guarantees and discuss the chance to realize it on near-term quantum chips with advantages.
