Private learning implies quantum stability
Year: 2021

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 its entries. Motivated by learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proc. 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 ρ can be learned “approximately" using linear in n many copies of ρ. 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 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 extend their work to the real-valued setting, and further extend 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 equivalences 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, various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.

heading: 1 Introduction
text: Learning an unknown quantum state ρ, given copies of the state is a fundamental task in quantum computing, often referred to as tomography. Tomography is of great practical interest since it helps in tasks such as verifying entanglement, understanding correlations, and is useful for calibrating, understanding and controlling noise in quantum devices. In the last few years, questions about the fundamental limits of this task have gained a lot of theoretical attention: how many copies of an n-qubit quantum state ρ are required to estimate the density matrix of ρ up to small error? Recent
∗https://stanford.edu/∼yquek
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
breakthrough results of [1, 2, 3] showed that Θ(22n/ε2) copies of ρ are necessary and sufficient to learn ρ up to trace distance ε. Unfortunately, this exponential scaling in complexity hampers practical applications of tomography; the best known experimental implementation of full-state quantum tomography has been for a 10-qubit quantum state [4].
Simultaneously, the use of machine learning for quantum states has gained lot of traction in quantum computing. In this area, the goal is to use heuristics to learn an unknown quantum state, often with the motivation of physical implementation. Provable results in this area are very few, but interest is widespread due to the number of emerging quantum hardware devices. Given the fundamental importance of tomography and the natural connection to learning, Aaronson [5] formally defined a variant of tomography: PAC learning quantum states. This problem brings together two ripe exciting topics: classical machine learning and quantum computing. Following his work, there have been a few other papers that have introduced models of learning quantum states with various constraints.
In this work, our main contribution is to show implications between several seemingly different quantum learning models. The main technicality is extending known results in classical learning theory from Boolean functions to real-valued functions with noisy labels – a setting motivated by learning quantum states, but with potential extensions to learning other physical systems (e.g. [6]). Along the way we also show how certain implications that hold for classical Boolean functions do not hold true in the real-valued setting (which could be of independent classical interest). See Figure 1 for a summary of our results.

