On the Role of Entanglement and Statistics in Learning
Authors: Srinivasan A
Vojtěch Havlíček
Louis Schatzki
Venue: NeurIPS 2023 poster (2023)
Keywords: Quantum Computing
Statistical Learning
Quantum learning theory
Entanglement
TL;DR: We show an equivalence between entangled and separable exact learning, exponential separation between quantum statistical queries and noisy measurements, and generalize known limitations on quantum error mitigation and learning distributions.

Abstract: In this work we make progress in understanding the relationship between learning models when given access to entangled measurements, separable measurements and statistical measurements in the quantum statistical query ($\mathsf{QSQ}$) model. To this end, we show the following results.

$\textbf{Entanglement versus separable measurements.}$ The goal here is to learn an unknown $f$ from the concept class $\mathcal{C} \subseteq \{f:\{0,1\}^n\rightarrow [k]\}$ given copies of  $\frac{1}{\sqrt{2^n}}\sum_x \ket{x,f(x)}$.  We show that, if $T$ copies suffice to learn $f$ using entangled measurements, then $O(nT^2)$ copies suffice to learn $f$ using just separable measurements. Additionally, we exhibit a concept class $\mathcal{C}$ for which, in order to learn some \emph{property} of $f$, the sample complexity of learning using entangled measurements is exponentially smaller than separable measurements.

$\textbf{Entangled versus statistical measurements}$ The goal here is to learn a function $f \in \mathcal{C}$ given access to separable measurements and statistical measurements.   We exhibit a concept class $\mathcal{C}$ based on degree-$2$ functions that gives an exponential separation between $\mathsf{QSQ}$ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of (Blum, 2003) that separates classical $\mathsf{SQ}$ learning from classical $\mathsf{PAC}$ learning with classification~noise.

$\textbf{$\mathsf{QSQ}$ lower bounds for learning states.}$ The main technical contribution is to introduce a quantum statistical query dimension ($\mathsf{QSDA}$), which we use to give lower bounds on the $\mathsf{QSQ}$ complexity of learning. Using this, we prove exponential $\mathsf{QSQ}$ lower bounds for testing purity of quantum states, learning CCHL states, coset states of Abelian groups, degree-$2$ functions, planted bi-clique states and learning output states of Clifford circuits of depth polylog($n$).

$\textbf{Further applications.}$ Using our $\mathsf{QSQ}$ lower bounds give an $\textit{unconditional}$ separation between weak and strong error mitigation and prove lower bounds for learning distributions in the $\mathsf{QSQ}$ model. Prior works by (Quek et al., 2022), (Hinsche et al., 2022), and (Neitner et al., 23) proved the analogous results $\textit{assuming}$ diagonal measurements and our work removes this assumption.

