Online Learning of Pure States is as Hard as Mixed States
Authors: Maxime Meyer
Soumik Adhikary
Naixu Guo
Patrick Rebentrost
Venue: NeurIPS 2025 poster ()
Keywords: quantum state learning
tomography
pure and mixed states
online learning
sequential fat-shattering dimension
smoothed analysis
Primary area: theory
TL;DR: We study online learning of quantum states and prove that learning a pure state is as hard as learning a mixed state, id est that the rank of the matrix has no impact on the complexity of the learning problem.

Abstract: Quantum state tomography, the task of learning an unknown quantum state, is a fundamental problem in quantum information. In standard settings, the complexity of this problem depends significantly on the type of quantum state that one is trying to learn, with pure states being substantially easier to learn than general mixed states. A natural question is whether this separation holds for any quantum state learning setting. In this work, we consider the online learning framework and prove the surprising result that learning pure states in this setting is as hard as learning mixed states. More specifically, we show that both classes share almost the same sequential fat-shattering dimension, leading to identical regret scaling. We also generalize previous results on full quantum state tomography in the online setting to (i) the $\epsilon$-realizable setting and (ii) learning the density matrix only partially, using smoothed analysis.

Online Learning of Pure States is as Hard as Mixed States
Maxime Meyer
Soumik Adhikary
Department of Mathematics & IPAL, IRL2955
Centre for Quantum Technologies
National University of Singapore
National University of Singapore
Singapore
Singapore coumik@nus.co edu.
maxime. mex.imemmyyeru...o nus.aanuuusee..
Naixu Guo
Patrick Rebentrost
Centre for Quantum Technologies
Centre for Quantum Technologies & School of Computing National University of Singapore Singapore cqtfprēnus eewerruuuuueuu.... sg
National University of Singapore
Singapore naixugou.mut nus. edu
Abstract
Quantum state tomography, the task of learning an unknown quantum state, a fundamental problem in quantum information. In standard settings, the complexity of this problem depends significantly on the type of quantum state that one trying to learn, with pure states being substantially easier to learn than general mixed states. natural question whether this separation holds for any quantum state learning setting. In this work, we consider the online learning framework and prove the surprising result that learning pure states in this setting as hard as learning mixed states. More specifically, we show that both classes share almost the same sequential fat-shattering dimension, leading to identical regret scaling. generalize previous results full quantum state tomography in the online setting to (i) the e-realizable setting and (ii) learning the density matrix only partially, using smoothed analysis.
also
Introduction
Learning information from unknown quantum state is fundamental task in quantum physics. An N N-ddimensional quantum state is represented as an x positive semi-definite Hermitian matrix with unit trace. Given several perfect copies of p. full quantum state tomography seeks to reconstruct the complete matrix representation of p via measurements. It has a wide range practical applications, including tasks such characterizing qubit states for superconducting circuits [Lucero] et al. 2008). catrogen-vacance (NV) centers in diamond (Neumann et al. 2010]. and verifying successful quantum teleportation [Bouwmeester al. 1997). The ease of learning quantum state often characterized by the sample complexity, i.e. the number independent copies of the quantum state required for accurate reconstruction. For general state p. the sample complexity scales Ô(N²) for incoherent measurements. However, if the state is known be pure, the sample complexity can be improved Nevertheless, for n--ubit states, where N = 2", this scaling implies an exponential dependence on the number of qubits.
((N) Kueng al. 2017 Haah et al. 2016 Chen al. 2023
However, for many practical problems, such as certification of a quantum device Gross et al. 2010
Flammia and Liu 2011 Eisert et al. (0200 and property estimation for quantum chemistry [Huang
et al. 2021 Wu et al. 2023 Guo et al. 2024 Raza et al.) 2024 Miller et al.) 2024], only partial
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

information about the quantum state is needed. To address such cases, quantum PAC learning, also known as pretty good tomography, was introduced by [Aaronson (007). In this framework, fixed distribution 'D governs the selection of two-outcome measurements E, which are represented by N N Hermitian matrices with eigenvalues in [0, 1). The learner then tries to output a hypothesis state w such that Tr(Ep) 2 Tr(Ew) with high probability. The number of measurements required
E-D to output this hypothesis n--ubit state was shown to scale only linearly with the number of qubits yielding an exponential improvement over full-state tomography. However, a key limitation of both these approaches is that they do not account for adversarial environments, where the set of realizable measurements may evolve over time.
This limitation can be circumvented by generalizing to the online learning setting [Aaronson et al. 2018, Chen et al., 2024 Bansal et al. 2024]. where learning quantum state p is posed as a a Tround repeated two-plas iwo-player&& game. In each round t E [T], Nature-alss also called the adversary-chooss measurement Eg from the set of two-outcome measurements. The task of the learner is to predict the value (r,E,p) by selecting a hypothesis Wi and computing Tr( Exwr) based on previous results. Thereafter, Nature returns the loss, a metric quantifying the difference between the prediction and the true value. The most adversarial scenario arises when the measurement at each round is chosen from the set of all two-outcome measurements without any constraints, i.e., can be chosen adversarially and adaptively. It has been shown that in such cases, learner can output hypothesis state which incurs an additional O ((T))) loss compared to the best possible hypothesis state after T rounds of the game [Aaronson et al.) 2018). This measure of how much worse a learner performs compared to the best possible strategy in hindsight is called regret and serves as fundamental measure of performance for any online learning problem.
a
Given the clear separation in sample complexity between pure and mixed state tomography [uunng
ct al. 2017 7 Haah et al. 2016), we ask the central question that this work aims to address:
Is there any separation between online learning of pure and mixed quantum states?
In this work we show that the answer is No. Our proof is based on the analysis of the sequential fat-shattering dimension of pure and mixed states. Informally, it can be seen as the minimum number of mistakes-define as errors exceeding threshold 8-that learner must make before successfully learning a quantum state p against a perfect adversary. We have shown that both pure and mixed states share almost the same sequential fat-shattering dimension of order O f)) and hence the same regret. Indeed, it has been demonstrated that both upper and lower bounds on regret can be expressed in terms of this dimension [Rakhlin et al.) 2015b).
We believe that this result is surprising. Indeed, not only is there a significant difference in sample complexities between learning pure and mixed states in the standard tomographic settings, but this distinction also holds in specific online learning scenarios. For instance, under bandit feedback with adaptive measurements, Lumbreras et al. 20022 2024 shows that the regret for mixed states grows exponentially faster than for pure states.
A prior work AAronson et al.) 2018 established tight bounds on the sequential fat-shattering dimension of general mixed states. In this work, we establish lower bounds on the sequential fat- shattering dimension and consequently on the regret of several subclasses of quantum states, the most important of which is the class of pure states. Our approach employs a distinct proof strategy, providing new insights and extending naturally to various subsettings of the online quantum state learning problem. As a result, we show that the regret for online learning of both pure and mixed quantum state scales as ((vTT).
A key feature of the online learning setting considered here is the adversary's ability to select measurements in a completely unconstrained manner. As a result, this setting may effectively incur full state tomography, even in cases where only partial information about the state is needed. We therefore introduce the concept of smoothness for online learning of quantum states. Smoothed analysis was first introduced in (Spielman and Teng [2044] as tool that allows for interpolation between the worst and the average case analysis. Later, Haghtalab et al. (2024] extended this concept to the online setting, where the degree of adversariality is quantified by smoothness parameter a E [0, 1]. The particular value a = corresponds to independent and identically distributed (i.i.d.) inputs, while the limit a + 0 corresponds to fully adversarial inputs. In this work, establish an

---

upper bound on regret for smoothed online learning of quantum states, providing insights into the effect of adversariality on regret scaling.
1.1 Main Contributions
Equivalence between pure and mixed state learning: We show that pure and mixed states share almost the same sequential fat-shattering dimension, leading identical regret scaling under the L1 loss in Section 4 We also prove a novel dependence of minimax regret with L2 loss on the Rademacher complexity. This allows us to extend the tightness of regret the Le loss setting for both pure and mixed states.
Extensions of Online Learning of Quantum States to more realistic settings: We obtain new regret bounds for two settings of interest, which capture more accurately the settings encountered by experimentalists, in Section 5 The first is the e-realizable setting, where the learner able to measure Tr(E,p) Ppp) with errrr at every round. The second is the smooth setting, where the learner is only interested about learning specific properties of the quantum state p.
1.2 Related Works
Pure and mixed state tomography: In full state tomography of an N dimensional quantum state the goal is reconstruct its complete classical representation given several independent copies. The associated sample complexity refers to the number copies required to obtain a classical description of p up an accuracy It has been shown that the sample complexity up trace distance is ((Nr/e2) for incoherent measurements (Haah et al. 2016 Kueng al. 2017 Chen al. 2023). where r is the rank of the density matrix p. This result highlights a fundamental separation in the sample complexities between pure and mixed state tomography, as the rank of pure states is 1. Given the fundamental nature of this separation in quantum information science, one might expect it to persist in the online learning setting. In fact, Lumbreras al. (2022) studies the online learning of properties of quantum states under bandit feedback with adaptive measurements, obtaining regret scaling of e ((VT) for mixed states. Subsequently, Lumbreras et al. (2024) improved this result (polylog T)) for pure states with rank-1 1 projective measurements, showing an exponential separation. In contrast, our results demonstrate that, in the general online learning setting, the regret scaling for pure and mixed states is identical.
Existing bounds: Aaronson et al. (2018) showed that the sequential fat-shattering dimension of quantum states with parameter is tight, of order ) They also use result from Arora al. [2012] to show that the regret is tight for the L1 loss in the non-realizable case (that is when the data isn't assumed to come from an actual quantum state), being of order @VvnT). In this paper, we generalize this result to several new settings of interest. We also introduce a new proof technique that allows us to provide lower bounds for sequential fat-shattering dimension for restricted settings, notably proving near-tightness for pure states in Theorem
2
Preliminaries
2.1 Quantum States and Measurements
general mixed n-qubit (quantum bit) quantum state p corresponds to a Hermitian positive semi- definite matrix of size 2n and of trace 1. It will be called pure state if and only if it is of rank 1 (or cquivalently and only if Tr(p²) = 1). We can thus identify any pure state p to a vector in the 2n dimensional Hilbert space C²". typically expressed in the Dirac notation as (b)). Under this notation,
any pure state vector can be expressed as [v)) E c: (i) with G E C and Σ²r |c,12 = 1. Here, {1i) 2 corresponds to the canonical basis of the vector space. For pure state (1)) the corresponding density matrix representation given by = ( (1/), where (wi = |,5) is the complex conjugate of (e))
Information from quantum states can be obtained via quantum measurements. In our work we will focus on two outcome measurements. They are represented by two-element positive operator- valued measure (POVM) (F, 1 F).. where F. E (2rme(2") and Spec(F)) c [0, 1]. Since the second element of the POVM is uniquely determined by the first, two-outcome measurement can
3

---

effectively be represented by single operator E. A measurement E' is said to accepr quantum state p with probability Tr(Ep) and reject with probability 1 Tr(Ep), For given quantum state o. predicting its acceptance probabilities for all measurements E' is tantamount to characterizing it completely. Hence learning a quantum state p is equivalent to learning the function Trp. defined as (F)(F) Tr(Ep).
2.2 Online Learning of Quantum States
Online learning, or the sequential prediction model, is 7 round repeated two-player game (Cesa- Bianchi and Lugosi 2006]. In each round [T] of the game, the learner is presented with input from the sample space 2 E X. Without any loss of generality, we can assume that z2 is sampled from distribution (X) where D; may be chosen adversarially. The learner's goal is to learn an unknown function h X - ) from the data they receive. Here, y denotes the space of possible labels for each input zg. The learning proceeds by designing an algorithm that outputs a sequence of functions h2 X' + 3 chosen from hypothesis class H. After each round, the learner incurs loss and aims to minimize the cumulative regret- which corresponds to the difference with the loss incurred by the best hypothesis in hindsight at the end of all I rounds of the game. The main figure of merit used in online learning, which represents the regret of the best strategy from the learner, when presented with the hardest possible inputs at every round is called the minimax regret (Rakhlin al. 2015a]
Definition 2.1 (Minimax regret). Let X' denote the sample space, y its associated label space, and H the hypothesis class. Let P and A(H) be sets of probability measures defined on X' and H respectively. In each round t E [T] of the online learning process, the learner incurs loss le (H()) Me), where yr E y is the true label associated to H,. The minimax regret is then defined as:
T
V/-
inf sup sup E QEA(H) de D.EP h
E
Σ (0((()))))) inf Σ (=1
((h(a)))))) (1)
B,ND
REH t=1
where (.)T_, denotes iterated application of the enclosed operators.
The question of learnability of an online learning problem can then be reduced to the study of Vr. Given pair XH, a problem is said to be online learnable if and only if limy-+00 V1 /T 0.
In the context of quantum state learning. we define the sample space as X C { Herme Spec))) E) C [0, 1]}. Denoting Cn as the set of all n-qubit quantum states, we set the hypothesis class to be H., = (Tr.., w E C. and Q can be seen as a distribution over C,, Here, the learner receives a sequence of measurements (Fx (E)))T(T) each drawn from a distribution D, (chosen adversarially) one at time. Upon receiving each measurement, the learner selects a hypothesis wr E C. and thereby incurs a loss of (Tr,,, (Fe), vr) e, (Tr E,we), Vt). In practice, for quantum tomography, le is taken to be either the L1 or the L2 loss (that is (a b) E {la b), (a - 6)2)). Lastly, the label y/: E y [0, is revealed to the learner. It may be an approximation of Tpp,,)) but it is allowed to be arbitrary in general.
2.3 Sequential fat-shattering dimension
The main notion we will be studying in this paper is that of sequential fat-shattering dimension. Definition 2.2 (Sequential fat-shattering dimension). A X-valued complete binary tree x of depth T is deemed to be 5-shattered by a hypothesis class H if there exists a real-valued complete binary tree of same depth T' such that for all paths E [+1]7-1
3he H. E [2] ee(h(xi(e)) ve)) 2 2
The sequential fat-shattering dimension at scale 6, sfats X'), is defined to be the largest T for which H d-shatters -vauuued tree of depth T.
Recall that a X'-valued complete binary tree of depth T. x, is defined as a sequence of T mappings (X1, X2, ... Xr), where x, (+1)--1 + X, with a constant function x1 X' as the root. In simpler terms the tree can be seen collection of T' length paths (E1, E2, (r--1) e [+1)7-1 (+1