heading: 1.1 Background: Models of interest
text: To explain our main results, we start by introducing some learning models of interest. We state them in the language of quantum state learning. However, these are at their core, classical learning models for real-valued functions with imprecise feedback, and the translation is stated precisely in Section 2.2. We also formally translate them to the classical learning setting in Supplementary material (Section A), which we omit here due to space constraints.
PAC learning. Valiant’s Probably Approximately Correct (PAC) learning, lays the foundation for computational learning theory. Aaronson [5] considered learning quantum states in the PAC model. In this model, let ρ ∈ C be an unknown quantum state (picked from a known concept class C of states) and let D : E → [0, 1] be an arbitrary unknown distribution over all possible 2-outcome measurements E. Suppose a quantum learner obtains training examples (Ei,Tr(ρEi)) where Ei is drawn from D, and the goal is to output σ such that with probability ≥ 0.99, σ satisfies PrE∼D[|Tr(σE)−Tr(ρE)| ≤ ζ] ≥ 1−α. How many training examples suffice for such a (ζ, α)-PAC learner? In answer, he showed that the number of examples necessary and sufficient to learn C is captured by the fat-shattering dimension of C.
PAC learning with Differential privacy. A well-studied area of computer science is differential privacy (DP) (which says that an algorithm should behave “approximately" the same given two datasets that differ in one element). This notion can be extended to the quantum realm, where we ask that the quantum PAC learner proposed above is also differentially private, wherein given two datasets S = {(Ei,Tr(ρEi))}i, S′ = {(E′i,Tr(ρE′i))}i such that there exists a unique i such that Ei 6= E′i, then a quantum (γ, δ)-DP PAC learning algorithm needs to satisfy Pr[A(S) = σ] ≤ eγ Pr[A(S′) = σ] + δ, where A(S) is the output of A on input S. 2
Communication complexity. Consider the standard one-way communication model between Alice and Bob. Suppose Alice has a quantum state ρ (unknown to Bob) and Bob has an unknown (to Alice) measurement E. The goal of Bob is to output an approximation of Tr(ρE) if only Alice is allowed to communicate to Bob. A trivial strategy for this communication task is for Alice to send a classical description of ρ, but can we do better? If so, how many bits of communication suffice for this task?
Online learning. Several features of the PAC learning model and tomography are somewhat artificial: first, the assumption that the measurements (training examples) are drawn from the same unknown distribution D that the learner will be evaluated on, which does not account for adversarial or changing environments, and secondly, it may be infeasible to possess T -fold tensor copies of the unknown quantum state ρ, rather we may only be able to obtain sequential copies of it. The quantum
2Our notion of DP differs from the notion of DP proposed by [7]. They consider DP measurements with respect to a class of product states, whereas here we require DP with respect to the dataset {(Ei,Tr(Eiρ)}i.
online learning model addresses these aspects. Online learning consists of repeating the following rounds of interaction: a learner obtains a copy of ρ, maintains a local σ which is its guess of ρ, obtains a description of measurement operator Ei (possibly adversarially) and predicts the value of yi = Tr(ρEi). Subsequently it receives as feedback an ε-approximation of yi. On every round, if the learner’s prediction satisfies |Tr(σEi)− yi| ≤ ε then it is correct, otherwise it has made a mistake. The goal of the learner is the following: minimize m so that after making m mistakes (not necessarily consecutively), it makes a correct prediction on all future rounds.
Importantly, while the goal in the above model is to make real-valued predictions yi, it departs from the real-valued online learning literature in allowing for ε-imprecision in the feedback. This imprecision is inherent to all learning settings where the feedback is generated by a statistical algorithm (in our setting, the feedback arises from processing the outcomes of quantum measurements), and this generalization has non-trivial implications, as we show. Working in this model, Aaronson [8] showed that for learning the class of all quantum states, it suffices to let m be at most sequential fat-shattering dimension of C (a combinatorial parameter which was originally introduced by Rakhlin et al. [9]).
Motivating question. All these learning models can be seen as variants of full-state tomography, and are known to require exponentially fewer resources than tomography. A natural question is:

heading: Is there a relation between these learning models, communication and combinatorial parameters?
text: Understanding this question classically in the context of Boolean functions has received tremendous attention in computational learning theory and theoretical computer science in the last two years. There have been several papers establishing various connections [10, 11, 12, 13, 14, 15, 16, 17, 18], just to cite a few. However, these papers leave two important questions open:
1. Do these results apply to learning quantum states?
2. Do the classical results (for Boolean functions) also hold for real-valued functions?
Ours is the first work that studies the first question. In the process, we not only explore how implications between Boolean learning models translate over to the quantum setting, but we also introduce new notions of (classically) privately learning quantum states and quantum stability (linked to privacy), contributing another perspective to an ongoing discussion of what differentially-private quantum computation could look like [19, 20, 7]. The second question indirectly received attention recently in NeurIPS’20 by Jung et al. [11] for multi-class learning, but their work left several open ends (when translated to real-valued learning) which we tie up here (see Section 3.4 for a more in-depth comparison).

heading: 2 Overview of main results

heading: 2.1 Quantum results
text: To condense our (affirmative) answer to the first question above, we derive a series of implications going through all these models, starting from differentially-private PAC learning to online learning to quantum stability (our conceptual contribution which we define and discuss below).
Taking a step back, quantum online learning and DP PAC quantum learning seem very different on the surface. Online learning ensures that eventually (after m mistakes) we learn the state approximately, but makes no guarantees on when the last of m mistakes occurs with respect to the series of examples seen. DP PAC learning is not online – it separates the learning into train (offline) and test (online) phases, and also introduces a distribution, D, from which measurements are drawn. Ultimately DP PAC learning says that after seeing T measurements from D, we have (privately) learned the state. We show that in fact DP PAC learning sample complexity can be lower bounded by the sequential fat-shattering dimension which also characterizes the complexity of online learning [9]. We give a summary of our results in Figure 1. Also, we say an algorithm is pure DP (resp. approximate DP) when δ = 0 in our definition (resp. δ > 0). We remark that only a few arrows are efficient in both sample and time complexity, otherwise these implications are primarily information-theoretic.
Conceptual contribution. The main center piece in establishing these connections is the concept of quantum stability, which is the new conceptual contribution in this work. Intuitively, we say a quantum learning algorithm is stable if, for an unknown state ρ, given a set of noisy labelled
examples from a distribution D, there exists one state σ such that, with “high" probability, the output of the learning algorithm is “close" to σ. More formally, we say a quantum learning algorithm A is (T, ε, η)-stable with respect to distribution D over a set of orthogonal 2-outcome measurements if, given T many labelled examples S consisting of Ei drawn from D and ζ-approximations of Tr(ρEi), there exists a state σ such that Pr[A(S) ∈ BM(ε, σ)] ≥ η, (1) where the probability is taken over the examples in S and BM(ε, σ) is the ball of states ε-close to σ with respect toM, i.e., BM(ε, σ) = {σ′ : |Tr(Eσ)− Tr(Eσ′)| < ε for every E ∈ M}. In other words, quantum stability means that up to an ε-distance, there is some hypothesis state σ that is output by A with “high" (at least η) probability. A classical analog of stability can be written as: a classical learning algorithm for concept class C : X → [0, 1] (run on examples {(xi, ĉ(xi))} where |ĉ(xi)− c(xi)| < ζ, c ∈ C) is stable if there exists a hypothesis f such that Pr[A(S) ∈ T (ε, f)] ≥ η, where T (ε, f) := {g ∈ C : |g(x)− f(x)| < ε for every x ∈ X}. Consistent stability implies learnability. While we will make this precise later, the significance of an algorithm A being stable is that σ, the output state at the ‘center of the ball’, is a good hypothesis for estimating measurement probabilities (and hence A is a good learner). This is not at all obvious from the definition of stability, which does not inherently require that this σ is a good approximation of ρ. Yet, it turns out that if A is a stable and consistent learner (i.e., its output does not contradict any of the training examples it has seen), σ has low loss with respect to D. This means that, using hypothesis σ to predict outcomes of future measurements drawn from distribution D as Tr(Eσ) will yield ε-accurate predictions with high probability.

heading: 2.2 Classical results
text: In order to see the connection to classical learning theory we first observe the following. Learning n-qubit quantum states over an orthogonal basis of n-qubit quantum measurements,M, is equivalent to learning – with imprecise adversarial feedback – an arbitrary real-valued function in the class D = {f : X → [0, 1]} when X =M: there is a one-to-one mapping between the set of all quantum states and the set of bounded real-valued functions onM.3 To elaborate, for every σ, one can clearly associate a function fσ :M→ [0, 1] defined as fσ(M) = Tr(Mσ) and for the converse direction, given an arbitrary c :M→ [0, 1], one can find a density matrix σ for which c(M) = Tr(Mσ) for all M ∈M (and this uses the fact thatM is an orthogonal measurement basis crucially). Hence, if one can learn D when we fix theM to be an arbitrary orthogonal basis of 2-outcome measurements then one can learn the class of quantum states C, and the converse is also true.
3Indeed, in Section 4 of this paper, we slightly abuse notation; when C is a class of quantum states, we use sfat(C) to mean sfat(D).
So, our results for quantum learning naturally follow from our study of learning from noisy examples real-valued concept classes over arbitrary domain X , which are the focus of this work. As we mentioned in the introduction, some of the implications we study are well-known for the case of Boolean functions. However, motivated by the setting of learning quantum states, we were confronted with two questions: (i) do these Boolean learning results also hold for real-valued learning? (ii) in the real-valued class learning problem, the learner is not provided with exact data, but is given imprecise feedback which could correspond to a different class label altogether, so are these results robust?
Our main contribution is thus in establishing all the arrows in Figure 1 for real-valued concept classes. As far as we are aware, even classically establishing equivalences between online learning, stability and approximate differential privacy for real-valued functions with imprecise feedback was not explored before. In the precise feedback model, a few of the arrows in Figure 1 were proven implicitly in [11], when they considered multi-class learnability but they left several open ends which we tie up here (see Section 3.4 for more). Strikingly, when considering real-valued functions, a technique due to [10] showing stability implies approximate DP PAC for Boolean functions, is a no-go in our setting, as we show. We give a counterexample concept class which can be reduced to fingerprinting codes, for which we show that stability does not imply approximate DP PAC without a domain size dependence.

heading: 3 Proof sketches for our main results (Fig. 1)
text: We break down the proofs of the arrows in Figure 1 into four steps and discuss them below. Before this, we provide a quick introduction to necessary quantum information theory.
Quantum information preliminaries. An n-qubit quantum state ρ is a positive semidefinite matrix with trace 1. An arbitrary valid quantum operation on quantum states can be expressed as a unitary matrix U (which satisfies UU∗ = U∗U = 1). An application of a unitary U to the state ρ results in the quantum state UρU∗. Finally, in order to extract meaningful classical information out of a quantum state, one can perform a POVM (positive-operator valued measurement) which is specified by a set of m positive semidefinite matrices E1, . . . , Em satisfying ∑ iEi = 1. A measurement on a state ρ using such a POVM returns a classical outcome i ∈ [m] with probability Tr(Eiρ).
3.1 Pure DP PAC learnability implies finite sfat dimension
It is known that if there is a DP PAC learning algorithm for a Boolean function class C then the representation dimension of the class is bounded by the sample complexity of said algorithm. Representation dimension, itself, upper bounds classical communication complexity as well as a combinatorial dimension of the concept class known as the Littlestone dimension.
All of the above connections and combinatorial parameters pertain to learning Boolean functions, but we show that they can be robustly ported to our ‘quantum-inspired’ DP PAC setting of learning real-valued functions and with adversarial imprecision. Analogous to the Littlestone dimension, the ζ-sequential fat shattering dimension [9] (denoted sfatζ(·)) is a combinatorial parameter that can be associated to every real-valued concept class. In this direction, a key contribution is: prior to our work, [21] showed that Littlestone dimension lower bounds one-way classical communication complexity, but we show that for learning real-valued functions, the sfat dimension lower bounds both classical and quantum communication complexity. We omit the proofs of these implications and refer the reader to Section D in Supplementary material.

heading: 3.2 Finite sfat(·) implies online learnability and resolving an open question of Aaronson
text: In the second step, the goal is to go from a concept class C having finite sfat(C) to design an online learning algorithm for C that makes at most sfat(C) mistakes even in the presence of imprecise feedback. In this direction, one of our technical contributions is to construct a robust standard optimal algorithm (denoted RSOA) which satisfies this mistake-bound. This RSOA algorithm and result below will be crucial for the following steps.
Result 3.1 (Informal). Let C be a concept class with sfatζ(C) = d. There is an explicit robust standard optimal algorithm RSOA that makes at most d mistakes in online learning C.
Indeed, the word ‘robust’ in the name of the algorithm indicates that it is robust to ζ-imprecise adversarial feedback. This robustness property allows RSOA to be relevant in contexts where the feedback is generated by some physical measurement process. In this case, our end goal is to use RSOA for learning quantum states, where typically, the feedback is generated by the learner itself by measuring E repeatedly on copies of the quantum state ρ. Averaging these measurements will provide a ζ-approximation of Tr(ρE) instead of its exact value.
To accommodate this imprecision, we introduce the notion of an interleaved ζ-cover of the [0, 1] interval, Ĩζ , as the set of overlapping half-open intervals (‘super-bins’) of width 2ζ given by{
[0, 2ζ), [ζ, 3ζ), . . . , [1−2ζ, 1] } with the midpoints Ĩζ = { ζ, 2ζ, . . . , 1−ζ } where |Ĩζ | = 1/ζ−1.
We also define the following: given a set of functions V ⊆ {f : X → [0, 1]}, r ∈ Ĩ2ζ and x ∈ X , define a (possibly empty) subset V (r, x) ⊆ V as V (r, x) = { f ∈ V : f(x) ∈ [r − 2ζ, r + 2ζ] } , i.e., V (r, x) are the set of functions f ∈ V such that f(x) is within a 2ζ-ball around r. We present our RSOA algorithm in Algorithm 1. We now make a few comments regarding this result. Classically, for the Boolean setting, it is well-known that the so-called Standard Optimal Algorithm is an online learner for any concept class, that makes at most Littlestone dimension-many mistakes [22]. Eventually, [9] generalized the work of Littlestone for real-valued functions, showing that real-valued concept classes can be learned using their FAT-SOA algorithm, with at most sfat(C) many mistakes. Now, our RSOA algorithm generalizes this, showing that real-valued concept classes can be learned with sfatζ(C) many mistakes, even in the presence of adversarial imprecision of magnitude ζ.
Algorithm 1 Robust Standard Optimal Algorithm Input: Concept class C ⊆ {f : X → [0, 1]}, target (unknown) concept c ∈ C, and ζ ∈ [0, 1]. Initialize: V1 ← C
1: for t = 1, . . . , T do 2: The learner receives xt and maintains set Vt, a set of “surviving functions". 3: For every super-bin midpoint r ∈ Ĩ2ζ , compute the set of functions Vt(r, xt). 4: The learner finds the super-bin which achieves the maximum sfat(·) dimension
Rt(xt) := { arg max r∈Ĩ2ζ sfat2ζ (Vt(r, xt)) ∈ Ĩ2ζ }
5: Learner computes the mean of the set Rt(xt), i.e., ŷt := 1|Rt(xt)| ∑ r∈Rt(xt) r. 6: The learner outputs ŷt and receives feedback ĉ(xt). 7: Update Vt+1 ← {g ∈ Vt | |g(xt)− ĉ(xt)| ≤ ζ} 8: end for
Outputs: The intermediate predictions ŷt for t ∈ [T ] and a hypothesis f(x) := RT+1(x).
The basic principle that underlies our RSOA algorithm is, keep track of a set of ‘surviving’ functions, and after every round of learning, eliminate those which were grossly inconsistent with the adversary’s feedback. In more detail: beforehand, the learner discretizes the function range [0, 1] into 1/ζ − 1- many 2ζ-sized overlapping bins. During learning, upon receiving the domain point x, the learner evaluates all remaining functions at x and ‘counts’ (using sfat(·) dimension as a proxy) the number of functions mapping to each bin, and finally outputs the bin with the highest sfat(·) dimension. The intuition is that quantifying the number of functions in each bin with the sfat(·) dimension (of only the functions in the bin) instead of their raw count, allows the learner to reduce the surviving set of functions efficiently. Furthermore, the learner never makes more than sfat(C) prediction mistakes in the course of learning. For a proof of correctness, refer to Section B in the supplementary material.
Resolving an open question. Prior to our work, Aaronson [8] considered quantum online learning and showed that sfat(·) of all n-qubit quantum states is at most n, which in particular shows the existence of a quantum online learning algorithm for the class of all quantum states that makes at most n mistakes. However, their focus was on online learning with regret bounds, and so they didnn’t provide an explicit algorithm that achieves the sfat(·) mistake bound, but raised this question in their work. Our Result 3.1 resolves their question, by showing that our RSOA is such an algorithm.

heading: 3.3 Online learnability implies stability
text: We now show that if a set of quantum states has sfat dimension d (i.e., it can be online-learned with noisy measurements with d-many mistakes), then it can be learned by an (T = ε−d, ε, εd) quantumstable algorithm A satisfying Eq. (1)). That is, for unknown state ρ from this online-learnable set, given O(ε−d)-many examples which consist of 2-outcome measurements Ei from an orthogonal set M and ε-accurate Tr(ρEi), there exists a σ having low loss, such that PrS∼DT [A(S) ∈ BM(ε, σ)] ≥ εd. We now state this formally in terms of real-valued learning.
Result 3.2. Let α, ζ ∈ [0, 1]. Let C ⊆ {f : X → [0, 1]} be a concept class with sfat2ζ(C) = d. Let D : X → [0, 1] be a distribution and let S = {(xi, ĉ(xi))} be a set of T = ζ−d/ε-many examples where xi ∼ D and |ĉ(xi) − c(xi)| < ζ where c ∈ C is an unknown concept. There is a (T, ζ−d, ζ)-stable learner G, that outputs g ∈ B(f, ζ) such that Prx[|f(x)− c(x)| ≤ ζ] ≥ 1− α.
Proof sketch. To prove this theorem we borrow the high-level idea from [10] (for the case of Boolean functions). Before our work we didn’t have an RSOA algorithm which could be used as a black-box in order to emulate the proof-technique of [10] for the quantum/robust real-valued setting. Our stable learner in the result above is essentially the RSOA algorithm that we designed earlier, but run on a carefully tailored input distribution over the examples, with T being the overall sample complexity of our algorithm. Most of the work in the proof arises in explaining how to tailor the set of examples drawn from the original distribution D into a new set S on which RSOA is guaranteed to succeed.
We prove this theorem in two steps: in step (1) we provide a tailoring algorithm that defines distributions ext(D, 1), . . . , ext(D, d) (where sfatζ(C) = d) as a function of the unknown target distribution D (to which we have black-box access). Just as in [10], the key idea for the tailoring is to inject examples into the sample that would force RSOA to make mistakes (we give more details about this below). We adapt this idea for the robust, real-valued setting. Unfortunately, this tailoring algorithm uses an unbounded number of examples (in the worst case). To handle this, step (2) is to compute the expected number of examples drawn by the tailoring algorithm, then use Markov’s inequality to compute what the cutoff should be. This will be our final stable algorithm.
We now give more details about step (1). We sample many labelled examples from the unknown distribution D and instead of feeding these examples directly to the black-box RSOA, we plant amongst them some “mistake examples" before giving the processed sample to RSOA. A “mistake example" is an example which is correctly labelled, but on which RSOA would make the wrong prediction. That is to say, from a large pool of T = ζ−d examples drawn from D, craft a short sequence of O(1/ζ) examples that include at most d mistake examples; now feed the short sequence into RSOA. This works, because RSOA satisfies the guarantee that after making d = sfatζ(C) mistakes, it would have identified the target concept up to O(ζ) prediction error.
Our technique for creating mistake examples differs from that of [10]. In the Boolean case, to insert a mistake, it suffices to do the following: Let c : X → {0, 1} be the unknown target function. First, take two candidate samples S1, S2, feed them into two parallel runs of SOA, and obtain two different output hypothesis functions f1, f2 respectively. Next, identify a point in the domain x at which f1(x) 6= f2(x). Say f1(x) = c(x) and f2(x) = c(x), then it suffices to append an example (which will be the mistake example) of the form (x, c(x)) to S2, so that when SOA is now run on S2 ◦ (x, c(x)), SOA’s hypothesis function just before seeing the last example is f2, which it then uses to make a (wrong) prediction on the last example. To generate the bit c(x) for their mistake example, [10] simply flip a coin b ∈ {0, 1} and with probability 1/2, b = c(x). For us this does not work because our target function is real-valued, i.e. c(x) ∈ [0, 1]. Instead, we discretize [0, 1] into 1/ζ many ζ-intervals, pick a uniformly random interval and let b be the center of this interval. Clearly now, with probability 1/ζ, c(x) lies in the ζ-ball around b and is thus valid adversarial feedback. Overall, the construction of our quantum stable learner is more involved in order to work around the looser approximation guarantees of RSOA due to the possibility of imprecise adversarial feedback. We skip the proofs here and refer the reader to Section C in Supplementary material.
3.4 Stability does not imply approximate DP PAC learnability
So far we showed that quantum/robust real-valued online learning C implies a quantum/robustly stable learner for C. For Boolean-valued Cs, [10] went one step further and created a approximately differentially-private learner from a stable learner; in this sense, stability can be viewed as an
intermediate property between online learnability and differential privacy. A natural question here is, can we extend this result to our setting, i.e., does quantum/robust stability in turn imply differential privacy? If so, then Figure 1 would start and end with differential privacy (albeit starting from pure DP and resulting in approximate DP).
Alas, we show that the technique of [10] does not go through for real-valued learning. More precisely, one cannot go from a stable learner (in the sense of Result 3.2) to a differentially private learner without a domain-size dependence. First observe that our “stability" guarantees on G (Result 3.2) are somewhat unusual: there exists some function ball (around the target concept) such that the collective probability of G outputting its member functions is high, in contrast to the Boolean setting [10], where global stability means that a single function is output with high probability. The stability guarantees differ because, in our setting, the learner only obtains ε-accurate feedback from the adversary. Since all functions that are in the ε-ball of c are consistent with the feedback of the adversary, the learner cannot uniquely identify the target concept c. We thus allow the learner to output a function in the ε-ball around the target concept. This difference, however, also prevents us from applying the generic transformation from a stable learner to a private learner employed in [10], as we now explain.4
That transformation first generates a list of hypothesis functions by running the stable learner G of Result 3.2, n many times, each of which outputs a function fi. By Result 3.2 and a Chernoff bound, one can show that with high probability, an η = ζd-fraction of the list should lie in B(ζ, f) for some f . Next one would like to privately output some function in B(ζ, f), i.e. solve the following problem: Problem 3.3 (Query release for function balls). Given as input a list of n functions {fi : X → R}i∈[n], an η-fraction of which satisfy |fi(x) − f∗(x)| ≤ ζ for all x, f∗ : X → R output some function g such that |g(x)− f∗(x)| ≤ ζ for all x.
We also introduce the following related problem: Problem 3.4 (Clique identification on a discrete domain). For domain Y = [4]d, given as input a relation R = {(x, y) ∈ Y × Y : ‖x − y‖∞ ≤ 1} and a dataset D ∈ Yn under the promise that (x, y) ∈ R for all x, y ∈ D, output a z ∈ Y such that (x, z) ∈ R for every x ∈ D.
Observe that Problem 3.4 reduces to Problem 3.3. We give a lower bound on the number of samples necessary to solve problem 3.4, which gives a lower bound for our query release on functions balls. In order to do this one can use a slightly non-standard reduction to the well-studied 1-way marginal release problem [24]. Subsequently, one can use a modified argument from fingerprinting codes [25, 26] and show that for δ < 1/1500, every (1, δ < 1/n)-DP algorithm solving Problem 3.4 with probability at least 1499/1500 requires n ≥ Ω̃( √ d). This implies that every (1, δ)-DP 5
algorithm for Problem 3.3 requires n ≥ Ω̃( √ |X |). In particular, this lower bound is unbounded if |X | is unbounded, which is precisely the case if we are performing quantum learning on the domain of all possible 2-outcome measurements. See Section C in the Supplementary material for more.
Linking this discussion back to our motivating setting of quantum learning (see Section 2.2), when M is the orthogonal basis of n-qubit Paulis, then |M| = 4n and so the above implies that one needs sample complexity Ω̃(4n/2) in order to go from stability to approximate differential privacy.
We can also give a quadratically-worse upper-bound on the sample complexity of pure private PAC learning in our quantum/robust setting (which naturally also upper bounds its approximate version). We simply invoke the generic private learner of [27, 10], without going through the intermediate step of producing a stable learner. Given any set of functions H, this learner simply draws O (log |H|) examples, and samples a function from H with probability inverse exponential in the function’s loss on the examples. To learn quantum states in C – again withM the orthogonal basis of n-qubit Paulis – with the Generic Private Learner, we discretize the [0, 1]-range of D into bins of size ζ, obtaining a resulting function class H with size (1/ζ)4n . Therefore the sample complexity of differentially-private quantum learning is Õ(4n).
Comparison to prior work [11]. After completion of this work, we were made aware of the work by [11] (in NeurIPS’20). While they extended the work of [10] to multi-class functions, they claim that their results also apply to real-valued learning by discretizing the range of the functions (we
4The following argument was communicated to us by Mark Bun [23]. 5In differential privacy, we are typically interested only in values of δ < 1/n, in order to rule out algorithms
that simply pick a point in their input uniformly and then process them in a possibly non-private manner.
couldn’t find a version of the paper that spells out the proof that online learnability implies a stable real-valued learner, but this seems implicit from their proofs). While they state a notion of stability for learning real-valued functions that, similar to ours, invokes the notion of function balls, in order to go from an online learner to stable learner they crucially rely on a alternate Littlestone dimension. In this work, we use the standard notion of sequential fat-shattering dimension – which we also bound for the case of quantum states. Secondly, while [11]’s online and PAC learning settings assume that the learner receives exact real-valued labels, in all our learning models, we allow for ε-imprecise labels. Thus, all our implications are robust to such adversarial imprecision (making our work closer to “classification-noise learning"). This additional consideration bars the usage of [10]’s technique, developed for Boolean functions as a black-box. We discuss further differences between our works in the paragraph above Section D in the Supplementary material.

heading: 4 Faster algorithms for quantum state learning
text: Our previous sections were written for the general setting of robustly learning a real-valued function class. Now we switch gears, applying these results to our motivating problem: tightly characterizing the complexity of quantum state learning. See section E in the Supplementary material for details.
1. Faster shadow tomography for classes of states. Aaronson [28] introduced a learning model called shadow tomography. Here, the goal is to learn the “shadows" of an unknown quantum state ρ, i.e., given m measurements E1, . . . , Em, how many copies of ρ suffice to estimate Tr(ρEi) for all i ∈ [m]. Aaronson surprisingly showed that O(n, logm) copies of ρ suffice for this task (in contrast to the trivial tomography or sampling bound of O(exp(n),m)), and an important open problem is can we get rid of the n dependence (even for a subclass of quantum states)? Subsequently, there were many works that tried to improve the complexity of general shadow tomography [29, 30]. We can now answer this question affirmatively: the complexity of shadow tomography (assuming that the unknown state ρ comes from a set C) can be made O(sfat(C), logm). Result 4.1 (Informal). There is a (α, δ)-gentle (1− ε)-accurate shadow tomography procedure for a set of states C using poly ( sfat(C), logm, 1/(αε), log(1/δ) ) copies of ρ.
This result relies on an observation of [7] that a mistake-bounded online learning algorithm (we plug in RSOA) can be used as a subroutine in gentle shadow tomography, where gentle can be viewed as a proxy for privacy (albeit, the notion of DP here is with respect to states and different from ours).
2. A better bound on sfat(·). Let Cn be the class of all n-qubit states. As we mentioned earlier, [8] showed that sfat(Cn) is at most O(n), but clearly for a subset C ⊆ Cn of quantum states it is possible that sfat(C) sfat(Cn). In this direction, using techniques from quantum random access codes (which was also used before [5, 8, 31, 32]) we first give a general upper bound on the sequential fat shattering dimension of a class of quantum states in terms of Holevo information of an ensemble. Result 4.2 (Informal). Let C be a set of states on n qubits. Then sfatp(C) ≤ 11−H(p) maxG⊆C χ(EG), where χ is the Holevo information and EG is a uniform ensemble over the states in G.
Now, an immediate consequence of this result is a class of states for which sfat(·) is much smaller than n. Consider the set C of “k-juntas",6 i.e., each n-qubit state lives in the same unknown kdimensional subspace. In this case it is not hard to see that χ(EG) is at most log k, which improves upon the trivial upper bound of n on sfat(C). We discuss more such classes of states below. 3. Learning noisy quantum states. Let C again be a class of quantum states and letN be a quantum channel. Let C′ = {N (U) : U ∈ C} be the set of states obtained after passing through quantum channel N . Suppose the goal is to learn C′ (i.e., to learn states that have passed through a noisy channel N ). This connects to the question of experimental learning of quantum states, i.e., can we learn the unknown noise (or states) in a noisy-quantum device. Here we show that sfat(C′) ≤ C(N ), i.e., sfat(C′) is upper bounded by the classical capacity of N . Fortuitously, recent advances in quantum Shannon theory enable upper bounds on these previously hard-to-compute capacities, and we use them to bound the complexity of learning states corrupted by noise from depolarizing channels, Pauli channels and bosonic channels (e.g. fiber optic cables). As far as we are aware, this is the first work to consider learnability of continuous-variable states.
6k-juntas are well-studied in computational learning theory, wherein a Boolean function on n bits is a k-junta if it depends on an unknown subset of k input bits.

heading: 4.1 Open questions
text: Our work opens up several questions relevant to both classical and quantum machine learning: (1) Can we extend our work to the agnostic setting (which is more applicable in the setting of implementing quantum algorithm in a device with unknown noise)? (2) Recently, [12] improved upon [10] by showing that one needs a polynomial blow-up in sample complexity in going from online learning to differential privacy, can we use similar techniques to improve our results? (3) Classically, [27] established connections between statistical query learning and local differential privacy, can we extend this also to the quantum regime, using the recently defined notion of quantum statistical query learning [33]? (4) Recently, [15] showed that the equivalence between private learning and online learning cannot be made computationally efficient assuming existence of one-way functions, do these extend to the quantum setting?
Acknowledgments and Disclosure of Funding
We thank Mark Bun for various clarifications and also for showing us how to prove that stability does not imply approximate DPPAC. SA was partially supported by the IBM Research Frontiers Institute and acknowledges support from the Army Research Laboratory, the Army Research Office under grant number W911NF-20-1-0014. YQ was supported by the Stanford QFARM fellowship and an NUS Overseas Graduate Scholarship. JS and SA acknowledge support from the IBM Research Frontiers Institute.

Review summaries:
The paper develop a series of relationship between quantum learning model.  (1) Pure DP PAC learnability implies finite sequential fat shattering dimension. (2) Finite sequential fat shattering dimension implies online learnability (3) Online learnability implies certain notion of quantum stability. (4) quantum stability may not implies approximate PAC learnability.  The work (especially point 3,4 above) is inspired by the recent breakthrough of Bun, Livni and Moran (Journal of the ACM'21) on proving online learnability implies private PAC learnability, extends the result to real-valued setting.  

This paper presents a number of connections between private learning, online learning and stability in the quantum and real-valued settings, generalizing recent work of Bun, Livni and Moran '20 in the Boolean-valued setting. The main results are:  - An algorithm (termed RSOA) that accomplishes online learning of real-valued functions (requiring feedback only within an $\epsilon$ precision) with a mistake bound given by the sequential fat-shattering (sfat) dimension of the class  - A notion of real-valued and quantum stability (generalizing Bun et al's "global stability"), along with a proof that online learnability implies this kind of stability  - A no-go result for (one approach for) converting stability to approximate PAC learnability  - An improved shadow tomography result with sample complexity in terms of the sfat dimension  - Bounds on the sfat dimension of quantum state classes in terms of Holevo information  Many of the key notions and proofs are natural generalizations of the Boolean and (exact) real-valued analogs as studied e.g. in Bun et al '20 and Rakhlin et al '10. The concrete applications to quantum state learning are novel and interesting, and address some questions raised in earlier works such as Aaronson et al '18.

This paper derives relationships between several models of approximately learning quantum states. Specifically, it extends results in learning boolean functions to learning real-valued functions with imprecise feedback, and shows that the complexity of learning in Pure DP PAC upper bounds quantum CC and the sequential fat-shattering dimension. The Sfat dimension in turn implies online learnability. A conceptual contribution of this paper is quantum stability, and the authors show that online learnability implies the existence of stable learners, but contrary to results on boolean functions, quantum stability does not imply Approximate DP PAC. The authors also propose the RSOA algorithm, which is central to proving the results. 

This paper is motivated by the problem of learning n-qubit quantum states in different learning models, such as differentially private PAC learning and online learning with imprecise feedback, and proves information-theoretic equivalences and implications between them. One of the main results of the paper is proving that pure DP PAC learning of quantum states implies learning of quantum states in the online learning model with imprecise feedback.  The line of implications goes as follows: a bound on the sample complexity of Pure DP PAC learning implies a bound on the probabilistic representation dimension of the class, which implies a bound on the one-way communication complexity of quantum learning, which bounds the *sequential-fat-shattering* dimension of the class (a generalization of the Littlestone dimension from boolean to real-valued function classes).  If the sequential-fat-shattering dimension is bounded then there exists an online learning algorithm which is robust to imprecise feedback (as must be the case for the training samples-measurements of quantum states), called Robust-SOA.   The authors then also prove that this online learner implies the existence of a learning algorithm that satisfies a type of stability, called quantum stability, which says that there exists a state such that the algorithm’s output is within a ball of this state with high probability.  Among others, a significant implication included in the results is a new bound on the complexity of shadow tomography which includes the sequential-fat-shattering dimension (sfat) instead of the number of qubits n (and sfat<=n for any class but there exist classes with sfat significantly smaller than n).