Quantum Differentially Private Sparse Regression Learning

• URL: http://arxiv.org/abs/2007.11921v2
• Date: Mon, 30 May 2022 06:38:57 GMT
• Title: Quantum Differentially Private Sparse Regression Learning
• Authors: Yuxuan Du and Min-Hsiu Hsieh and Tongliang Liu and Shan You and Dacheng Tao
• Abstract summary: We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
• Score: 132.1981461292324
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
  We present a novel quantum high-dimensional linear regression algorithm based on the classical LARS (Least Angle Regression) pathwise algorithm. Our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. We prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm is robust to errors.
  arXiv  Detail & Related papers  (2023-12-21T18:57:54Z)
• A Unifying Quantum Speed Limit For Time-Independent Hamiltonian Evolution [0.3314882635954752]
  We show that the Mandelstam-Tamm bound can be obtained by optimizing the Lee-Chau bound over a certain parameter. We find that if the dimension of the underlying Hilbert space is $lesssim 2000$, our unifying bound optimized over $p$ can be computed accurately in a few minutes.
  arXiv  Detail & Related papers  (2023-10-13T01:52:04Z)
• QAOA with $N\cdot p\geq 200$ [2.926192989090622]
  We demonstrate the execution of a hybrid quantum/classical optimization algorithm with high $Ncdot p$. This is the highest $Ncdot p$ demonstrated on hardware to date.
  arXiv  Detail & Related papers  (2023-03-03T16:32:49Z)
• Lattice-Based Quantum Advantage from Rotated Measurements [2.0249250133493195]
  We show a new technique that uses the entire range of qubit measurements from the $XY$-plane. We construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.
  arXiv  Detail & Related papers  (2022-10-18T20:18:15Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
  We study the problem of finding $K$ collision pairs in a random function $f : [N] rightarrow [N]$ by using a quantum computer. We prove that the number of queries to the function must increase significantly when the size of the available memory is limited.
  arXiv  Detail & Related papers  (2020-02-20T18:48:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.