---

indicating right and -1 indicating left from any given node) and x₁(e) = xi((1," ,4-1) E X denoting the label of the t-th node on the corresponding path e.
This dimension is a fundamental property in online learning, as it both upper and lower bounds regret [Rakhlin et al. b) as shown in Equations and
Vr < inf { 4aTL - 12LVV 020
f. stats X) log
2eT
dō
(2)
Note that this upper bound also holds for Dr. The bound in Equation (2) was used in Aaronson et al.] [2018] to derive the regret upper bounds for online quantum state learning. Similarly, the minimax regret can also be lower bounded by the sequential fat- fat-shattering dimension, provided that
l (he (2xe, 3e) = (xre) - Y/1 and that P is taken to be the whole set of all distributions on X.
Vr 2 sup {
8 min (sfats (a (H, X3,
4/2 8>0
3 Lower Bounds for Online Learning of Quantum States
In this section, we employ a distinct proof strategy than Aaronson et al. [2018) to obtain lower bounds on sequential fat-shattering dimension-recall that they proved sfat, X) ( This allows us to extend those bounds naturally to various subsettings of the online quantum state learning problem, characterized by a restricted hypothesis class H C Hn and a constrained sample space X. Such settings frequently arise in practical applications, where the focus is on characterizing specific subsets of quantum states. Furthermore, experimental constraints often limit the implementable set of measurement operations. We derive bounds on sfat (H, X) for several such practically relevant subsettings, leading up to the most general formulation of the learning problem.
Our proofs are based on the construction of X' x [0, 1]-valued trees, which can be looked upon as a means to extract information about a quantum state at every layer. After a certain number of layers, full information about the state is recovered. The number of layers achieved serves as a lower bound to the sequential fat-shatt dimension. Therefore, the goal to construct the largest tree before full information is recovered.
Intuition of proofs:
In our construction, we define gaining information simply as approximating the coefficients of the density matrix p. At each layer, we approximate a different coefficient as seen in Section [3.2] This how we construct the -a-vulued part of the tree. We can then approximate each coefficient to an error using the Halving Tree defined in Section 3.1 (Section 3.3 shows how to combine both trees). The intuition behind the choice of the coefficients we approximate comes from the study of chordal graphs in Section 3.4. An easier way to understand it is that we consider only the first row of the matrix, as it of rank 1. Finally, we find the optimal error e to obtain the lower bound.
To set the stage for the following sections, we first establish few notations: since we will frequently consider pure states, the quantum state (()) will be denoted by its associated vector [и(E)), where w(e) = (e(e)) (=(E)]. Furthermore, we define N = 2n to be the dimension of the Hilbert space under consideration. addition, we will denote the pair of binary trees (x, v) by single tree T. We call x the v'-uul part of T, and v the real-valued part of T.
We highlight that while many of the theorems in this section be recovered from existing results, our contribution lies in introducing a unified proof framework. This scheme not only underpins our main result in Section 4 but also offers a versatile foundation that can be adapted various sub-settings of interest.
3.1 Learning with respect to a single measurement
We start with the learning problem of estimating the expectation value of an unknown n-qui quantum state with respect to fixed measurement operator E. This learning problem is key to practical tasks such as quantum state discrimination and hypothesis testing [Barnett and Croke) 2009 Bae and Kwek 2015). Formally, we take X' {E) } to be the sample space and keep H. as the hypothesis class. As mentioned previously, we are focused on providing a lower bound on sfat, (aats(H,, (H,,,t)), which could then be used to lower bound Vy. We achieve this by constructing what
5

---

we call the Halving tree Th. which has a constant X --valued part, and a real-valued part as shown in Figure Every halving tree Tr [t, 7] (x, v) will thus be entirely determined by its depth T and the constant measurement [i]. The name follows from the distinctive structure exhibited by the real part of the tree Tx as shown Figure This construction will prove useful as a crucial
building block for establishing the regret bounds in more general settings (see Theorems 3.4 3.6
and
10) (0)
[1)
[1)
IT 1)(T 1
T 1)(T
Figure 1: Real-valued part of the halving tree Th. up N
Figure 2: X'-valudd part of the Von Neumann tree T en.
1 factor.
Theorem 3.1. Let E E H2rme(2"), Spec(E) C [0, 1] be a fixed measurement, and X {E) be the sample space. Let Hn (Trw, w E 3 be the hypothesis class, where Cn is the set of all n-qubit quantum states. Then we have (ant, X²) (2logg2 (t)).
We prove this result in Appendix A
Remark 3.2. Note that the lower bound on the fat-shattering dimension obtained above is independent of n, and therefore still holds if the hypothesis class is induced by I-qubit pure states.
3.2 Learning uniform superposition states
We now shift our attention to a harder setting, Consider the sample space X' consisting of the N measurements corresponding an orthogonal basis of C.. The hypothesis class will be induced by the uniform superpositions of basis states. Such states play an important role in fundamental quantum algorithms [Simon 1994 Shor 1997, Grover 1997). and for quantum random number generators Mannalatha et al. 2023]. We now provide a lower bound to the sequential fat-shattering dimension for this specific setting. We accomplish this by constructing what call the Von Neumann tree T Ten- The name follows from the fact that, while its real-valued part is constant, all nodes in the -vvalued part of T on are labelled by Von Neumann measurements as shown in Figure
Theorem 3.3. Let ".,,-..,IN 1)) be an orthogonal basis of C,,, where Cn is the set of all n- qubit quantum states. Denote the sample space as X = (i)) (il, E [0, - 1]}. Let H = [Tr,, = v ((min() 2))
_ Eier ii), C [0, 1]} be the hypothesis class. Then we have sfat, (H,
We prove this result in Appendix
3.3 Learning general states using Von Neumann measurements
Building on the setting established in the previous section, we consider the sample space X consisting of the N measurements corresponding to orthogonal basis of Cn. The hypothesis class in the present setting is however induced by the set of all pure quantum states. The corresponding learning problem involves learner estimating the expectation values of unknown n--ubit quantum state with respect to measurement operators, where the hypothesis is chosen from the set of all n-qubit pure quantum states. Related problems have been considered, for example, in Zhao al.] (2023]
We now provide lower bound to the sequential fat-shattering dimension for this specific setting. We accomplish this by constructing what we call the Von Neumann Halving tree Tonk, which is constructed by combining T,, and om as shown Figure 3 Our construction illustrates the utility of Th, demonstrating its effectiveness tool to multiply existing lower bounds by factor of n.

---

[o]
T.
T₁ I 3, - - - TA -2
[0)(0]
[1)
Figure 3: Von Neumann Halving Tree (Horizontal)
Theorem 3.4. Let (10),..,,I I.....,,N - 1)) be an orthogonal basis of Cn and X (1, 10, N - 1]} be the sample space. Let H. {'Tww E C.. Tr(w²) = =1 be the hypothesis class. Here Cn the set of all n-qubit quantum states. Then, for 2 8, we have (Hn, 22 (t) vn 1.
We prove this result in Appendix
3.4 Tightness of sequential fat-shattering dimension of quantum states
Having considered several restricted settings in the previous sections, formulation of the online quantum state learning problem. Formally, we define the sample space to be the space of all 2-outcome measurements X' while the Hypothesis class is given as Hn, Our objective is to derive a tight lower bound on sfat, X.). To accomplish this, we will use the techniques developed in the previous sections. In addition, we will establish new results completion of partial matrices, which are essential for our analysis. We start with the latter.
turn the most general
Let us first introduce few necessary definitions partial matrices and their completions. A partial matrix is a matrix in which certain entries are specified while the other entries are free to be chosen. It is called partial symmetric if it is symmetric
the specified entries. And a completion of partial matrix refers to specific assignment of values to its unspecified entries. The main result we will use is the following, proved in Appendix D
Lemma 3.5. Any real partial symmetric matrix w satisfying the following conditions
1. w1n 2. and wa IN-1 vi
NI.
2. Elements specified the set {wis wi). where i [N].
3. Vi E wwil 2VN-1'
can be completed to a density matrix. We will denote part( (12, W13. ... WiN) such matrix.
We now derive the lower bound for sfat, A'). ) The key idea is to construct a new tree analogous to the Von Neumann halving tree, with crucial distinction that accommodates more general measurements, extending beyond the |i> type measurements that have been considered thus far. Furthermore, given this tree, we apply Lemma 335 to ensure that all paths on the can be associated to valid density matrix. We show that this allows us to obtain the quadratic dependence on in the lower bound of sfat, (Hn, X), thus establishing the almost tightness.
Theorem 3.6. Let X {E' H. = (Tr,, , w C., as the hypothesis class, where C, is the set of all n--ubiit quantum states. Then, for 8 = 2 ", we have sfat, (Hn, = Vn < 2.
C 1]} be the sample space. Define
We prove this result in Appendix Note that this result directly implies tightness of regret for L1 loss [Aaronson et al. 2018], aswell as for L2 loss as shown in Appendix G
Remark 3.7. As mentioned in the beginning of this section, our method for lower bounding the sequential fat-shattering dimension differs from that employed in Aaronsson [2007]. and is adaptable to various restricted online quantum state learning settings. For cases involving further restrictions, whether on the sample space, the hypothesis class the relationship between and (Recall that
Aaronson 2007 required 2 (n-)3nn /8) we conjecture that the techniques from Appendix involving matrix completion would serve valuable foundation.
4 Online Learning of Pure States is as Hard as Mixed States
While the tightness of the sequential fat-shattering dimension, and hence of the minimax regret were already known, we emphasize that the results were derived for hypothesis class being induced by
7

---

the set of all n--uuii quantum states. In this section, we consider more restrictive setting where the hypothesis class is induced solely by the of all n-qubit pure states. The derivation closely follows the techniques developed in the previous section with notable distinction: whereas the previous sections relied on matrix completion results (without defining the states w(E) explicitly), here we shall construct the states w(e) = (s)(e) explicitly. We show that the bounds on the sequential fat-shattering dimension and consequently the minimax regret remain tight in this setting.
Theorem 4.1. Let X' {E' Herme Sp)c(E) [0, 113 be the sample space. Define H = (Tr,, E Cn. Tr(w²) = as the hypothesis class, where Cn is the set of all n-qubit quantum states. Then, for 5 = 2 ", have sfatg (H, X) ) 2.
Now, building on the result in Theorem 4.1 we proceed to demonstrate the tightness of the minimax regret Vr, proving that it is asymptotically the same for mixed states:
Corollary 4.2. Lel X {E E Herme(2"), Spec(E) C [0,1]} be the sumple space. Define H = (Trw, E Cu: Tr(w²] 13 as the hypothesis class, where Cn is the set of all n-qubit quantum states. Then we have Vr = St( (VV)),, assuming the loss function under consideration is the Ly-loss. This result still holds for the Lı loss, as long as T S 4".
We prove these results in Appendices and respectively.
An important aspect notice here is that the significance of the sequential fat-shattering dimension extends beyond regret analysis. Several corollaries follow from Theorem 4.1 One such example is the fact that Theorem from Aaronson al. (2018), which has been shown to be optimal for mixed states, is also optimal for pure states.
Corollary 4.3. Let p be an n-qubit mixed state, and let E2... be a sequence of 2-outcome measurements that are revealed to the learner one by one, each followed by value b, E [0, 1] such that (Tr(F.p) - b.| S e/3. Then there an explicit strategy for outputting hypothesis states W1, w2.... ... such that [Tr (E))) - Tr( Exp)) > e for at most O ( values t. This mistake bound is almost asymptotically optimal, even if we restrict to be a pure state.
5
Extensions of Online Learning of Quantum States
5.1 The e-realizable setting
In practice, experimenter does not have access to the exact value of TTp..)) Assuming completely adversarial feedback is overly pessimistic and renders the learning problem particularly challenging. This motivates the consideration of the e-realizable setting, where the learner incurs the L1 loss with respect to a fixed quantum state p, and receives noisy feedback y/: at each round. Specifically, the feedback y/ is an approximation of Tr (Ep) with error parametrized by For instance, Ys may be drawn from a uniform distribution over the interval [Tr(E,p) e. Tr(EE,) + e), or from a Gaussian distribution A (Tr( (E,p), e). More generally, any non-deterministic distribution μ centered at Tr(E,p) is permissible.
We show that even in this more favorable setting, the regret admits the same lower bound as in the fully adversarial case-asse asymptoittlll independent of
Dr
inf
sup CEEN SEEE t=
sup PEC,
Σ Tr(EEar) - Tr(Eip))
QEA(C..
D.EP w B.rDDauMH
Theorem 5.1. The minimax regret in the c-realizable setting satisfies Dr = =((vnT) In particular, these bounds are independent of..
We prove this result in Appendix H
5.2 Smoothed Online Learning of Quantum States
The online learning framework discussed thus far fully adversarial, allowing the adversary to select arbitrary two-outcome measurements at each round t. However, highlighted in Section practical

---

learning tasks often target specific properties of the quantum state p. rather than aiming for full state tomography. Within the PAC learning paradigm, such tasks are typically modelled by fixing distribution D over the space of measurements, reflecting the learner's interest in particular subset of observables.
To bridge the adversarial and distributional regimes, we adopt the lens of smoothed analysis, which interpolates between worst-case and average-case models. Specifically, we require that at each round t, the adversary selects a distribution D, over measurements that remains close to the target distribution D. This models an adversary with limited power to perturb the measurement process.
This smoothed perspective is not merely a theoretical convenience - captures an important aspect of experimental practice. Indeed. quantum devices rarely implement measurements with perfect fidelity. Instead, small temporal fluctuations in control parameters, thermal drift, or calibration errors cause the realized measurement deviate slightly from the intended one Leibfried et al. (003) From a learning-theoretie theoretic standpoint, these deviations can be modelled as stochastic perturbations: at each round, the performed measurement sampled from distribution that is s-close the nominal one. Thus, smoothed analysis offers a principled framework for reasoning about online learning in the presence of structured noise in the measurement process.
Definition 5.2 (Smooth distributions). A distribution is said to be a-smooth with respect to fixed distribution D for a E (0, 1] if and only (Haghtalab et al. 2020]:
1. l is absolutely continuous with respect to D, i.e. every measurable set A such that D(A) = 0 satisfies y(A) =
2. The Radon Nikodym derivative du/dD satisfies the following relation:
dp dD
ess
<
(5)
Let B(a, D) be the set of all a-smooth distributions with respect to D. In smoothed online learning, the adversary is restricted by the condition D, E B(a, D). Note that in this setting we recover the case of an oblivious adversary for = 1, while we get the completely adversarial case for a + 0.
Recall the expression of minimax regret in Equation (T). In the smoothed setting, the expression gets slightly modified accounting for the restriction imposed on the adversary:
VT -
inf sup QEA(H) D.EB(o.D)
A D, 1=1 Σ (hr()))) inf LEH
E )
Ee(h(z))))
(6)
Here, the key difference with Equation ① is that D; is now restricted to the set of all a-smooth distributions with respect to D instead of all possible distributions on X. We recall that for quantum state learning, we have X' C {E E (2r) Spec(E) C [0, 1]], Hr = [Tr E C,) and target state p. For the sake of brevity, we will continue using the notation H; to indicate input data and h to indicate the hypothesis. The derivation here closely follows the approach in Block et al. 2022) (which derives the regret bounds for classical smoothed online supervised learning) with one important difference; in the original derivation, for given input 2; E X, the authors distinguish between a predicted label it E y and (x,))) distinction as our labels are always related to our inputs via the hypothesis.
where y the label space. We do not make this
Theorem 5.3. Let X' = { E Herme (2"), Spec(F) C [0, 1]} be the sample space. Define the hypothesis class H. (Tr,, E Cn, Tr(w²] =1} the set of n-qubit pure states, where Cn is the set of all n-qubit quantum states. Furthermore let a E (0, 1] be the smoothness parameter. Then we
have VT =0 =0
(V
|TTORT
We prove this result in Appendix K
Conclusion and Limitations
Lower bounds on fat-shattering dimension: this work, we established lower bounds on sequential fat-shattering dimension of various subproblems within the quantum state learning framework.

---

Crucially, we showed that pure and mixed states almost share the same asymptotical dimension. that, although our construction directly implies that the regular 6- Sat-shattering dimension pure states scales as S2( (2(zz)) whether we can recover 22 82 for pure n-qubits in the offline setting remains an open question.
Note
Consequences on regret: This lower bound on sequential fät-shattering dimension has several implications, including the key result that learning pure and mixed states the online setting will incur the same asymptotical regret for the Ly-loss. However, the lower bound for the L2 loss might leave room for improvement. Additionally, sequential fat-shattering dimension may serve as fundamental tool for deriving bounds on other key complexity measures in quantum state learning.
Smoothed online learning: Finally, extend our analysis from standard online learning of quantum states to the smoothed online learning setting. To our knowledge, this work represents the first application of smoothed analysis quantum state learning. In this setting, we establish an upper bound on the regret. However key open question is whether this bound tight.
Possible extensions to classical learning theory: While general (mixed) quantum state can be represented as a positive semi-definite Hermitian matrix of rank (up to) 2", a pure state can be represented as positive semi-definite Hermitian matrix of rank 1. The fact that this restriction on the rank of a matrix has no impact on the sequential fat-shattering dimension lower bound (and hence the regret lower bound) is highly con-intuitive and does not seem to apply in varied settings of classical learning: Alon et al.] [2016] shows that rank of sign matrices impact VC
dimension, |Brrtlett et al. 2022 shows that the e-fat shattering dimension of learned SCW matrices
of rank is ( n : (m + A Flog I
n + log (t))) and Srebro and Shraibman 2005 shows that the
pseudodimension of matrices scale linearly with the rank.
The reason why this scaling of dimension with rank vanishes in quantum is the additional assumptions on the density matrices, which are semi-definite positive, Hermitian, and of trace 1. Such matrices have however been extensively studied in Learning Theory (Tsuda et al, 2004| Shen et al., 2008 2009]. In addition, common matrices satisfying those conditions kernel matrices, and Laplacian matrices differ only for the fact that their trace is constant equal to 2m, where is the number of edges of the associated graph. We leave future work to see how results translate to these other settings interest.
normalized covariance and
10

---

Acknowledgements
The work of Maxime Meyer, Soumik Adhikary, Naixu Guo, and Patrick Rebentrost was supported by the National Research Foundation, Singapore and A*STAR under its CQT Bridging Grant, its Al and its Quantum Engineering Authors thank Josep Lumbreras, Aadil Oufkir, and
Singapore Programme (AISG Award No: AISG2-PhD-2226-01--655 Programme under grant NRF2021-QEP2-02-2 Jonathan Allcock for their insightful discussions and kind suggestions.
References
Scott Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089-31144 September 2007. ISSN 1471-2946. doi: 10. 10.1108/sspa.2000.11.1 URL hatp::/dxx doi wttp://0//111111///1//... 2007 2013.0113
Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Advances in neural information processing systems, 31, 2018.
Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors. 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 47-80, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https::/proceeddii saaieeddiinnmi.r..........m. mt..e/eerr..ee/////mepm
html
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing, 86)):111-664 2012. doi: 20.408
v008a006. URL //tps//r/// http://///bbrrroooooooui.g.ng computing. org/ articlastccleeee/e httg/arrcclese000000 v008a006
Joonwoo Bae and Leong-Chuan Kwek. Quantum state discrimination and its applications. Journal of Physics A: Mathematical and Theoretical, 4888)0003 January 2015. ISSN 1751-8121. doi: 10.
URL
doi. org/ 1088111111111111111111111
8/083001
Akshay Bansal, Ian George, Soumik Ghosh, Jamie Sikora, and Alice Zheng. Online learning of panoply of quantum objects, 2024. http://:://.aa...ooooo/b///a////
Stephen M. Barnett and Sarah Croke. Quantum state discrimination, Adv. Opt. Photon,, 1(2):238-2) 278. 2009. doi: 10. 1..4//AOP...00022.
Bartlett, P. Indyk, and Wagner. Generalization bounds for data-driven numerical linear algebra. Conference on Learning Theory, 2022. UtL.ttts:://pp nsf http://oobbbooo/oooo 1004/17744
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 482, 2003. URL https:
semanticscholar: :ntg/CorpuSI::::000 463216
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Muchine Learning Reseurch, pages 1716-1786. PMLR, 02-05 Jul 2022. URL TtLLhhttps://// htttps://proceedinnngg mlr. press/v178/ block22a. htm
Dik Bouwmeester, Jian- Wei Pan, Klaus Mattle, Manfred Eibl, Harald Weinfurter, and Anton Zeilinger. Experimental quantum teleportation. Nature, 39006660):55557779 December 1997. ISSN 1476- 4687. doi: 10. 10.1038/37539. http://t:/// htt//xxxooii..e wwtp:/oooo..rg////// 1038/37539
Nicolò Desa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. ISBN 100--00521---108-- doi: 10. 10.1001/CB00978051 1546921.
Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. When does adaptivity help for quantum state learning? In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 391-404, 2023, doi: 10.1109FFOC5799902293000
11

