Private learning implies quantum stability
Authors: Yihui Quek
Srinivasan A
John Smolin
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Quantum learning theory
differential privacy
online learning

Abstract: Learning an unknown n-qubit quantum state rho is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in n many copies of rho to estimate its entries. Motivated by 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 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 to 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.

Private learning implies quantum stability
Srinivasan Arunachalam
IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, USA Srinivasan Arumachalam@i com
Yihui Quek
Information Systems Laboratory, Stanford University, USA yquek@stanford.co edu
John Smolin
IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, USA Smolin@us ibm. com
Abstract
Learning unknown n-qubit quantum state is fundamental challenge in quan- tum computing. Information exponential in many copies of p estimate its entries. Motivated by learning the- ory, Aaronson et al. introduced many (weaker) learning models: the PAC model learning states (Proc. of Royal Society A'07), shadow tomography (STOC' 18) for learning "shadows" " of 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 p. But there any relationship between these models? In this paper we prove sequence of (information-theoreee PAC learning online learning and then 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 aooolean-valuee concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first extend their work the real-valued setting, and further extend the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust adversaria imprecision. We then show informationntheorree equivalences between DP learning quantum states the PAC model, learnability quantum states 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.
Information-theoretiallf. theoretically, is known that tomography requires
implications from differentiallly-riiaas
Introduction
Learning unknown quantum state given copies of the state is fundamental task in quantum computing, often referred to as tomography. Tomography is of great practical interest since it helps in tasks such 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 lot of theoretical attention: how many copies of an n--uuii quantum state p are required to estimate the density matrix of up to small emrr? Recent
"hats://stanfor..cddd-vvyg
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

