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:2102.07171 · neural information processing systems

Private learning implies quantum stability

Srinivasan Arunachalam, Yihui Quek, John A. Smolin

Published Feb 14, 2021• 11 citations
arXivHTMLPDF

Abstract

Learning an unknown $n$-qubit quantum state $ρ$ is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in $n$ many copies of $ρ$ to estimate it up to trace distance. Motivated by computational learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proceedings of Royal Society A'07), shadow tomography (STOC'18) for learning "shadows" of a state, a model that also requires learners to be differentially private (STOC'19) and the online model of learning states (NeurIPS'18). In these models it was shown that an unknown state can be learned "approximately" using linear-in-$n$ many copies of rho. But is there any relationship between these models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning, to communication complexity, to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM'21) who showed that finite Littlestone dimension (of Boolean-valued concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first consider their work in the real-valued setting and further extend their techniques to the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust to adversarial imprecision. We then show information-theoretic implications between DP learning quantum states in the PAC model, learnability of quantum states in the one-way communication model, online learning of quantum states, quantum stability (which is our conceptual contribution), various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.

DOI
10.48550/arxiv.2102.07171

Related papers

Stabiliser states are efficiently PAC-learnable

Andrea Rocchetto

The exponential scaling of the wave function is a fundamental property of quantum systems with far reaching implications in our ability to process quantum information. A problem where these are particularly relevant is quantum state tomography. State tomography, whose objective is to obtain an approximate description of a quantum system, can be analysed in the framework of computational learning theory. In this model, Aaronson (2007) showed that quantum states are Probably Approximately Correct (PAC)-learnable with sample complexity linear in the number of qubits. However, it is conjectured that in general quantum states require an exponential amount of computation to be learned. Here, using results from the literature on the efficient classical simulation of quantum systems, we show that stabiliser states are efficiently PAC-learnable. Our results solve an open problem formulated by Aaronson (2007) and establish a connection between classical simulation of quantum systems and efficient learnability.

arXiv:1705.00345•Quantum Information and Computation•Jun 1, 2018•31 citations

The power and limitations of restricted quantum learning models

Louis Schatzki

Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan

•Aug 25, 2025•0 citations

Covert Quantum Learning: Privately and Verifiably Learning from Quantum Data

Anand, Abhishek, Caro, Matthias C., Ari Karchmer +1 more

Quantum learning from remotely accessed quantum compute and data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner's data-collection strategies and resulting conclusions. The covert (verifiable) learning model of Canetti and Karchmer (TCC 2021) provides a framework for endowing classical learning algorithms with such guarantees. In this work, we propose models of covert verifiable learning in quantum learning theory and realize them without computational hardness assumptions for remote data access scenarios motivated by established quantum data advantages. We consider two privacy notions: (i) strategy-covertness, where the eavesdropper does not gain information about the learner's strategy; and (ii) target-covertness, where the eavesdropper does not gain information about the unknown object being learned. We show: Strategy-covert algorithms for making quantum statistical queries via classical shadows; Target-covert algorithms for learning quadratic functions from public quantum examples and private quantum statistical queries, for Pauli shadow tomography and stabilizer state learning from public multi-copy and private single-copy quantum measurements, and for solving Forrelation and Simon's problem from public quantum queries and private classical queries, where the adversary is a unidirectional or i.i.d. ancilla-free eavesdropper. The lattermost results in particular establish that the exponential separation between classical and quantum queries for Forrelation and Simon's problem survives under covertness constraints. Along the way, we design covert verifiable protocols for quantum data acquisition from public quantum queries which may be of independent interest. Overall, our models and corresponding algorithms demonstrate that quantum advantages are privately and verifiably achievable even with untrusted, remote data.

arXiv:2510.07193•Oct 8, 2025•0 citations

Online learning of quantum states*

Scott Aaronson, Xinyi Chen, Elad Hazan +2 more

Abstract Suppose we have many copies of an unknown n -qubit state . We measure some copies of using a known two-outcome measurement E 1 , then other copies using a measurement E 2 , and so on. At each stage t , we generate a current hypothesis about the state , using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that , the error in our prediction for the next measurement, is at least at most times. Even in the ‘non-realizable’ setting—where there could be arbitrary noise in the measurement outcomes—we show how to output hypothesis states that incur at most excess loss over the best possible state on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results—using convex optimization, quantum postselection, and sequential fat-shattering dimension—which have different advantages in terms of parameters and portability.

arXiv:1802.09025•Journal of Statistical Mechanics Theory and Experiment•Dec 1, 2019•67 citations

Quantum statistical query learning

Srinivasan Arunachalam, Alex B. Grilo, Henry Yuen

We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.

arXiv:2002.08240•Feb 19, 2020•53 citations

Gentle Measurement of Quantum States and Differential Privacy

Scott Aaronson, Guy N. Rothblum