---

Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang, and Rui Yang. Adaptive online learning of quantum states, Quantum, 8:1471, September 2024, ISSN 2521-327X. doi: 10.22331/ 1-2024-09-12-144 1471. http/t/://dx doi org/ 220911/--024-09-122-
Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking, Nature Reviews Physics, 2(7):382-390) June 2020. ISSN 2522-5820. doi: 10. 0200442222-000008886-6 URL http:
7/dx .og.do....///.....ooo...o....... 1038/ 442254 020 0186-44
Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few pauli measurements. Physical Review Letters, 106(23). June 2011. ISSN 1079-7114. doi: 10. 103/phystevllet. 106.2l230000002000000 URL
http://dx. doi. org / 10. 1..03/hhyReeLeet..om 106, 230500
Robert Grone, Charles R. Johnson, Eduardo M. Sá, and Henry Wolkowiez. Positive definite
completions of partial hermitian matrices. Linear Algebra and its Applications, 58:108-:122 1984. ISSN 0024-3795. doi: https://oo..ag////..o0o000244473
URL https
//www www.sccencedirect.coom htt.://cccc....co.ooccccoo/oa///
David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. Quantum state tomog- raphy via compressed sensing. Physical Review Letters, 105(15), October 2010. ISSN 1079-7114. doi: 10.1 0003/physrevlet.10....5. 105. 150401
URL http://dx>: doi www.ddo...oooggooooooo wtt.:///........///.eee...t.tt..
Lov K. Grover. Quantum mechanics helps in searching for needle in haystack. Physical Review Letters, 79(2)3355332,, July 1997. ISSN 1079-7114. doi: 10. 10. 10.100///yys URL
http://dx.co doi. www.:roi...ooooooo
org/10../... /0. 1103//hysseeeett....mmm 79.325
Naixu Guo, Feng Pan, and Patrick Rebentrost. Estimating properties of quantum state by importance- sampled operator shadows, 2024. URL ltttps://axxii .rg httgg/bb/233055 003223335500094444
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 113,925, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 978 14503413255 doi: 10.1 10.1145289751882887555 URL
1145 2897518. 2897585
2897758
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differen- tially private learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9203-9215 Curran As- sociates, Inc., 2020. URL//bttps//pprcceediig www.wgs..........ee..... ww/ppppr.pp.. lappppprflleeeeee files/ https//pperr/20000 Fil16666ree066666677766888811113
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. Journal of the ACM, 7 71(3):1-34, 2024.
Hsin-Yee Yuan Huang, Richard Kueng, and John Preskill. Efficient estimation of pauli observables by derandomization. Physical Review Letters, 127(3). July 2021. ISSN 1079-7114, doi: 10.1 physreviett.1277 0300033 URL http::/tt///t h/tp::///xx doi. org/ 10. 1et111100/haae www.:///////eett...ooo 127. 030503 1370030
Richard Kueng, Holger Rauhut, and Ulrich Terstiege. Low rank matrix recovery from rank one measurements. Applied and Computational Harmonic Analysis, 42(1))88-116, 2017.
D. Leibfried, R. Blaut, C. Monroe, and D. Wineland. Quantum dynamics of single trapped ions. Rev. Mod. Phys., 75:281-2300 --24, Mar 2003, doi: 10. 00.100//e/MMddhyy.5...55 URL https //link. aps www.///g////ooooooooo 1103 /00//eeModPhys 75. 281
Erik Lucero, M. Hofheinz. M. Ansmann, Radoslaw C. Bialezak, N. Katz, Matthew Neeley, A. D. O'Connell H. Wang, A. N. Cleland, and John M. Martinis. High-fidelity gates in single josephson qubit. Phys. Rev. Leut 100:247001, Jun 2008 doi: 10. 10.1Phyyysseelll.et 1tt. 100.24701. URL https: / //tp///in../////////// aps http://oo/11... 1100/ 1103/PhysReLLett...mmm 100. 247001
12