On the role of entanglement and statistics in learning
Srinivasan Arunachalam
Vojtëch Havlíček IBM Quantum
IBM Quantum
Almaden Research Center
TJJ. Watson Research Center
Srinivasan Arunachal am@i bm. com
Voch. Havl wewlicckkibb.. com
Louis Schatzki
Electrical and Computer Engineering University of Illinois, Urbana-Chane Chaaaa--hammpiin louisms20i11 www.mm201llmmmm wwwilliiiii.....i. edu
Abstract
In this work we make progress in understanding the relationship between learning models when given access to entangled measurements, separable measurements and statistical measurements in the quantum statistical query (QSQ) model. To this end we prove the following results
1. For learning Boolean concept classes, we show that the entangled and separa- ble sample complexity are polynomially related.
We give concept class that shows an exponential separation between quan- tum PAC learning with classification noise and QSQ learning. This proves the "quantum analogue" the seminal result of Blum et al. [ that separates classical SQ learning from classical PAC learning with classification noise.
3. The main technical contribution is to introduce quantum statistical query dimension (QSD), which we use to give lower bounds on the QSQ learning. Using this, we prove exponential QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted bi-clique states and learning output states of Clifford circuits of depth polylog(n).
Using our QSQ lower bounds, we give an unconditional separation between weak and strong eтror mitigation and prove lower bounds for learning dis- tributions the QSQ model. Prior works by Quek et al. [2), Hinsche al. (3] and Neitner et al. [4] proved the analogous results assuming diagonal measurements and our work removes this assumption.
Introduction
In the last few decades, machine learning (ML) has emerged as of the most successful parts of artificial intelligence with wide-ranging applications in computer vision, image recognition, natural language processing. More recently, ML has been used in popular applications such as AlphaGo and Alpha zero (to play the games Go and chess), chatGPT (to mimic a human conversation) and Alphafold (for solving some hard instances of protein folding). Simultaneously. understanding the power of quantum physics for ML has received much attention in the quantum computing community. There have already been many theoretical proposals for quantum algorithms providing speedups for practically relevant ML tasks such as clustering, recommendation systems, linear algebra, convex
optimization, SVMs, kernel-based methods, topological data analysis [5 There are several surveys dedicated to understanding the power of quantum methods for ML
15 18
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Quantum learning theory provides a theoretical framework to understand quantum ad advantages in ML. Here, there a concept class C. which is a collection of n-qubit quantum states, a learner is provided with several copies of a state p E C, performs an arbitrary entangled operation on po and the goal to learn p well-enough. This framework encompasses several results in quantum learning such as tomography, shadow tomography, learning interesting classes of states, learning an unknown distribution and functions encoded as a quantum state 219 3 2 177
Given that machine learning is believed be one of the first near-term applications of quantum computers, a natural question is how implementable are these algorithms in order to see quantum computational advantage in practice? The concern when considering near-term implementation of the above learning algorithms is twin-fold, (i) the infeasibilty of preparing copies of P and (1i) performing arbitrary entangled measurements on many copies of p at once, both of which seem out of reach for near-term devices. Motivated by near-term implementations, recently (27 introduced the model of quantum statistical query (QSQ) learning to understand the power of measurement statistics for learning, inspired by Kearns [28] classical SQ model. Since its introduction, variations of it have found applications in differential privacy, quantum supremacy, quantum neural networks, learning distributions and error mitigation [2 B1) In the QSQ model, learning algorithm can two-outcome measurements {M, M. and the goal is to learn the unknown P well enough using the measurement statisties. Clearly this model is weaker than that given access to p.T since the learner is only allowed access to expectation values over single copy of p. Given that recent works error mitigation have shown that good estimates of expectation values may be accessible well before tolerant quantum computation 32 33) understanding the power of QSQ algorithms of fundamental importance.
perform poly(n (n) -ann sifcieentl-impllmeent
In this work, we primarily consider concept classes constructed from Boolean functions. In Valiant's PAC learning framework, the goal is to learn a concept class C C fe: 13 + (0. 1] In the PAC model a learning algorithm is given many uniformly random (x' c* (x')) where e* E C is unknown and it uses these to learn c* approximately well. Bshouty and Jackson introduced the quantum PAC (QPAC) model [34] wherein quantum learner is given quantum examples )
ie., coherent superpositions |bb-)) = Vzm Σn [z, c² (z)), and needs to learn the unknown c* E well enough. The complexity measure here is the sample complexity, i.e., copies of classical or quantum examples used by the algorithm. There have been works that have looked at this model and proven positive and negative results for learning function classes (see 17 for a survey).
setting it is known that PAC and QPAC have the same sample complexity (35. However, the same need not be true in the distributtinn-dpendeen setting, where, for example, quantum learners can efficient learn DNF formulas over the uniform distributions [34]. Second, it is a well-known fact that the classical statistical query (SQ) model is exponentially--sparaae from PAC learning as witnessed by the class of parity functions [28]. However, in (27 they show that parities can be learned in the QSQ model efficiently. In fact, in (27 they observed that, many positive results using quantum examples can be transformed into algorithms in the weaker QSQ framework. This motivates the following questions:
Relationships Between Models. First, in the distribution-independde
1. Do entangled measurements offer any advantages in learning function classes?
2. Do measurement statistics suffice for learning function classes, i.e. is there a separation between QSQ and QPAC?
Here, we resolve both these questions. We show that (i) for learning Boolean function classes the sample complexity of learning with entangled measurements and separable measurements are polynomially related, thereby showing that separable measurements are sufficient to witness quantum speedups in practice and (ii) there is an exponential separation between learning with entangled mea- surements (even in the presence of classification noise) and learning with just measurement statistics, thereby showing that just measurement statistics might be insufficient to witness quantum speedups in practice.
1.1
Main results
We now give detailed description of our main results before we give an overview of their proofs in the next section.
For simplicity, we discuss PAC learning under the mniformmdistributien i.e., x is uniform in 10"

---

Entangled versus Separable measurements. Since entangled measurements are vastly more difficult to realize experimentally, much recent work has gone into characterizing the limitiations of separable measurements. Bubeck et al. [36 gave a property testing task for which entangled measurements are necessary for obtaining the optimal bounds. More recently, for learning classes of arbitrary quantum states (i.e., not necessarily states constructed from function classes), two recent works by 126, 37 showed exponential separations for learning properties of quantum states with entangled vs separable measurements. Here, we study if similar separations exist when considering function classes, a small subset of all quantum states. Our first result shows that in order to exactly learn function class, every learning algorithm using entangled measurements can be transformed into a learning algorithm using just separable measurements with a polynomial overhead in sample complexity.
Result 1. For concept class C S {c: [0,1]* + {0, 1}}, iST copies of (ba) suffice to learn an unknown e C, then OnTT²) copies to learn e using only separable meusurements,
QSQ versus noisy-QPAC learning. Classically, Kearns posed the question SQ learning equal to PAC learning with classification noise. The seminal result of Blum et al. [ resolves this question by showing that the class of parity functions acting on the first O(log log log n1) bits separates these two models of learning (under constant noise rate). In [27]. the authors asked question if there a natural class of Boolean functions for which, QSQ learning can be separated from QPAC learning with noise (in fact, prior our work, no separation Classically it is well-known that parities separates SQ learning from PAC learning. In [27], it was observed that the class of parities, juntas, and DNF formulas learnable in the QSQ framework, leaning no clear candidate to separate QSQ from QPAC. This motivates the following questions:
known even in the presence of noise).
(a) In the noisy-quantum PAC model
learning algorithm is given copies of 34
35
W
- (V + V (z)));
/
(0
and the goal is learn c*. Is there class that separates noisy-quantum PAC from QSQ learning?
(b) Admittedly, the class constructed by Blum et al. [ is "unnatural", can we obtain the separation in (a) for natural concept class?
Does such separation hold for non-constant error rate 1/?
Here, we describe natural problem that witnesses this separation, resolving the three questions.
Result 2. The concept class C = {fA: : {0, + f0, 1} fa(z) T Ax (mod 2), A E FnX"} of all degree-2 Boolean functions can be (exact) learned using quantum examples and separable measurements even in the presence of r-classification noise in time poly(n, 1/(1 2n)), whereas every QSQ algorithm requires 20n)) queries to (approximately) learn C.
Further applications. While we first considered learning function classes, the QSQ model is meaningful for a much broader class of tasks in quantum information theory and to that end we prove the following: (a) we show hardness of shadow tomography (quadratically improving the prior bound (26 for separable measurements) and show hardness of even the simplest Abelian hidden subgroup problem in the QSQ model; (b) we give ceaubly-exponentii lower bound for testing purity of an unknown state; (c) we give an exponential separation between weak and strong error mitigation and (d) we give superpolynomial lower bounds for learning output distributions of quantum circuits (when measured in the computational basis). Prior works 2 considered tasks (c), (d) and showed
these separations when the QSQ queries correspond diagonal measurements, and we remove the diagonal assumption here. We discuss this further in Section 4.2
2 Models of learning
We discuss the learning models of interest in our submission this section. For quick introduction to quantum information notation, we refer the reader to Section i the Supplementary material. In all models, we are primarily interested in improper learning, i.e. the learner need not output a state or function from the concept class.
3

---

Classical PAC learning. Valiant [38] introduced the classical Probably Approximately Correct (PAC) learning model. In this model, a concept class C C (c: [0, - {0. 13} is collection of Boolean functions. The learning algorithm A obtains labelled examples (2t, e(x)) where x E {0. 1 uniformly random and c E C is the unknown target function P The goal of an (c, 5--earnnggg algorithm A is the following: for every e E C, given labelled examples {(x (<=")((=')), with probability
21-6 6 (over the randomness of the labelled examples and the internal randomness of the algorithm), for hypothesis h {0, 1 + {0, 1 such that Pra (e(z) h()] 2 - E. The sample complexity and time complexity of a learning algorithm the maximal number of labelled examples and time used by the optimal learning algorithm respectively.
outputs succint sirciitrrpreseentain
Quantum PAC learning. The quantum PAC model was introduced by Bshouty and Jack- son 34 wherein, they allowed the learner access to quantum examples of the form (+be) = v2 Ere(a. [a, c(z))) Like the classical complexities, one can similarly define the (c, -ssmple and time complexity for learning C as the quantum sample complexity (i.e., number of quan- tum examples (15,) used and quantum time complexity (i.e., number of quantum gates used in the algorithm) of an optimal (e, ()-larrrrr for C. Similarly, Bshouty and Jackson [4 de- fined quantum learning with classification noise, wherein a learning algorithm is given access to + vnle(z))), Such quantum examples have been investigated
1x-2) = / Σg [z) &
in prior works 34 35 39
Learning with entangled versus separable measurements. Observe that in the usual definition of QPAC above, a learning algorithm is given access to (+)))T and needs to learn the unknown e E C. In this paper we make the distinction between the case where the learner uses entangled measurements, i.e., perform an arbitrary operation on copies of (&)) versus the setting where the learner uses separable measurements, i.e., performs a single-copy measurement on every copy of W/) in the learning algorithm. When discussing learning with entangled and separable measurements. in this paper we will be concerned with exact learning, i.e., with probability 2 2/3, the learner needs to identify c. We denote EntExact the sample complexity of learning with entangled measurements and SepExact as the sample complexity of learning with separable mcasurements.
Quantum statistical query learning. We now discuss the QSQ model, following the definitions given in 27. More generally, in order to learn unknown quantum state p. in the QSQ model, the learner makes Qstat queries that take as input a bounded linear operator M over the Hilbert space of p, satisfying |M]] < 1, and tolerance and outputs a r-approximation of Tr Tr(Mp), i.e.
Qstat: (M,r) + a E [Tr(Mp) -, Tr(Mp) + +r]
The goal of the QSQ learner is: with probability 2 1-6,, output succinct description of a state a such that lpp iip-olly I. S E. In order to learn function class using quantum examples, we have p = ( and on input M, the Qstat oracle responds with a E [K Mbby) - T, ( M + 7].
In this case, the goal of a QSQ learner is to output a hypothesis h that satisfies (I (wb,, (()) S E, which translates to Pr.. (r=:) = [[x))] 2 Ve. The query com- plexity for learning C, denoted QSQ(C), is the number of Qstat queries an optimal algorithm makes and the quantum time complexity is the total number of gates used by an optimal algorithm (which includes the gates to number of gates to implement M). We say a n-bit concept class C is QSQ learnable if C can be learned using poly(n) many Qstat queries, each with tolerance 5 1/ poly(n) and observable M which is implementable using poly(n) many gates. There are three ways to motivate the QSQ model
From theoretical perspective, performing 2-outcome measurements easier to implement than arbitrary separable measurements, which is in turn casier to implement than entangled measurements, so is useful to understand the power of expectation values in quantum learning theory and the QSQ captures this question in theoretical framework 3
2 MMore generally in PAC learning. there an unknown distribution {0, 11tt + [0, 1] from which drawn. Throughout this paper we will be concerned with uniform-distribution PAC learning, i.c., D is the uniform distribution, so we describe the learning model for the uniform distribution for simplicity.
Cllerlly any binary measurement (M, 7 M) can be simulated with Qstat query M or T- M. In the opposite direction, any observable M such that || || < 1 can be converted into the POVM { (1,M I-M Thus, Qstat queries detined above and binary POVMs are essentially the same model.

---

2. We emphasize that QSQ learner is a classical algorithm since it receives statistical estimates of measurements on quantum states. One could envision framework of learning where quantum states are prepared in the "cloud" and a classical learner needs to interact with the cloud only classically: QSQ models such a quantum framework.
3. Most quantum complexity classes are defined by making a binary measurement on a read- out qubit. This can be readily subsumed into the QSQ framework. The QSQ model also naturally extends recent works 24 wherein they consider the limitations of classical SQ in the setting where M = Σ2 (2)) is diagonal.
4. QSQ naturally generalizes SQ. That is, one can think of QSQ as being a form of statistical learning where the learner can change the basis of their statisties. Indeed, SQ corresponds to the case when all queried observables are diagonal.
Some positive results in QSQ In quantum learning theory, there are a few well-known function classes that are learnable using quantum examples: parities, juntas, DNF formulas, the coupon collector problem, learning codeword states. It was observed in 335 that the first three classes are learnable in QSQ already, primarily because version of Fourier sampling is implementable in QSQ. In this work we first observe that the coupon collector problem and learning codeword states are also learnable in the QSQ framework. We next observe that the class of Fourier-sparse functions are QSQ learnable (which subsumes all the positive results in (27)).
The class of k- k-Fourieer sparse functions, the class of codeword states, coupon collector problem can be learned in the QSQ model.
Theorem 1.
Beyond learning example states, we next observe that one can do tomography on the set of trivial states, i.c., states (b) C'(O)) where C is a constant-depth n--ubiit circuits. in polynomial time in the QSQ model. An open question of this work, and also the works of [3] 4. is if we can learn the distribution Pa = { (ar ) } using classical SQ queries. The theorem below shows that
we had direct access to (15), one can learn the state and the corresponding distribution Pc, using Qstat queries.
Theorem 2. The class of n-qubit trivial states can be learned up to trace distance S using poly(n, 1/e) Qstat queries with tolerance poly(e/n).
For further details we defer the corresponding proofs to Section 5.1 in the Supplementary material.
3
Proof of results
In this section we outline the proof our two results.
3.1 Proof overview for Result
Our starting point towards proving this result is that one could use result of Sen [40 that, given copies of [v)e-), one could apply random measurements on single copies of this state and produce an h that is approximately close to c* using at most T (log |C')/e copies of > So, for separable learning, by picking ε = Mmin as the minimum distance between concepts in C, one could exactly learn C' using T quantum examples. Proving lower bound on entangled learning C is fairly straightforward as well: first observe that (log [CI)/m is a lower bound on learning (since each quantum example gives bits of information and for exact learning one needs M(log (C]) bits of information) and also observe that 1/1min is a lower bound, since to distinguish just between c, d' C that satisfy [c(x) c' (x)] = -mmin so needs 1 1/Timin copies of the unknown state. Putting this separable upper bound and entangled lower bound together gives us SepExact(C)) < EntExact(C)² for all C. This relation is however sub-optimal.
We further improve the entangled lower bound as follows. Let 1/s, = Ee,ete (ra(((() + dx)))-
We use a inforriaiin-theeretie argument (inspired by a prior work (35)) as follows: define a random variable A, B and the quantum state PA.B = Eoec |c) (c) & \//c)) ( @k (assuming that k is the sample complexity of EntExact). For exact learning we know that [(A B) =(ooog |C]) again because one
needs to learn A exactly. Next we know that 7(A: B) < le I(A: B1) (where B, corresponds the
'This idea was used in an earlier work of Chung and Lin 41 as well, but they weren't 't concerned with entangled and separable measurements.
5

---

first register in B1). Now using a non-trivial analysis, one can analyze the reduced density matrix on the subsystem A, Bj and analyze its eigenvalues show that [A :,) I mna. Chaining these inequalities gives that EntExact 2 max (1 /Tmm (log (mm)/(mm)) Combining this entangled lower bound with the separable upper bound, we get that
SepExact & 0(n EntExact min {Na/ mm EntExact))
For further details we defer the proof Section in the Supplementary material. It is not hard that this relation is optimal as well for the class of degree-2 functions defined as
C = (x) AA
Aa
(mod 2) : A E F2 1
(2)
For this class 77 = 7/m = -1) by the Schwartz-Zippel lemma. Recently it was shown [24] that SepExact (n²2) and EntExact = (n) showing the optimality of our relation above.
3.2 Proof overview for Result
3.2.1 Technical contribution.
A fundamental issue in proving QSQ result is, what techniques could one prove these lower bounds? Prior to our work. in (27) they introduced two new techniques based on differential privacy and communication complexity that give lower bounds QSQ complexity. However, both these lower bounds are exponentially weak! In particular, the lower bounds that they could prove were linear in for learning n-bit concept class. Classically, there have been sequence of works [42]- 44 with the goal of proving SQ lower bounds and finally the notion of statistical dimension was used to obtain close-to- to-tttimal bounds for SQ learning certain concept classes and the breakthrough works of [44] used it to settle the complexity of learning the planted k-bicliqqe distribution.
this work, our technical contribution is a combinatorial parameter to lower bound QSQ complexity akin to the classical parameter. To this end, we follow three-step approach.
1. Reduction to Decision Problems. We show that algorithm A that learns concept class below error in trace distance using Qstat queries of tolerance T can also be used to solve the following decision problem: for fixed such that min (p, o)) 2(7 ++), s), decide if an unknown state is either some E C or equals a. Calling QQC the complexity of such decision problem, we show that
QSQ(C) 2 max (ax((QQ((Co)) 1 min (r, 2(T + DEC
2. Quantum Statistical Dimension. Next, we define the notion of quantum statistical di- mension QSD: for 7 > 0, a class of states C and a a $ C, the QC,,(C,o) is the smallest integer such that there exists a distribution v over Qstat queries M satisfying P (p o))l > r] 2 1/d for all C. From an operational perspective QSD is natural, it can be viewed
the smallest expected number of observables that can distinguish all states in C from a. We then show that if the decision algorithm succeeds with probability at least 1 have that:
QQC(C, σ) (1 (E1-26)QSSD.AA 26))SD)
3. Lower Bounds on QSD. Even with this lower bound, proving bounds on QSD(C, a) non-trivial. To this end, we further give two lower bounding techniques for QSD(C, .r) one based on the variance of Qstat queries across (inspired by the work of Kearns (28) and one based on average correlation (inspired by the work of Feldman (43). In particular, define two combinatorial quantities Var(C) and QAC(C, a) which can be associated with every class and it lower bound QSD.
Let μ be distribution over C, such that 01 Epl $ C. We define Var(C) as follows:
Var(C) = = min
(3)
M.J
pmia
where
Var Tr(pP)] = Tr(pM)? - (Tr(pM)))² p-p
Pmop
pmeps

---

We show that QSD, 01) 2 Var(C), which we eventually use to lower bound QSQ(C). Next, for 02 & C. we define the average correlation QAC(C, 02) as
QAC(C,
sup (x? #e7-frac(Co, o2))=1 Co cc
where x²? neZ-frac(Co, 02) is combinatorial parameter capturing correlations between states in Co and d2 We then show that QC,,(C,o2) 2 QAC(C, 02) and use this in turn to lower bound QSQ(C)
Putting together the three bullets above, the QSQ complexity of learning can be lower bounded by the variance bound and the average correlation bound that we define in this work. We remark that although, our quantum combinatorial parameters are inspired by the classical works of Feldman et al. (42-44), proving that they lower bound QSQ complexity and also giving lower bounds for the corresponding concept class using these parameters non-trivial and is key technical contribution of our work. Below, we apply these lower bounds to obtain our learning results. For further details we defer the formal definitions and proof' to Section 3 in the Supplementary material.
3.2.2 QSQ versus noisy QPAC
We now sketch the proof of Result As mentioned carlier, previous to work we did not have candidate class to separate QPAC from QSQ (Iet alone with noise). There have been a few works that have shown exponential lower bounds for learning using separable measurements 26 37 45
but
all these lower bounds correspond to learning classes of mixed quantum states. Hence was open if there is very simple structured function class such that quantum examples corresponding this function class is hard for QSQ (in fact given our polynomial relation between entangled and separable learning, it is conceivable that for the small class of function states, QSQ are QPAC are polynomially related as well). In this work, we look at the degree-2 concept class C defined in Eq. (2).
Recently, was observed that [24] this class is learnable using (1)) quantum examples with entangled measurements and (n²) quantum examples with separable measurements. Our main contribution is in showing that the QSQ complexity of learning C with tolerance 7 is 0(2n/22 79). When = 1/ (nly(n) this is an exponential, 20(n), lower bound. We prove the hardness for algorithms using Qstat queries using the variance lower bounding technique. particular, we show that for every + 1 qubit operator M such that || < we have that
(Tr 1) ((2
(5)
where we let , = |w/ (ub+l for notational simplicity. Combined with our variance lower bound
introduced in Section 3.2.1
we obtain our lower bound the QSQ complexity of learning C. It To this end, we need to understand
remains to establish Eq.
5
Var f (Tr(M)))))) EE [Tr [Tr[M (Hy[T+[M+)]))
(6)
To do so, we decompose b as follows. For every f {0, 13a - {0, 13 let (/5) v2th lx,
E f(x))
and (ob,) (-1)((x)) For convenience we let |u) V2" En lz)). Then see that
(eb)) ( = 2 (0r) & 1-X-1 ( & x
lu) (orl o |+ @
pf
p
o
We now note that any + qubit observable M can be decomposed as M = En, Ma,s & |a) (b) where now a, b (+,-), Since |M < also have that ||Ma, S 1, however the off- diagonal blocks now no longer need be Hermitian. In an abuse of notation we now discard the
last qubit of p and denote the resulting state also as p For ease of notation we further introduce
the notation M1 M_.-. M2 M_,+, M3 = M+.,, and M1 M+.+ Thus, we see that
Tr[Myy] = $ >. T and further the variance can be written as
'We point out two subtleties, discussed in detail in Section 3 of the Supplementary Material. Firstly, definition of QAC defined only for as that are full rank. Secondly, as stated, the Var(C) lower bound only yields a QSQ lower bound if minpge dn (p. 01) ) > 2(T + E). This does not impact the lower bound proofs by this technique that we present here. In Section 3 of the supplementary material, we also briefly discuss an alternative approach to hiding decision problems in C that relaxes this condition.
7

---

Var, (Tr/(Tr(MMb))) 4
Σ 1
B Tr(pi)) Tr(M))p)) Tr(M Tr(M, (7)
At this point, we upper bound all these terms by exp(-n1/2). Proving this upper bound is fairly combinatorial but crucially it involves understanding the properties the ensemble {(,y)} and its moments for uniformly random degree-2 2 functions f. Finally,
observe that the concept class can be learned given noisy quantum examples like in Eq. ( using poly (n, ((1-2)) examples (proving this uses the standard procedure take derivatives of quantum states and the observation that this procedure is noise-resifient). This gives us the claimed separation between QSQ and noisy-QPAC, the "quantum analogue" of the seminal result of Blum et al. [ for natural class and with non-constant error rate close to 1 1/2. We refer the interested reader to Section 4.1 in the Supplementary material.
3.3 Smallest class separation
Above saw that the concept class of quadratic functions separated QPAC from QSQ. Observe that states in this concept class can be prepared by circuits of size (n²)) ) and depth ((n) consisting of (Had, X, CX) gates. A natural question is, states prepared by smaller circuits also witness such a separation between QPAC and QSQ? In Section 2 we saw that trivial states are learnable in QSQ, is it necessary to have super-constant depth in order to show super-polynomia lower bounds? In the theorem below we answer this in the positive, by using a simple padding argument inspired by prior work of Hinshe et al. 3. In particular,
show that the class of states produced by wlog nı) --epthh already hard to learn for QSQ algorithms using a polynomial number of queries. For further details we defer the proof to Section 4.2 the Supplementary material.
Theorem 3. For any
(0, there exists family of qubit Clifford circuits of depth d (log n/a and size dt that requires 20(4) Qstat queries to learn the state error S 1/2 in trace distance.
4 Further applications
In this section we first use lower bound techniques to give QSQ lower bounds for interesting classes of states and then use our QSQ lower bounds for further applications outside learning. For further details we defer the proof to Sections and 5 in the Supplementary material.
4.1 QSQ lower bounds for learning states
Extending our lower bounds from above, we consider fundamental problems in quantum computing and prove QSQ lower bounds for these tasks. We summarize our results in the table below, for r = ( poly(n)) before expanding upon these the following subsections.
Problem
QSQ Bound
General Complexity
Shadow tomography
9(4")
O(2") with separable measurements 26
with Pauli observables
Learning coset states
20(n)
( with separable measurements
from Abelian hidden subgroup problem
2 200
O(1) with entangled measurements
Purity testing
((")) with separable measurements [26
Learning states from ((2") approximate 2-designs
20(0)
((n) for stabilizer states
with entangled measurements
Hidden subgroup problem. Coset states appear often in the hidden subgroup problem (HSP) [46] a fundamental problem in quantum computing. is well-known that coset states the Abelian HSP can be learned exactly from separable measurements in polynomial sample complexity and for non-Abelian groups, it was well-knows that separable measurements 48 require exponential many copies to learn a coset state. A natural question is, what is the QSQ complexity of learning coset states? Given that the standard approach for HSP is based of Fourier sampling and (27 showed that version of Fourier sampling is easy in QSQ, it is natural to expect that HSP is implementable in QSQ. Surprisingly, in this work, we show that, even for Abelian groups, the QSQ sample complexity of learning the unknown coset state is exponentially large. In particular, we show a lower bound of

---

1(T* 2n) on the QSQ complexity of learning using Qstat(r) queries and the proof of this is done via the average correlation method we introduced in Section 3.2.T
Shadow tomography. In recent times, there have been a lot of works surrounding the framework of shadow tomography [1 37.. The goal here is, given copies of an unknown quantum state p. the learner has to predict the expectation value Tr[O,p] of collection of known observables [Oe) up to error e. It is well-known to be solvable using poly (n, log k) copies of p. In (26 the authors show (2") copies of are necessary and sufficient for shadow tomography using separable measurements. To prove the lower bounds the authors construct many-vs-one decision task where I/2" and C= (p: 1==0.1, ). Assuming that Tr Tr[O.] O and Tr[O = 2 for all O., then algorithm which solves the shadow tomography problem with high probability also solves the decision problem. Thus, lower bound the latter is also lower bound on the sample complexity of shadow tomography. Here we give a quadratically stronger lower bound of 52(4)) when given access to only Qstat measurements, which we prove using the average correlation method. Our result shows that even separable measurements and not just statistics play non-trivial role in shadow tomography.
Does tolerance matter? A natural question when discussing QSQ learning is, is there a natural distribution learning task that can be solved with tolerance TQ TC such that classical Stat(rc) queries cannot solve the task but Qstat(TQ) can solve the task? Here we consider the class of bi-clique stales introduced in the seminal work of Feldman et al. (44). In their work they showed that for detecting a planted bipartite k-clique distributions when the planted k-clique has size n2/22c (for constant > 0), it is necessary and sufficient to make superpolynomial in n many Stat(kt/n queries. Here we show that one can achieve the same query complexity quantumly but with Qstat( (kk/n), i.e. with quadratically larger tolerance we can detect a k-biclique. A classical SQ algorithm cannot solve this task with TC- vk/n queries.
A doubly exponential lower bound? So far all our lower bounds for learning n-qubit quantum states are exponential in n. A natural question is, can one prove a doubly exponential lower bound for some task? In this work, we show that the natural problem of festing purity, i.e., given a quantum state / return an estimate of Trip"), requires 7x)(2">²) many QSQ queries to solve. Previous work of (26) showed that it is necessary and sufficient to (2*)) many copies of p to test purity if we were allowed separable measurements, but our work considers the weaker QSQ model and proves a doubly-exponential lower bound. The proof of this uses Levy's 's lemma and the ensemble of Haar random states to lower bound the quantum statistical dimension in a manner similar to that of the variance based technique.
4.2 Applications outside learning
Using our QSQ results we present two applications. First we give an exponential separation between weak and strong error mitigation, resolving open question of Quek et al. [2]. Second, we show super-polynomial lower bounds for learning output distributions (in the computational basis) of n- qubit Clifford circuits of depth wlogg n) and Haar random circuit of depth-O(n)). extending the works of 3 4. All these results (2/4 proved these lower bounds for QSQ algorithms assuming diagonal observables. For further details we defer the proof to Section 6 in the Supplementary material.
Error mitigation. Error mitigation (EM) was introduced as an algorithmic technique to reduce the noise-induced in near-term quantum devices, hopefully with a small overhead, in comparison to building a full-scale fault-tolerant quantum computer to harness general quantum advantages (50). In recent times, EM has obtained a lot of attention with several works understanding how to obtain near-term quantum speedups as a surrogate to performing error correction. EM has been an important component in recent QML demonstrations
(37 51 [0].
More formally, an EM algorithm A takes as input a quantum eircuit C. noise channel A and copies of (00) (CC (*)) In strong EM protocol, AA needs to produce samples from a distribution D that satisfies (D. [(x]CC C' )z) S E and in the weak EM setting, given observables My...., Mş the goal is to approximate ( M R upto e-error. In [2] they asked the question: how large should be order to simulate weak EM by strong EM? They show that when M,s are diagonal, then
k (22),, i.e., they gave an exponential separation between weak and strong EM. In this work, our main contribution is to use Result 2 to remove the assumption that M,s are diagonal and show an exponential separation unconditionally between weak and strong EM.
9

---

Learning distributions. Recently, the works of Hinsche et al. [3] and Nietner et al. 4 initiated the study of learning output distributions of quantum circuits. In particular, they considered the following general question: Let |vvr) U! where U E L is family of interesting unitaries and let (ar = (x)) be a distribution. How many Q5Q queries does one need to learn the Py to dTv at most E? To this end, the works of [ 4
looked at diagonal Ms, i.e., M = Ex ((x) |x)) (a] for 6: {0, 11"" + [-1, 1] and showed the hardness of approximately learning Pt: for 2 being w ([oo n)- depth Clifford circuits and depth-d E {a<(log n)) ) and d + oo-depth Haar random circuits [
In this work, we improve upon their lower bounds by removing the assumption that M is diagonal and prove a general QSQ lower bounds for these circuit families that is considered in their work. In order to prove this bound, we follow the following three step approach
(i) We first observe the following simple fact: for distributions 9 : Z - [0, 1]. define (etp) ExEe V pp(2)(2) and /15/) similarly. Then Ill 11,1) 1lf, I 21pp Allead. So it suffices to prove the hardness of learning the output state, in order to prove the hardness of learning the distribution. (ti) Next we consider the class C of states forming a y-approximate 2 2-design where y 0(2 and show that learning states from C with error S. 2/3 in trace distance requires Q 2 2") Qstat(T) queries. (iii) Finally, using that (epth-O(n) circuits form design, invoke our QSQ lower bound in order to prove the hardness of learning the output states of these circuits. These three steps proves the hardness of learning output distributions (in the computational basis) of quantum circuits.
Open questions. There are a few natural questions that our work opens up: (1) Can we show that for every concept class C, we have that SepExact < On EntExact)?, (di) Following 3 what is QSQ complexity of learning the output distribution of constant-depth circuits assuming we only use diagonal operators? (iii) Theoretically our work separates weak and strong error mitigation, but in practice there are often assumptions in the mitigation protocols, can we show theoretical separations even after making these assumptions? (ir) Classically it is well-known that several algorithms can be cast into the QSQ framework, is the same true quantumly? ? If so, that would suggest that QSQ as a (v) What is the QSQ complexity of the Hidden subgroup problem when given access to function states, instead of coset states (which is the case only in the standard approach).
unifying framework for designing new learning algorithms.
References
[1] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519) 2003.
3 8
[2] Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. 15055:2210.11505. 2022.
2 5
[3] Marcel Hinsche, Marios loannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Fisert, and Ryan Sweke. A single T -gaate makes distribution learning hard. arXiv:2207.033 0000000..3444.. 400 2022.
TO
[4] Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Keung, Jens Eisert, Marcel Hinsche, and Jonas Haferkamp. On the average-case complexity of learning output distributions of quantum circuits, 2023. arXiv:2305.05765
3
5
9 10
[5] S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum algorithms for supervised and unsupervised machine learning, 2013, arXiv:1307.0411
[6] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han- Lin, Ewin Tang, and Chunhao Wang. campling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. Journal of the ACM, 69(5):1-72, 2022.
[7] F. G. S. L. Brandão, A. Kalev, T. Li, C. Yen- Yu Lin, K. M. Svore, and X. Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In 46th International Colloquium on Automata, Languages, and Programming, ICALP, pages 27:1-27:14 2019.
'They prove that learning
(1 - eexp(-n)) fraction of the circuits in these families is hard in SQ model.
10

---

[8] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113(13)113003, 2014.
[9] I. Kerenidis and A. Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference, ITCS. pages 49:1-49:21, 2017.
[10] Vojtech Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567(774))209--222 2019. g
[11] Sam McArdle, András Gilyén, and Mario Berta. A streamlined quantum algorithm for topologi- cal data analysis with exponentially fewer qubits. arXiv:2209. /2887, 2022.
[12] Casper Gyurik, Chris Cade, and Vedran Dunjko. Towards quantum advantage via topological data analysis. Quantum, 6:855, 2022.
[13] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimiza- tion using quantum oracles. Quantum, 4:220, 2020.
[14] E. Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 5/st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 217-228, 2019. 0
[15] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195 202, 2017. [
[16] M Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick Coles. Chal- lenges and opportunities in quantum machine learning. Nature Computational Science, 2(9):567~ 576. 2022.
[17] Srinivasan Arunachalam and Ronald de Wolf. Guest column: A survey of quantum learning theory. ACM Sigact News, 48(2):41-67, 2017. 2
[18] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, An introduction to quantum machine learning. Contemporary Physics, 56(2):172-188 2015. T
[19] Ryan 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
[20] Jeongwan Haah, Aram Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the forty-eiighhh annual ACM symposium Theory of Computing, pages 913-925, 2016.
[21] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 325-338. ACM, 2018.
[22] Hsin- Yuan Huang, Richard Kueng, and John Preskil. Predicting many properties of quantum system from very few measurements. Nature Physics, 16: 16:1050-1057, 2020.
[23] Ashley Montanaro. Learning stabilizer states by bell sampling. arXiv: 2017.
[24] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J Yoder. Optimal algo- rithms for learning quantum phase states. arXiv:2208.0785/, 2022.
7
[25] Yuan Huang, Yu Tong, Di Fang, and Yuan Su. Learning many-body hamiltonians with heisenberg-limited scaling. Physical Review Letters, 130(20):200403, 2023.
[26] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 62nd IEEE Annual Symposium on Foundations of Computer Science, pages 574-585, IEEE, 2021.
[27] Srinivasan Arunachalam, Alex Grilo, and Henry Yuen. Quantum statistical query learning. arXiv:2002.08240. 2020. 2

---

[28] Michael Kearns, Efficient (JACM), 45(6):983-1006, 1998.
learning from statistical queries. Journal of the ACM
[29] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao. Learnability of quantum neural networks. PRX Quantum, 2(4):040337, 2021. 2
[30] Aravind Gollakota and Daniel Liang. On the hardness of pac-learning stabilizer states with noise. Quantum, 6:640, 2022.
[31] Armando Angrisani and Elham Kashefi. Quantum local differential privacy and quantum statistical query model. axXi:2203.03591, 2022. g
[32] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evidence for the utility of quantum computing before fault tolerance. Nature, 618(79655:500-555,, 2023.
[33] Youngseok Kim, Christopher J Wood, Theodore Yoder, Seth Merkel, Jay M Gambetta, Kristan Temme, and Abhinav Kandala. Scalable error mitigation for noisy quantum circuits produces competitive expectation values. Nature Physics, pages 1-8, 2023. 2
[34] Nader H. Bshouty and Jeffrey C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. Wolfgang Maass, editor, Proceedings of the Eigth Annual Conference Computational Learning Theory, COLT, pages 118-127. ACM, 1995.
[35] Srinivasan Arunachalam and Ronald de Wolf. Optimal quantum sample complexity of learning algorithms. Journal of Machine Learning Research, 19(71):1-36, 2018,
[36] Sébastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 6l IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 692-703. IEEE, 2020. 3
[37] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. Quantum advantage in learning from experiments. Science, 376(6598)111822 112-111211111 1186 2022. 3
[38] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11:1134-1143 1984.
[39] Alex B Grilo, Iordanis Kerenidis, and Timo Zijlstra. Learning-withh with-errors problem is easy with quantum samples. Physical Review A, 99(3):032314, 2019.
[40] Pranab Sen. Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. In 2/ Annual IEEE Conference on Computational Complexity (C)C pages pp- IEFE, 2006. 5
[41] Kai-Min Chung and Han-Hsuan Lin. Sample efficient algorithms for learning quantum channels in PAC model and the approximate state discrimination problem. In Min-Hsiu Hsich, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, July 5-8, 2021, Virtual Conference, volume 197 of LIPIcs, pages 3: 3:1222 Schloss
Dagstuhl- Leibniz-Zentrum für Informatik, 2021. 5
[42] Vitaly Feldman, Will Perkins, and Santosh Vempala. On the Complexity of Random Satisfiability Problems with Planted Solutions. arXiv e-prints, page arXiv: 1,4821, November 2013. 6
[43] Vitaly Feldman. A General Characterization of the Statistical Query Complexity. arXiv e-prints, page
02198, August 2016. 6
[44] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1-37, 2017. 7
[45] Cristopher Moore, Alexander Russell, and Leonard Schulman. The symmetric group defies strong fourier sampling. SIAM Journal on Computing, (7 2008, 7
12

---

[46] A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. guant-ph/951102. 1995.
[47] Daniel Simon. On the power quantum computation. SIAM journal on computing, 26(5):1474-148) 1997. g
[48] Cristopher Moore, Daniel Rockmore, and Alexander Russell. Generic quantum fourier trans- forms, 2003. g
[49] Sean Hallgren, Alexander Russell, and Amnon Ta-Shma. Normal subgroup reconstruction and quantum computation using group representations. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 627-635, 2000,
[50] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. Error mitigation for short-depth quantum circuits. Physical review letters, 119(18): 180509, 2017. g
[51] Jennifer R Glick, Tanvi P Gujarati, Antonio Corcoles, Youngseok Kim, Abhinav Kandala, Jay M Gambetta, and Kristan Temme. Covariant quantum kernlls for data with group structure. arXiv:2105.03446, 2021.
13


Reviews:
[{"review_id": "iXaeZCCyEt", "reviewer": "Reviewer_AabW", "summary": "This paper considers the task of learning an unknown concept class with quantum accesses. In particular, the authors make a comprehensive comparison of the settings with entangled measurements, separable measurements, and statistical measurements in the quantum statistical query (QSQ) model, respectively, and showed that entangled measurements are at most polynomially more powerful than separated measurements, which are exponentially more powerful than QSQ learning. Notably, this second separation is a quantum analog of the classical result separating between classical SQ learning from classical PAC learning. The authors also discuss possible extensions and applications of their result.", "questions": "Following my previous point, could you please elaborate more on the connection between the two settings?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides a clear answer on the possible role of entanglement the quantum PAC learning setting, and establishes a distinct separation between quantum PAC learning and QSQ learning, which provides an interesting conceptual message. The technical contribution of this paper is solid, and the presentation is clear.", "weaknesses": "The two main results of this paper are not closely related from my perspective. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments.\n\nWhile the proof techniques seem very different in both these results, we believe that both the results are related within the theme \"need for entanglement in learning\". Previously, it was known that QSQ measurements >= Sep measurements >= Ent measurements for all learning tasks. Our work aims to solidify the understanding of the power of the three models and show that Sep and Ent are polynomially related and QSQ measurements are exponentially weaker than Ent measurements. In our revision, we will keep your comment in mind to make our paper look more cohesive.\n\nThank you very much for pointing this out!"}, {"review_id": "LMnVTXcHjU", "reviewer": "Reviewer_gCmC", "summary": "This submission investigates the relationship between learning models with access to entangled measurements, separable measurements, and statistical measurements in the quantum statistical query (QSQ) model. The authors make several notable contributions: they establish the polynomial relationship between the sample complexity of entangled and separable measurements for learning Boolean concept classes, demonstrate an exponential separation between quantum PAC learning with classification noise and QSQ learning, introduce the concept of quantum statistical query dimension (QSD) to provide lower bounds on QSQ learning, prove exponential QSQ lower bounds for various tasks, show an unconditional separation between weak and strong error mitigation, and derive lower bounds for learning distributions in the QSQ model. These contributions advance our understanding of quantum learning theory and have implications for the development of quantum learning algorithms.\n\n\n\n\n", "questions": "It is recommended that the authors address the issues outlined in the Weakness section.\n\n\n\n\n", "limitations": "The authors have acknowledged the limitation by discussing open questions in the Discussion section.\n\n\n\n\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper successfully addresses multiple open questions regarding the capabilities of diverse quantum learning models. The insights gained from the obtained results offer a valuable understanding of the potentials and limitations of near-term quantum machines in comparison to fault-tolerant quantum computers. Additionally, the authors leverage the findings from the QSQ model to enrich our comprehension of crucial aspects in the field of near-term quantum machines, such as error mitigation and distribution learning. The theoretical contributions made in this work play a vital role in advancing quantum learning theory and provide practical guidance for developing and optimizing quantum algorithms on both current and future quantum hardware.\n\n\n\n\n", "weaknesses": "According to the whole main text, I did not find the main weakness of the submission While I did not review the entire proof, the portion I examined did not reveal any apparent issues. However, I did notice some minor concerns such as typos and incorrect notations. I suggest that the authors thoroughly examine their work to address these issues, ensuring a self-consistent and easily understandable manuscript. For instance:\n1. Line 346, 'a important'\n2. Line 375, '?, (ii)'\n3. Line 41, Supplementary: '$\\sum_{x\\in D_0}$'\n4. Line 44, Supplementary: '$I(D_0(x)\\leq D(x))$'\n5. Line 123, Supplementary: 'a n-bit'\n6. Line 602, Supplementary: 'Theorem ??'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\nWe will definitely address these and also look over the document for the next revision."}, {"review_id": "kBx9OP2W7O", "reviewer": "Reviewer_JWWq", "summary": "This paper studies the power of different quantum machine learning models for learning Boolean functions, namely quantum PAC-learning (QPAC) with entangled measurements, QPAC with separable measurements, and quantum statistical query (QSQ). It has two main results. First, it shows that QPAC with entanglement measurements is not more powerful than separable measurements in this task. More specifically, to *exactly* learn an $n$-bit Boolean function class, every learning algorithm using entangled measurements with $T$ copies of the quantum sample $|\\psi_c\\rangle=2^{-n/2}\\sum_x |x,c(x)\\rangle$ can be transformed into a learning algorithm using just separable measurements with O(nT^2) samples. Second, it provides an exponential separation between QPAC with noise and QSQ. In the QSQ model, the learner can query the oracle with any observable $M$ (implementable with $poly(n)$ gates) and obtain an estimate of $tr[M\\rho]$ within $1/poly(n)$-additive error. It constructs a concept class of $n$-bit Boolean functions that is QPAC learnable with $\\eta$-classification noise (i.e., $|\\psi_c\\rangle=2^{-n/2}\\sum_x \\sqrt{1-\\eta}|x,c(x)\\rangle+\\sqrt{\\eta}|x,1-c(x)\\rangle$) in time $poly(n, 1/(1 − 2\\eta))$, whereas every QSQ learner requires $2^{\\Omega(n)}$ queries. Furthermore, it also provides several applications in shadow tomography, testing purity of quantum state, error mitigation, and learning output distributions of quantum circuits. ", "questions": "* In Sec. 3.2.1, it could be better to provide the classical definition of the statistical dimension and compare it to the quantum one. \n\n* This paper considers proper learning. What about quantum improper learning? The input is still the quantum sample state for some unknown Boolean function, but the goal is just to output some quantum state close to the given quantum sample state. Are the techniques in this paper still apply to this setting?", "limitations": "The limitations are stated. Potential negative societal impact does not apply here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Understanding the power of different quantum learning models is an important research question in quantum learning theory. The results of this paper are quite solid. More specifically, for the first main result about the relation between entangled measurements and separable measurements, prior to this work, we only knew that they are exponentially separated when learning quantum states. This paper focuses on a smaller concept class and shows that they are polynomially related, which is quite surprising. For the second result about measurement statistics, compared to the classical result that separates PAC from SQ due to Blum et al., the construction in this paper is based on degree-2 polynomials, which are more natural. And the proof of this result provides a novel approach to lower bound the complexity of QSQ via the quantum statistical dimension, which is the main technical contribution of this paper. The applications also improve over prior works in several aspects. Furthermore, this paper is well-structured, and most proofs are mathematically sound to me.", "weaknesses": "This paper may seem quite difficult to follow for people not working on quantum computing. Also, the proof overview section is too technical, and more intuition should be given. \n\nThe relation between entangled measurements and separable measurements is $O(nT^2)$, which seems to be not tight. (It has already been pointed out in the paper)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very interesting questions/comments.\n\nIndeed, our bound on $O(n T^2)$ is suboptimal, but in our main theorem statement we have a slightly combinatorial parameter $\\eta$ and we show a bound of $O(n T \\eta)$ which we show is tight for a certain concept class. We suspect that the right relation should be $O(nT)$ and leave it for future work.\n\nRegarding proper versus improper: our results do $\\textit{not}$ assume that the learning algorithms are proper. In particular, our lemma bounding learning complexity with decision complexity holds for both proper and improper learners. Then, of course, for decision problems there is no concept of proper/improper learning. In our revision we will make it clear that our lower bound holds for even improper learners."}, {"review_id": "hkXmjAY3Pm", "reviewer": "Reviewer_UDTy", "summary": "This paper studies quantum learning theory, in particular the relationship between the quantum version of PAC learning and the quantum version of the statistical query (QSQ) model, as well as their connection to other considerations in quantum computing, such as entangled measurements and separable measurements. Specifically, the authors proved that\n\n1. For learning Boolean concept classes, the entangled and separable sample complexity are polynomially related (at most quadratic power).\n\n2. There exists a concept class with an exponential separation between quantum PAC learning with classification noise and QSQ learning.\n\nAlong this, the authors also proposed novel technical tools of quantum statistical query dimension, and these technical results are applied to problems ranging from states learning, distribution learning, and specific problems in quantum computing such as shadow tomography, error mitigation, etc.", "questions": "Can the techniques in this paper be applied to prove separation results between quantum and classical PAC learning or SQ models? As far as I see, this paper studies purely quantum learning concepts and their relationships. It would be helpful to deliver more conceptual message about the difference between quantum and classical learning, which may be of general interest (this is also the storyline set at the beginning of intro, but quickly drives into purely quantum things).", "limitations": "N/A – this work is purely theoretical.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "This paper is technically very solid and is able to prove a series of new results in quantum learning theory. PAC learning and SQ learning models are both important concepts in classical learning theory, and it’s nice to see that the authors are able to generalize them to the quantum domain, connect them to natural definitions in quantum, and prove separation results between these concepts. It’s also nice to see that the authors are able to find wide applications in quantum learning theory.", "weaknesses": "From my perspective, the most notable weakness of this works is its interest to the general machine learning community. There are theory papers in NeurIPS each year, many of which are very interesting and well received by NeurIPS audiences, but I’m afraid that this one falls into too much on the theory side and might be of limited interest to the NeurIPS community. In general, the topics of PAC learning and SQ model are more of theoretical interest and target more on theoretical computer science. The quantum version further delves into those directions and bring into definitions that do not exist in classical machine learning, such as entangled measurements/separable measurements, shadow tomography, etc. As another evidence, the references in the main body contain literally 0 paper coming from top-tier machine learning conferences targeting at general audiences, including, NeurIPS, ICML, ICLR, AAAI, etc. Instead, there are many top-tier theory papers at STOC/FOCS, Journal of the ACM, and top-tier physics journals. In general, I believe that this paper can be quite competitive in top-tier theoretical computer science venues or quantum physics venues, but is out of scope for NeurIPS due to lack of insights for up-to-date trends in current machine learning research. \n\nAs a minor point of weaknesses, I think the references can be better presented. First, I find it a bit hard to locate references: there are quite a few big brackets citing >5 papers at the same time, and it’s very difficult to determine which paper talks about which topic. For instance, in Page 1, “There have already been many theoretical proposals for quantum algorithms providing speedups for practically relevant ML tasks such as clustering, recommendation systems, linear algebra, convex optimization, SVMs, kernel-based methods, topological data analysis [34, 14, 9, 42, 32, 26, 35, 23, 49, 46]” can be better written as … such as clustering [xx], recommendation systems [xx], linear algebra [xx], convex optimization [xx], SVMs [xx], kernel-based methods [xx], “and” topological data analysis [xx].\n\nActually, I think here the authors lost some quantum computing papers accepted by past NeurIPS/ICML conferences that provide quantum speedup for solving machine learning problems, such as Kapoor et al. (https://proceedings.neurips.cc/paper/2016/hash/d47268e9db2e9aa3827bba3afb7ff94a-Abstract.html) and Li et al. (http://proceedings.mlr.press/v97/li19b.html) for classification, Arunachalam and Maity (https://proceedings.mlr.press/v119/arunachalam20a.html) for boosting, Childs et al. (https://proceedings.neurips.cc/paper_files/paper/2022/hash/933e953353c25ec70477ef28e45a2dcc-Abstract-Conference.html) for logconcave sampling, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments!\n\nRegarding your question about separating quantum vs. classical techniques: There are known separations between classical and quantum PAC for the distribution-dependent setting, for example for DNF formulas [Bshouty, Nader H., Jackson, Jeffrey C.: Learning DNF Over the Uniform Distribution Using a Quantum Example Oracle; COLT '95]. Similarly, there are separations between classical SQ and quantum SQ witnessed by the parity functions [Arunachalam, Grilo, Yuen: Quantum Statistical Query Learning; CoRR]. Prior to the submitted work, no separation was known between quantum SQ and quantum PAC, which is why we focus on that. Based on your remark, we will improve the discussion of prior results in the introduction and focus on the delivery of the conceptual message to the broader community. Thank you for pointing that out!\n\nWe value your comment regarding references and will update the introduction accordingly with references to these results in the revision. We will add references and improve their presentation according to your suggestion.\n\nOn a higher level, our results provide an insight into where to look for quantum advantages in machine learning and what resources this requires—something we feel is of broader interest in the ML community. Thus, it is interesting to characterize the limitations of QSQ, a natural generalization of SQ that models near-term capabilities in quantum hardware. Our work can be viewed as a provable separation between QML with near term hardware and QML with more sophisticated hardware, by introducing techniques to understand the QSQ model better. \n\n On the classical side, the SQ model is intimately linked to (local) differential privacy and optimization, in particular, theoretical and practical algorithms fall into the SQ framework [Feldman, Ghazi; On the Power of Learning from k-Wise Queries; ITCS '17]. Theoretical results on PAC/SQ learning and quantum learning theory [Arunachalam, Quek, Smolin: Private Learning Implies Quantum Stability; NeurIPS ‘21] have been published earlier in NeurIPS. We believe that understanding their counterpart in the quantum setting is of interest for the broader ML community, especially those parts of it that have interest in quantum, and that NeurIPS is an appropriate venue for our work.\n\nBased on your recommendation, we will improve the discussion of quantum vs classical learning, to set the context for the typical audience at NeurIPS. Due to the lack of space for the NeurIPS submission we didn't delve into this to sufficient depth, but will implement it in the revision."}]

Author rebuttal:

Meta-review: Understanding the power of different quantum learning models is an important research question in quantum learning theory. This paper has made solid contributions to this research frontier. In particular, it studies the relationship between the quantum version of PAC learning and the quantum version of the statistical query (QSQ) model, as well as the difference between entangled and separable measurements. The paper establishes an exponential separation in the former while demonstrating a polynomial relation in the latter.  We wanted to ask the authors to include more discussions (e.g., from the rebuttal) on the connection of the learning theory results to the machine learning community, as well as the connection between the two main results in the revision.
Decision: Accept (poster)