breakthrough results of 222 showed that @ /E2) copies of are necessary and sufficient to learn p up to trace distance E. 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
Simultancously, the use of machine learning for quantum states has gained lot of traction in quantum computing. In this area, the goal use heuristics learn an unknown quantum state, often with the motivation of physical implementation. Provable results in this area are very few, but interest 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 ! for a summary of our results.
1.1 Background: Models of interest
To explain our main results, 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 We also formally translate them to the classical learning setting in Supplementary material (Section A), which we omit here due to space constraints.
2.2
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 p E C be an unknown quantum state (picked from a known concept class C of states) and let D 3 [0, 1] be arbitrary unknown distribution over all possible 2-outcome measurements E. Suppose a quantum learner obtains training examples (E,, Tr(pE,)) where E, is drawn from D, and the goal is to output such that with probability 2 0.99, satisfies PrE-D[ [T(aa -)(((E) Tr(pE) < <) 2 1 a-a. How many training examples suffice for such a (C. PPPAC learner? In answer, he showed that the number of examples necessary and sufficient to learn C is captured by the fat-shatering 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 {EE, Tr(pE,)) S" {(E), Tr(pE,)) } such that there exists unique such that E, & E,, then a quantum (y, DD PAC learning algorithm needs to satisfy Pr(A(S) = o I ee Pr[A(S') = a] + 5, where A(S) is the output of A on input S.P S
Communication complexity. Consider the standard one-way communication model between Alice and Bob. Suppose Alice has quantum state (unknown to Bob) and Bob has an unknown (to Alice) measurement F. The goal of Bob is to output an approximation of Tr(pE) 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 p. 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 p, rather we may only be able to obtain sequential copies of it. The quantum
"Our notion of DP differs from the notion of DP proposed by 77. They consider DP measurements with respect class of product states, whereas here require DP with respect to the dataset {(E,, Tr(E.p) ).
2

---

online learning model addresses these aspects. Online learning consists of repeating the following rounds of interaction: learner obtains copy of p. maintains local a which is guess of p. obtains description of measurement operator F; (possibly adversarially) and predicts the value of V/ = F)) Subsequently it receives as feedback an 6-approximation of yi- On every round, if the learner's prediction satisfies (Tr(a Fg.) y/l S e then it is correct, otherwise it has made 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-valuee predictions ys. departs from the real-valued online learning literature in allowing for e --imprecision in the feedback. This imprecision inherent to all learning settings where the feedback 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-shuttering dimension of C (a combinatorial parameter which was originally introduced by Rakhlin et al.
Motivating question. All these learning models can be seen as variants of full-state tomography, and are known require exponentially fewer resources than tomography. A natural question is:
Is there relation between these learning models, communication and combinatorial parameters?
Understanding this question classically 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 [0] [2 [3] [4 [5 16 [7] just to cite 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- 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 differeentially-rrvaan quantum computation could look like [19 20) The second question indirectly received attention recently in NeurlPS'20 20 by Jung et al. [1]] 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 more in-depth comparison).
2
Overview of main results
2.1 Quantum results
To condense our (affirmative) answer to the first question above, we derive a series of implications going through all these models, starting from differentially-prinn quantum stability (our conceptual contribution which we define and discuss below).
PAC learning to online learning to
Taking step back, quantum online learning and DP PAC quantum learning seem very different on the surface. Online learning ensures that eventuully (after mistakes) we learn the state approximately, but makes no guarantees on when the last of in 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 summary of our results in Figure] T Also, we say an algorithm is pure DP (resp. approximate DP) when 5 = 0 in our definition (resp. 8 > 0). We remark that only few arrows are efficient in both sample and time complexity, otherwise these implications are primarily
coommation-thooretie
Conceptual contribution. The main center piece in establishing these connections is the concept of quantum stability, which the new conceptual contribution in this work. Intuitively, we say quantum learning algorithm is stable if, for unknown state p. given set of noisy labelled
3

---

Pure DP PAC
Representation dimension
One-way CC
Sequential fat- fat-shattering
Gentle shadow tomography
Approximate DP PAC
Online learning
Stability
no-go
*
Figure Summary results for learning real-valued concept classes and quantum states with imprecise feedback. Except for the +-arrow arrow A B implies that, if the sample complexity of learning in model A or the combinatorial parameter is SA. then the complexity of learning in model B or the combinatorial parameter B is Sg poly(SA). The dotted arrow signifies that technique used to prove that arrow for Boolean functions a no-go for our quantum learning setting.
examples from distribution D, there exists state such that, with "high" probability, the output of the learning algorithm "close" to a. More formally, we say quantum learning algorithm AA is (T, e, -tt-bbl with respect distribution D over of orthogonal 2-outcome measurements if, given 7 many labelled examples S consisting of E; drawn from D and (-approximations of Tr(pE.), there exists state such that
Pr(A(S) E (M(E, 2 7
(1)
where the probability is taken over the examples in S and (M o) is the ball of states E-close to with respect to M, i.c. BM(s, words, quantum stability means that up to an e-distance, there is some hypothesis state a that is output by A with "high" (at least 17) probability.
fo' (Tr(Eo) Tr(Ea') < e for every E e .M. In other
classical analog of stability can be written as: a classical learning algorithm for concept class C: X' [0, 1] (run examples {(x; ((x;))} where (ā(x;) c(x.)) S. C) is stable if there exists a hypothesis ʃ such that
Pr(A(S) f(, n.
where T(E, (g C: (: - f(x) < E 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 a, the output state at the 'center of the ball', is good hypothesis for estimating measurement probabilities (and hence A a good learner). This is not at all obvious from the definition of stability, which does inherently require that this is good approximation of p. 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 has seen), has low loss with respect D. This means that, using hypothesis a to predict outcomes of future measurements drawn from distribution D as Tr( Ear will yield e-accurate predictions with high probability.
2.2 Classical results
In order to see the connection to classical learning theory we first observe the following. Learning n-qubii quantum states over an orthogonal basis of r--uubit quantum measurements, M, 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 one-to-one mapping between the of all quantum states and the set of bounded real real-valued functions on M To elaborate, for every a, one can clearly associate a function fa : . - [0, defined (MM Tr(Mo) and for the converse direction. given an arbitrary e: .M- - [0, 1]. one can find density matrix for which el c(M) Tr( (((Ma) for all M E M (and this uses the fact that M is an orthogonal measurement basis crucially). Hence, if one can learn 'D when we fix the M to be an arbitrary orthogonal basis of 2-outcome measurements then one can learn the class quantum states C, and the converse also true.
IIndeed, in Section 4 of this paper, we slightly abuse notation; when C' is 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 different class label altogether, so are these results robust?
Our main contribution is thus in establishing all the arrows in Figure 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 [ were proven implicitly in [1], 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, 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.
3 Proof sketches for our main results (Fig.
We break down the proof' of the arrows in Figure D into four steps and discuss them below. Before this, we provide quick introduction to necessary quantum information theory.
Quantum information preliminaries. An n--ubit quantum state p is a positive semidefinite matrix with trace 1. An arbitrary valid quantum operation on quantum states can be expressed unitary matrix U (which satisfies UU* = U = 1). An application of a unitary U to the state p results in the quantum state U Finally, in order to extract meaningful classical information out of quantum state, one can perform a POVM (positive-operatee valued measurement) which is specified by a set of m positive semidefinite matrices E1,... Em satisfying Σ, E, 1. A measurement state p using such a POVM returns a classical outcome E [m] with probability Tr(E,p).
3.1 Pure DP PAC learnability implies finite sfat dimension
It is known that if there is a DP PAC learning algorithm for Boolean function class C then the representation dimension of the class 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 show that they 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 [ (denoted s-) 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.
3.2
Finite sfat(-) implies online learnability and resolving an open question of Aaronson
In the second step, the goal is to go from 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 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 sCat:(C) = d. There is an explicit robust standard optimal algorithm RSOA that makes at most d mistakes in online learning C.
5

---

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 generated by the learner itself by measuring E repeatedly on copies of the quantum state p. Averaging these measurements will provide a (-approximation of Tr(pZ) instead its exact value.
To accommodate this imprecision, we introduce the notion of an interleaved (-cover of the [0, 1] interval, f4. as the set of overlapping half-open intervals ('super-bins") of width 2 given by where | 1/5-1 1. We also define the following: given a set of functions V C (f X x -00 [0, E F2g and x E X, define a (possibly empty) subset V(r, x)) S V as V
{10, 25), ................................ [1 2(; 11} with the midpoints A (c.,(....,,1=
2Ç, r + 2 i.e.
V(r, 2) are the set of functions f E V such that ((x) is within 2ç-ball around r.
We present our RSOA algorithm in Algorithm We now make few comments regarding this result. Classically, for the Boolean setting. it 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- valudd 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 (C) many mistakes, even in the presence of adversarial imprecision of magnitude Ç.
Algorithm 1 Robust Standard Optimal Algorithm
Input: Concept class C C (S X' + [0, I]}, target (unknown) concept e E C, and Ç E [0, 1].
Initialize: V/2 + C
1: for = I,.... T' do
2: The leamnr receives Fa and maintains set Vi, set of "surviving functions".
3: For every super-bin midpoint F2g. compute the set of functions V((r,z)),
4: The learner finds the super-bin which achieves the maximum sfat(-) dimension
R4 (xx) = arg max sfatzę (Ve(r, E Fzc re.32c
5: Learner computes the mean of the set R4 (xte), i.e., Ur = [R((,,)] EvERo(O.)
6: The learner outputs ýt and receives feedback 2(x;).
7:
Update Ve+1 + {g V, [g(2,) -(x,,) $ {}
8:
end for
Outputs: The intermediate predictions ÿ, for t E [T] and a hypothesis f(z) = R1
The basic principle that underlies our RSOA algorithm is, keep track of set of 'surviving' functions, and after every round of learning, eliminate those which were grossly inconsistent with the adversary's 's feedback. In more detail: beforehand, the learner discretizes the function range [O, 1] into 1/5 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 proof of correctness, refer to Section B in the supplementary material.
Resolving an open question. Prior to our work, Aaronson g considered quantum online learning and showed that sfat(-) of all n--ubit 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 mistakes. However, their focus was on online learning with regret bounds, and so they didnn't t provide an explicit algorithm that achieves the sfat(-) mistake bound, but raised this question their work. Our Result 3.1 resolves their question, by showing that our RSOA is such algorithm.

---

3.3 Online learnability implies stability
We now show that if a set of quantum states has sfat dimension (i.e., can be online-learned with noisy measurements with d-many mistakes), then it can be learned by an (T = E E=") quantum- stable algorithm A satisfying Eq. (T)) That is, for unknown state p from this maline-lcarnable set, given (( ") m-many examples which consist of 2-outcome measurements E, from an orthogonal set M and e-accurate Tr(p there exists a a having low loss, such that Prş-DT (A(S) E (M(e,o)) 2 ed, We now state this formally in terms of real-valued learning.
1]. Let C {s= : X + [0, 11 be a concept class with sfatz; (C) = Let D X - [0, 1| be a distribution and let S = {(ar, [x:))) be a set of = =<- /e-mayy examples where I2 D and (ū(x,) - -c(xa) < Ç where E C is an unknown concept. There is (T,5-, (S)stablee learner G, that outputs g E B(f,() such that Præ(lf(x) -c(x) S 5) 1 - a.
Result 3.2. Let at S E [O,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 '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/robustt real-valued setting. Our stable learner in the result above is essentially the RSOA algorithm that we designed earlier, but run on 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 tailor the set of examples drawn from the original distribution D into new set S on which RSOA is guaranteed to succeed.
We prove this theorem in two steps: in step (1) we provide tailoring algorithm that defines distributions ext( (D, .)..... ext(D, (D, d) (where (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 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 large pool of T = Ç ç-d examples drawn from D, craft short sequence of ((1/C) 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 sCat((C) mistakes, it would have identified the target concept up to O()) prediction error.
Our technique for creating mistake examples differs from that of [0]. 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 Si (x) * f2(2)) Say (x = c(x) and f2(x) = c(x), then it suffices to append an example (which will be the mistake example) of the form (z, c(x)) S2, so that when SOA is now run on S2 (xc, 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 coin b E {0, 1} and with probability 1/2. 6 c(r). For us this does not work because our target function is real-valued, i.c. c(x) [0, 1]. Instead, we discretize [0, 1] into 1/C many (-intervals, pick uniformly random interval and let b be the center of this interval. Clearly now, with probability 1/C, c(x) lies in the Ç-ball around 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-valuse Cs, [10 went one step further and created approximately differentially-priinn learner from stable learner; in this sense, stability can be viewed as an
7

---

intermediate property between online learnability and differential privacy. A natural question here is, can we extend this result our setting, i.c., does quantum/robust stability in turn imply differential privacy? If so, then Figure ] 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 domain-size dependence. First observe that our "stability" " guarantees on 9 (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 E-accurate feedback from the adversary Since all functions that are in the g-ball of are consistent with the feedhack of the adversary, the learner cannot uniquely identify the target concept We thus allow the learner to output function in the e-ball around the target concept. This difference, however, also prevents us from applying the generic transformation from a stable learner to private learner employed in [0] we now explain !
That transformation first generates a list of hypothesis functions by running the stable learner & of Result 3.2 n many times, each of which outputs a function ft. By Result 3.2 and a Chernoff bound, one can show that with high probability, an n = 5dh -r-ffratioon of the list should lie B(C, f) for some f. Next one would like to privately output some function in BCC, f), i.e solve the following problem:
Problem 3.3 (Query release for function balls). Given as imput a list of n functions {fe X + R] Re an r-fraction of which satisfy (fa(x)) - (x)) S for all x, S X - IR ouiput some function g such that (g(z)) f*(x)) S for all x.
We also introduce the following related problem:
Problem 3.4 (Clique identification on a discrete domain). For domain y = [4] given as input relation R {(x. y) E ) x y || vll S 11 and a dataset D E y under the promise that (x.y) E R for all x. E D, output a 2 E ) such that (x. 2) E R for every x E D.
We give 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 22 26] and show that for 5 < 1/1500, every (1,8 < 1/n)-DP algorithm solving Problem 3.4 with probability at least 1499/ /1500 requires 2 Š2( (((v)). This implies that every (1, -DP 5 algorithm for Problem 3.3 requires n 2 5)( ). In particular, this lower bound is unbounded | 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.
Observe that Problem 3.4 reduces to Problem 3.3
Linking this discussion back to our motivating setting of quantum learning (see Section 2.2 when
M is the orthogonal basis of nt-qubit Paulis, then [M| 4th and so the above implies that one needs sample complexity (2(4/22) 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 T0,, 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 with M the orthogonal basis of n-qubit Paulis- with the Generic Private Learner, we discretize the [0, l]-range of D into bins of size Ç. obtaining a resulting function class H with size (1/c)²". Therefore the sample complexity of iifferentialll-priveel quantum learning is ((4").
Comparison to prior work (1). After completion of this work, we were made aware of the work by 11 (in NeurIPS'2O) While they extended the work of [00 to multi-class functions, they claim that their results also apply real-valued learning by discretizing the range of the functions (we
'The following argument was communicated to us by Mark Bun 23
'In differential privacy, we are typically interested only in values of 5 < 1/n, in order to rule out algorithms that simply pick point in their input uniformly and then process them in a possibly non- non-private manner.
8

---

couldn't 't find version of the paper that spells out the proof that online learnability implies 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- fat-shattering dimension which we also bound for the case of quantum states. Secondly, while [[]]s online and PAC learning settings assume that the learner receives exact real-valued labels, in all our learning models, we allow for s-imprecise labels. Thus, all our implications are robust to such adversarial imprecision (making our work closer to "classification-niis learning"). ). This additional consideration bars the usage of [10]ss 's technique, developed for Boolean functions as black-box. We discuss further differences between our works in the paragraph above Section D in the Supplementary material.
4 Faster algorithms for quantum state learning
Our previous sections were written for the general setting of robustly learning a real-valued function class. Now 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 p. i.e., given measurements Ei...., Em. how many copies of p suffice to estimate Tr(pE;) for all i E [m]. Aaronson surprisingly showed that On, log m) copies of suffice for this task (in contrast to the trivial tomography or sampling bound of ((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 p comes from set C) can be made (Csfat(C), logm). m).
Result 4.1 (Informal). There is (a, 8)-gentle (1 E) -accurate shadow tomography procedure for a set of states C using poly (sfat(C), log m, log(18))) copies of p.
This result relies on an observation of 7 that in RSOA) can be used as subroutine in gentle shadow tomography, where gentle can be viewed as proxy for privacy (albeit, the notion of DP here is with respect to states and different from ours).
-buunded online learning algorithm (we plug
2. A better bound on sfat(-). Let C. be the class of all n-qubit states. As we mentioned earlier, g showed that sfat(C,,) is at most (n). but clearly for subset C C C, of quantum states is possible that sCat(C) < sf.)(C.). In this direction, using techniques from quantum random access codes (which was also used before 5 31 32)
we first give 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 (Cat, S I-HØ maxgge x(EG), where x is the Holevo information and Eg is a uniform ensemble over the states in G.
Now, 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" [ i.e., each n-qubit state lives in the same unknown k- dimensional subspace. In this case it is not hard to that x(EG) is 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 class of quantum states and let N be a quantum channel. Let C² = (M(U)) : U E C) be the set of states obtained after passing through quantum channel N. Suppose the goal is to learn C' (i.c., to learn states that have passed through noisy channel N/). This connects to the question of experimental learning of quantum states, i.c., can we learn the unknown noise (or states) in noisy-quantun device. Here we show that sfat(C") < C(N). i.e., sC't is upper bounded by the classical capacity of N. Fortuitously, recent advances in quantum Shannon theory enable upper bounds on these previously co-mppue 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-variabl states.
k j-juntas are well-studied in computational leaming theory, wherein Boolean function on n bits is a k-junta if it depends on wnknown subset of & input bits.

---

4.1
Open questions
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 needs 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,
extend this also to the quantum regime, using the recently defined notion of quantum statistical query learning ? (4) Recently, [13] 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 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 W91 10-1144 YQ supported by the Stanford QFARM fellowship and an NUS Overseas Graduate Scholarship. JS and SA acknowledge support from the IBM Research Frontiers Institute.
References
[1] Ryan O' O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 899-912, 2016.
[2] Ryan O'Donnell and John Wright, Efficient quantum tomography II. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, STOC, pages 962-974. ACM, 2017.
[3] Jeongwan Haah, Aram Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628-5641 2017.
[4] Chao Song, Kai Xu, Wuxin Liu, Chui-ping Yang, Shi-Biao Zheng, Hui Deng, Qiwei Xie, Keqiang Huang, Qiujiang Guo, Libo Zhang, et al. 10-qubit entanglement and parallel logic operations with a superconducting circuit. Physical review letters, 199111180051,, 2017.
[5] Scott Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463((2088)3089--311 Sep 2007.
[6] Gregory R. Steinbrecher, Jonathan P. Olson, Dirk Englund, and Jacques Carolan. Quantum optical neural networks. npj Quantum Information, 5(1):60, 2019.
[7] Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 322-333, 2019.
[8] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Advances in Neural Information Processing Systems, pages 8962-89777 2018.
[9] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. In Advances in Neural Information Processing Systems, pages 1984-1992, 2010.
[10] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction, 2020. To appear Journal of the ACM. 3rXiv:2003.00563.
10

---

[11] Young Hun Jung, Backjin Kim, and Ambuj Tewari. On the equivalence between online and private learnability beyond binary classification. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS, virtual, 2020.
[12] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy, 2020. arXiv:2012.03893.
[13] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Proceedings of the S1st Anmual ACM SIGACT Symposium on Theory of Computing, pages 852-860, 2019.
[14] Olivier Bousquet, Roi Livni, and Shay Moran. Passing tests without memorizing: Two models for fooling discriminators, arXiv preprint arXiv: arXiv: 1902.03462, 2019.
[15] Mark Bun. A computational separation between private learning and online learning. Advances in Neural Information Processing Systems, 33, 2020.
[16] Alon Gonen, Elad Hazan, and Shay Moran. Private learning implies online learning: An efficient reduction. In Advances in Neural Information Processing Systems, pages 8702-8712, 2019.
[17] Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Conference Learning Theory, pages 119-152. PMLR, 2020.
[18] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. arXiv preprint arXiv:2006. 10/29, 2020.
[19] Li Zhou and Mingsheng Ying. Differential privacy in quantum computation. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 249-262, 2017.
[20] Yuxuan Du Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao. Quantum differen- tially private sparse regression learning, 2020.
[21] Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Conference on Learning Theory, pages 1000-1019, 2014.
[22] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new threshld algorithm. Machine Learning, 244) 1988.
[23] Mark Bun, Young Hun Jung, Backjin Kim, and Ambuj Tewari, 2021. Unpublished manuscript.
[24] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. In SIAM Journal on Computing Special Issue on STOC '14., STOC 144, page 1-10, 2014.
[25] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. SIAM Journal on Computing, 47(5): 100))188881988 2018.
[26] Thomas Steinke and Jon Ullman. Between pure and approximate differential privacy. 2015.
[27] Shiva Prasad Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 201
[28] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, STOC, pages 325-338. ACM, 2018
[29] Costin Bädescu and Ryan O'Donnell.
Improved quantum
data analysis, 2020.
arXiv:2011.10908.
[30] Yuin-Yuan&ua Huang, Richard Kueng, and John Preskil. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16:1050-1057, 2020.
11

---

[31] A. Nayak. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) pages 369-376, 1999.
[32] Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM (JACM), (9(4):496-514 2002.
[33] Srinivasan Arunachalam, Alex B. Grilo, and Henry Yuen. Quantum statistical query learning, 2020. arXiv:2002.08240.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Every statement in this submission is backed by an informal result statement, proof sketch followed by reference to the Supple- mentary material with detailed theorem statements and proofs.
(b) Did you describe the limitations of your work? [Yes] In the open problem section, describe certain limitations of this work, which could be improved as future work. Additionally, main contribution of this work is describing limitations of gen- eralizing known techniques from Boolean to real-functions which we address in Section 3.4.
(c) Did you discuss any potential negative societal impacts your work? [Yes] This is theoretical paper with no societal impacts. We have discussed the importance and relevance this work the age quantum computing and machine learning in the introduction between lines 24-48.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We are explicit about our classical and quantum learning models in Section 1.1 (Background) and Supplementary section A. All our results work in this framework.
(b) Did you include complete proofs of all theoretical results? [Yes) In Lines 200, 237, 292, 331, 357, we give explicit references to sections in the Supplementary material where we present complete proofs.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "kvmSzD-IOYt", "reviewer": "Reviewer_XTWD", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper makes solid technical contributions towards addressing the motivating question of relating different learning models. The learning models are designed with learning quantum states in mind and extend previous settings on exact feedback to imprecise feedback. The results answer an important question and make progress in understanding the complexity of learning quantum states. Overall the paper is well-written, and the following minor points might improve the clarity of the paper: 1) can the authors comment on the computational complexity of the RSOA algorithm? 2) does the improved bound on sfat() use techniques in the previous sections of the paper? It’s not clear to me how this is an application of the previous results, but it is a well-motivated task. \n\nPost rebuttal: I have read the authors' response and I intend to keep my score. I agree with reviewer C1db's point on clarifying the reduction, but overall I think this paper is above the acceptance threshold.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "di-qeYm9Pkl", "reviewer": "Reviewer_fFb9", "summary": "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.\n\nThe 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). \nIf 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. \n\nThe 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.\n\nAmong 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).\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reasoning behind the “pure DP PAC learning->online learning of quantum states->stability “ result follows a recent line of papers which prove that for the case of classification (Boolean function classes), DP PAC learning implies online learning which implies a type of stability, called global stability, which in turn, implies DP PAC learning, with the main quantity in these implications being the Littlestone dimension of the class. However, learning of quantum states seems to come with additional difficulties, since the classes are real-valued and the measurements are noisy (which leads to the online learning with imprecise feedback model and to the proposed “quantum stability” being an approximate version of global stability). Getting over these challenges seems to require many new (intermediate) results and connections, which could also be of independent interest, especially given that the paper considers many different types of learning models and combinatorial quantities, not necessarily tied to quantum learning.\n\n=============\nI have read the authors' responses and still think that overall this paper's results merit acceptance. I also found the paper a bit hard to read in places but cannot come up with concrete suggestions, since the issue seems to be the breadth of results and the effort to compile them together is clear. I do second adding clarifications to the reduction as per Reviewer C1db's comments. Finally, (again, not having changed my opinion on the paper) I think it is beneficial to refer to the recent paper \"Differentially Private Nonparametric Regression Under a Growth Condition\" by Noah Golowich which appeared at COLT 2021 : it studies private learnability in the real-valued domain and gives a relaxed sufficient condition, compared to Jung et al, which includes the eta-sequential-fat-shattering dimension.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "LutG-Z2ClaC", "reviewer": "Reviewer_C1db", "summary": "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:\n - 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\n - 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\n - A no-go result for (one approach for) converting stability to approximate PAC learnability\n - An improved shadow tomography result with sample complexity in terms of the sfat dimension\n - Bounds on the sfat dimension of quantum state classes in terms of Holevo information\n\nMany 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The motivation for this work is primarily to obtain an improved understanding of online learning and shadow tomography of quantum states, as well as to see what the consequences of Bun et al's breakthrough are for the quantum setting. Along the way, one is naturally forced to first consider learning of real-valued functions, and much of the paper deals with generalizing existing results to the real-valued setting with \"imprecise feedback\". This requires technical care in some places, but to a large extent seems to be reasonably straightforward. These generalizations are arguably not too surprising, but it is still good to have them established.\n\nThe authors define a kind of private analog of PAC learning quantum states that is a natural theoretical extension of classical private learning, but privacy for quantum states does not seem particularly well-motivated in its own right, or at any rate could use some more discussion and motivation (other than that it implies other things such as one-way communication and online learning, which is certainly nice).\n\nThe RSOA algorithm and its mistake bound in terms of the sfat dimension seems to follow similar ideas to Rakhlin et al's FAT-SOA and indeed Littlestone's original SOA. The proof that online learning implies stability roughly follows Bun et al's elegant approach, except with some definite extra care to handle the real-valued setting properly. The characterization of one-way communication in terms of sfat dimension seems quite interesting, although I do not have too much knowledge of this area. The applications to quantum state learning, especially shadow tomography and online learning, are definitely interesting and make concrete progress in directions suggested by Aaronson et al. The no-go result for online learning implying (approximate) private learning is a little unfortunate, as this was perhaps the main point of Bun et al 20 (although see my question under Limitations below).\n\nThe writing is mostly reasonable but not always fully clear, although I do appreciate that the authors have a tricky job on their hands with the scope of this paper and the space constraints. There is some looseness with technical language in a few places. For instance, the definition of stability says \"$A$ is stable with respect to distribution $D$ if, given a sample $S \\sim D^T$, there exists a state $\\sigma$ such that ...\" -- but this makes it sound as though $\\sigma$ depends on $S$ when in fact it only depends on $D$. That is, it should be something like \"$A$ is stable wrt $D$ if there exists $\\sigma$ such that whp over sample $S$ ...\". (I had to read the original definition in Bun et al to clarify this for myself.) Also, it is a bit confusing that $\\mathcal{M}$ is used sometimes to denote all 2-outcome measurements and sometimes just an orthogonal basis; it would be nice to use different letters just for clarity.\n\nOverall, there are many results in this paper, and many of them answer natural questions. Some of them are unsurprising and not necessarily highly original, but have value regardless. With everything added up, this paper definitely makes significant contributions to the area. I did not verify every proof but did try to look over the main ones; I also do not claim familiarity with all of the areas touched upon.\n\nUPDATE: Following discussion with the authors,  I understand the reduction better now but definitely still think it calls for more careful exposition. Overall I continue to think this is a good paper and merits acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not aware of any potential negative societal impact of this work, which is primarily theoretical.\n\nI am a bit confused about the no-go theorem between quantum/approximate stability and approximate DP PAC learnability. The claim is that the approach of BLM20 cannot work (in a domain size-independent way) because it amounts to \"query release for function balls\" (Problem C.7), which is sufficiently general that clique identification (Problem C.8) (shown to be hard in Claim C.9) can be reduced to it. But this reduction seems to obscure the fact that the type of access to the input seems quite different between the two problems. In clique identification, the algorithm is presumably only told that a size-$n$ clique $D$ _exists_ and must find it using access only to the relation graph, whereas in the instance of \"query release for function balls\" naturally generated by the BLM20 approach, the set of functions $\\\\{ f_i \\\\}_{i \\in [n]}$ is very much at hand. If this were the clique (and note that the reduction has $\\eta = 1$, so all the functions are in the clique), then one could just output any one of these functions (uniformly at random to ensure privacy, I would think) and one has found the clique trivially. Put differently, \"query release for function balls\" seems trivial in the $\\eta = 1$ regime generated by the reduction; the reduction would only seem to make sense if the query release algorithm could not see the functions as part of the input. I may be misunderstanding something, and would appreciate it if the authors could clarify exactly what is happening. (Incidentally, it would be good to be more careful about the use of the word \"given\" in Claim C.8 so as to distinguish the assumptions made in the problem versus the input the algorithm is literally given. Similarly with the term \"special case\": a more explicit reduction would be helpful.)\n\nAt a higher level, probably my main (subjective) quibble with the paper is that it feels a little unfocused and is perhaps attempting too many different things. It feels a little hard to take away a set of clean insights, and I do think that despite the collection of nice results this lack of focus is a limitation. I wonder if the paper would have been well served by being split into two roughly-standalone parts, one for the real-valued generalizations and another for the quantum applications. It is likely difficult to make any such changes for this conference, but it could be something to keep in mind when making edits.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JjqPQNfcG1", "reviewer": "Reviewer_uKof", "summary": "The paper develop a series of relationship between quantum learning model. \n(1) Pure DP PAC learnability implies finite sequential fat shattering dimension.\n(2) Finite sequential fat shattering dimension implies online learnability\n(3) Online learnability implies certain notion of quantum stability.\n(4) quantum stability may not implies approximate PAC learnability.\n\nThe 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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: It is certainly exciting to see the relationship between quantum learning class, and as far as I know, this is the first paper that intends to show such equivalence between quantum learning class (although the classical counterpart has been well-studied) The proof is also non-trivial.\n\nDrawback: From my view, the major unsatisfactory of this paper is that the implication (from online learnability) stops at the level of quantum stability, but the major breakthrough of Bun, Livni and Moran (Journal of the ACM'21) actually takes a step further and showing (classical) stability implies private PAC learning. Though the later step is not the technical core of BLM'21 and this paper proves such implications do not hold in quantum regime, it weakens the conceptual contribution of this paper, as it is not clear afterwards why quantum stability is interesting.\n\nSummary: Overall, I think this is a nice paper, but I hope the author could response to my comment above (drawback), and it might be good to put this into discussion or open questions.\n\n\nI have read the author's response and my evaluation stays the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "looks good", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Bun, Livni and Moran recently proved that finite littlestone dimension implies private (approximate) PAC learning of a Boolean concept class. This paper generalizes it to 1) learning real valued functions instead of Boolean valued functions and 2) to learning quantum states. In the process, the paper discovers several interesting relationships between different models of learning and points out an interesting "no-go" theorem for relating a (natural notion of ) quantum stability to online learnability. 

The paper makes fundamental connections between learning models: both positive (by translating algorithmic results) and negative (by exhibiting counter-examples for what might be natural conjectured relationships). The reviewers had a high opinion of the paper and authors' response and the ensuing discussion clarified what makes the no-go theorem between quantum stability and private learning non-trivial.   We recommend acceptance.  
Decision: Accept (Spotlight)