Quantum Differentially Private Sparse Regression Learning

Abstract

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 $\Omega (N+d)$ and $\Omega (\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.

Final Version. Accepted in IEEE Transactions on Information Theory on 19 March, 2022

References in corpus (13)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Quantum Data Fitting
• Architectures for a quantum random access memory
• Quantum noise protects quantum classifiers against adversaries
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
• Quantum statistical query learning
• Private learning implies quantum stability
• Robust quantum minimum finding with an application to hypothesis selection
• Quantum Privacy-Preserving Perceptron

Cited by in corpus (7)

• Towards understanding the power of quantum kernels in the NISQ era
• Quantum Machine Learning for Finance
• Transition Role of Entangled Data in Quantum Machine Learning
• Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
• Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing
• Mathematical comparison of classical and quantum mechanisms in optimization under local differential privacy
• Accelerating variational quantum algorithms with multiple quantum processors