In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most eps about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that "damages the states by at most alpha," even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is alpha-gentle for small alpha is also O(alpha)-DP, and any product measurement that is eps-DP is also O(eps*sqrt(n))-gentle. Illustrating the power of this connection, we apply it to the recently studied problem of shadow tomography. Given an unknown d-dimensional quantum state rho, as well as known two-outcome measurements E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts rho], for every i in [m], by measuring few copies of rho. Using our connection theorem, together with a quantum analog of the so-called private multiplicative weights algorithm of Hardt and Rothblum, we give a protocol to solve this problem using O((log m)^2 (log d)^2) copies of rho, compared to Aaronson's previous bound of ~O((log m)^4 (log d)). Our protocol has the advantages of being online (that is, the E_i's are processed one at a time), gentle, and conceptually simple. Other applications of our connection include new lower bounds for shadow tomography from lower bounds on DP, and a result on the safe use of estimation algorithms as subroutines inside larger quantum algorithms.

arXiv:1904.08747•Electronic colloquium on computational complexity•Apr 18, 2019•10 citations
Learning an unknown nnn-qubit quantum state ρρρ is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in nnn many copies of ρρρ to estimate it up to trace distance. Motivated by computational learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proceedings of Royal Society A'07), shadow tomography (STOC'18) for learning "shadows" of a state, a model that also requires learners to be differentially private (STOC'19) and the online model of learning states (NeurIPS'18). In these models it was shown that an unknown state can be learned "approximately" using linear-in-nnn many copies of rho. But is there any relationship between these models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning, to communication complexity, to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM'21) who showed that finite Littlestone dimension (of Boolean-valued concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first consider their work in the real-valued setting and further extend their techniques to the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust to adversarial imprecision. We then show information-theoretic implications between DP learning quantum states in the PAC model, learnability of quantum states in the one-way communication model, online learning of quantum states, quantum stability (which is our conceptual contribution), various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.
The exponential scaling of the wave function is a fundamental property of quantum systems with far reaching implications in our ability to process quantum information. A problem where these are particularly relevant is quantum state tomography. State tomography, whose objective is to obtain an approximate description of a quantum system, can be analysed in the framework of computational learning theory. In this model, Aaronson (2007) showed that quantum states are Probably Approximately Correct (PAC)-learnable with sample complexity linear in the number of qubits. However, it is conjectured that in general quantum states require an exponential amount of computation to be learned. Here, using results from the literature on the efficient classical simulation of quantum systems, we show that stabiliser states are efficiently PAC-learnable. Our results solve an open problem formulated by Aaronson (2007) and establish a connection between classical simulation of quantum systems and efficient learnability.
Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan
Quantum learning from remotely accessed quantum compute and data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner's data-collection strategies and resulting conclusions. The covert (verifiable) learning model of Canetti and Karchmer (TCC 2021) provides a framework for endowing classical learning algorithms with such guarantees. In this work, we propose models of covert verifiable learning in quantum learning theory and realize them without computational hardness assumptions for remote data access scenarios motivated by established quantum data advantages. We consider two privacy notions: (i) strategy-covertness, where the eavesdropper does not gain information about the learner's strategy; and (ii) target-covertness, where the eavesdropper does not gain information about the unknown object being learned. We show: Strategy-covert algorithms for making quantum statistical queries via classical shadows; Target-covert algorithms for learning quadratic functions from public quantum examples and private quantum statistical queries, for Pauli shadow tomography and stabilizer state learning from public multi-copy and private single-copy quantum measurements, and for solving Forrelation and Simon's problem from public quantum queries and private classical queries, where the adversary is a unidirectional or i.i.d. ancilla-free eavesdropper. The lattermost results in particular establish that the exponential separation between classical and quantum queries for Forrelation and Simon's problem survives under covertness constraints. Along the way, we design covert verifiable protocols for quantum data acquisition from public quantum queries which may be of independent interest. Overall, our models and corresponding algorithms demonstrate that quantum advantages are privately and verifiably achievable even with untrusted, remote data.
Abstract Suppose we have many copies of an unknown n -qubit state . We measure some copies of using a known two-outcome measurement E 1 , then other copies using a measurement E 2 , and so on. At each stage t , we generate a current hypothesis about the state , using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that , the error in our prediction for the next measurement, is at least at most times. Even in the ‘non-realizable’ setting—where there could be arbitrary noise in the measurement outcomes—we show how to output hypothesis states that incur at most excess loss over the best possible state on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results—using convex optimization, quantum postselection, and sequential fat-shattering dimension—which have different advantages in terms of parameters and portability.
We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.
In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most eps about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that "damages the states by at most alpha," even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is alpha-gentle for small alpha is also O(alpha)-DP, and any product measurement that is eps-DP is also O(eps*sqrt(n))-gentle. Illustrating the power of this connection, we apply it to the recently studied problem of shadow tomography. Given an unknown d-dimensional quantum state rho, as well as known two-outcome measurements E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts rho], for every i in [m], by measuring few copies of rho. Using our connection theorem, together with a quantum analog of the so-called private multiplicative weights algorithm of Hardt and Rothblum, we give a protocol to solve this problem using O((log m)^2 (log d)^2) copies of rho, compared to Aaronson's previous bound of ~O((log m)^4 (log d)). Our protocol has the advantages of being online (that is, the E_i's are processed one at a time), gentle, and conceptually simple. Other applications of our connection include new lower bounds for shadow tomography from lower bounds on DP, and a result on the safe use of estimation algorithms as subroutines inside larger quantum algorithms.