---

Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Explo- ration versus exploitation when learning properties of quantum states. Quantumn 6:749, June 2022. ISSN 2521-327X. doi: 10.22331/4-20022----9-9-999 9-2022-06-29-77
URL http://dx doi org/10. 22331/
Josep Lumbreras, Mikhail Terekhov, and Marco Tomamichel. Learning pure quantum states (almost) without regret, 2024. URL httpt:://xxsii......./ org./ htt//bb//24000 18370
Vaisakh Mannalatha, Sandeep Mishra, and Anirban Pathak. A comprehensive review of quantum random number generators: concepts, classification and the origin of randomness. Quantum Infor- mation Processing, 22(12), December 2023. ISSN 1573-1332. doi: 1121000/11122--03--417333
URL http://xx doi. org. 10///10.1100 100100000/11111 023 04175-y
Daniel Miller, Laurin Fischer, Kyano Levi, Eric Kuchnke, Igor O. Sokolov, Panagiotis Kl. Bark- outsos, Jens Eisert, and Ivano Tavernelli. Hardware-tailored diagonalization circuits. npj Quantum Information, 10(1), November 2024. ISSN 2056-6387. doi: 10.0038/41134-02400000000 URL
http://dx. doi ooooorg///// 10 1038/ s41534 024-
Philipp Neumann, Johannes Beck, Matthias Steiner, Florian Rempp. Helmut Fedder, Philip R. Hemmer, Jörg Wrachtrup, and Fedor Jelezko. Single-shot readout of single nuclear spin. Science.
12945541) 2010. doi: 10. 126/science. 11t.nne...11997... 189075. URL https: //ww//wwwww// www.nceiencccccc org/
doi/abs//0. 1126 ht1/////ccencee 1189075
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexi- ties. J. Mach. Learn. Res., 16(1):155-186, 2015a.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:1 11-153, 2015b.
Asad Raza, Matthias C. Caro, Jens Eisert, and Sumeet Khatri. Online learning of quantum processes. 2024. /tRLhttss///axxxv org/ abs /bw/ 24222422660000
Chunhua Shen, Alan Welsh, and Lei Wang. Psdboost: Matrix-generatie linear programming for positive semidefinite matrices learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bot- tou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Asso- ciates, Inc., 2008. URL httptttts////occeeeteeee hew.rooceeennnss.......s....... nwwrips....... ctteeiis.cccpppppe wwtpppppe..iiiiieeee wtt.ee/epppppe/0000... pd
Chunhua Shen, Junae Kim, Lei Wang. and Anton Hengel. Positive semidefinite metric learn- ing with boosting. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009. URL
www..nn...pp..... wwtpccppppp....cc files/ /aapeer_/Lees/ppppr/2///////11 /aper//009//i1ee/ pdf
Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms quantum computer. SIAM Journal Computing, 26(5):14441150, October 1997. ISSN 1095-7111. doi: 10.1137766099753999599991121
URL /Rtp::t:://dxx http:::/dxxddii.orggggg www.:doo..ogg/10/ 1137/
$0097539795298172
D.R. Simon. On the power of quantum computation. In Proceedings 35th Anmual Symposium Foundations of Computer Science, pages 116-123, 1994. doi:
Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385-63 2004.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In Peter Auer and Ron Meir, editors, Learning Theory, pages 545-560, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
ISBN 978-3-540-31897 192-777...
Koji Tsuda, Gunnar Rätsch, and Manfred K. K Warmuth. Matrix exponential gradi- ent updates for on-line learning and bregman projection. In L. Saul, Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004. URL Uttptttsss///p/ooeeeedggg wwwpeeseeerrissccco saaper_filee//pper//0////iii haro054488r00222266977666666 .pff
13

