Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2502.04758

Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms

Chenjian Li, Mingsheng Ying, Guan, Ji

Published Feb 7, 2025• 0 citations
arXivHTMLPDF

Abstract

We study the differential privacy (DP) of the quantum recommendation algorithm of Kerenidis--Prakash and its quantum-inspired classical counterpart. Under standard low-rank and incoherence assumptions on the preference matrix, we show that the randomness already present in the algorithms' measurement/$\ell_2$-sampling steps can act as a privacy-curating mechanism, yielding $(\varepsilon,δ)$-DP without injecting additional DP noise through the interface. Concretely, for a system with $m$ users and $n$ items and rank parameter $k$, we prove $\varepsilon=\mathcal O(\sqrt{k/n})$ and $δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)$; in the typical regime $k=\mathrm{polylog}(m,n)$ this simplifies to $\varepsilon=\tilde{\mathcal O}(1/\sqrt n)$ and $δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)$. Our analysis introduces a perturbation technique for truncated SVD under a single-entry update, which tracks the induced change in the low-rank reconstruction while avoiding unstable singular-vector comparisons. Finally, we validate the scaling on real-world rating datasets and compare against classical DP recommender baselines.

DOI
10.48550/arxiv.2502.04758

Related papers

Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms

Armando Angrisani, Mina Doosti, Elham Kashefi

Differential privacy provides a theoretical framework for processing a dataset about $n$ users, in a way that the output reveals a minimal information about any single user. Such notion of privacy is usually ensured by noise-adding mechanisms and amplified by several processes, including subsampling, shuffling, iteration, mixing and diffusion. In this work, we provide privacy amplification bounds for quantum and quantum-inspired algorithms. In particular, we show for the first time, that algorithms running on quantum encoding of a classical dataset or the outcomes of quantum-inspired classical sampling, amplify differential privacy. Moreover, we prove that a quantum version of differential privacy is amplified by the composition of quantum channels, provided that they satisfy some mixing conditions.

arXiv:2203.03604•Mar 7, 2022•10 citations

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang

We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n.

arXiv:1807.04271•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•367 citations

Bridging Quantum Computing and Differential Privacy: Insights into Quantum Computing Privacy

Yusheng Zhao, Hui Zhong, Xinyue Zhang +3 more

While quantum computing has strong potential in data-driven fields, the privacy issue of sensitive or valuable information involved in the quantum algorithm should be considered. Differential privacy (DP), which is a fundamental privacy tool widely used in the classical scenario, has been extended to the quantum domain, i.e., quantum differential privacy (QDP). QDP may become one of the most promising approaches toward privacy-preserving quantum computing since it is not only compatible with classical DP mechanisms but also achieves privacy protection by exploiting unavoidable quantum noise in noisy intermediate-scale quantum (NISQ) devices. This paper provides an overview of the various implementations of QDP and their performance in terms of privacy parameters under the DP setting. Specifically, we propose a taxonomy of QDP techniques, categorizing the literature on whether internal or external randomization is used as a source to achieve QDP and how these implementations are applied to each phase of the quantum algorithm. We also discuss challenges and future directions for QDP. By summarizing recent advancements, we hope to provide a comprehensive, up-to-date review for researchers venturing into this field.

arXiv:2403.09173•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•5 citations

Private training in quantum machine learning

Tigran Sedrakyan, Frédéric Grosshans, Elham Kashefi

With the emergence of machine learning (ML) models trained on large datasets containing potentially sensitive data, a major question in AI safety is how to make learning private with respect to the training data. Similar to classical machine learning, quantum machine learning (QML) models are not devoid of privacy vulnerabilities. Differential privacy (DP) is a standard tool for training ML models on sensitive data, but its impact in QML remains poorly understood. In this work we study private training in hybrid variational QML models using a classical private DP-SGD optimizer applied to pipelines with classical inputs and outputs. We analyze the interplay between gradient clipping and calibrated noise addition in DP-SGD, and its impact on optimization and accuracy for noisy and noiseless quantum models. We first explain why quantum noise does not provide a satisfactory replacement for the calibrated noise in DP-SGD for ensuring privacy. We then show how the deterministic bounds on gradient norms for a wide class of quantum models translate into explicit control of the detrimental clipping bias introduced by DP-SGD. Finally, we formulate a numerical comparison protocol under fixed clipping threshold and privacy budget and evaluate it on synthetic and image-classification tasks for equivalent quantum and classical models. Our results suggest that quantum models can retain higher accuracy in private-training regimes where the formal privacy guarantee is ensured by a classical DP-SGD mechanism.

