On Adaptivity in Quantum Testing
Authors: Omar Fawzi
Nicolas Flammarion
Aurélien Garivier
Aadil Oufkir
Venue: Accepted by TMLR ()

Abstract: Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection?  
  We exhibit problems where adaptive strategies provably reduce the number of required samples by a factor four in the worst case, and possibly more when the actual difficulty of the problem 
  makes it possible. In addition, we exhibit specific hypotheses classes for which there is a provable polynomial separation between adaptive and non-adaptive strategies -- a specificity of the quantum framework that does not appear in classical testing.

Published in Transactions on Machine Learning Research (September/202)
On Adaptivity in Quantum Testing
Omar Fawzi
omar:fouziiens--yyn..f
Univ Lyon, Inria, ENS Lyon, UCBL, LIP, F-69842, Lyon Ceder 07, France
Nicolas Flammarion
EPFL, Lausanne, Switzerland
Aurélien Garivier
aurclien..ertoeeeneenns--....p
Univ Lyon, ENS de Lyon, UMPA UMR 5669, F-69564 Lyon Cedex 07, France
Aadil Oufkir
aadil oufkir fealkkir@ensslyon.ff
Unio Lyon, Inria, ENS Lyon, UCBL, LIP, F-69942, Lyon Ceder 07, France
Reviewed on OpenReview: https: openreview. net/ forum? id= #f
Abstract
Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection? We exhibit problems where adaptive strategies provably reduce the number of required samples by factor four in the worst case, and possibly more when the actual difficulty of the problem makes it possible. In addition, we exhibit specific hypotheses classes for which there is provable polynomial separation between adaptive and non-adaptive strategies a specificity of the quantum framework that does not appear in classical testing.
1 Introduction
Testing properties of quantum states is an important question in quantum learning theory which generalizes testing properties of discrete probability distributions (Nielsen & Chuang 2002; Montanaro & de Wolf,
2013 Arunachalam & de Wolf, 2017 Anshu & Arunachalam 2023). Indeed, quantum state admits intrinsic probability description given by the list of its eigenvalues. Learning completely quantum state is expensive and requires a significant number of copies even at the presence of quantum memory (Haah) cct al. 2016). Since quantum resources are costly, it is crucial to design procedurcs to efficiently test the important properties of quantum systems. A simple way of reducing the sample complexity is to allow the testing algorithm to update its stopping rule (sequential) and/or its way of acquiring new data (adaptive) depending the previously obscrved data. Here focus the question of the effect of sequential and the sample efficiency. This is very active area. in statistics and machine learning starting from the works of Wald (Wald 1945) and in the learning literature under the name of bandit problems (Lattimore & Szepesvári 2020).
adaptive strategies
Here, we consider this question for quantum testing problems. Specifically, we focus on the hypothesis selection problem using incoherent measurements, where the tester is asked to determine the hypothesis set containing the unknown quantum state p with high probability. This problem is ubiquitous in the quantum learning theory literature, and several variants considered: testing identity (O'Donnell & Wright 2015 Bubeck et al. 2020; Chen et al. 2022c), testing closeness (Yu, 2020). binary hypothesis testing (Hiii &
Petz, 1991), (Audenacrt et al.] 2007; Nusssaau & Szkola, 2009 composite quantum hypothesis testing
Bjelaković el al. 2005). If the tester is limited to incoherent measurements, the problem is very related to classical testing problems. Indeed, on the one hand, every classical testing problem on discrete distributions can be cast into quantum testing problem by taking diagonal quantum states corresponding the discrete distributions. Measuring these quantum states is equivalent to sampling from the classical distributions. On the other hand, the quantum hypothesis selection problem can be seen bandit problem (see e.g. (Garivier

---

Published in Transactions on Machine Learning Research SSeptember22222
Non Sequential
Sequential
Non adaptive
(Prop.
3.1
[,6(1
(Prop. 3.3
Adaptive
2 8²
(Prop.
3.1
Log 25
(Prop. 3.3
Table 1: Copy complexity for testing whether probability.
01 or = 02 where & = 1101 -02ller and ō is the error
Non Sequential
Sequential
(( dd// (og(1/8)
d (1g(1/8)
d log(1/8)
Non adaptive
Bubeck et al.
2020)
0 min
(Prop. 3.4
6²
6²
p- 1/all
Adaptive
+
4/2 (
Chen et al. 2022a
O min
log(1/0)
d
log 1
(Prop. 3.4
I/dl12
Table 2: Copy complexity for lesting whether p _ or ||p
aller 2 e where d is the dimension of quantum
states and ò is the error probability.
Lumbreras al. 2022 Brahmachari et al. 2023 ) Born's rule defines exactly the classical distribution of the reward when pulling particular arm (performing measurement). Note that these probability distributions are not arbitrary: they are governed by the unknown quantum state.
& Kaufmann 2019
This connection leads to an important question: Can sequential strategies oulperform non-sequential ones for some hypothesis selection problem with incoherent measurements? In other words, if the tester is allowed choose the measurement device at given step depending on the previous observations, would it require fewer copies of the unknown quantum state?
Note that from practical point of view in quantum experiments, adaptive and sequential strategies be implemented without much overhead. Thus, finding efficient adaptive/sequennt strategies can lead to practical savings for quantum experiments as shown by Granade et al. (2117).
Classically, sequential strategies prove to have an advantage over non-sequential ones for instance for binary hypothesis testing problems (see (Wald 1945)), testing continuous distributions (see (Zhao et al.) 2016 Balsubramani & Ramdas 2015)), ), testing identity and closeness problems with small alphabet size (see (Fawzi al. 2021 2. This speedup comes, mainly, from the fact that sequential algorithm can make comparisons at each step and respond carlier once it has the enough confidence. However, soquential strategies in the quantum setting have not only the capacily choose the stopping time, but also to change the measurement devices adaptively. We expect then larger gap between sequential and non-sequential strategics. To avoid confusion, sequential strategics can choose the stopping time according to the previous observations and thus they have random stopping times, while adaptive strategies are allowed to adapt their measurement. devices at each step according to past observations. With these definitions, strategy can be sequential and adaptive, sequential and non-adaptive, non-sequential and adaptive, or non-sequential and non-adaptive. When we don't specify whether the strategy is non-sequential or sequential (resp. non-adaptive or adaptive), it can be both and the statement remains true.
On the other hand, non-adaptive strategies have been shown to be optimal for many interesting quantum testing problems, including testing identity by CChen et al. 2022a), purity testing and shadow tomography by (Chen et al., 202T), tomography by (Chen et al. 2022b These works suggest that adaptive/sequenet strategics cannot outperform non-adaptive non-soquential ones. The goal of the article is to show the contrary: there are some situations where sequential or adaptive strategies require fewer measurements than non-adaptive non-sequential ones.
Contributions
When the number of hypotheses m is equal to 2 and the hypotheses are simple (i.c., only one possible state), we can precisely characterize the optimal worst case complexity for non-sequential and sequential strategies. We show that sequential strategies outperform non-sequential ones by a factor For the lower bounds, we show how to reduce this problem to the classical testing identity problem, then apply the lower bounds of Fawzi et al. (2022). For the sequential upper bound, we design stopping rules inspired by time uniform concentration inequalities. We refer Table. for a summary of these bounds.
2

---

Published in Transactions on Machine Learning Research (September/2025
Non Sequential
Sequential
Non adaptive
θ
min
md
(Prop.
4.4
4.5)
min
mid
(Prop.
4.4
4.50
Adaptive
(Prop.
4.3
4.9
(Prop.
4.3
4.9
c2
Copy complexity for the hypothesis selection problem (P) (4.1 where d is the dimension of quantum states, m is the number of hypotheses and the precision parameter. There is a polynomial separation between non adaptive and adaptive strategies when exp(O(d)) > m 2 2(d).
Table 3:
Morcover, we show that sequential algorithms can adapt to the actual difficulty for the testing mixedness and testing closeness problems. For this, we show lower bound on the TV-distance between the prob- ability distributions after measurement depending on the actual 1-norm between the quantum states (see Lemma 3. This inequality helps to reduce quantum testing to classical testing at the cost of a factor 1/vd (d is the dimension of the quantum states) and can be useful for other applications. We refer to Table, 2 for a summary of these bounds.
For number of hypotheses m 2 2, we prove a separation between adaptive and non-adaptive strategies for specific problem. The learner has the information that the unknown quantum state can be diagonalised in a basis amongst m known orthonormal bases and would like to approximate it. See Def. 4.1 for a formal definition of this problem. We show that this problem can be solved by adaptive algorithms using Olllog(m)/s copies of p. On the other hand, every non-adaptive algorithm solving this problem will require ( log(m))", 2, dd (=²)) copies of p. The upper bounds follows from the shadow tomography algorithm of Huang et al. (2020). For the lower bounds, we construct an e-separated family of quantum states close to the maximally mixed state (I/d) and use it to encode message from [me A learning algorithm can be used to decode this message with the same success probability. Hence, the encoder and decoder should share at least (llg(mm)+ bits of information (Fano's inequality (Fano 1961)). On the other hand, after each step, we show that the correlation between the encoder and decoder can only increase by at most (s² log(m)/m++ + <²/d) bits for non-adaptive strategies and it can only increase by at most O(s²) bits for adaptive strategies. We obtain an improvement by a factor or m/ log(m) for non-adaptive strategies by exploiting the randomness in the construction and the independence of the observations at different steps. We refer to Table. 3 for a summary of these bounds.
Related work Quantum testing identity using entangled measurements is well understood OO'oonnell & Wright 2015 Bädescu et. al., 2019):: it is known that (dds²) copies are necessary and sufficient. For incoherent measurements, it starts with the work of Bubeck et al. (2020) where we have two different lower bounds for testing mixedness problem using independent adaptive and non-adaptive measurements. This result is generalized for general testing identity to some quantum state a by Chen et al. (202cc). Recently Chen et al. (2022a) show that adaptive algorithms cannot significantly outperform non-adaptive ones neither for testing mixedness nor testing identity.
If entangled measurements are allowed, the quantum hypothesis selection problem can be solved using poly(log(m)) copies of p (see (Bädescu & O'Donnell, 2021)). )) This poly-logarithnic complexity in m can be explained by the fact that pdr can be reused after measurement. In contrast, this is not possible using incoherent measurements for which the state collapses after performing the measurement. In general, the quantum hypothesis selection problem, where each hypothesis contains only one quantum state, is highly related to the shadow tomography problem where the learner asked to uniformly approximate the expected values (tr(pO:))sejmm of m known observables {O:)semm] by measuring the unknown quantum state p. A popular algorithm for the shadow tomography problem is given by Huang et al. (2020) and uses at most Ollog(m)d/e² non-sequential non-adaptive incoherent measurements. On the other hand, independent adaptive strategies are shown to be useless for shadow tomography (and purity testing) by Chen et al. 20011.
Morcover, sequential adaptive strategics have been used by Li al. (2022b) (soc (Li ct al. 2022a) for quantum channel discrimination) to achieve the optimal rates given by the quantum relative entropy for both type and type II errors at the same time for binary hypot testing problem using entangled measurements.
3

---

Published in Transactions on Machine Learning Research (epttember/2223)
Adaptive strategies have been considered for testing quantum channels in (Harrow al. 2010 Pirandola jet al. 2019: Salek et al. 2022). In particular, Harrow et al. (2010) and [Salek et al. (2022) provide examples for which adaptive strategies outperform non-adaptive ones for testing quantum channels. We note that for channels, one has the possibility to adapt the input of the channel to the previous observations, but this is not the case for testing states. As such; it is more challenging to find a separation between adaplive and non-adaptive strategics for testing quantum states than for channels.
For the tomography problem, Chen et al. (022b) shows that adaptive independent strategies cannot beat non-sequential non-adaptive ones and thus need at least 12dd/=²) copies to learn the quantum state p. However, it is unclear whether adaptivity can help for learning restricted families of states such as graph states (Ouyang & Tomammicell 2022). On the other hand, sequential strategies were used for online state tomography by Kueng & Ferrie (2015); Youssry et al./ (2019); Stricker et al. (2022): : Rambach et al. (2022). Note that the word "online learning" usually used to refer to a learning task where the properties or the
state we want estimate change on the fly. The problems we consider here are not of this type: the task is fixed in advance. For this reason we use the words adaptive and sequential instead of online.
Finally, other works consider testing properties of quantum states/ states/distributionn /distiibutinns with different access models. For instance, (Acharya et al.) 2020)p studies the copy complexity of estimating entropies of a quantum state, (Gilyén & Li 2019) studies testing closeness between unknown distributions with coherent access and [Belovs] 2019) studies the quantum query complexity of discriminating two probability distributions encoded by quantum oracles.
2 Preliminaries
Throughout the paper, d is the dimension of the quantum states. A quantum state is a positive semi-definite Hermitian matrix of trace 1. We use the bra-ket notation: column vector is denoted (ø) and its adjoint is denoted (ø) = 1o)t. With this notation, (ølv)) is the dot product of the vectors & and & and, for unit vector (o), loXol is the rank-l projector on the space spanned by the vector Φ. The canonical basis {eheed is denoted {1i) heed = {le)))e((
We define the trace norm or the 1-norm of matrix M as |M = ftr (VMTM) and the 2-norm as ||Mla (MtM). An observable is Hermitian matrix O satisfying O > 0 and I O > 0 where I is the identity matrix.
Given two quantum states P and o, we can compare them using the quantum relative entropy defined as: D(ploa) tr(p(log(p) - log(o)))
the quantum Chernoff divergence defined as:
C(p,o) = - log inf (n(pte oses1
The total variation (TV) distance between two probability distributions P and Q on [d] is defined as:
TV(P 1 Σ
P. Qil
and the (KL) divergence is defined as:
d KL(PIIQ) = Σ P. log
(
Finally, for two numbers q E [0, 1], we denote (T.(pllg) = KT.(Ber(p)] Ber(g))-
All the problems discussed in this article are special cases of the general hypothesis selection problem. Given an unknown quantum state p E Cdxd and m hypothesis classes [H.)e the learner asked to find one of the hesot classes containing P with high probability. Formally:
4

---

Published in Transactions on Machine Learning Research (eeptember/2023)
Definition 2.1 (Quantum hypothesis selection). Let E Caxd be unknown quantum state. Let (Hi) be m hypothesis classes. We have the promise that at least one of the following assertions is satisfied:
p Hi,e E H ... P Hm
An algorithm A 8-correct for this problem if it verifies the following property:
Vi E [m] : p H, - P)
The difference between quantum and classical testing is that in the quantum case we have the possibility to choose a mcasurement (given by positive operators summing to the identity). If the quantum states are restricted to be diagonal, we may assume the measurement is always the same and so the problem becomes classical testing problem (see Lemma 3.2
The quantum state p is unknown, but the learner extract classical information from it by performing measurement. The way the unknown quantum state p is measured is important and can lead to different results about the number of copies needed for this task.
Definition 2.2. A measurement is defined by a POVM (positive operator-valued measure) with finite number of elements: this is a set of positive semi-defiitee matrices M = (M))xx acting on Hilbert space H and satisfying Eiex M,- Mx. Each element M, in the POVM M is associated with the outcome i E X. The tuple (tr(pM:) hex is non-negative and sums to 1: it thus defines a probability denoted by p(M). Born's rule (Born 1926) says that the probability that the measurement on a quantum state p using the POVM M will output i is exactly tr(pM,).
We distinguish between two types of measurements depending on the considered Hilbert space:
Definition 2.3 (Entangled measurement). An entangled measurement is given by a POVM on the Hilbert
space H =-= = (I where N is the number of copies available of the quantum state p. We can measure the whole state paN at once. An interesting POVM related to the observable O on Cd is given by M(O) = (MaJoskst where Mr = Eze |=|== O @ 8... O=N, Measuring p@N with the POVM M(O) outputs a sample from the binomial distribution (n, tr(pO)).
Definition 2.4 (Incoherent measurement). An incoherent measurement is given by a sequence of POVMs [Mehne[N]: cach of them acts on the Hilbert space k Cd_ In this case, we measure at step the quantum state P using the POVM Mr. For instance, for an observable O, measuring with the POVM M(O) = (I 0, outputs a sample from the Bernoulli distribution Ber(tr(pO)).
In this article, we focus on algorithms using incoherent measurements. In this case, we can distinguish between two four types of strategies depending whether the number of measurements and the POVMs (Me) fixed in advance or not.
Definition 2.5 (Adaptive strategies). strategy is called non-adaplive when the POVMs (Me)+ are fixed in advance (i.e., do not depend on the outcomes of the previous measurements). When M, can be chosen depending on the results of the previous measurements with the (Ma)sct, we call it an adaplive stralegy.
Definition 2.6 (Sequential strategies). the number of measurements is not fixed beforehand and can be chosen as function of the previous measurement outcomes, the strategy is called sequential and has a random stopping time N. In this case, the expected copy complerity of the procedure is E (N). Otherwise, the strategy has fixed number of measurements N and is called non-sequentiol.
The goal of this article is to assess the potential improvement of sequential algorithms non- adaptive non-sequential ones.
3 Sequential improvement for problems involving two hypotheses
In this section, we focus on sequential algorithms for problems having only two hypotheses (m = 2), which can be simple not. The results of this Section are true for either adaptive and non-adaptive settings.
5

---

Published in Transactions on Machine Learning Research (September/202) 2002)
3.1 Provable constant improvement of sequential strategies
The simplest case for hypothesis selection problem with 2 corresponds to hypothesis sets containing only one known quantum state. Formally, the learner would like to distinguish two hypothesis: H1 = {or} and H2 = {o2}. We want to characterize the exact number of copics the learner needs to solve this problem using sequential and non-sequential independent measurements.
3.1.1 Non-sequential strategies
The tester knows the quantum states and d2 and can hence calculate the actual 1-norm between them, denoted by & = ||o 02 lr The optimal POVM to distinguish between 0i and 02 is thus given by = (I -0,0) (Holevo-Helstrone theorem, see [Watrous] 2018)) where 0 & O & satisfies
& =
- - tr((011-1)))))))) - 02)
(1)
Let X1,..., X be the outcomes of mcasuring p by the POVM M. By Born's rule, they follow the Bernoulli distribution of parameter tr(pO). Let be the statistic given by the difference between the empirical mean and the actual mean under H2: S ,/4 - X; tr(o20). Its expected value is tr((p-o2) which is e under H₃ and 0 under Hz. The learner can mcasure a sufficient number times, compare the statistic $ with e/2 and decide accordingly: I > a/2 accepts H1, otherwise it accepts H2. Following the Chernoff- Hoeffding inequality (Hoeffding, 1963 sufficient number of measurement for the learner be ò-correct
is
log(1/8) KL(tr((a) + (L(tr((a)+ 02)01/21(tr((100) KL(tr((o)+ (000://luuoo))))k///(((otttt0))) (201)//(0+
log(1/8)
2 log (1g/)
max
The latter inequality follows from Pinsker's inequality (Fedotov al. 2003). Note that this previous upper bound is optimal in the worst case setting where fix and take the infimum over all and dg satisfying ||o 02ller = E. This first result is summarized in the following proposition:
Proposition 3.1. There is a non-sequential non-odaptive algorithm for testing Hi 01 H2 02 using number of measurements
2 (10(1
N S
Moreover, there erists two quantum states σi and 0g satisfying ||o - 021lu E so that every non-sequential adaptive algorithm distinguishing between H1 dn and H2 p d2 needs number of measurements salisfying
N log(1/6)
2
lim inf 8-50
2 max KL + as 11/2 KL 3e
6-+0 2²
where a E (0,1) and B E 10, are defined such that (1/ + aell1/2) = KI(112 + aell1/2 + t) and KL(1/2- - 3/]11/2) = KL(1/2 B/||1/2 =).
For the lower bound, construct two quantum states, σ1 = 1l//2 and 02 an perturbation of it. For each POVM, show that the optimal sample complexity is at least 2log(1/8) (when - 0), with equality iff the POVM is the optimal one defined in Eq. ( This reduction can be proven using the following lemma on measurements of diagonal quantum states.
Lemma 3.2. Let Dj and D2 be two discrete distributions and and P2 their corresponding diagonal quantum states. Let M be a POVM. Measuring the quantum state pI (resp. p2) with the POVM M can be seen as post-procese pess-processing (independent of the quantum states) of samples from the distribution D2 (resp. Dz).
Hence, for each POVM, measuring the constructed quantum states 01 and 02 a post-processing of samples from D1 Ber(1/2) and D2 Ber(1/2 + e). Note that this reduction (and the lower bound) works even for entangled strategics. Once the reduction to classical testing identity is done, we can invoke the lower bound
of (Fawxi et al. 2022h. The proof is deferred to App. A.1

---

Published in Transactions on Machine Learning Research (September/2022
3.1.2 Sequential strategies
If we allow the tester to adapt the measurements and choose its stopping time according to previous obser- vations, it can outperform (in expectation) every non-sequential algorithms by a factor Precisely, it can be proven that an expected number of measurements asymptotically equivalent to log(1/0) is sufficient to distinguish between H, : : σi and H2 : p = d2 with probability at least 1 8. We use again the optimal POVM M defined in Eq. (I) to distinguish between σi and 02. Let XI,..., X, ~ Ber(tr(pO)) the outcomes of measuring p by the POVM M. Let St Ei= X; the empirical mcan until the time Contrary to the algorithm described in the previous subsection, sequential algorithm can make comparisons al each time until the tester is confident enough to answer the correct answer H1 or H2. Under H1, the statistic St has expected value ((a,,). On the other hand, under H1, the statistic S, has expected value tr(a20). These expected values are known to the tester, so it can compare at each time the statistic St with two thresholds: 2*(++1) tr(or0)- -60, t) and tr(o00) + ((), where 1)² = log 5 If S, S tr(a, - (66, t), the tester can answer H2 confidently. Similarly, would answer H1 S, 2 tr(o20) + Φ t). However if none of these incqualities is verified it does not answer and makes defined by the thresholds coincide. The idea of comparing the statistic with time dependent thresholds has been previously used for classical sequential testing by Balsubramani & Ramdas (2015); Fawzi et al. (2021 2022). In these latter articles, it is proven that in expectation this algorithm outperform the non sequential one by a factor 4. We adapt their result to the quantum setting in the following proposition.
2x
measurement, and so forth until the regions
Proposition 3.3. There is sequential non-adaplive algorithm for lesting H1 oi us H2 : p 02 using an expected number of measurements:
log(1/5) 2²a + log(1/6)2/3 + 2 logg(11)))
(1/0)//1//////// +1
E(N) &
z²
Moreover, there are two quantum states 0n and 02 satisfying || 101-02h 021l = e so that every sequential adaptive algorithm dislinguishing between Hi : p= = ai and H2 = 02 needs number of measurements salisfying:
log(1/8)
1
E(N)= 2 min (KL (1/2 [|[12)]] e-0 222
Note that the expected stopping time is the most natural figure of merit for the sample complexity of soquential algorithms. Morcover, using the same analysis for the algorithm, one can also obtain similar bounds on the number of measurements with high probability.
Observe that the upper bound admits the asymptotic limit sup log(1/8) S 2+a hence log(1/8) is 2n²
B(N)
asymptotically the worst-case optimal complexity of discriminating between two quantum states at the limit 8, + The correctness of the algorithm presented here is proved using the following time uniform concentration incquality which an application of union bound and Hoeffding's inequality (Hocffding 1963)
P P (E (SS) ((,,1)
where ((d,t)
2 log 21(++1
The lower bound follows from the previous proof's reduction and the lower bound on the expected mumber of samples for testing uniform using sequential algorithms: Ber(1/2) Ber(1/2 (see (Fawzi et al. 2022 The detailed proof can be found in App. A.1
Note that Li et al. 2022bb have also established an advantage of sequential adaptive strategies over non- adaptive non-sequential ones in terms of the error exponents. The type I error is the probability that the testing algorithm answers the hypothesis H₃ while the hypothesis Hu is the correct one while the type II error is the probability that the lesting algorithm answers the hypothesis Ho while the hypothesis H, is the correct one:
aN PP. (AN =
and BN PH, (AN 0)

---

Published in Transactions on Machine Learning Research (epteember22223)
where N is the number of copies used. The error exponents (rates) are then given by
-og((NN)
log(Bw) N
Ro
lim N000
and R1 lim
N
N
Concretely, Li et al. (2022b) show that adaptive sequential strategies achieve the best rates (at the same time) given by the quantum relative entropy between two states for both type 1 and 11 errors. On the other hand, it is known that non soquential non adaptive strategics can only achieve the quantum Chernoff rate exponent when the error probabilities are equal (Nussbaum & Szkota, 2009; Audenaert et al. 2007). For the particular states 01 = y and 02 = diag(? + E. E), we can show that the quantum relative entropy and the quantum Chernoff divergence between 01 and 02 are asymptotically equivalent to:
E²
D(01 D(02l101)
2 and C(01.02) ~ 200 2
2-30
Therefore, we can recover the factor 4 improvement by comparing the quantum relative entropy and the quantum Chernoff divergence:
2=a z 4. C(a),02)) C(o 02) e-0
((01 D(02ll01)
2
We refer to App. A.1.3 for the detailed computations.
3.2 Sequential strategies adapt on the actual difficulty of the problem without prior knowledge
In this section, we change the previous setting by letting the second hypothesis be multiple. Precisely, we consider the problem of testing identity with H1 = {T/d} and H₂ = {o ll - T/d]ler e} where & is a positive parameter. (Chen et al., 2022a has proved that the optimal non-sequential adaptive copy complexity is O(d3/2/E²) We show that while non-sequential adaptive algorithms cannot improve the copy complexity, sequential non-adaptive algorithms can be used to adapt to the actual difficulty of the problem. Mainly we show the following result:
Proposition 3.4. There is sequential non adaptive algorithm for testing identity problem using a number of measurements satisfying:
1/2 log
(og(1/))
2 log(1/0) 1p I/d }).
E (N) O min
e2
In particular, the expected copy complexity can be reduced to (rrd/21og((18)) if the quantum state has 1og(1/8) if the trace-less matrix I/d has low rank even if the algorithm does not have any information about these ranks (see App. A.2 The algorithm uses random measurements and a time-dependent stopping rule. Since we have already sequential algorithms for the classical testing identity problem, it is sufficient to show how to reduce the quantum problem to the classical onc. For a POVM M and a quantum state p; let p(M) denotes the classical probability distribution {tr(pM:)}. The following lemma captures the main ingredient of the reduction:
low rank r 5/2 or O pg /rd-/21og(1/5)) Ie-I/d|
Lemma 3.5. For all 8 >>>000 0, let of columns with probability at least 1-8:
log(2/5) and U U?...., U E [axd be Haar- unitary matrices M = (HUU/XU// is POVM and for all quantum states and a we have
TV(P(M). 1
1pp aller
20
20
where is the rank of (p a).
It is, in general, difficult to compute the expected value of the 1-norm under Haar measure, but the 2 and 4-norms can be computed exactly with the Weingarten caleulus (see Lemma D.1 and Lemma D.2), we
8

---

Published in Transactions on Machine Learning Research (0pptember/2023)
use Hölder's inequality to lower bound the 1-norm by expression involving the and 4-norms. Moreover, this will only give a lower bound in expectation, so we sample more Haar-distributed unitaries and construct a new measurement device by concatenating a fraction of the columns of each unitary. Then, we need to show that the TV-distance is Lipschitz to be able to apply a concentration incquality for functions of Haar- distributed unitaries (Theorem D.3). This is done by carefully applying the Cauchy Schwarz inequality. The complete proof can be found at App. A.2 Sen (2006) proved a slightly weaker (by a logarithmic factor) lower bound on the TV distance using a POVM constructed with Gaussian random variables. Also, a similar lower bound (in expectation) can be found in (Matthews et al,, 2009) where the authors analyze the uniform POVM and a POVM defined by a spherical 4-designs. However, for our reduction, it is important to minimize the number of outcomes of the POVM.
Lemma 3.5 gives a POVM for which our problem reduces to testing identity: P= U, vs TV(P, 20va with high probability, where n (2/0)(2/0) and M(p). Under the alternative hypothesis H2, the TV distance between and Un can be lower bounded by TV Un) 2 - I/d||2- Therefore we can apply the sequential classical testing uniform result of (Fawii et al. 2022 obtain a copy complexity
d @/211g11/0)
(max d 1/d
A matching lower bound can be obtained in the worst case sctting where we are interested only in the parameters d, E and | I/d]lu- This can be done using Markov's inequality to transform the algorithm to a deterministie-time one then invoking the lower bound of (Chen et al. 2022a Any adaptive algorithm for testing identity would require Mcd5//e²)) copies of p.
Note that, using Lemma 3.5 and the sequential tester of (Fawzi et al. 2022,, we obtain the same copy complexity for testing closeness (i.e., testing P vs || a ler 2 & where we can measure the unknown quantum states p and o) for testing identity. This is different from the classical case where testing identity (Diakonikolas et al.) 2017) can be done with much less copies than testing closeness DDiakonikolss et al. 2020).
4 Provable separation between adaptive and non-adaptive strategies
In this section, we fix the error probability to 8 = 1/3. We construct a problem for which we have a separation between adaptive and non-adaptive algorithms.
Definition 4.1. [Hypothesis selection problem (P)) Let (d.....,, be a set of e-separated known quantum states. The unknown quantumn state p is e/3-close to (at most) one of the quantum states de. E {(i,.... mm) and has the same diagonalisation basis than di.. We aim to learn the quantum state to within s/10 with high probability. Formally, the goal is to design an algorithm that mcasures number of copics of p and returns a quantum state z (an e/ e/10-approximation of p) such that with probability (the randomness comes from the measurements and possibly the algorithm) at least. 1 -:
8
| Pller S
10
The problem described above is not a hypothesis selection problem in the strict sense of the term. However it is equivalent to the following hypothesis selection problem which has the same order of copy complexity. For
E [m)] let a; = Σ Au Xotl and {arsbeta an E/ e/10-covering of the set {o = Σx a Pul TV(A,)) S e/3}. Our problem is equivalent to the hypothesis selection problem for {Hi, = ((oo.,.e/10)]l
poi.s = o. haem))jeeM For simplicity, we use the first formulation of the problem and refer to it as (P).
4.1 Upper bound
In this section, we present an adaptive algorithm for the problem (P) achieving a copy complexity strictly less than the lower bound which holds for all non-adaptive algorithms. The first step to determine with high probability the closest quantum state or to p, then remains to approximate p by measuring it in its basis of diagonalization.
9

---

Published in Transactions on Machine Learning Research SSeptember2222)
Algorithm Hypothesis selection problem (P).
Input: N = (0mm///m//))/= incoherent measurements on p and m quantum states o1,,..,,
Output: Two quantum states og and أ satisfying with a probability at least 1- 6: I|,, - plltr I e/3 and
l </10 For all i # E [m], let Oz.j observable satisfying ||o; - -oyl- ir -t)(a,-a))
For all i o j E [m]] let Mi, e/10 approximation of tr(pOcg) given by classical shadow tomography of
(Huang et al. 2020).
Let h- = argmin, max,, Pa, tr,))
Tet M [ the POVM corresponding to the basis of diagonalisation ok-
Measure p independently M = 200 log(2 (2)+222))))))))) /8)/E² times using the POVM M and denote the outcomes
[FahisiM--
[EEen] 18y= M
return p= -iEee(
4.1.1 Adaptive strategies.
For all i j j E [m], let Oi, an observable satisfying ||o,- o,lor tr Oz -o)). In Sec. 3.1 we have seen that such observable Oi, can be used to distinguish between p = o, and p p= o, if one of the two hypotheses is satisfied. The quantum state d2. has the property to minimize the 1-norm between P and {o,)á, so is natural to take the state minimizing the statistics of expected value roughly max,, tr Oz oi) for E [mi] To do this, we need lo approximate ir pOi, for all i + j. We can use the classical shadow tomography algorithm of (Huang et al. 2020) to predict all these events using a few number of copies of
Thcorem 4.2. (Huang al. 2020) Let (Ot...., 0m) be tuple of observables. There is an algorithm using non-adaplive incoberent mensurements requiring:
N N ( (dlog(m/0))
g2
copies of p to predict tr(pO;) to within s-error for all i I,..., with at most an ervor probability of 8.
Once we find the quantum state de, we know the basis of diagonalization of p. Hence we learn the eigenvalues of the unknown quantum state by measuring it using the measurement device corresponding to its basis of diagonalization. This requires O(d/e²) incoherent copies. The algorithm is summarized in Alg. [ This algorithm can be split in two phases. The first phase can be seen as an exploration phase, where the algorithm looks for the optimal eigen-basis. It collects (non-adaptively) the information given by the approximations μi, tr(pOs,;). Then it uses this information to choose ks = argmin, maxi,; Mi.j -tr(o:,,,)) After this step, in the second exploitation phase, the algorithm adapts its measurement device M according the previous information K* and measures only with the POVM corresponding the the eigen-basis of o
Alg. is 8-correct (detailed proof deferred to App. Bp It can be split in two parts for which we independently upper bound the copy complexity. The first part relies on the shadow tomography algorithm of (Huang et al. 2020 and needs number
(4loggmmmm - 11/00) = ( log(m/8) (s/10)2
N1 = O
g2
of copies of p. The second part requires a number N₂ = 200 1og(2 /8)
copics of Finally, since
N = N1 + N2 and 8 = 1/3, we have proven the following proposition: g²
Proposition 4.3. Alg. 1 has total copy complexity satisfying:
(dlog(m)
N =
22
10

---

Published in Transactions on Machine Learning Research (September/202)
4.1.2 Non-adaptive strategies.
We can slightly modify Alg. [ to have a non-adaptive algorithm for the problem (P) with incoherent mea- surements. amounts to first. ineasuring p all the basis corresponding to the known quantum states (oi); and preparing m approximated quantum states (pt).. Then the tester can look for the closest quantum state o3. and finally returns the approximated quantum state P.. This non-adaptive algorithm has copy complexity
mN₂ + N = ( [nd m log log(1/5) + dlog(m//))
g²
This complexity is almost optimal for m S (scc Prop. 4.5 However, is no longer optimal for m 2 d since md/e² 2 df/ /E². that case, we can still design an almost optimal non-adaptive algorithm as follows: for each E [m], , let (lof)); an orthonormal basis of diagonalization for og. For each E [m] and B
[m], let O Eien lof We use the classical shadow tomography of (Huang et al. 2020 within e/40 simultaneously using
predict
(Er(p0 U
Oddlog(m² + m/²) O(d log(m)))/e)
copies of p. We find the closest quantum state dg. to p the same way the Alg, ! does. Next, look for probability distribution À satisfying for all B C [m] |²(B) - - s c/40, where pn is the prediction of shadow tomography algorithm for )r(pOg) Such Ā exists since the vector À of eigenvalues of p satisfies the following property:
)r(p0%)= tr
Σ iE(d)
Ao Xof
Σ iEB
of Xof
Σ Ao
~
REMd)iEB
IEB
I e/40. We thus return the quantum state ý == Eiela delot Xof as an approximation of p. We can verify that it is indeed an e/10 approximation of pt
and [A(B) أل = (t((pO))) u
|p Pller S
D4s Arl = 2 max A(B) - X(B) BCId]
1=1
< 2 max X(B) 1/ + 2 max MB X(B) BCld
BC(d]
< 23 22/40- - 2=/400 - E/10.
The copy complexity of this algorithm is O(dd² + log(m))//² which matches (up to logarithmic factors) the lower bound for 2 d.
Proposition 4.4. There a non-adaptive algorithm for the the hypothesis selection problem (P) with a total copy complezity satisfying:
N 0 min ( d log(m)
md)
)
g²
g²
4.2 Lower bound
In this section, we derive lower bounds for the problem (P) both with adaptive and non-adaptive incoherent measurements. Note that the same lower bounds (up to constants) could be proven for sequential strategies as well. This is because if sequential algorithm uses N copies in expectation, then by Markov's inequality, it uses at most 10E(N) copics with probability at least 9/10.
We start with a lower bound for non-adaptive algorithms that matches the copy complexity of the algorithm presented in Sec. 1.1.2
Proposition 4.5. There is tuple of quantumm states (Ø1 am) such that any learning algoritio with non-adaptive incoherent measurements requires
md log(m)e?
d? T })
N = Ω min
11

---

Published in Transactions on Machine Learning Research (cpptember/203)
copies of p to approzimate p to at most z/10 with at least a probability 2/3.
This result with m = d, together with the analysis of the adaptive Alg. gives a nearly quadratic advantage for adaptive algorithms over non-adaptive ones.
Sketch of the proof. We construct a large set of quantum states randomly as follows: for y E (1,...,m) By = UyAU y = 2 om+1-y: where Uy is a d unitary matrix matrix with entries (1#10=)/d Using the concentration inequality for Lipschitz functions of unitaries chosen according to the Haar measure, we can prove that this family is e-separated with high probability:
and A is a diagonal
Lemma 4.6. Suppose that I exp(d)/3000) For y [m/2], let Uy Haar(d) and σy UyAUS. We have with at least a probability 9/10, for all + z:
1o - 0211tr 1 >
Then, for each y,, we construct an e/10-separated family of quantum states on the sphere of center By and radius e/3 which have the same eigen-basis as ay. This can be done by laking random eigenvalues and using Hoeffding's inequality. This leads to family of end states (for some constant c) that we denote by (Pu.y
By definition of the problem (P), any d-correct non-adaptive algorithm for the problem (P) can be used to distinguish between the states {p2.wha with probability at least 1 -- ô. Thus, we can use these quantum states to encode a message in [ead] x [m]] to a quantum state p p= Pa,y in the family constructed above. The decoder receives this unknown quantum state, performs non-adaptive incoherent measurements, and learns it. Therefore a d-correct algorithm can decode with a probability of failure at most 8. By Fano's inequality, the encoder and decoder should share least ([oog(m) d) bits of information.
Lemma 4.7
(Fan 1961 ) The mutual information between the encoder and the decoder is at least
1 2 2/3 log(me'") - log(() 2 Q(log(m) + +d).
The remaining and crucial part of the proof is to upper bound the mutual information for a non-adaptive algorithm. After some manipulations, the use of Jensen's 's inequality, and some elementary inequalities of the logarithm function, we obtain an upper bound on the mutual information of the form:
I < sup (d)
8N
Σ
Wdldpay- TT)6))22
(2)
m ead [E(m/2].eE(eedd]
The next step is to show that the right hand side of the previous inequality cannot be bigger than O ((NE² log(m) m + 2)) with a probability at least 9/10. This is the object of the following lemma.
Lemma 4.8. By writing Pr,y = + ZU,OZ. and M mxeed, we have with at least a probability 9/10, for all wnil vector (Ø):
2
(ol(daz. D)6)² Cllo(m) C.
21
Σ
d +
M
m
(ele=").vElma
This Jemma can be proven by considering concentration inequality for the function
(Uv)v m x end a jejee [.
2
Σ
(ol(dpa.y - 1)
then considering a 1/m-net on the unit sphere to deduce the required inequality for the previous function uniformly on the sphere. The proof uses techniques similar to the ones of (Haah et. al.) 2016 and CCen
et al. 2021 The detailed proof can be found in App. C.1
A similar proof strategy allows to derive lower bound on the copy complexity of adaptive strategies. The result is stated in the next proposition.
12

---

Published in Transactions on Machine Learning Research (epttember/2223)
Proposition 4.9. There is tuple of quantum states (01:..., om) such that any learning algorithm with possibly adaplive incoherent measurements requires
d ( log(m)
( g2
N = Ω
copies of p to approzimale p to al most e/10 with at least probabilily 2/3.
The proof is similar to the one for non-adaptive strategies, with the minor difference that the adaptivity makes difficult to simplify some products, thus we cannot upper bound the mutual information as in Ineq. 2 We use instead a Cauchy Schwarz inequality to break the dependencies created by the adaptiveness of the algorithm. We obtain then an upper bound on the mutual information I I O(Ne²). The detailed proof can found in App. C.2
This proposition along with the analysis of Alg. show that the near optimal copy complexity of the problem (P) using adaptive incoherent measurements is θ ( This latter along with Prop. 4.5 imply the separation between adaptive and non-adaptive strategies for the problem (P) for m >> 1. In other words, knowing that the eigen-basee basis of the quantum state belongs to some family of bases gives an advantage to adaptive strategies since they can find the eigen-basis, and then focus on measuring the quantum state with the corresponding POVM. Up to our knowledge, this is the first example for which adaptive independent strategies outperform non-adaptive ones for testing quantum states.
5
Conclusion
We have constructed hypothesis selection problems for which sequential adaptive strategies are more efficient than non-sequential non-adaptive ones. The problem for which the advantage is the most significant is the one presented in Sec. 4 It would be interesting to see if there are other natural problems for which such separation exists. We conjecture the separation would be polynomial in for the composite hypothesis selection problem: distinguishing between (m and p E (om+1I....,00 22m] with high probability.
References
Jayadev Acharya, Tbrahim Issa, Nirmal V Shende, and Aaron B Wagner. Estimating quantum entropy. IEEE Journal on Selected Areas in Information Theory, 1(2):454 468, 2020.
Amurag Anshu and Srinivasan Arunachalam. A survey on the complexity of learning quantum states. arXiv preprinl orXio:2305.20063 2023.
Srinivasan Aruacchaam and Ronald de Wolf. Guest column: A survey of quantum learning theory. ACM Sigact News, 48(2):41-61 2017.
Koenraad MR Audenaert, John Calsamiglia, Ramón Munoz- Tapia, Emilio Bagan, LI Masanes, Antonio Acin, and Frank Verstracte. Discriminating states: The quantum chernoff bound. Physical review letters, 98 116):160501, 2007.
Costin Bädescu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Compuling, pp. 2019.
Akshay Balsubramani and Aaditya Ramdas. Sequential nonparametric testing with the law of the iterated logarithm. arXiv preprint arXiv:1506.000 03486, 2015.
Aleksandrs Belovs. Quantum algorithms for classical probability distributions. 1xXiv:1904.02198 2019.
arXiv preprint
Igor Bjelakovié, Jean- Dominiqee Deuschel, Tyll Krüger, Ruedi Seiler, Rainer Siegmun-Schultz, and Arlcta Szkola. quantum version of sanov's theorem. Communications mathematical physics, 260(3):659- 6616677,, 2005.
13

---

Published in Transactions on Machine Learning Research (epttember/2223)
Max Born. Zur Quantenmechanik der Stoßvorgänge. Zeitschrift fur Physik, (7(2)):863 867, December 1926. doi: 10.1007/BB011397777.
Shrigyan Brahmachari, Josep Lumbreras, and Marco Tomamichel. Quantum contextual bandits and recom- mender systems for quantum data. arXiv preprint (xXi::201113524, 2023.
Costin Bädescu and Ryan O'Donnell. Improved Quantum Data Analysis, pp. 1398-1411. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380530. URL https://dol.org//0
1145/3406325.3M4 3451109
Scbasticn Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property lesting- In 2020 IEEE 61st Annual Symposium on Poundations of Compuler Science (FOCS), pp. 692 703. IEEE, 2020.
Sitan Chen, Jordan Cotler, Hsin-Yusl Huang, and Jerry Li. Exponential separations belween learning with and without quantum memory. arXiv preprint arXtt:2111.05881, 2021.
Sitan Chen, Brice Huang, Jerry Li, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. arXiv preprint ar 07155, 2022a.
Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. Tight bounds for state tomography with incoherent measurements. arXiv preprint Xiv:22200 05265, 2022b.
Sitan Chen, Jerry Li, and Ryan O'Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory, pp. 2541 2596. PMLR, 2022c.
Tlas Diakonikolas, Themis Goulcakis, John Peebles, and Eric Price. Optimal identity testing with high probability. orXiv preprint Xiv::11708. 1,2.0288, 2017.
Thas Diakonikolas, Themis Goulcakis, Daniel M Kane, John Peebles, and Eric Price. Optimal testing of discrete distributions with high probability. arXiv preprint arXiv:2009.0634 2020.
Robert M Fano. Transmission of information: A statistical theory of communications. American Journal of Physics, 29(11):793-79) -944, 1961.
Omar Fawzi, Nicolas Flammarion, Aurélien Garivier and Aadil Oufkir. Sequential algorithms for testing
closeness of distributions. Advances in Neural Information Processing Systems, 34, 2021.
Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, and Aadil Oufkir. Sequential algorithms for testing identity and closeness of distributions. arXiv preprint arXiv:2205.0600 2022.
Alexei A Fedotov, Peter Harremoës, and Flemming Topsoe. Refinements of pinsker's inequality. 1EEE Transactions on Information Theory, 49(6))1491- 2003.
Aurélien Garivier and Emilie Kaufmann. Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models. ar preprint arXiv:1905 1rXiv:1905.03495, 2019.
András Gilyén and Tongyang Li. Distributional property testing a quantum world. arXio preprint arXiv:1902.0083 2019.
Christopher Granade, Christopher Ferric, and Steven Flammia. Practical adaptive quantum tomography. New Journal of Physics, 19(11):113017, 2017.
Yinzheng Gu. Moments of random matrices and weingarten functions. PhD thesis, 2013.
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In STOC'16- Proocedings of the 48th Annual ACM SIGACT Symposium Theory of Compuling, pp. 913 925. ACM, New York, 2016.
Aram W Harrow, Avinatan Hassidim, Debbie W Leung, and John Watrous. Adaptive versus nonadaptive strategies for quantum channel discrimination. Physical Review A, 833300332339 2010.
14

---

Published in Transactions on Machine Learning Research (September/2233)
Fumio Hiai and Dénes Petz. The proper formula for relative entropy and its asymptotics in quantum probability. Communications in mathemalical physics, 143(())99-114, 1991.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc 58:13-30 30, 1963. ISSN 0162-1459. URL http:://inks /ttp://wwwggg.accaaaaaaaooaaaaaa
Usii-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050 1057, 2020.
Richard Kueng and Christopher Ferrie. Ncar-optimal quantum tomography: estimators and bounds. New Journal of Physics, 17(11))123013, 2015.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yonglong Li, Christoph Hirche, and Marco Tomamichel. Sequential quantum channel discrimination. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 270-275. IEEE, 2022a.
Yonglong Li, Vincent YF Tan, and Marco Tomamichel. Optimal adaptive strategies for sequential quantum hypothesis testing. Communications in Mathematical Physics, pp. 1-35, 2022b.
Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum, 6:749, 2022.
William Matthews, Stephanie Wehner, and Andreas Winter. Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding. Communications in Mathematical Physics, 291 (3):881133-88 843, 2009.
Elizabeth Meckes, Mark Meckes, et al. Spectral measures of powers of random matrices. Electronic commu- nications in probability, 18, 2013.
arXiv preprint Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. arXiv:1310.22 2013.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Michael Nussbaum and Arleta Sakola. The chernoff lower bound for symmetric quantum hypothesis testing. 2009.
Ryan O'Donnell and John Wright. Quantum spectrum testing. In Proceedings of the forby-seventh annual ACM symposium on Theory of compuling, pp. 529 538, 2015.
Yingkai Ouyang and Marco Tomamichel. Learning quantum graph states with product measurements. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2963 2968. IEEE, 2022.
Stefano Pirandola, Riccardo Laurenza, Cosmo Lupo, and Jason Percira. Fundamental limits to quantum channel discrimination. npj Quantum Information, 5(1):50, 2019.
Markus Rambach, Akram Youssry, Marco Tomamichel, and Jacquiline Romero. Efficient quantum state tracking in noisy environments. Quantum Science and Technology, 8(1):015010, 2022.
Farzin Salek, Masahito Hayashi, and Andreas Winter. Usefulness of adaptive strategies in asymptotic quan- tum channel discrimination. Physical Review A, 105(2):022419, 2022.
Pranab Sen. Random measurement bases, quantum state distinction and applications the hidden subgroup problem. In 21st Annual IEFE Conference on Computational Complerity (CCC'06), pp. 14- IEEE, 2006.
Roman Stricker, Michael Meth, Lukas Postler, Claire Edmunds, Chris Ferrie, Rainer Blatt, Philipp Schindler, Thomas Monz, Richard Kueng, and Martin Ringbauer. Experimental single-setting quantum state tomog- raphy. PRX Quantum, 344)00403 2022.
15

---

Published in Transactions on Machine Learning Research (rpptember/202)
Abraham Wald. Sequential tests of statistical hypotheses. 117-186, 1945.
The annals of mathematical statistics, 16(2):
John Watrous. The theory of quantum information. Cambridge university press, 2018.
Akram Youssry, Christopher Ferrie, and Marco Tomamichel. Efficient online quantum state estimation using a matrix-exponentiated gradient method. New Journal of Physics, 21 (33:000,, 2019.
Nengkum Yu. Sample optimal quantum identity testing via panli measurements. arXiv preprint arXiv:2009.1 11518, 2020.
Shengjia Zhao, Eize Zhou, Ashish Sabharwal, and Stefano Ermon. Adaptive concentration inequalities for sequential decision problems. Advances in Neural Information Processing Systems, 29:1343 1351, 2016.
16

---

Published in Transactions on Machine Learning Research (cpptember2023)
In this appendix, we give more details and the technical lemmas needed for the proofs of the article's main results.
We start by stating general tools to reduce quantum lesting to classical lesting in App. A along
with the proofs for upper/ upper/lower bounds on the problem of discriminating two quantum states using sequential/non non adaptive strategics.
Then we move to prove the correctness of Alg. in App
B
Next, we prove the lower bounds for the hypothesis selection problem (P) in App.
Finally, we group the technical lemmas we often need in App. D
A Reduction to classical testing problems
One of the main difficulties in quantum testing is the freedom in the choice of measurement at each step. So, to simplify the analysis of quantum testing problems, we provide some techniques permitting the reduction to classical testing problems which are well understood.
A.1 Testing single hypothesis vs single hypothesis
A.1.1 Non-sequential strategies
We start by the simple remark that for diagonal quantum states, incoherent measurements can be seen as a post-processing of samples from the distribution given by the diagonal elements of the quantum state. Moreover, the stochastic map for this post-pas post-processing does not depend on the quantum state.
Lemma A.1. Let D be discrete distribution and p its corresponding diogonal quantum state. Let M be POVM. Measuring the quantum state p with the POVM M can be post-processing of samples from the distribution D.
Proof. Let M
For each i e [k], we write
M
Σ M
a.
By Born's rule, the probability distribution of the outcomes of the measurement p by the POVM is:
M(p) (iEaa -f or Σ Dall<Kol Σ
Miny (w))
a.y
ied
Σ Mr Dz PD,
iEd
where (MM.a)i is stochastic matrix. Indeed, M implies M (x|M) 2 0 and E, M implics
M M Ext/ (xla)) =
Note that the post-processing map is independent of the quantum state, hence we can generalize the state- ment to any number of discrete distributions.
Corollary A.2. Let D and DD be discrete distributions and P1 and P2 their correspording diagonal quantum states. Let M a POVM. Measuring the quantum state P1 (resp. P2) with the POVM M can be seen post-processing (independent of the quantum states) of samples from the distribution Dj (resp. D2).
17

---

Published in Transactions on Machine Learning Research (Gptemmber20223)
We move now to the proof of the following upper and lower bound discriminating two quantum states using non sequential incoherent. measurements:
Proposition A.3. There is a non-sequential algorithm for testing H1 p H2 p using number of measurements
N Σ 200
Moreover, there erists two quantum states and 02 satisfying | - 02l1ur = e so that every non-sequential algorithm distinguishing between H1 : 01 and H2 02 needs number of measurements satisfying
N
2
inf 5-+0
(1g(1/6)
KL(1/2 + ae 1/2) KL(112 3ell1/2)
2
where E (0,1) and B E (0,1) are defined such that KL(1/2 + a=ll1/2) = KL + 1/2 + E) and KI(1122 //2 = (1/112- //2
Proof. The correctness of the batch algorithm presented in Sec. 3.1.1 can be done using Chernoff-Hoeffding inequality, p = σs the error probability can be upper bounded as follows:
(S tr(a20) s e/2) P PS tr(o, s/2-
PP - -((s))r(0)))) S -e/2)
<xp((NNKI(tr((00)) - e/2lltr(r)00))
On the other hand, if ===0y-
P - tr(a20) 2 e/2) cxp((N +
Therefore to ensure that the batch algorithm is 8-correct we need N to satisfy
log(1/6) - - KT(tr(o20))+ + +
log(1/5)
N max
Moreover by Pinsker's inequality (eedoovv et al. 2003 the right hand side is upper bounded by:
log(1/0)
log(1/8)
log(1/5) e²
max
S
- (
For the lower bound, let d = O = diag(1,-1)) 11). Let A be non sequential algorithm that distinguishes between H1 and H2 using N measurements. Let the tth measurement be M₁ = (I - O.). Measuring P = σ1 (resp. σ2) with the POVM M; (T - O,, O.) is equivalent to sampling from Ber(tr(O:)/2) (resp. Ber(tr(O.)/2+ str(O,,)) The optimal sample complexity of testing identity: Hp p tr(0,)/2 H4 : (r(0.)/2+ is
= I/2 and 02 diag((1 + /2) (1 - 22) = T/2 + e0 where
asymplotically equivalent to (when e 0) Fawzi al. 2022
8(tr(O:)/2)(1 - (r) log(1/6)
4tr(O,) - (r()))/2) (000)())0())))))g1( c²tr(0,0)2
e²tr(0,0)2
Let's write O; = (yi
we have tr(0,0) = A - d2. Since * O; x I, we have 0 I A S 1 for = 1,2.
Hence
4tr(O.) log))))) 2(A1 + +2)(2 - \1 - log(18)) (rr(0,0)²
2 llg({188
e²(A1 22)
This latter incquality is true since
(A1 + +2) \ A2) 2 (A1 X2)² A + 2 0,
18

---

Published in Transactions on Machine Learning Research (cpttember2202))
with equality iff X; 0, for i = 1,2. The cases X1 X2 eliminated because the sample complexity has denominator (Λ1 -2)). It remains the cases X1 = 1 X2 E (0,1) for which O; is rank projector. Therefore, the optimal measurement reduces to testing uniform: Ber(1/2) vs Ber(1/2 + E). This problem requires sample complexity asymptotically equivalent to / Note that we can also use Lemma A.1 to
make the desired reduction. We show how this reduction works for entangled strategies. We have 01 and 02 @N 1 diag ((1 + 2s)) 2c) <e(o.)> where = +......... +i.. By Lemma A.1 measuring
2
the quantum states &N (resp. N can be seen as post-processing of samples from the distribution Dj [1/2" (o (resp. D2 = {1/2 - (1/2+
ie (0.1)w) Observe that sample i = (h....., ,x) ~ D1 is given by N i..dd random variables {ix (er (2) Similarly, a sample (i1,..., D2 is given by N i.i.d. random variables {úx /12 6) h) KE(N)- Therefore, distinguishing øn from 02 using entangled copies can be reduced to testing Ber(1/2) vs Ber(1/2 e) using N samples. This latter requires number of samples Faazi et al. 2022):
N log(1/5)
2 500 c2
lim inf 6-+0
2 max KL as 11/2) KL(1/2 3=|11/2)
where (0,1) and B (0,1) are defined such that KL(1/2 + a=ll1/2) KL(1/2 + aell1/2 + E) and
KT(1/2- 1/2) KT(1/2 /e211/2-
A.1.2 Sequential strategies
Discriminating two quantum states using sequential strategies can be done with fewer measurements than non-sequential strategics. Since the reduction to lower bound similar, we give only the proof for the upper bound.
Proposition A.4. There is a sequential algorithm for testing H1 =p= 01 es H2 : = 02 using an expected
number of measurements:
log(1/5) 1og(1/6)2/3 + log 1ogg///(/00000///222222 +
E(N)= <
6²
Moreover, there are two quantum states on and 02 salisfying || - Ø2'l so that every sequential algorithm distinguishing between H1 = 01 and H2 p 02 with high probubility needs in expectation rammbrr
log(1/6)
E(N) 2 min (KL (1/2 + E 1/2)]
of measurements.
Proof. The algorithm is presented in Sec. 3.1.2
Correctness.
Let's start by showing that this algorithm is 8-correct. To this end, we need a time uniform concentration inequality which be obtained by Hoeffding inequality along with the union bound, recall that S. (Et Xt)/t Xt)/t and X; ~ Ber(tr(pO)):
P P > 1: |S EE (8,) ((,,t)
Σ
P ((S, ES.) ((),t)
121
Σ
(mp(-2t066 t)3)
t(t + 1)
121
5.
19

---

Published in Transactions on Machine Learning Research (eeptember/2023)
Complexity. To obtain upper bound the complexity, use the following lemma: Lemma A.5. N random variable taking values in N2 we have for all k N
E(N) S +
PPN221)
12k
This inoquality can be proved by writing E(N) = E1z0 P(N 2) then upper bounding the first l terms by 1.
Let (0, and the smallest integer so that for all & k ((), - as. We focus only on the case p oi (the other being similar), the expected stopping time of the algorithm can be controlled as follows:
(N) S k +
Σ
P( 2 t)
12k
$ k: +
Σ
P(S < (r(o20)+ 1))
S +
Σ
P(S. - tr(o, < + aE)
12k-1
< k
Σ
P(S: - tr(or))))))))) < -(1 a)=)
12-11
< k +
Σ
2exp(- Fexp(-2((1 a)
12k-
2exp(-20 - 1) a)
< k +
exp( 2(1 - 2)2
2 2exp(-20 (22(- |: 1) a)p6?)
< k +
a1-a)
On the other hand we have (00, k)) < 08 and @60, k 1) 2 ae
(k
2 2(k 1)a?c? 1)k 8
log
Therefore:
k: 15 log(1/8)
+ log(log(1/6)/(n)))
2n
a²g²
Hence:
E (N)
1
+2 (og)
1
2 exxp( 2(k - 1)(1 a)
+ log(1/6)(1 - -22)
log L/8)
2a?=2
1og(1/8)o
log(1/8)
and by taking 5 + 0, then 1 obtain:
((N)
lim sup log (1/5) <
2g
8
A non asymptotic upper bound can be obtained by choosing a = (1 + (19/
log(1/5)
/1tp:///000000oggg////////////// + e2
E(N) <
2e
The lower bound follows from the previous reduction to testing Ber(1/2) vs Ber(1/2 + E) and (Fawzi al. 2022
20

---

Published in Transactions on Machine Learning Research (September/2023
A.1.3 Asymptotics of the quantum relative entropy and Chernoff divergence.
Recall that we consider the particular states σi 1 and 02 diag(3 + E, 2 - E). An asymptotic (when + 0) of the quantum relative entropy between 0n and 02 is given by:
1
1
D(o1 = log 2
log
28²
1 25
2
1
25
c->0
D(02ll01) = + log(1 (1 + 22)
+
log(1 - 25) ~ E-2
20a.
2
On the other hand, asymptotic (when 0) of the quantum Chernoff divergence between the states øi and can be upper bounded using the incquality log(x) 2 (x 1) (x 1)² valid for E (2,
C(0).02) = sup - -lgg(tr(ofo3-")
05*51
sup - log
( (1 2=)² + 2 22)*
1
0$$51
1 51 20)²
1/ 2s) + -1 22) -1 1]²
sup
(1 25)x
0S*5]
E²
< sup [2s(1 S)E² +o(=²)] + o(s))
05a51
5-5 2
Morcover, it can be lower bounded using the incquality log(x) S
C(a1,02)) = sup
log
5 (1 + 28)* + = 2z)*
05
2 sup
[
- (1 + 22)* - -/ 20)²
1
05551
2
e²
[2s1 s)B² + +0(s2)
sup 05.51
500
Finally 0()1)02) ~ o² 802 T.
A.2 Testing single hypothesis vs multiple hypothesis
In this section, we relate the TV-distance between the distributions obtained after the measurements and the 1-norm between the quantum states.
Lemma A.6. Let U E Cdxd be a Haar-random unitary matria of columns {lUs)ssssa M(U) = (UUXUUI) is POVM and there crists a universal constant such that for all quantum states p and a we have:
|lp ollur
E (MM))
Vd
Proof. Let & p-p-o, o, we have Ule,) (U,) and we use Weingarten Calculus D.1 and D.2 to calculate
E [(US]E = I.. ((CAEEEE
E|
Σ Wg(Ba ,djtrs (ex(el)))
a,
d(d tr(g2).
21

---

Published in Transactions on Machine Learning Research (enteebber/202.,
Similarly
E (UN,))))) E
E BRCeGCCCCCCCCCCCCAAAAUAAAAAAAAAU
XUNCUUUUUKKKUUUUUUUXUXXUUUUUUUUR a,
- -E
(eXe)))
d(d + 1) + 2) +3 (6ir(52) + 6lr((*)):
d
d(d 1)(d + (33 tr(
We can now conclude by Hölder's inequality:
d = E ((US))
2E (TV(((M))
Σ
(BRUAKCU))))
E [UGC))))
dd (d
tr((22 d
2 2c/tr(p - -0)2.
This Lemma is about the expected TV distance. Actually, we prove that we have the same inequality with high probability.
Lemma A.7. Let I = e (log(1/8)) and U U ...., U [dxd be Haar-random unitory matrices of columns (17)) hisaassss MM- = (UU is POVM and there crists universal constant such that for all quantum states p and a we have with probability at least 1 - 8:
(M( 2 1lp ole
Vd
22

---

Published in Transactions on Machine Learning Research (September/2023 22023
Proof. Let f(U)= (M()( we first show that f is Lipschitz by using the triangle and Cauchy
Schwarz inequalities:
((U))1(V))
Σ
7
-
E Isisa.sisi
|
Σ
tt(E9)) ( 1V3xv
isiddisisi
V (r((2)
Σ
b((1//0011-12xxx00
isisdisis!
$ 1 ViT(EE))
1SiSi
1 Vt((E)) V1l2,HS
hence f is L / ( Liipschizz, therefore by Theorem D.3.
2 (ttgttr(())e))///
P (((())- > Vtr((2)) s
= -10./24 = =8/2.
4812
for 1 24)) Finally with high probability (at least 5/2) we have
TV(((M). E - - E(TV(((M),((M))
(T((((M)
tr(??) tr((2)
2 tr((2)
c
c 1p - oll
2 Vr
where is the rank of (p I/d).
Once we have the lower bound on the TV distance between the distributions obtained after performing the measurements, we can deduce upper bounds on sequential algorithms for testing identity depending on the rank of p or I/d.
Dependence in the rank of p 1/d From the previous lower bound on the TV-distacce, we can achieve an upper bound using the sequential tester of (Fawzi et al. 2022
0min min o
2/2 1og(1/))2/2
11p 1/d1=1) 1/d]|=))2² (max(e/Vallo-///111)) 1) =0
log(1/8)
13/2 (og(111))
(max(f/v/ |lp
max ( -I/d
log(1/0) d3/2
r/2 log(1/0) )):
= min
62
Pp
T/d 1
where is the rank of (p-I/d) I/d) and Cauchy Schwarz obtain the latter inequality.
23

---

Published in Transactions on Machine Learning Research (Cpteember22223)
Dependence in the rank of p The proof of Lemma 3.5
permits to deduce that with high probability:
1
2
d-r
IV(P,U,) 2 clpp - T/dll2 2
A
d
+
d
2 c
Σ i=1
x d VV
1
01
1
2r
where r is the rank of supposed to be less than d/2 and we use Cauchy Schwarz inequality. Therefore we can test whether p = 0 or || - allrr > & with probability at least 1 - using
( (max 11/V.11/22
d² log(1/0)
=0 min {
d log(l1// rrd 1og(1/5) (10))
O
2²
copies of p.
B Analysis of Alg. 1
In this section prove the correctness of the Alg. Alg. [ finds the closest quantum state di- to p.
We need to show that with probability at least 1 - 8/2,
Lemma B.1. For all + E [m), let Pij e/10 approzimation of tr(pOis) given by classical shadow tomography of [Huang et al. 2020). Let k* = argmin, max,j Pajj - tr(o)Oi)). We have with at least probability 8/2:
|p ob 11+ s//3.
Proof. Classical shadow tomography of (Huang et al. 2020 permits to have the following approximations
Vi j [m] |na, - tr(pOs,)l S e/10,
with probability at least 8/2 using only N O(dlog(m)/ee) copies of p.
Let the closest quantun state to p. We want to prove that with high probability 1 = We have for all I # it: 10 ulluu > e hence:
max pi.j - tr(o) 2 pr. Moo-tt(o00;..) 1.j
tr(p0;,.1) (r( E/10
2 (i(a;-0i..) ir(a)O+.,) (r(pOrr.)) 1r(;;-0r.)))) e//10
2 1100 - all,rr - 11p- - oz | - 8/10
2 e/3 e/10
> e/2.
On the other hand
max M4.j tr(a Ois)) b.
S max p4j tr(a, ig
I max tr(pO.,)) tr(o,, O1s) e/10 1
< ||p or 1lrr + 5/10
< 5/3 + 10
< <//2.
Therefore, with high probability, ks cannot be different from it
24

---

Published in Transactions on Machine Learning Research (Cpteember22223)
Once we know, with high probability, the closest quantum state to P read its basis and use it to to learn p. The following lemma indicates how to construct this approximation along with the number of copies/ measurements needed for this learning task.
Lemma B.2. Let p E'= AolosMos). Let A AN the outcomes of the measurement of independently by the POVM M (1oiooilte. The quantum state
Ej=
1A,=i
p
is e/10-close in 1-norm to with a probability at least 1 - 6/2 if N = 200 log(24+2/8)/=2
Proof. p a quantum state so it is a Hermitian matrix positive semi definite of trace Hence, we can write probability distribution and {di}: is an orthonormal basis. Therefore Σ lxXo; = and M is valid POVM. Measuring P via the POVM M is equivalent to sampling from the distribution (tr(Ie.Xo:lp = EE Aytr(1oXoo1ll))00 = {it hence
p p= E > > Xóxl where(A:);
AI,..., AN a...d (Ai)i.
On the other hand p and I have the same basis of diagonalization the norm between them is simply
1p pller
Σ AobiXo
Σ Xo
Σ ()e Xoooeoo
Σ A del
2 TV(A, X),
NN where (2:); -
1n J. It is well known that the TV distance can be written N
TV(A, X) max (A(B) A())).
BCl4
Chernoff-Hoefflinn (Hoeflding 1963)
inequality implies for all B [d]
P = LAEB X(B)
(E) 2
< 2exp
-2N
20
20
Therefore by union bound we obtain
P P Rller > e/10)= -P (2TTVV À) > E/10)
Σjnn lA,ER
20 :))
e)
= =P 3B C [d]
X(B)
N
2d+1 exp
-2N
(E)
20
Finally for N 200 (ogg2ll) we have with at least probability 1-8 8 1 +llu S $/10.
Grouping the two previous Lemmas, Alg. finds the closest quantum state d₁. and returns an E/10- approximation of p with probability least (5/2 + 5/2) - 8. Finally, Alg, 1 is 8-correct.
25

---

Published in Transactions on Machine Learning Research (September/2022
C Lower bound for the problem (P)
In this section, we focus on proving lower bounds for hypothesis selection problem (P) for non-adaptive and adaptive strategics.
C.1 Non non-adaptive strategies
We recall the thcorem we want to prove:
Theorem C.1. There tuple of quantum states (o1,..., 0m) such that any learning algorithm, for problem (P) with non-adaptive incoherent measurements requires
md (m) 5² })
d2
N
min
copies of p.
Construction For the construction, we choose m unitary matrices {U,]y chosen randomly from the Haar(d) distribution, then we choose for each unitary (orthonormal basis) random eigenvalues:
Lemma C.2. Let m S exp(dP/300)). Let {Uy)veim/2 m/2 unitaries Haar(d) distributed. For y E [m/2],
let oy = 21/d Om+l-y = UUAUT where A à + diag (Ai)seta)) = diag (1+(-u)110 Jeeid) We have with a probability at least 9/10, for all y # [m]:
|o - 1 ZE.
Proof. Let y * [m/2] and < f(U) = tr (U diag (fdiletaa) Ut diag (Ai where U ~ Haar(d), we have E (f(U)) = -trdiag ((xeheea)) O 58 (see Weingarten Calculus D.1 The function f is 20c -ipsschch
< satisfying Irdiag (Dwileta)) -5e. Let
vi
If(U) f(V)
(Aelieta)) Ut diag (Ahiliete) --aierr))ii--- trVV diag (Dxchiete) Vt diag ((Nileeaa))
-Ir(UU diag
< [tr(U diag
(Ailieta)) Ut diag ((Nslie(a)) ) vitol
< II(U V) diag (Pattreta) Utllee + diag (Aelveta)) (U- vitlle
< |IU Vllall diag (Axhheta) U 112 + VIV diag (Aer)eeja) |lall(U - v)'l22
10s
d (IIU V|[2I1 diag (((-1))) Ut|l2 + V diag
(((-1)))e(a) )eeee) ||alI(U v)2
20s
UU V112,
where we have used Cauchy Schwarz inequality.
Using the fact that the Haar distribution invariant under the multiplication by unitary and the concen- tration inequality for Lipschitz functions D.3 the probability that the states {oy]ve(m/2) not e-separated
26

---

Published in Transactions on Machine Learning Research (September2222)
is upper bounded by
m²
P (3y, 2 [m/2] ll,, - 02ller 5e)
P (loa ozllur S)
m²
(IU, diag (UNileeaa) Ug Us diag (AAdhEea)) Uf se)
4
m
P (iVjU, diag (fhitiela) ) UtU: diag (DNitieta) ll S
4
m
P (IUdiag (Diiheta)) U -diag diag (Darlseaa) ll Sc)
4
m
(tr U didg (Dilieta)) Ti diag
4
m
(((U)) (f(U)) 5 55)
m²
P (E(((U) - f(U) 2 4s)
m
=2
exp
4
x 40062
m²
d²
exp
1000
4
which is smaller than 1/10 if m² & 2 exp(d (df 11000//5.
For the case when y E [m/2] and 2 E [m] \ (m/2), let x = m + 2 E [m/2]] we have
10 lll
= 11, 2T/d + aællur
2 1| 21/d + Jzllur 10 0z1lur
2 2|10, - -Lddlir + I|rr - 100, - l|rr
26
Finally, for the case when y E [m] MoolVro [m/2] and E [m] \ [m/2], let y' = m 1- E [m/2] and x' = m m+1-2 - E [m/2] we have
10, - 0211ir = 1|2I/d dd By 211/d + as
2 ||0 11r
2 8.
We have shown how to construct the unitaries, we move to prove the existence of the eigenvalues:
Lemma C.3. There erists family of quantum states (p= (where is a universal conslant) such that for each y E [m], (Prw)a e/5-separated and commute.
Proof. We start by writing the eigen-decomposition of the known quantum states oy as
oy oy= Uy
Σ oxa Uy.
We claim that we can choose of to construct an e/5-separated family of me quantum states (c is constant to chosen later) the form
of (2(3333)
Pz,y U.
Σ
X
lixil Ug.
d
27

---

Published in Transactions on Machine Learning Research (Cpttember22023)
for |x|| [ead] and [m]] Note that for convenience of notation, the labels can be positive and negative. Moreover the distance between Pay and By is exactly:
Pr Byllur 3
Concretely, we look for (oshsisass such that
1. ag = =1,
2. a; -a
3. of + /////2 (we suppose d is even) and
4. Vr + x' E of a. > d(1/2 - 1/200).
2/2
The third point ensures that has trace 1 while the fourth one implies 1P Por llr > e/3 8/100 > e/5. Starting by the simple quantum states Pi.y By + Li=l
d/2 [2e/31 U Uibiiiil Σn 2i=d/2+1 (2e/3) (0 and
f-1.y = -21/d Pl.y am+l-y - - (2=/3) have constructed Q e-separated family of the form described above of cardinality M < end Let 01....,0d//2 0.// i.i.d random variables taken values in {+1} with probability 1/2 each. We have by Hoeffding's inequality
d U + -i d/-d/2+1 (22/3) Un liXiitt and we suppose that
4/2
4/2
P
Pp E Q:
Σ i=1
a -asl S 2(1/2-1/200) OR Σ
oil S d(1/2 d
i=1
d/2
d/2
= P
3p3 E Q:
Σ
0 ail s d(1/2 1/200) OR
Σ
10 + +ail _ d 1/200)
1=1
1=1
d/2
d/2
<
P
0==0 > d/4 + d/400/400
+
P
Σ
1a= S d/4 d/400
2
2
< Me 4/2000
which is strictly less than 1 if M < d/2000, So let's take 1/2000, we deduce that
4/2
Vpz E
Σ 2 11/20)))) >
therefore there exists some E {=1]d verifying the desired conditions. We can repeat this construction until Card( Q) 2 eed
We have constructed the e-separated family of quantum states {ayly an the corresponding e e/5-separated {eru)a for all y, we can use tools from communication theory to deduce the lower bound (see (Haah et al, 2016)). Alice encodes a message (x,y) E (l,...,e edd] x [m] Pa.y and sends it Bob. To read the message, Bob tries to approximate the quantum state that he received from Alice. We suppose that Bob approximate (up to e/10 in trace norm) state e/3 close to one of (ay) and diagonalized in the basis of this quantun state with probability at least 2/3. Bob uses N copies to decode Alice's message and returns (x'.y') E (1....,e.4 x [m], therefore by Fano's inequality ((aano) 1961 we have the following lower bound on the mutual information:
Lemma C.4 (Fano). The mutual information can be lower bounded:
T(X,Y: X', Y') 2/3 log(me log(2) ' 2(log(m) + +d).
28

---

Published in Transactions on Machine Learning Research (0pptember/2023)
On the other hand be the outcomes of a non adaptive algorithm solving the problem (P). By using the data-processing inequality for the Kullback-Leibe
upper bound the mutual information between (X, Y) and YY) Let I1...., IN
divergence and the fact that every non adaptive algorithm for the problem (P) can used as a 2/ 3/3-correct decoder we can upper bound the mutual information as follows:
Lemma C.5 procesproessiing. The mutual information between (X,Y) and (X', is smaller than the mulual information belween (X,Y) Y) and (J,,..,, IN):
I(XY X',Y' s I(X,Y I1... IN).
The next step is to upper bound the mutual information between (X,Y) and (I1....,Iy) Ix). This latter depends on the quantum states (ay)y: therefore it is random variable. We will show that with at least probability 9/10, it is upper bounded by expression involving the parameters of the problem. First we start by proving the following upper bound relating the mutual information with the unitaries {Uyh, hy defining the quantum states {oy]y-
Lemma C.6. For all unitories {Uyby, we have:
I(X,Y: : I..... IN) < 4N
sup
Σ (,,'),,,,
M
|al.ySm/2
where for (xr (), Oz, = (dpxy.y T)Ug-
Proof. We suppose that the eigenvalues of By have the form
108
d
where 3.¹ - 1 satisfying 3. 8 (exactly half are equal to +1) and 33 = -fm+113 (we suppose m even).
The diagonalizing matrices {Ughy are chosen randomly they satisfy Um+1-y Uy for all y S m/2 and other conditions to be specified later.
Let denote by M the POVM used at step t. Without loss of generality, we suppose that the non-adaptive algorithm performs only measurements of the following form:
M {lo
where we have the condition Σ, |of = II implying for all i and t: 1oofll S 1.
Let M = od we can write the mutual information as follows:
I(X,Y I IN) = H
Σ
tr((peg))
Nn ON CN (M)
Σ H (tr((pay) a.
JN (
M
M
3.11
II N (p 1p
(o) (e.. log
= Ei + Ez,
M
Ex. H. (0) lo.yldd
2. Mlsnea
where ΣS and Eg are defined as follows:
1 Σ Σ
N II
N II
Σ
(ot
lp ( (t,)log log
M
3.9 $1...d
Σn
1 Σ
Σ
II
(ot (o (e,. log
( (e
M
M 2.0
3.G $1 11..0
Since
1+ (10,3 + 2a /3)
Pa.y = Uy diag
Ut
d
(E(d)
29

---

Published in Transactions on Machine Learning Research (September 20023)
can write
1.a.yg
+ ui,
( (
d
where ui 1.
(0), Uy diag (110/3) + 20//33) (3) Uylo())
(-11, 11).
Denote by Oz.y
diag
(1033% +2a /31s)))) we remark that
d
L.
Σ
(0) Uy diag (1108) + 2a, /3)aa)) Uplot,) = irú,, diag (1108% + 207/3)/e(a) U,
1==1
81
d tr diag (11033 + -2a, / /3((())))
105 +2a / Σ
Moreover, the couples of quantum states (pa p=z,)) and (Pe.g pa,m+l-)) are symmetric with respect I/d by the construction of (az) and (ff) hence
1. 1.-r,m++ +1 = (of, [Um+1 1- diag (100 -2, 1/3 kE(A))
U Um 1n+1-g1l1)
(of, IUy diag (1-10,3 -2a (3)se)))) Unlo!)
-dd,, Uy diag (11033 +2 /3)se(4)) Uplo%)
L.N.y.
Uic
Suppose that 8 < 0.05. We can start by controlling En using Jensen's inequality:
N
1.2.Us
Σg
Σ
II
+
Mie
log
23 (.
2,8 f1
2,
M ΣI
N
1 +
Uie
L.N.V
Σ
log II (1 + uhy
(.
d
M
t-l t=l
2,8
N
+ u t.
1
Σ
log (1 + ut, (.
M
d
M
t. t=l
2.8.
N
1 + u4
L.
log (1 + ut (.)) + log (1
u. 2.0.9 E)
z
|=l.uSm//2.
L.a.y 1 +
ΣI
Uie
e
Σ
log
M 2-1
d
M
Ixl.uSm//2.
30

---

Published in Transactions on Machine Learning Research (yppeember/222,,
Now, we can use the inequality
- -oog(1 x²)=
2x² for |2|| S 1/v2:
N
f.
E2 S
Σ
II
+
Use
1
Σ
log (1 - (uf
M
M
1=1
Iml.uSm/2.tt
N
ΣI
ui
Σ
2(u ?2?
$ M
d
M
2,8, t=1
ΣI
N
+
ui
Σ
$
sup
M
d
M
2
|=/.5/m222
NN sup
Σ
2
M
Using the fact that Ei, " ب 2x for |x|| I 1/v2 we can upper bound the first sum Σx:
for all t, 2, y along with the incquality (1+z))og(11) +z) +(1 2)) log(110))) S
1 +
LRV b1 d
Σ1
Il
log
II t=1
(1 + uie (. E)
M
s.y.i t=1
N
+ Ui,
Σ log
[I + Uix
M
d
n.y.i t=1
k
ΣΣ
E
II
1 + Ug
log (1 (1+ u
k.
d
K.y.k iN f ton t=1
K.N.y &
1 Σ
+ Wik
+ tha k
log
M
K.i.k in
Σ
Σ
1
us
log 1 + u
(1- u/
k log (1 (1-
u//
k.
Md
flvSm/2,,k in
Σ
2 232
Md
al,ymm/2,k.i
1 Σ
((0U,,0,UU))))))
d
sup
M
R.
Iol.usm/2
2N sup
Σ
(0UU,0,,UU 0)26
al.ySm/2
Finally the upper bounds En and Σg imply the required upper bound on their sum E, + I(X.Y: I,...,, IN).
Note that we need to take a supremum over all possible vectors & because the learner knows the quantum states {ay), and so it can choose measurements dependent on the unitaries (Uyhy- We can now show that with high probability on the choice of the unitaries {Urhy, the latter supremum can bounded and so the mutual information too.
Lemma C.7. Let (U m unitary matrices Haar(d) distributed. We have with a probability at least 9/10:
Σ (MU,O..,UU10) = No*
-oNN6 log(m) Ne2
(Ne"lgg(m)
4N sup M
+ d
d.
Isl.u5m/2
31

---

Published in Transactions on Machine Learning Research (0pptember/2023)
Proof. To upper bound the previous supremum, use similar approach to (Chen et al, 2021 ): For U Haar(d), a E B(0, 1) and trace-less Hermitian matrix O, let f(d, U) (p|UOU" (0), we have E (f((, U))
{ = 0 (see Weingarten Calculus D.1p and f is 1-ipsphissh:
(f(U) f(V) < ( V)ou*()) = 2ll01lIi Vll2
Therefore by the concentration incquality
D.3
P (If(UU) > t) S
Hence
(()(U)) S exp( exp(-dt/48).
For m/2 unitaries UI...., ,,m/2 and X = 2d/C for sufficiently large C. Denote by X = (f(U)) by Markov's inequality:
2
xt) exxp(-Amt/2) (e^X) m/2 S sexp(-Amt/2) 1+ (o d m/2
P
Σ |f(U,))?+
m
ISuSm/2
(
(C")m/² S exp(-dmt/CC mogg(")))
with O' another constant. In order to prove inequality valid for all Φ eE B(0, 1), let's take 17-nct {ørh of size at most (1 + 2/1)2d. For & E B(0, 1), there is os such that || Φill2 S 1). Moreover (f(,,U) s |0 so
2
Σ
f(0,U,)² (am))=f(o,.00 U,)
Σ 1yySm/2
If(Ø, -,2 ((..U,,)
m
m
1Sy5m/2
2|[011((6]] (o.)u, 1)) (0.1(, O12
15y5m/2
Therefore
2
1
P
36
Σ
SP 36;
If Uk)
m
m
1SvSm/2
< (1 + 2/n) 2d
/C + log(C"))
Taking 1/m yields:
P
3Ø
2 m
Σ
{f(d,U,) > ++ 2
I (1 + 2x))dexp(ddn))) + m log(("))
15y5m/2
Applying the union bound, we can obtain:
P 30, Er, Σ (ol,,Onn 2 210
s 4e 41 + 2m) am))dexpp( + m log (C')).
vSm/2
Let's take C add log(1 2m) ) mm (C")
in order to have
dm
2 211On.vll' (dlU,O,. stt
P
Yo, M
Σ
m
I=l.umm/2
Oz Ut Ut < 2 2110
P
Vo, Vo.
Σ
O
m5m/2
9/10.
32

---

Published in Transactions on Machine Learning Research (tnembbrr/2023)
Therefore we have the existence of {Uyhy such that for all
1oa - 02 tr > e,
and
sup M elllllas1
1
Σ
(. 0)
tr(O 2.9
+ +t
2/102.011
d(d
1)
m
201
+ C log(440) + cd + 2d + 2m) + log(("))
242
$ d+1
+
dm
Finally, we showed the existence of quantum states {Z such that:
log(m) m
1(,Y 4 IN)
IN)= =
Ne².
To sum up, we have shown the exislence quantum states {on.y) such that:
2(log(m) + +d) & I(X,Y: X", xY,Y Y") & I(X.Y: I.....,. IN) s o (2 log(m) No..
m
We conclude that N = Ω min
md
})
log(m))
C.2 Adaptive strategies
It is important to see why this proof doesn't work for adaptive strategies. The lower bound the mutual information has nothing to do with the non-adaptive/ /atrre////viie option of the algorithm so it remains true. However, upper bounding the mutual information camnot be done the same way since now the POVM used at time depends on the previous outcomes. Let {ur be a sequence constituted by the outcomes of a correct adaptive algorithm. Let M = {ook [oo"<XX0*** Xo="(Jo the POVM used at time t given the previous outcomes Uet- Recall that the mutual information between (X,Y) and (I,,..., IN) can be expressed as:
I( IN) = E1 + E2.
The second sum can be upper bounded by the same technique as before (using for example Jensen's inequality and the inequality - log(11 - x²) < 2x²) and yields the same upper bound. The first sum is more involved because the product cannot be simplified due to the dependence between the POVMs and the previous outcomes. To see this, we try simplify the first sum far possíble:
N
Σ
1 Σ
Σ
II
Gue Pawv
sace) log
II
(ou suci |dpe.yl (lace)
K. M...MM 1=1
Σ Σ
Il
Tovee Ia 0000 log (1ouee |dpz. ((tee))
M
Si t=1
N
=
II
M
II
Sonce Pa.y
Panlo (omre)) log ((0Mcc (d (dtc))
K.y.k Ml 1=1
= 1 Σ Σ
II
Ko ppsstlloooll Pee.llar log ((0 (dpe.s/ (dpe.ol
M
K.y.k My th [=1
33

---

Published in Transactions on Machine Learning Research (September/202g
where the last equality follows from the fact that
E(oti (rayy = (r(pa,y) = 1,
for 1>> k and log ((0us (lor)) is independent from uy- But we are stuck at k, we cannot simplify the sums on Us for s < k since (ov. (pa.yoa. () has common terms with (ous f |paay (as") which is inside the log function.
In order to circumvent this difficulty, we can upper bound the h term which poses the obstacle of simplifi- cation. Using the inequality log(x)
S
x - for all x > -1 we obtain:
E =
EE M
II
Paalee.r log ((o's*|ppsyy (
2, Mi Mi f=1
E M
(o
o Payl
(MQu |dpa.yl - 1)
Z.G.K Mi pooeyll t=1
E
Σ
II
Toue (oavl (1obt" Idcpsstdddollll00 puatt 1)
M
2.U.K Mi Mi
1
E
II Onv
(o0t:)\00"x" x. 10
+E
M.
d
d
2,9,8 Mly f=1
1 Σ Σ
R-1
I
Oas
(ouel
+
E
(oueHlI I + (m.)l0==)))))) (00 an 10 )
M
d
d
d
2. Mi
uu
k-1
Onn d
Σ
+
d
M
d
2.y.k Migeolil tml
+ M
Σ
Σ
II
k-1
II
+
E
Oze
l0uc
Σ
1
pack (00x. 22
u
d
d
d
K.y.k M1 1=
E
Σ
Σ
R-1
+
E
Omn
x x tr((0z..))
M
d
2. Mi Mo
Σ
Σ
1-1
II
II
+
Oze
1
x ÿ 2002002
1
M
d
d
k.y.k 01
1 M
E
Σ
Σ
k-1
II
I +
Onv
(Qurc)
1 x d
de
d
Z.y,K Wi.... t=1
1 Σ 1x
M 2,8.6
< No?
where we use again En, (0lr 10 = tr((Oz.) = 0 for all f and
Σ 14
2.
Σ
tr tr(O wow No (orylou [xxxx=
tr 1 ( = tr( S 112d.
34

---

Published in Transactions on Machine Learning Research (September/202)
Therefore the mutual information can be upper bounded by
I(XY x X',) & 121N2² + 2N sup e.ll@|aS1
Σ I
M
123Ne
Since the mutual information is always lower bounded by (m)og(mm + d) we conclude that N D((d log(m)/c2)) Finally, have proven the following lower bound on adaptive strategios for hypothesis selection problem: Proposition C.8. Any learning algorithm with adaptive incoherent measurements requires
N2 d ( log(m)
copies of p to find the closest quantum state dg. p and approzimate p to at most E/10 with at least probability 2/3.
This Proposition implies that Alg. is almost optimal and @dde²² is the optimal copy complexity of hypothesis selection problem using adaptive incoherent measurements.
Technical lemmas
In this section we group technical lemmas useful for the previous proofs this article.
D.1 Weingarten Calculus
Since we use generally a uniform POVM, which consists in sampling a Haar-unitary matrix, we need some facts from Weingarten calculus in order compute Haar-unitary intergrals. If a permutation of (n], let Wg(#, d) denotes the Weingarten function of dimension d. The following lemma is crucial for results. Lemma D.1. Gu 2015) Let U be a d x d dist-diitd unitary matrir and {A, Bihs sequence of d x d complex matrices. We have the following formula
[Ir(UU,,UU AU A.U...UB.A .BB An))
Wg(Ba ,d)rrg- " (Bi, ...,, Ba) Ba)tr (0 (A1...., An); a.B.S.
Σ
where (12 n) and lr (M, Mn) = I,tr(Uli Mi) for a = II, and Cj are cycles.
We need also some values of Weingarten function:
Lemma D.2. Wg((1), 1
Wg((12), d) ब
Wg((1)(2), d) = Ø-1:
Wg((123), d) a(d (F--1)d-- 3
Wg((12) d) (d- 44) 4
Wg(()) d) बe 11)
D.2 Concentration inequalities for Haar-random unitary matrices
Theorem D.3. [Meckes et al. 2013) Let M U(d)* endowed by the Ly-norm of Hilbert-Schmidt metric. F M + R is I.-ippschlzz, then for any t. t>0 ()
P( U,) E (F(U1, 22)) at /1213
where Uz,..., Up are independent Haar fnar-distributed unitary matrices.
35


Reviews:
[{"review_id": "6m6V8AMnBJ", "reviewer": "Reviewer_9Wc6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors characterize and compare the sample complexity for sequential and non-sequential strategies showing that sequential adaptive strategies are more efficient than non-sequential non-adaptive ones for some specific problems.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Disclaimer**: In all fairness to the authors, I do not know anything about quantum testing / quantum theory, and my review here is cosmetic at best going through just the organizational aspects of the writeup as suggested by the esteemed Action Editor. The organizational aspects of the paper appear fine.\n\nThis paper considers the quantum hypothesis selection problem. The authors characterize and compare the sample complexity for sequential and non-sequential strategies showing that sequential adaptive strategies are more efficient than non-sequential non-adaptive ones for some specific problems.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "NA", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OFZXCSb44u", "reviewer": "Reviewer_W2pY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The paper presents solid theoretical results for analyzing the performance of hypothesis testing strategies in quantum learning theory and rigorously establishes a polynomial separation between adaptive and non-adaptive strategies.\n2. The technical contributions made by this paper in analyzing the adaptive and non-adaptive strategies for hypothesis selection are novel, advancing our understanding of the fundamental question of the advantages of the adaptive regime.\n3. The results and insights presented in the paper have potential implications for quantum information theory.\n\n### Weaknesses\n1. The introduction could be improved by more clearly explaining the motivation for this problem, and the significance of the research question being addressed. As for this journal TMLR, it will be better to mention more background/motivations on how the problem is related to (quantum) learning theory.\n2. The paper could benefit from a more systematic organization of its main results, including clear definitions and a table of the different settings under consideration. While reading, the current versions sometimes confused me about these many different settings and terminologies. The clear presentation of the definition and conclusion could be improved to make the results more accessible to a wider range of readers.\n3. One main result in this paper is the advantage established in section 4. It is unclear to me about the intuition behind the constructed problem and meanwhile it seems not very direct that how the constructed problem is a hypothesis selection problem. Also, are there any further applications of this problem in quantum information or learning theory？\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission presents an exploration of whether sequential strategies can outperform non-sequential ones in solving the hypothesis selection problem, which is an important problem in quantum learning theory. The main focus is to understand how many measurements are needed to select the hypothesis with certain probability and error tolerances under different regimes, including sequential/non-sequential adaptive/non-adaptive algorithms.\n\nThe authors show that there are some situations where sequential or adaptive strategies require fewer measurements than non-adaptive non-sequential ones. For the setting of two hypotheses, the paper shows that sequential strategies outperform non-sequential ones by a factor of 4, which was also shown in Li et al. (2022b). For the setting of more hypotheses, the paper constructs a particular problem and establishes a provable polynomial separation between adaptive and non-adaptive strategies. Overall, this paper presents new insights into the performance of testing strategies for quantum systems, with potential implications for understanding the power and differences between adaptive and non-adaptive protocols in quantum information processing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the comments on Weaknesses.", "broader_impact_concerns": "The contribution of this paper is theoretical and I do not see any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eDpzcfXFtC", "reviewer": "Reviewer_csnD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The influence of adaptivity is an interesting topic, and it reflects the difference between offline learning and online learning. It is nice to know that in the quantum setting, namely the hypothesis selection of quantum states, there’s provable separation between adaptive and non-adaptive strategies.\n\nWeaknesses: I think this work has two main weaknesses: novelty and connection to machine learning.\n\nIn terms of novelty, the problem studied in Proposition 3.1, non-adaptive testing of quantum states, is called quantum state discrimination and is a standard problem in quantum information theory. Its adaptive version, Proposition 3.3, has significant overlap with Li et al. (2022b). In terms of the classical shadow problem studied in Section 4, Theorem 4.1 is from Huang et al. (2020). In general, my personal take on this paper is that the perspective of telling the story in adaptivity vs. non-adaptivity is nice, but technically the contribution is not that significant and it glues existing techniques together into this high-level picture.\n\nAnother notable weakness is the connection to machine learning. In general, the technical results in this paper may suit better in quantum information theory or theoretical computer science, for instance most papers cited by this one fall into those two categories. So why is this paper particularly suitable for TMLR? I think the authors should think about this question and write the paper in a more favorable way to machine learning audiences. For instance, how is the adaptivity vs. non-adaptivity story in this paper same or different compared to classical online machine learning vs. offline machine learning? Do the results in this paper have further implications in classical machine learning? Answers to those questions will be very helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of quantum hypothesis selection, with the focus on understanding whether using adaptive strategies can significantly improve the sample complexity of quantum states. Specifically, the paper proved that for testing between two states, there is a factor of 4 improvement compared to non-adaptive strategies. A more significant speedup is established for the learning with shadow problem in Huang et al. (2020), whose adaptive complexity is ~O(d/eps^2), but this paper proved that non-adaptively it takes Omega(d^2/eps^2) copies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please try to address my two concerns in weaknesses above.\n\nIn addition, it would be helpful if the authors can make improvements on the following points:\n\n- Between consecutive paragraphs, there should be an empty line for spacing. The current template is a bit dense for reading.\n\n- There are a few other papers about property testing of quantum states/distributions that the authors should probably cite, for instance Acharya et al. https://ieeexplore.ieee.org/abstract/document/9163139/ (copy complexity of estimating entropies of a quantum state), Gilyen and Li https://arxiv.org/abs/1902.00814 (it studied ell_1 and ell_2 norm closeness testing problems), and Belovs https://arxiv.org/pdf/1904.02192.pdf (distinguishing between classical distributions encoded by quantum oracles).\n\n- I’m a bit confused by Section 3.1.2. It seems that the adaptive strategy still uses the optimal POVM by the Holevo-Helstrom theorem, so how can the bound improve by a factor of 4 compared to the non-adaptive case? More explanations will be helpful.", "broader_impact_concerns": "I don't think this work has any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study whether sequential strategies can outperform non-sequential ones in solving the hypothesis selection problem, which is an important problem in quantum learning theory. The main focus is to understand how many measurements are needed to select the hypothesis with certain probability and error tolerances under different regimes, including sequential/non-sequential adaptive/non-adaptive algorithms.

The authors show that there are some situations where sequential or adaptive strategies require fewer measurements than non-adaptive non-sequential ones. For the setting of two hypotheses, the paper shows that sequential strategies outperform non-sequential ones by a factor of 4, which was also shown in Li et al. (2022b). For the setting of more hypotheses, the paper constructs a particular problem and establishes a provable polynomial separation between adaptive and non-adaptive strategies. 

Overall, this paper presents new insights into the performance of testing strategies for quantum systems, with potential implications for understanding the power and differences between adaptive and non-adaptive protocols in quantum information processing.
Decision: Accept (poster)