Quantum Differentially Private Sparse Regression Learning

DOI10.1109/TIT.2022.3164726MaRDI QIDQ5096987zbMATH OpenOpenAlexFDO

Authors Yuxuan du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, Dacheng Tao

Publication date 19 August 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11921

zbMATH Keywords

efficient quantum differentially private (QDP) Lasso estimatorquantum non-private Lassosparse regression tasks

Mathematics Subject Classification ID

Privacy of data (68P27) Quantum computation (81P68)

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 $Nlld$, we first prove that the optimal classical and quantum non-private Lasso requires $Omega(N+d)$ and $Omega(sqrtN+sqrtd)$ runtime, respectively. We next prove that the runtime cost of QDP Lasso is extit{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 $ildeO(N^{-2/3})$ with privacy guarantees and discuss the chance to realize it on near-term quantum chips with advantages.

Cited in

(3)

• Encrypted quantum state tomography with phase estimation for quantum Internet
• A survey of quantum machine learning: understanding the current landscape and future opportunities
• Mathematical comparison of classical and quantum mechanisms in optimization under local differential privacy

This page was built for publication: Quantum Differentially Private Sparse Regression Learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096987)