quant-pharXiv:2606.29293•Jun 30, 2026•0 citations

Mathematical comparison of classical and quantum mechanisms in optimization under local differential privacy

Yuuya Yoshida

Abstract Differential privacy (DP) is an influential method of protecting private data, and is a condition for a conditional probability distribution. Since we can regard DP as a condition for a tuple of probability vectors, it is natural to consider a similar condition for a tuple of density matrices as a quantum version of DP. This condition is called classical-quantum DP (CQ-DP) because it is considered in converting classical data to quantum states. In the study of DP (including CQ-DP), a positive parameter ɛ represents the privacy level to be guaranteed. In this paper, we show that CQ-DP has a quantum advantage in certain optimization problems. Moreover, we compare classical DP and CQ-DP mathematically to clarify a relation between privacy level and quantum advantage.

arXiv:2011.09960•Journal of Physics A Mathematical and Theoretical•Dec 18, 2024•4 citations

Guaranteeing Privacy in Hybrid Quantum Learning through Theoretical Mechanisms

Hoang M. Ngo, Tre' R. Jeter, Incheol Shin +3 more

Quantum Machine Learning (QML) is becoming increasingly prevalent due to its potential to enhance classical machine learning (ML) tasks, such as classification. Although quantum noise is often viewed as a major challenge in quantum computing, it also offers a unique opportunity to enhance privacy. In particular, intrinsic quantum noise provides a natural stochastic resource that, when rigorously analyzed within the differential privacy (DP) framework and composed with classical mechanisms, can satisfy formal $(\varepsilon, δ)$-DP guarantees. This enables a reduction in the required classical perturbation without compromising the privacy budget, potentially improving model utility. However, the integration of classical and quantum noise for privacy preservation remains unexplored. In this work, we propose a hybrid noise-added mechanism, HYPER-Q, that combines classical and quantum noise to protect the privacy of QML models. We provide a comprehensive analysis of its privacy guarantees and establish theoretical bounds on its utility. Empirically, we demonstrate that HYPER-Q outperforms existing classical noise-based mechanisms in terms of adversarial robustness across multiple real-world datasets.

