Quantum Differentially Private Sparse Regression Learning

Du, Y; Hsieh, M-H; Liu, T; You, S; Tao, D

Quantum Differentially Private Sparse Regression Learning

Du, Y Hsieh, M-H Liu, T You, S Tao, D

Permalink

Publication Type:: Journal Article
Citation:: 2020
Issue Date:: 2020-07-23

Closed Access

	Filename	Description	Size
	2007.11921v2.pdf		1.33 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Du, Y
dc.contributor.author	Hsieh, M-H
dc.contributor.author	Liu, T
dc.contributor.author	You, S
dc.contributor.author	Tao, D
dc.date.accessioned	2023-03-13T23:05:08Z
dc.date.available	2023-03-13T23:05:08Z
dc.date.issued	2020-07-23
dc.identifier.citation	2020
dc.identifier.uri	http://hdl.handle.net/10453/167219
dc.description.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.
dc.language	en
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Quantum Differentially Private Sparse Regression Learning
dc.type	Journal Article
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access	*
dc.date.updated	2023-03-13T23:05:05Z

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/167219