---

Bujiao Wu, Jinzhao Sun, Qi Huang, and Xiao Yuan. Overlapped grouping measurement: A unified framework for measuring quantum states. Quantum, 7:896, January 2023. ISSN 2521-327X. doi: 1,222331442222--01113-333
URL https://doi...... org/ 10. 22331 2000///12222-------2-
Liming Zhao, Naixu Guo, Ming-Xing Luo, and Patrick Rebentrost. Provable learning of quantum states with graphical models, 2023. URL
14

---

A Proof of Theorem 3.1
Proof. Without loss of generality, we set X = {1 with E [0, N - 2]. Define x as the complete binary tree of depth 7 such that Vt e [2'] V (#1)7-1
(c) [i)
(7)
Furthermore, define (Figure I {+1]7-)
as the complete binary tree of depth T such that VT E [T], Ve
1 Vi(E) =
Σ cx k
42 2-2
(8)
2
k=
k=0
Here, we set ED 1. Given (x, v), we now set:
(x(())
Σ k=
102-k-11p)) + 1 - Σ
c22 k-1 11).
2
(9)
k=
Then, for T [10g (which implies S 2 V E (+1)
1A E [T],
have:
T-1
c (x)) c
Σ
cx2 k-1 Σ
42 --
k-=
k=0
T-1
=4 Σ
422 222kk11
k=
T-1
= 2 +
Σ
k=t+1
T-1 Σ 2-k-
22
b=++1
= 2-1111 (2-t-1 - 2 2-T)
2 8
(10)
where the first incquality follows from the minimum value that the term e, 7- cx2 2 k can
take, and the last inequality is by direct computation and the assumption T = log 5 ). Thus, we show that the set X' is d-shattered by the hypothesis class H., with sfats(H,, X) 2(log2 (f)).
O
We can replace v by slightly modified version of itself, where each node is scaled by a factor v. Therefore, the quantum state associated to a path has an amplitude corresponding to |i): Tr(li) (i)w bounded by N. We will write Tx T| = (x, v) the resulting vaiued tree and call it the Halving Tree of depth? T. The index indicates the Von Neumann measurement associated to x.
B Proof of Theorem 3.3
Proof. Let e [V]. Define v as the complete binary tree of depth such that Vt E Ve T-
ve(c) 27
(11)
Furthermore, denote (Figure 2 the complete binary tree of depth T such that Vt E [ c (+1]7-1,
xx(E) = t- (t- -1---- 1/.
(12)
We refer to the pair (x, v) as the Von-Neumann tree T
15

---

Given the Von Neumann tree, we now associate each path to a pure quantum state:
((())
VK+1 N 1),
(13)
VK
where K = Ei=o e1 and 1==1 is an indicator function which takes value 1 if c = and 0 otherwise. Then, for 0 < 27 V {+1]+-1 74 E [7]:
1a=1
c (x ve(c)) = ct
K + 1
2T
2 6.
(14)
Thus, we show that the X' is 5-shattered by the hypothesis class H with sfats (H, X) ((min()) 2))).
C Proof of Theorem 3.4
Proof. Without any loss of generality, we can chose the sample space to be a set Von Neumann
measurements X' {|t (i} E [0, N - 1.] Denote t' = - and = t- 1-'. We then define
x the complete binary tree of depth ((N 1) such that Vt E [T(N 1)), (=1) I(--))11
xx (t')
(15)
Furthermore, denote v the complete binary tree depth T(N 1) such that Vt E [T(N- - 1)], (+1)7(N-1)-1
vz(e) 2n+1 (1 + Σ 2
(16)
k=1
We refer to the pair (x, v) as the Von Neumann halving tree T Tenh- The name follows from the fact that the trees and as defined in Equations (15) and (16) can be constructed by replacing each node on the f-th layer of Ten for both X' valued and real valued parts, by the corresponding parts of the halving tree [t, T).
Given the Von Neumann halving tree we can now associate each path to a pure quantum state:
N-2
(v((e)
Σ
Σ
aa/N-1 1)
(17)
where Vi E [0, - 2].
a == ==V + 27 E(tttTr 2
(18)
Then, for 5 2n4T41, we can show that V [+1] Vt E [TNN- - 1)]:
ee ex[Tiw(e)(x((t) v.(e)) = (+) 2T+n-1 E('++)7 2n+1 +
2 *)]
1
Et Et
6KTTC2
2 (1 1+
2 2-1]]
1=1
k=
"
2x
2
k=
Σ
Q4Te2-k
2
28+1
k=
2
(19)
16

---

In particular, let k E N Taking å and T [log2(167) we get TN = 2(no 1+1) Therefore, we have shown that the set A' is 5-shattered by the Hypothesis class Hr with sfats (HG.) 0 ()) Vn 1.
D Proof of Lemma
To prove Lemma 3.5 we rely on Theorem 7 in Grone et al. [9844]. We begin by introducing the necessary definitions. Let G = (V. E) be a finite undirected graph. A cycle in a sequence of distinct vertices U1, v2, Us E V such that (v 04+1 E E for all E [s IJ. and {us, vi E E. A cycle is said to minimal if and only it has no chord, where a chord is an edge (u, ji-il jl 1 and {i.}} * {}.
with
matrix said be G-partial when its entries way are determined if and only {i.}} E, while other elements are undetermined. A G-partial matrix w is said to be non-negative if and only if (a) wig = Wjis vii,j] E and (b) for any clique of G, the principal submatrix to C (which has entries corresponding to C) is positive semidefinite. Recall that clique C of g is a complete subgraph of G. The corresponding principal submatrix obtained by keeping only the indices in C.
corresponding
completion of a G-partial matrix w is full Hermitian matrix M such that My wij for all {i,j} E E. We say that M is non-negative completion if and only if M is also positive semidefinite. graph G is said be completable and only any 9-partial non-negative matrix has non -egnnegtteve completion. With these definitions in place, we proceed to state the relevant results in Grone et al.
1984..
Lemma D.1 (Grone et al. 1984) ) A graph G is completable and only if every minimal cycle in the graph is of length < 4.
Now that we have covered the necessary background, we can proceed to prove Lemma 3.5
Proof. Let w be a partial matrix as stated in Lemma 3.5 Consider the graph G = (V, E), where
V = [N] and E ((i,)),E [N]. (1,0)) (fi, [M]]
2
3
N
Figure 4: Graph representation of G = (V, E)
One can easily check that G is completable using Lemma D.I Therefore, if we prove that w is non-negative G-partial, it will have positive semidefinite Hermitian completion. Combining with the first two conditions in Lemma 3.5 we can show that the completion of w is Hermitian, positive semidefinite, with trace equal to 1, and therefore is density matrix. Now to show that w is non- negative G-partial, let C {1 } be a clique of G. Since |wis S 2/N-I by assumption, the principal submatrix of corresponding to C, i.e.,
2
Wli
(20)
Wil
2(N-1)
can be shown to be non-negative.
17

---

W112
WIN
112
2(N
2(N-1)
W1N
2(N-1)J
Figure 5: General form of the partial matrix described in Lemma 3.5 the unspecified entries in the matrix.
The interrogation marks denote
E Proof of Theorem 3.6
Proof. Set X = [o,,, i E [N - 11} where Eo,; (10) + |0i{|| + [i] + [i)(0]). Define
:'= | and = 1-1 - TV' for T > 0. Write the complete binary tree of depth T(N 1) such
that Vt E [T(N 1 [+1]7-1.
xx(E) ro
(21)
and v the complete binary tree of depth T(N - 1) such that VE [T(N - 1) {+1)7-1
1
Vz(c) AVN
24Tr2~*) A=1
(22)
The pair (x, v) resembles the Von Neumann halving tree constructed in the previous section, with the key difference being that the nodes in the X valued part of the new tree are now labelled by different class of measurement operators. We will replace with slightly modified version
ve(c) = v,(E) + 1 N-T)
(23)
We now associate every path e to any nonnegative completion w(e) of part(an....an where vi e [1.N- 1].
1
a: = v 2T+2 N - ((+1)T
(24)
Recall that the partial matrix part(a aN 1) satisfies all the conditions in Lemma 3.5 and hence can be completed to a valid density matrix (c).
Then, for 8
2 have that V e E (=1)7(--1)-) Vt [T(N- 1)].
e, ([TTw(e)(x((e)) ve(e)]
(6) ST+2VN-1 E(F+2)T
1
4vN (1 + Σ
2 2
km
T
+
EKTTH22
(1 +
Tk [1]
A
AVN
kml
k
(4TTF-k
4/N
k=
1
2
AVN
21+1
k=
28.
(25)
2 By taking 8 + and T [log2( / ). get TN Q(nd 1+7). Therefore, have shown that the set X is d-shattered by the Hypothesis class H., with sfats (( Vn < 2. D
18

---

F Proof of Theorem 4.1
Proof. Set X {Eo,i, IN - 1]} where Ea,; (10) |, + [0) [()()]). Define
t'= L'= and = t - 1 Tt' for T > Write x the complete binary tree of depth T(N 1) such
that Vt E [T 1)
[=1]"-1 {
(x(E)= = Eo
(26)
and v the complete binary tree of depth T such that VI [ (=1]²-1
i
vr(c)
(1+ + Σ
(27)
AVN
A=
We can associate every path e to pure state
N-2
N-2
(x(())
1
00)
04 1)
1
Σ
ap
IN 1)
(28)
V2
2
where,
a, = vor(e) + 2T -1 (i+1)7
(29)
Here i E [1,N - 2]. Let w. v2 2/2 + a a2441). Then, for 8 22 22
we have that
VEE (=1]T(N-2)-1, Vt [T(N 2)].
f & ((T) (x,(e)) - ww(()) = ((++I)((E) + 22+2
(2/+2)T
(1 +
2-k)]
v2
4 N
k=1
T
i
tt
(1 +
GKTTH2-
(1 +
Ck+TH 2-k
22 AVN N -
AVN -1
k=1
k=1
T
Σ
2
4 2/2(NN - 1)
k=i+1
1 4 - 1)
+
Σ
6
2i+1
k=ī+2
Nd
(30)
In particular, let l: E N By taking 8 and T =
[log
48/N ). we get TN = Ω(nō IT ).
N
Therefore, we have shown that the set X' is d-shattered by the Hypothesis class H. with sfatt ( (H, X²) = Vn 2.
2 m. ((H)
G Proof of Corollary 4.2
the minimax regret is lower bound by the Proof for the L1 loss. From Rakhlin al. [2015a b). sequential fat-shattering dimension as:
Vr sup V
(52T 8T min (Hn, X)), T}
4 820
provided that the loss function under consideration is the Losss Now combining this result with
the lower bound on sfats (Hn, X) established Theorem w. get Vy 2 ((vTT).
LI
Proof for the Lo loss. From Equation ① and taking the ye be Rademacher random variables, we get:
19

---

VT 2
sup
inf
E
(he(
y1)2
inf
Σ (h(xr) vn)
IiEH
NEH
t=l
T
T
M
sup
inf MEH
+ 122)
By sup
-(h(2))) - y1)2
1=1
NEH
T
T
IV
sup
En sup
- (1(()))) - y1.
NEH
T
sup 21
By,, sup
(h(x)z) - yi)²
hEA t=1
sup
Byg sup NEW t=1
Σ 20ch(xr)) (126)))
1=1
T
sup
sup
21(x+)) (xx)) + sup NEH
2h(x)) 11 12(())))
1=1
KEH
T
IV
sup
sup
(2xe( - 1((x))) +
2h(xz) - 112 112 IN
2
NEH
T
IV
sup
1=1
2
NCH t=1
sup
Σ
h(x))
+
Σ
t=1
N
2
N2
1
3T
A
(H)
(31)
2N
Where we used the fact that
T
(T)
sup
RT(H, H)
21
t=1
sup
E
sup
(ete)
2x
t=1
WCH
(=1
sup
sup MEH
he((
sup hCH
ho(xe)
t=1
T
sup
sup bEH
hx(()))
(32)
t=1
1=1
H Proof of Theorem 5.1
Proof. All need do in order lower bound Vr is exhibit particular strategy (Dz)xejr) the adversary can adopt. We will then show that such a strategy guarantees a minimax regret greater then (VvTT), independently of the strategy picked by the learner.
It was shown in Aaronson 2007 that n--ubbi quantum states, considered as hypothesis class, have (6, -----iee-aaattriie dimension greater than D) J. Let T' N and write å / x This means that there exists (Ei)eE()) E x such that V(E,) {+1)" P 3p Cn, Vt e [D]:
20

---

2 8
8a 1
6)
if c2 -1,
Tr(Pap) E
(33)
+ 8, 2 8
8a
if 62 1.
We will denote by p 2D quantum state in Equation (33. We can now show that if the adversary picks E, every round no matter the strategy chosen by the learner, there exists a quantum state p that will guarantee loss greater than Vnl.
Cn the function that associates every path to the corresponding
For every t [D], write G = sgn E Tr((Ew))) Then, we clearly have that
T
E Win
Tr(E TT((p) 2 D8
2 ((T - nT
IV
(34)
Remark H.1. The last thing we need check that the feedback received by the learner doesn't give much more information than the interval of size in which lies Tr(Epp). as defined in Equation 33
yt U(Tr(EE,)) e, Tr(E,p) + el) for instance, this amounts 2 8² id est 2 + For general distribution, picking 7'' big enough such that the probability of yr E [TT(Eep)) -E, greater than will only divide the lower bound by
Finally, the fact that B8y.) = Tr(Epp) allows us to conclude.
Therefore, Dr = D(vTT). easy to see that D S VT = O(VTT).
I Regret bounds with sequential complexities in classical online learning
Notions of complexity for given hypothesis class have traditionally been studied within the batch learning framework and are often characterized by the Rademacher complexity [Bartlett and Mendel?
son 2003
Definition 1.1 (Rademacher complexity). Let X' be sample space with an associated distribution D and H be the hypothesis class. Let (Iı))y[mm) D be sequence of samples, sampled i.i.d. from X'. The Rademacher complexity can then be defined as:
Rm, (H) (Dy)<Dm
E
sup
KEH
where 'r .mm) called Rademacher variables, that satisfy P(c (1c=+)) P(c -1) 1/2.
Perhaps not surprisingly, in addition to being indicator for expressivity of given hypothesis class, Rademacher complexity also upper bounds generalization error in the setting of batch learning Bartlett and Mendelson 2003).
Rademacher complexity generalises to sequential Rademacher complexity the online setting [Rakhlin et al. 2015a]. In order to define sequential Rademacher complexity let first define X-valued complete binary tree.
Definition 1.2 (Sequential Rademacher complexity). Let be a X-valued complete binary of
depth T. The sequential Rademacher complexity of a hypothesis class H on the tree x is then given
as:
Ri x) = -
E sup NEW
ex((x((e)]]]
21

---

The x dependence of the sequential Rademacher complexity can be subsequently removed by considering the supremum over all X'vaalued trees of depth T: (H) supx Mr (H.,x)). Similar to how Rademacher complexity upper bounds the generalization error, the sequential Rademacher complexity was shown upper bound the minimax regret [Rakhlin et al. 2015a]. For the case of supervised learning, the following relation holds:
VT S 2LT (H).
(35)
Here, comes from the fact that the loss function considered is L-Lipschitz.
The growth of sequential Rademacher complexities has been shown to be influenced by other related notions of sequential complexities. One prominent example the sequential fat-shattering dimension [Rakhlin et al.; 2015a]. It was shown in [Rakhin et al. [2015a] that this dimension serves as an upper bound the sequential Rademacher complexity, which subsequently provides a bound on the minimax regret as per Equation (35). Similarly, recall that the minimax regret can be lower bounded by the sequential fat-shattering dimension (Equation (3) (3), provided that & (ft (2x), Mc) = |/te (xx,)) -0: yel and that P is taken to be the whole set of all distributions on X. In fact, it is also lower bounded by the Rademacher complexity [Rakhlin et al. 2015a
VT
sup D.EP
sup Σ ceh(x((e))
ZiNDD 1=1
REH
sup 4/2 8>0
8 mintsfats 2),, T)
(36)
where e = (41, 62, ... ,er) are Rademacher variables.
J
Coupling
To establish regret bounds in smoothed online learning, Haghtalab et al. (2024) Block et al. [002 introduced the concept of coupling. The key idea here is that if the distributions (D.) are a d-smooth with respect D, we may pretend that in expectation the data is sampled i.i.d from D instead of (D=Y== For more formal description, define (a D) to be the set of joint distributions D,, on X where each marginal distribution D+(- ...y Tt-1) is conditioned on the previous draws.
Definition J.1 (Coupling). A distribution D, E (a, D) is said to be coupled to independent random variables drawn according to D there exists a probability measure IT with random variables (xx,, Zi [ETTEE II satisfying the following conditions:
1. xy. D,(1211222""" 1t-11).
2. {2: heftl.e ~ D@AT
Te-ak, 3. With probability at least ak we have I E (Z) Vt E [T].
The last relation is particularly interesting and is used to derive the regret bounds for smoothed online quantum state learning.
K
Proof of Theorem 5.3
For this proof, we will use the notion of Rademacher complexity and few related results that can be found in Appendix [[] We also use the concept of coupling described in Appendix
Consider the sequential Rademacher complexity Ry H. x) in Definition 1.2 defined on the function class f o H. For the purpose this proof let us consider slightly modified version of the sequential Rademacher complexity defined as:
Re o H, Dx) xnD,
Ri(l H,
T
E
E
sup MEH
(37)
x~D,
T é
22

---

where DA E Br(a,D) Moreover we will call (e H. Br) = eu Ry o ).). The key idea now is to relate (e H. DA) to R(H) (Rademacher complexity assuming i.i.d. data inputs; see Definition I.I. This can be achieved using the idea coupling discussed in the previous section.
Lemma K.1. Let DA E Br D) be a distribution that is coupled to independent random variables drawn according the distribution D, as per Definition J. Let H be Hypothesis class and & be the loss function. Then we have Ry (E H. xx) S
T e ox Re H)
Proof. Let A be an event that xx(E) E 1 Vt E [7]. Furthermore, let XA be the corresponding indicator function and XA be XA. Then have:
Ry o HH =
E X
E
sup
(((((x(())),,xxxx())))
KEH
T
E
T
E
sup
e (x
x-1I
NIHH
j=1
Σ (x))
XA sup
x-11
hEN j=1
Σ (()(
E x~1l
E
XA= sup
T
KEH
((((((((()) + +722-ot
E
XA sup hEH
E
E
XA sup NEW
e (((h((x())))
x~1l
Σ
Σ
+ F8e E [=,e(M(ZZ),nn(22]]]] St
j (c)
T
E
E
XA sup
((((h(xx(E)),,xxx((()))
x-1l
T
+ E Σ
=n((h(12)) + 22e -k
j.Z (x,(()
1=1
E
sup
Σ Σ
(x((MZZ),,,
D
MEH
< TT okk + (e H).
(38)
Here the first inequality comes from the fact that coupling constructed in the previous section bounds the probability of (x) & { /- at least for one value of l. The second inequality follows from the fact that o, has a zero mean while the third one follows Jensen's 's inequality.
Proof of Theorem 5.3 As per Equation (35 Vr is upper bounded by the sequential Rademacher complexity (H.. Therefore it suffices to establish an upper bound on the latter in the smoothed setting considered here. Equation (38) bounds the distribution dependent sequential Rademacher complexity with the standard notion of Rademacher complexity which assumes independent samples. Assuming the loss function to be L-Lipschitz, the quantity Rur H. can be upper bounded as:
Ru H) I LR (H).
(39)
23

---

The sequential Rademacher complexity can be bounded above by the sequential fat-shattering dimension. Likewise, one can establish upper bounds on (xr(H))
2 REI (H) S inf 4akT 12 KT (. K (H) log 5 _d6].
(40)
where K and are constants. Note here that fats unlike its sequential counterparts assume independent data. Therefore one can recover the definition of fats(H) from their sequential version by replacing the X and vavued tree by the sets X' and R. Combining Equations (38) to (40) and setting k 2 2oo T get:
SaTlogT Rr(e o H. ST+ inf as0
2T Fllog T S( V Kfatts / (H) log fdd
+ 12
(41)
a
Now using the relation that fat, (Hn) = O(n/82) when Hn = (Tr, w E C.. and setting = = get:
laT
2nT log T
2
Ar o DA) S $1+ L inf a.0
12
82 log d8
(42)
Finally to eliminate the infimum in Equation 42p
recall that E [0, 1] and therefore for any
function f on a we get inf f(a) & f(a = a²); a E
[0, 1]. Thus setting a Tlog T we get:
no
(e Hn, Da) -0 =0(1
nT log T
(43)
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In addition do the abstract, the paper's contributions and scope are detailed in Section |
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All the assumptions are explicitly stated in the Theorems. In addition, the limitations of the paper are discussed in Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer:
[Yes]
Justification:
All the complete proofs can be found in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include any experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttpe//gguddeeeeeeouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
27

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wwaaaaecccccp/c////aaaaa
Answer: [Yes]
Justification: We affirm that we have read the NeurIPS Code of Ethics and that our research fully conforms to its guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is purely theoretical and does not involve deployed systems, real- world data, direct societal applications. As such, believe that it does not present immediate positive or negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve the release of data models, and poses foreseeable risk of misuse, as it is purely theoretical and focused on quantum state learning.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
31


Reviews:
[{"review_id": "QpMNCgVWAM", "reviewer": "Reviewer_NRAe", "summary": "This work explores quantum state learning with online learning theory. The authors prove that pure and mixed states share nearly the same sequential fat-shattering dimension, which is a key measure in online learning that dictates the performance of a learning algorithm. As a result, the regret scales identically for both types of states. This is a significant finding because, in standard settings, pure states are known to be much easier to learn than mixed states. The paper also extends its findings to more practical scenarios, including the case where measurements are not perfectly accurate, and smoothed analysis.", "questions": "1. The paper's central result is that the separation in learning difficulty between pure and mixed states vanishes in the online setting. What are the specific properties of the adversarial online framework, as opposed to standard tomography and other quantum online learning works, that cause this equivalence in hardness?\n2. What is the main advantage of your new proof strategy from previous results? Is it possible to adapt this strategy in the classical learning theory?\n3. For the smoothed analysis, what would be a practical, experimental situation where the adversary's measurements correspond to $sigma$-smooth rather than completely adversarial or completely random?", "limitations": "The limitations of this work are included in the Strengths and Weaknesses.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The central claim—that online learning of pure quantum states is as hard as learning mixed states—is highly impactful. It challenges the common intuition derived from standard tomography, where a clear separation in learning complexity exists. This can inspire the following research, including the classical learning theory. \n2. The authors introduce a new proof for the sequential fat-shattering dimension by the matrix completion. It is interesting to see new techniques coming out from the intersection between quantum and learning.\n3. The authors also introduce several extensions, including a realizable setting, smoothed analysis, and L2 loss. These additions make this work comprehensive.\n\nWeakness:\n1. As also mentioned in the conclusion and limitation section, it is not clear whether the conclusion for the online learning setting is still true for the offline setting (difference between sequential fat-shattering dimension and fat-shattering dimension). If true, this can lead to an even stronger result.\n2. The main result focuses on the L1 loss case. Authors also have some discussions on the L2 loss case, but not perfect. It feels a lack of explanation why L1 loss is important, or what are the technical limitations that authors can not explore other loss.\n3. For the smoothed analysis part, it is not clear when such a smooth distribution could be possible in practice and why this generalization is important for quantum.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review. We are especially glad that they found our main result impactful and appreciated the novelty of our techniques.\n\n**The main result focuses on the L1 loss case. Authors also have some discussions on the L2 loss case, but not perfect. It feels a lack of explanation why L1 loss is important, or what are the technical limitations that authors can not explore other loss.**\n\nWe thank the reviewer for raising this point. The focus on the $ L_1 $ loss is closely tied to the fact that Rademacher complexity is naturally aligned with $ L_1 $-loss. In particular, standard symmetrization techniques and contraction inequalities used in our regret analysis are sharpest when applied to $ L_1 $ loss.\n\nExtending our results to other losses, such as $ L_2 $, requires either extra constraints—such as the one we have in our derivations—or adapting existing complexity measures to take into account the curvature of the loss function. The latter falls outside the scope of our current analysis.\n\nMoreover, we note that the $ L_1 $ loss is commonly used in quantum state estimation tasks due to its operational relevance in distinguishing quantum states [1,2,3], which further justifies our focus.\n\n**The paper's central result is that the separation in learning difficulty between pure and mixed states vanishes in the online setting. What are the specific properties of the adversarial online framework, as opposed to standard tomography and other quantum online learning works, that cause this equivalence in hardness?**\n\nA key feature of the adversarial online setting is that the sequence of measurements is chosen adaptively, based on the information available to the learner at the time. This adversarial adaptivity prevents the learner from exploiting the low-rank (rank 1) structure of pure states as is the case in the stochastic or batch settings—where the measurements are entirely chosen by the learner. In this sense, although pure states are intrinsically simpler than mixed states, the online adversarial framework highlights that simplicity alone is not sufficient: a learning strategy must actively capitalize on this simplicity. However, this strategy cannot be implemented in the online adversarial setting where the measurements can be chosen adversarially.\n\n**What is the main advantage of your new proof strategy from previous results? Is it possible to adapt this strategy in the classical learning theory?**\n\nOur response to Reviewer~Yd1X provides a detailed account, but we briefly highlight the key idea here. Unlike prior approaches that rely on newly defined complexity measures or information-theoretic tools, our proof strategy is conceptually simpler and fully constructive. This not only extends existing regret lower bounds to the setting of pure quantum states, but also identifies the specific class of pure states that are the hardest to learn in the online adversarial setting.\n\nWe believe that this characterization of hard instances within a hypothesis class has potential relevance beyond the quantum setting. In particular, similar constructions may be useful in classical learning contexts involving black-box predictors subjected to adaptive querying. Such scenarios arise in the design of secure or privacy-preserving systems, where identifying hypothesis classes that are provably resistant to extraction is a central challenge.\n\n**For the smoothed analysis, what would be a practical, experimental situation where the adversary's measurements correspond to sigma-smooth rather than completely adversarial or completely random?**\n\nThanks for mentioning this. We feel that smoothed analysis may be useful for considering the noise in quantum measurements. In practice, quantum devices rarely implement measurements with perfect precision. Indeed, small perturbations (typically evolving through time) in control parameters can cause the executed measurement to deviate slightly from the intended one [4]. From a learning theory perspective, this can be modelled by the measurements being sampled from a $\\sigma$-smooth distribution centred around the intended distribution. Thus, smoothed analysis captures the realistic scenario where measurement choices are subject to noise.\n\n\nWe thank the reviewer once again for their time, careful reading, and thoughtful feedback.\n\n**References**\n\n[1] Aaronson, S. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089–3114, September 2007.\n\n[2] Aaronson, S. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018.\n\n[3] Chen, X., Hazan, E., Li, T., Lu, Z., Wang, X., and Yang, R. Adaptive online learning of quantum states. Quantum, 8:1471, September 2024.\n\n[4] Leibfried, D., Blatt, R., Monroe, C., \\& Wineland, D. Quantum dynamics of single trapped ions. Reviews of Modern Physics, 75(1), 281, 2003."}, {"review_id": "cNFyITElNf", "reviewer": "Reviewer_Yd1X", "summary": "Quantum state tomography seeks to reconstruct an unknown quantum state $\\rho$ from measurements. In standard (offline) settings, learning \\emph{pure} states is substantially easier than learning general \\emph{mixed} states, with the sample complexity for pure states scaling as $\\widetilde{\\Theta}(N^2)$ versus $\\widetilde{\\Theta}(N^4)$ for mixed states, where $N = 2^n$ for $n$ qubits. However, these results do not account for adversarial or sequential measurement scenarios.\n\n\nIn the online learning framework, learning proceeds as a repeated game over $T$ rounds. In each round $t$, the adversary selects a measurement $E_t$, and the learner predicts $\\mathrm{Tr}(E_t \\omega_t)$ for some hypothesis state $\\omega_t$. The learner then incurs a loss (e.g., $\\ell_1$ or $\\ell_2$) with respect to the true value $\\mathrm{Tr}(E_t \\rho)$. The performance is measured by the \\emph{regret} denoted $V_T(\\mathcal{C}_n)$ \nwhere $\\mathcal{C}_n$ is the set of $n$-qubit quantum states.\n\nTheir main results are as follows:\n \\textbf{No separation in online learning:} The paper proves that, in the online learning framework, \\emph{learning pure states is as hard as learning mixed states}. Both classes have essentially the same \\emph{sequential fat-shattering dimension}, leading to identical regret scaling.\n    \n \\textbf{Regret scaling:} For both pure and mixed states, the minimax regret scales as\n$$\n    V_T = \\Theta(\\sqrt{nT})\n    $$\n    where $n$ is the number of qubits and $T$ is the number of rounds.\n    \\item \\textbf{Technical approach:} The authors provide new lower bounds on the sequential fat-shattering dimension for pure states, matching those for mixed states, by constructing information-extracting trees and using matrix completion arguments.\n  \nThey have some additional results as well\n In the \\(\\epsilon\\)-realizable setting (where the learner receives noisy feedback), the lower bound on regret remains unchanged and is independent of $\\epsilon$.\n In the \\emph{smoothed analysis} setting (where the adversary is restricted to be close to a fixed distribution), the regret upper bound improves to\n        $$\n        V_T = O\\left(\\sqrt{\\frac{nT \\log T}{\\sigma}}\\right)\n        $$\n        where $\\sigma$ quantifies the degree of adversariality.\n\n\\textbf{Contrast with other settings:} In some restricted online learning scenarios (e.g., bandit feedback), pure states can be learned exponentially faster than mixed states. However, in the general online learning setting considered here, this separation vanishes.\n\\end{itemize}\n\n\\textbf{Implications:}\n\nThe result is counterintuitive compared to classical learning, where restricting the hypothesis class (e.g., to low-rank matrices) typically reduces complexity.\nIn adversarial or highly dynamic experimental settings, learning pure quantum states cannot be made significantly easier than learning mixed states, despite the much lower sample complexity for pure states in standard tomography.", "questions": "None.", "limitations": "Mentioned above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- I think the paper addresses a fairly natural question and makes a surprising contribution.\n- I like the idea of using smoothed analysis for quantum learning (as it has shown some interesting results classical recently)\n- Understanding pure state versus mixed state learning is a natural question\n\nWeakness:\n- It is not very clear to me at least from the introduction, what is the main technical challenge of their work? I do feel many of their results extend straightforward from classical techniques, but it'd be nice if they made clear what was the roadblocks in establishing these results. \n\n- I think from an ML perspective and quantum perspective the technical novelty is a tad limited (again the authors should correct me if wrong), but i still its a nice surprising result.\n\n- The bounds are non-optimal, did you make any efforts in tightening the upper and lower bounds? It seems like the bounds that are shown here directly follow from classical results (which are quantized in this paper).", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their insightful and constructive review, which offered a clear and comprehensive summary of our work, while recognizing its significance. In what follows, we aim to clarify its technical contributions and broader relevance.\n\n**It is not very clear to me at least from the introduction, what is the main technical challenge of their work? I do feel many of their results extend straightforward from classical techniques, but it'd be nice if they made clear what was the roadblocks in establishing these results. I think from an ML perspective and quantum perspective the technical novelty is a tad limited (again the authors should correct me if wrong), but i still its a nice surprising result.**\n\nWe sincerely thank the reviewer for mentioning this. While we do not introduce new concepts in online learning theory, we provide new proof strategies inspired from adjacent fields such as matrix completion. Based on this, we are able to make our proof both constructive and broadly interpretable. We consider this simplicity as a form of technical novelty.\n\nPrior work [1] approached the problem using advanced tools from information theory (e.g., random access codes) and introduced a new complexity notion (the fine-shattering dimension). By contrast, our proof is fully constructive, conceptually simpler, and yields a stronger result for online learning: it extends to pure states and explicitly identifies which instances of pure states are hardest to learn in the adversarial online setting. These extremal pure states (those used in our tree construction) are characterized by a high concentration of probability mass on a small number of basis states, with very low probability spread over the remaining basis states.\n\nWe believe that this insight into which instances of a given hypothesis class are hardest to learn has potential implications beyond the quantum setting. For instance, in classical learning theory, such constructions could inform the design of secure or privacy-preserving systems, where a model is deployed as a black-box predictor and must be protected from extraction via adaptive queries. Our techniques could thus provide a theoretical foundation for identifying classes of hypotheses that are provably hard to recover in such scenarios.\n\n**The bounds are non-optimal, did you make any efforts in tightening the upper and lower bounds?**\n\nThe lower bound we establish on the sequential fat-shattering dimension is $\\text{sfat}_\\delta(\\mathcal H, \\mathcal{X}) = \\Omega(n/\\delta^\\eta)$ for all $\\eta < 2$ asymptotically matches the known upper bound of $O(n/\\delta^2)$. We have explored several avenues for tightening this lower bound further, but did not find a sharper construction within our framework. That said, the gap does not affect the final regret bound, which remains asymptotically tight—which is what we are concerned with in the online learning setting, where performance is evaluated in terms of rate of convergence. In this sense, the sequential complexity bound we provide is sufficient for our main results.\n\nWe thank the reviewer again for their time, careful reading, and constructive engagement with the work.\n\n**References**\n\n[1] Aaronson, S., Chen, X., Hazan, E., Kale, S., and Nayak, A. Online learning of quantum states. Advances in neural information processing systems, 31, 2018."}, {"review_id": "j98VYtHZrG", "reviewer": "Reviewer_opiU", "summary": "This paper focuses on the problem of online learning for pure and mixed quantum states. The authors establish the equivalence between these two settings by first proving a lower bound on the sfat dimension and then demonstrating the equivalence for $L_1$-loss regret using Rakhlin’s characterization.\nFurthermore, they extend the results to a more practical setting called $\\epsilon$-realizable and discuss the concept of smoothness to better understand the effects of adversariality.", "questions": "1.\tIs it correct that your work closes the sfat dimension of pure states? What would be required to close the offline version, the $\\delta$-fat-shattering dimension?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper provides rigorous proofs for every result it presents.\n\n2.\tThe illustration of the sfat-tree construction makes the concept easy to understand.\n\n3.\tSmoothness is quite an interesting topic to discuss, as the adversariality of nature might not always be so extreme.\n\nWeaknesses:\n\n1.\tWhile the contribution is solid, the proof of the lower bound by constructing an sfat-tree is straightforward and somewhat unsurprising. It appears to lack technical novelty.", "was_revised": true, "final_justification": "The authors explained the technical contributions in their rebuttal, primarily focusing on two points: 1) While the final construction may seem simple, arriving at it required non-trivial insight. 2) Applying matrix completion methods to quantum/online learning, offering new intuition about instance hardness. I find both points reasonable, yet remain uncertain whether they sufficiently elevate the paper's overall contribution. Therefore, I maintain my original score, though I would support acceptance if space permits.", "rebuttal": "We thank the reviewer for their constructive feedback, and we appreciate their recognition of the rigor and clarity of our presentation.\n\n**While the contribution is solid, the proof of the lower bound by constructing an sfat-tree is straightforward and somewhat unsurprising. It appears to lack technical novelty.**\n\nAlthough the final tree construction may appear straightforward in retrospect, we would argue that arriving at this construction was highly non-trivial. Prior work [1] approached related lower bounds using information-theoretic tools such as random access codes and newly introduced complexity notions. In contrast, our proof is stronger in the sense that it is conceptually simpler, fully constructive, and applies uniformly to both pure and mixed quantum states, and potentially other classes of quantum states.\n\nMore importantly, it explicitly identifies which instances of pure states are hardest to learn in the online adversarial setting. Those states, used in our tree construction, are characterized by a high concentration of probability mass on a small number of basis states, with very low probability spread over the remaining basis states. In addition, our utilization of matrix completion techniques provide the intuition that other types of pure states indeed won't typically be as hard to learn.\n\nOur proof technique therefore allows us to identify which instances of a hypothesis class are hardest to learn. We believe that this identification of the hardest instances within a given hypothesis class may have many applications. For example, in classical learning theory, our constructions may inform the design of secure or privacy-preserving systems. The goal is to protect a model accessed as a black-box against extraction through querying. In such settings, our techniques could offer a theoretical foundation for identifying hypothesis classes that are provably hard to reconstruct.\n\nTo the best of our knowledge, we are the first to introduce matrix completion techniques to the quantum and online learning settings. Moreover, we view the simplicity of our proof, together with its potential to extend to other relevant settings, as a technical novelty in its own right.\n\n\n**Is it correct that your work closes the sfat dimension of pure states? What would be required to close the offline version, the $\\delta$-fat-shattering dimension?**\n\nYes, our work closes the asymptotic characterization of the sequential fat-shattering dimension for pure quantum states in the online setting. Specifically, we establish that pure and mixed states exhibit nearly the same sequential complexity, thereby resolving the gap that remained in prior works.\n\nHowever, closing the gap for the offline version would require a similar tight bound on $\\delta$-fat-shattering dimension. From our construction, one might infer a lower bound of $\\Omega(1/\\delta^2)$. But whether the optimal bound of $\\Omega(n/\\delta^2)$—known to hold for mixed states—also extends to pure states is unresolved. This remains an important and intriguing direction for future work.\n\nWe thank the reviewer again for their time and thoughtful engagement with our work.\n\n**References**\n\n[1] Aaronson, S., Chen, X., Hazan, E., Kale, S., and Nayak, A. Online learning of quantum states. Advances in neural information processing systems, 31, 2018."}]

Author rebuttal:

Meta-review: (a) Summary: This paper studies the complexity of learning pure and mixed quantum states in the online setting. In the standard tomography setting, learning pure states is easier than learning mixed states. The main result of this paper shows that in contrast, pure states are as hard to learn as mixed states in the online tomography setting. This paper also extends the online setting to the smoothed and $\epsilon$-realizable settings.

(b) Strengths:
- Solid result :The paper addresses a well-motivated and natural question, and its main result is a nice message that will be useful to the broader community.
- Technical soundness: The technical results are rigorous. In addition, a few reviewers appreciated bringing smoothed analysis to online learning of quantum states. 
- Clarity: The paper is very well-organized and clearly written. 

(c) Weaknesses of the Paper and Missing Elements:
- Technical novelty: A recurring concern (Reviewers Yd1X, opiU) was the lack of technical novelty -- the proof techniques seem to use standard tools in a straightforward manner. 
- Limitations: The main result only applies to the online setting, and it remains an open question whether the equivalence in hardness extends to the offline case. The analysis also focuses predominantly on the L1​ loss, with less discussion on other loss functions such as the L2 loss.

(d) Rationale: This paper makes a nice conceptual contribution in showing that learning pure states is as hard as learning mixed states in the online setting, contrary to known results in the standard setting. While there are some concerns about technical novelty, the consensus among reviewers is positive, and the work is technically solid and well-executed. 

(e) Summary of Rebuttal and Discussion: After the rebuttal and discussions, all reviewers had a positive view of the paper. The major concerns were:
- Technical Novelty (Reviewers Yd1X, opiU): The main concern was that the proof techniques seemed straightforward. Authors provided detailed responses that seemed to satisfy reviewer Yd1X, while to a lesser extent opiU.
- Limitations (Reviewer NRAe): The reviewer mentioned that the results only apply to the online setting and the L1 loss. The authors argued that the L1 loss is commonly used in quantum tomography, and adapting the results to the L2 case requires additional analysis that is out of the scope of the paper.
Decision: Accept (poster)