quant-pharXiv:2602.02364•Feb 3, 2026•0 citations
We study the differential privacy (DP) of the quantum recommendation algorithm of Kerenidis--Prakash and its quantum-inspired classical counterpart. Under standard low-rank and incoherence assumptions on the preference matrix, we show that the randomness already present in the algorithms' measurement/ℓ2\ell_2ℓ2​-sampling steps can act as a privacy-curating mechanism, yielding (ε,δ)(\varepsilon,δ)(ε,δ)-DP without injecting additional DP noise through the interface. Concretely, for a system with mmm users and nnn items and rank parameter kkk, we prove ε=O(k/n)\varepsilon=\mathcal O(\sqrt{k/n})ε=O(k/n​) and δ=O(k2/min⁡2{m,n})δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)δ=O(k2/min2{m,n}); in the typical regime k=polylog(m,n)k=\mathrm{polylog}(m,n)k=polylog(m,n) this simplifies to ε=O~(1/n)\varepsilon=\tilde{\mathcal O}(1/\sqrt n)ε=O~(1/n​) and δ=O~(1/min⁡2{m,n})δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)δ=O~(1/min2{m,n}). Our analysis introduces a perturbation technique for truncated SVD under a single-entry update, which tracks the induced change in the low-rank reconstruction while avoiding unstable singular-vector comparisons. Finally, we validate the scaling on real-world rating datasets and compare against classical DP recommender baselines.
Differential privacy provides a theoretical framework for processing a dataset about nnn users, in a way that the output reveals a minimal information about any single user. Such notion of privacy is usually ensured by noise-adding mechanisms and amplified by several processes, including subsampling, shuffling, iteration, mixing and diffusion. In this work, we provide privacy amplification bounds for quantum and quantum-inspired algorithms. In particular, we show for the first time, that algorithms running on quantum encoding of a classical dataset or the outcomes of quantum-inspired classical sampling, amplify differential privacy. Moreover, we prove that a quantum version of differential privacy is amplified by the composition of quantum channels, provided that they satisfy some mixing conditions.
We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n.
While quantum computing has strong potential in data-driven fields, the privacy issue of sensitive or valuable information involved in the quantum algorithm should be considered. Differential privacy (DP), which is a fundamental privacy tool widely used in the classical scenario, has been extended to the quantum domain, i.e., quantum differential privacy (QDP). QDP may become one of the most promising approaches toward privacy-preserving quantum computing since it is not only compatible with classical DP mechanisms but also achieves privacy protection by exploiting unavoidable quantum noise in noisy intermediate-scale quantum (NISQ) devices. This paper provides an overview of the various implementations of QDP and their performance in terms of privacy parameters under the DP setting. Specifically, we propose a taxonomy of QDP techniques, categorizing the literature on whether internal or external randomization is used as a source to achieve QDP and how these implementations are applied to each phase of the quantum algorithm. We also discuss challenges and future directions for QDP. By summarizing recent advancements, we hope to provide a comprehensive, up-to-date review for researchers venturing into this field.
With the emergence of machine learning (ML) models trained on large datasets containing potentially sensitive data, a major question in AI safety is how to make learning private with respect to the training data. Similar to classical machine learning, quantum machine learning (QML) models are not devoid of privacy vulnerabilities. Differential privacy (DP) is a standard tool for training ML models on sensitive data, but its impact in QML remains poorly understood. In this work we study private training in hybrid variational QML models using a classical private DP-SGD optimizer applied to pipelines with classical inputs and outputs. We analyze the interplay between gradient clipping and calibrated noise addition in DP-SGD, and its impact on optimization and accuracy for noisy and noiseless quantum models. We first explain why quantum noise does not provide a satisfactory replacement for the calibrated noise in DP-SGD for ensuring privacy. We then show how the deterministic bounds on gradient norms for a wide class of quantum models translate into explicit control of the detrimental clipping bias introduced by DP-SGD. Finally, we formulate a numerical comparison protocol under fixed clipping threshold and privacy budget and evaluate it on synthetic and image-classification tasks for equivalent quantum and classical models. Our results suggest that quantum models can retain higher accuracy in private-training regimes where the formal privacy guarantee is ensured by a classical DP-SGD mechanism.
Abstract Differential privacy (DP) is an influential method of protecting private data, and is a condition for a conditional probability distribution. Since we can regard DP as a condition for a tuple of probability vectors, it is natural to consider a similar condition for a tuple of density matrices as a quantum version of DP. This condition is called classical-quantum DP (CQ-DP) because it is considered in converting classical data to quantum states. In the study of DP (including CQ-DP), a positive parameter ɛ represents the privacy level to be guaranteed. In this paper, we show that CQ-DP has a quantum advantage in certain optimization problems. Moreover, we compare classical DP and CQ-DP mathematically to clarify a relation between privacy level and quantum advantage.
Quantum Machine Learning (QML) is becoming increasingly prevalent due to its potential to enhance classical machine learning (ML) tasks, such as classification. Although quantum noise is often viewed as a major challenge in quantum computing, it also offers a unique opportunity to enhance privacy. In particular, intrinsic quantum noise provides a natural stochastic resource that, when rigorously analyzed within the differential privacy (DP) framework and composed with classical mechanisms, can satisfy formal (ε,δ)(\varepsilon, δ)(ε,δ)-DP guarantees. This enables a reduction in the required classical perturbation without compromising the privacy budget, potentially improving model utility. However, the integration of classical and quantum noise for privacy preservation remains unexplored. In this work, we propose a hybrid noise-added mechanism, HYPER-Q, that combines classical and quantum noise to protect the privacy of QML models. We provide a comprehensive analysis of its privacy guarantees and establish theoretical bounds on its utility. Empirically, we demonstrate that HYPER-Q outperforms existing classical noise-based mechanisms in terms of adversarial robustness across multiple real-world datasets.