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.

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

References in corpus (52)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum random access memory
• Quantum Computational Supremacy
• Quantum Networks for Elementary Arithmetic Operations
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• Differentially Private Empirical Risk Minimization
• A Quantum Algorithm for Finding the Minimum
• Architectures for a quantum random access memory
• Prediction by linear regression on a quantum computer
• A quantum-inspired classical algorithm for recommendation systems
• Training of Quantum Circuits on a Hybrid Quantum Computer
• Quantum gradient descent for linear systems and least squares
• Quantum noise protects quantum classifiers against adversaries
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Quantum Algorithm for Linear Regression
• Quantum Approximate Counting, Simplified
• q-means: A quantum algorithm for unsupervised machine learning
• Quantum Perceptron Models
• Experimental Realization of Optimal Noise Estimation for a General Pauli Channel
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Optimizing Quantum Circuits for Arithmetic
• An Equivalence between the Lasso and Support Vector Machines
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
• 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
• Protocol for implementing quantum nonparametric learning with trapped ions
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• 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