# Quantum Sequential Hypothesis Testing

Esteban Martínez Vargas<EMAIL_ADDRESS>Física Teòrica: Informació i
Fenòmens Quàntics, Departament de Física, Universitat Autònoma de Barcelona,
08193 Bellatera (Barcelona) Spain  Christoph Hirche
<EMAIL_ADDRESS>QMATH, Department of Mathematical Sciences,
University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark  Gael
Sentís<EMAIL_ADDRESS>Física Teòrica: Informació i Fenòmens Quàntics,
Departament de Física, Universitat Autònoma de Barcelona, 08193 Bellatera
(Barcelona) Spain  Michalis Skotiniotis<EMAIL_ADDRESS>Física
Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat
Autònoma de Barcelona, 08193 Bellatera (Barcelona) Spain  Marta Carrizo
Física Teòrica: Informació i Fenòmens Quàntics, Departament de Física,
Universitat Autònoma de Barcelona, 08193 Bellatera (Barcelona) Spain  Ramon
Muñoz-Tapia<EMAIL_ADDRESS>Física Teòrica: Informació i Fenòmens
Quàntics, Departament de Física, Universitat Autònoma de Barcelona, 08193
Bellatera (Barcelona) Spain  John Calsamiglia<EMAIL_ADDRESS>Física
Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat
Autònoma de Barcelona, 08193 Bellatera (Barcelona) Spain

(August 27, 2024)

###### Abstract

We introduce sequential analysis in quantum information processing, by
focusing on the fundamental task of quantum hypothesis testing. In particular
our goal is to discriminate between two arbitrary quantum states with a
prescribed error threshold, $\epsilon$, when copies of the states can be
required on demand. We obtain ultimate lower bounds on the average number of
copies needed to accomplish the task. We give a block-sampling strategy that
allows to achieve the lower bound for some classes of states. The bound is
optimal in both the symmetric as well as the asymmetric setting in the sense
that it requires the least mean number of copies out of all other procedures,
including the ones that fix the number of copies ahead of time. For qubit
states we derive explicit expressions for the minimum average number of copies
and show that a sequential strategy based on fixed local measurements
outperforms the best collective measurement on a predetermined number of
copies. Whereas for general states the number of copies increases as $\log
1/\epsilon$, for pure states sequential strategies require a finite average
number of samples even in the case of perfect discrimination, i.e.,
$\epsilon=0$.

#### Introduction.

Statistical inference permeates almost every human endeavor, from science and
engineering all the way through to economics, finance, and medicine. The
perennial dictum in such inference tasks has been to optimize
performance—often quantified by suitable cost functions—given a fixed number,
$N$, of relevant resources Lehmann and Casella (2006); Helstrom (1976). This
approach often entails the practical drawback that all $N$ resources need to
be batch-processed before a good inference can be made. Fixing the number of
resources ahead of time does not reflect the situation that one encounters in
many real-life applications that might require an online, early,
inference–such as change-point detection Tartakovsky  _et al._ (2014); Sentís
_et al._ (2016, 2017, 2018), or where additional data may be obtained on
demand if the required performance thresholds are not met.

Sequential analysis Wald (1973) is a statistical inference framework designed
to address these shortcomings. Resources are processed on-the-fly, and with
each new measured unit a decision to stop the experiment is made depending on
whether prescribed tolerable error rates (or other cost functions) are met;
the processing is continued otherwise. Since the decision to stop is solely
based on previous measurement outcomes, the size $N$ of the experiment is not
predetermined but is, instead, a random variable. A sequential protocol is
deemed optimal if it requires the least _average number of resources_ among
all statistical tests that guarantee the same performance thresholds. For many
classical statistical inference tasks it is known that sequential methods can
attain the required thresholds with substantially lower average number of
samples than any statistical test based on a predetermined number of samples
Wald (1973). The ensuing savings in resources, and the ability to take actions
in real-time, have found applications in a wide range of fields Leung Lai
(2001); Tartakovsky  _et al._ (2014). Extending sequential analysis to the
quantum setting is of fundamental interest, and with near-term quantum
technologies on the verge of impacting the global market, the versatility and
resource efficiency that sequential protocols provide for quantum information
processing is highly desirable.

In this paper we consider the discrimination of two arbitrary finite
dimensional quantum states Bae and Kwek (2015), $\rho$ (corresponding to the
null hypothesis $H_{0}$) and $\sigma$ (corresponding to the alternative
hypothesis $H_{1}$), in a setting where a large number of copies can be used
in order to meet a desired error threshold $\epsilon$. A first step in this
direction was taken in Ref. Slussarenko  _et al._ (2017), which considers the
particular case where $\rho$ and $\sigma$ are pure states and restricts the
analysis to specific local measurement strategies. Here, we address the
problem in full generality, including arbitrary states, weak and collective
measurements. For collective strategies involving a large _fixed_ number of
copies the relation between this number and the error $\epsilon$ is
$N\sim-\frac{1}{\xi}\log\epsilon$ 111By $f(\epsilon)\sim g(\epsilon)$ we mean
asymptotic equivalence $\lim_{\epsilon\to 0}f(\epsilon)/g(\epsilon)=1$, where
the rate $\xi$ depends on the pair of hypotheses and on the precise setting as
we explain shortly. We show that one can significantly reduce the expected
number of copies, $\langle{N}\rangle$, by considering sequential strategies
where copies are provided on demand. We give the ultimate lower-bounds as a
single-letter expression of the form,

$\langle{N}\rangle_{0}\geq-\frac{\log\epsilon}{D(\rho\|\sigma)}+O(1)\;\mathrm{,}\langle{N}\rangle_{1}\geq-\frac{\log\epsilon}{D(\sigma\|\rho)}+O(1)$
(1)

for $\epsilon\ll 1$, where $\langle{N}\rangle_{\nu}$ is the mean number of
copies given the true hypothesis is $\nu\in\\{0,1\\}$ and
$D(\rho\|\sigma)={\rm tr}\rho(\log\rho-\log\sigma)$ is the quantum relative
entropy. In addition, we provide upper bounds which, for the worst case
$N_{\mathrm{wc}}=\max\\{\langle{N}\rangle_{0},\langle{N}\rangle_{1}\\}$, are
achievable for some families of states.

Specifically, we consider quantum hypothesis testing in a scenario where one
can guarantee that for _each_ realization of the test the conditional
probability of correctly identifying each of the hypotheses is above a given
threshold. This scenario, first introduced in Slussarenko  _et al._ (2017),
can be considered genuinely sequential since such _strong error_ conditions
cannot be generally met in a deterministic setting. The proof method can be
easily extended to the more common asymptotic _symmetric_ and _asymmetric_
scenarios involving the usual _type I_ (or _false positive_) and _type II_ (or
_false negative_) errors. We give the optimal scaling of the mean number of
copies when the thresholds for either one or both types of errors are
asymptotically small.

Before proceeding, let us briefly review these fundamental hypothesis testing
scenarios, which come about from the relative importance one places between
type I error—the error of guessing the state to be $\sigma$ when the true
state is $\rho$ whose probability we denote by
$\alpha=P(\hat{H}_{1}|\rho)$—and type II error—the error of guessing $\rho$
when the state is $\sigma$ whose probability is $\beta=P(\hat{H}_{0}|\sigma)$.
Often, the two types of errors are put on equal footing (_symmetric_ scenario)
and one seeks to minimise the mean probability of error
$\bar{\epsilon}=\eta_{0}\alpha+\eta_{1}\beta$ with
$\eta_{0},\eta_{1}=1-\eta_{0}$ the prior probabilities for each hypothesis.
The mean error decays exponentially with the number of copies with an optimal
rate given by the Chernoff distance Audenaert  _et al._ (2007); Nussbaum and
Szkoła (2009), $\xi_{\rm Ch}=-\inf_{0\leq s\leq 1}\log{\rm
tr}(\rho^{1-s}\sigma^{s})$.

Yet, there are asymmetric instances, e.g., in medical trials, where the effect
of approving an ineffective treatment (type-II) is far worse than discarding a
potentially good one (type-I). In such cases it is imperative to minimise the
type II error whilst maintaining a finite probability of successfully
identifying the null hypothesis, i.e., $p(\hat{H}_{0}|\rho)=1-\alpha\geq
p_{s}>0$. The corresponding optimal error rate for quantum hypotheses is given
by quantum Stein’s lemma Hiai and Petz (1991); Ogawa and Nagaoka (2000),
$\beta\sim{\rm e}^{-\xi_{S}N}$ where $\xi_{S}=D(\rho||\sigma)$ is the quantum
relative entropy. If, on the other hand, we require the type I error to decay
exponentially, i.e., $\alpha\leq{\rm e}^{-rN}$ for some rate $r$, then the
optimal rate is given by the quantum Hoeffding bound Hayashi (2007); Nagaoka
(2006). These optimal error rates for strategies with fixed number of copies
have found applications in quantum Shannon theory Wilde (2017), quantum
illumination Lloyd (2008), and provide operational meaning to abstract
information measures Audenaert  _et al._ (2008); Calsamiglia  _et al._ (2008);
Berta  _et al._ (2017).

What the above results also show is that for $N$ fixed there is a trade-off
between the probabilities of committing either error. The advantage of
sequential analysis is that it provides strategies capable of minimising the
average number of copies when _both_ errors are bounded, and yields higher
asymptotic rates in each of the settings described above.

#### Fixed local measurements.

We begin by considering the case when each quantum system is measured with the
same measurement apparatus $E$, giving rise to identically distributed samples
of a classical probability distribution. This strategy has the advantage of
being easily implementable, and that it lets us introduce the classical
sequential analysis framework. Specifically, the optimal classical sequential
test, for both the strong error as well as the symmetric and asymmetric
setting, is known to be the _Sequential Probability Ratio Test_ (SPRT)Wald and
Wolfowitz (1948) which we now review.

After $n$ measurements have been performed, we have a string of outcomes
$\mathbf{x}_{n}=\\{x_{1},x_{2},\ldots,x_{n}\\}$, where each element has been
sampled effectively from a probability distribution determined by the POVM
${E}=\\{E_{x}\\}$ and the true state of the system, i.e., either ${p}(x):={\rm
tr}(E_{x}\rho)$, or ${q}(x):={\rm tr}(E_{x}\sigma)$. For given error
thresholds $\epsilon_{0},\epsilon_{1}$, the strong condition demands that for
each conclusive sequence the conditional probabilities obey either

$\displaystyle P(\rho|\mathbf{x}_{n})$
$\displaystyle=\frac{\eta_{0}p(\mathbf{x}_{n})}{\eta_{0}p(\mathbf{x}_{n})+\eta_{1}q(\mathbf{x}_{n})}\geq
1-\epsilon_{0},\;{\rm or}$ (2) $\displaystyle P(\sigma|\mathbf{x}_{n})$
$\displaystyle=\frac{\eta_{1}q(\mathbf{x}_{n})}{\eta_{0}p(\mathbf{x}_{n})+\eta_{1}q(\mathbf{x}_{n})}\geq
1-\epsilon_{1}$ (3)

where $p(\mathbf{x}_{n})=\prod_{k=1}^{n}p(x_{k})$ since the copies are
identical and independent (the same holds for $q$). If neither condition is
met, a new copy needs to be requested and we continue measuring. That is,
starting at $n=1$ at every step $n$ we check whether

  1. 1.

$P(\rho|\mathbf{x}_{n})\geq 1-\epsilon_{0}$, then STOP and accept $H_{0}$,
with guaranteed probability of success $s_{0}=1-\epsilon_{0}$.

  2. 2.

$P(\sigma|\mathbf{x}_{n})\geq 1-\epsilon_{1}$, then STOP and accept $H_{1}$,
with guaranteed probability of success $s_{1}=1-\epsilon_{1}$.

  3. 3.

If neither 1 nor 2 hold, continue sampling.

Using (2) and (3), the condition to continue sampling can be written in terms
of a single sample statistic, the log-likelihood ratio

$\displaystyle
Z_{n}=\log\frac{q(\mathbf{x}_{n})}{p(\mathbf{x}_{n})}=\sum_{k=1}^{n}z_{k}\mbox{
with }z_{k}=\log\frac{q(x_{k})}{p(x_{k})}$ (4)

as $b:=\log B\leq Z_{n}\leq\log A=:a$, where
$A=\frac{\eta_{0}}{\eta_{1}}\frac{1-\epsilon_{1}}{\epsilon_{1}}$,
$B=\frac{\eta_{0}}{\eta_{1}}\frac{\epsilon_{0}}{1-\epsilon_{0}}$.

Figure 1: Random walk describing the likelihood function $Z_{n}$ under $H_{0}$
(green) and $H_{1}$ (orange). When the value of $Z_{n}$ crosses
$b\sim\log\epsilon_{0}$ ($a\sim\log\tfrac{1}{\epsilon_{1}}$) we decide in
favour of $H_{0}$ ($H_{1}$). $N$ indicates the corresponding stopping time.

It is convenient to interpret $Z_{n}$ as a random walk (see Fig. 1) that at
every instance performs a step of length $z_{k}$ with probability $p(x_{k})$,
if $H_{0}$ holds, or with probability $q(x_{k})$, if $H_{1}$ holds. Under
$H_{1}$ the mean position of the walker at step $n$ is given by
$\langle{Z_{n}}\rangle_{1}=\sum_{k=1}^{n}\langle{z_{k}}\rangle_{1}=n\langle{z}\rangle_{1}=nD(q\|p)>0$
where $D(q\|p)=\sum_{x}q(x)\log\frac{q(x)}{p(x)}$ is the relative entropy;
while for $H_{0}$, $\langle{Z_{n}}\rangle_{0}=-nD(p\|q)<0$. That is, under
$H_{1}$ the walker has a drift towards the positive axis, while under $H_{0}$
it drifts towards the negative axis. We define as the stopping time $N$ the
first instance in which the walker steps out of the region $(a,b)$, i.e.,
$N:=\inf\\{n:Z_{n}\notin(b,a)\\}$, and note that it is a stochastic variable
that _only_ depends on the current as well as the past measurement record. The
stochastic variable $Z:=Z_{N}$ is the position of the walker at $N$. The mean
value of this position can be related to the mean number of steps by Wald’s
identity Mitzenmacher and Upfal (2005),

$\langle{Z}\rangle_{1}=\langle{\sum_{k=1}^{N}z_{k}}\rangle_{1}=\langle{z}\rangle_{1}\langle{N}\rangle_{1}=D(q\|p)\langle{N}\rangle_{1}$
(5)

under hypothesis $H_{1}$, and likewise
$\langle{Z}\rangle_{0}=-D(p\|q)\langle{N}\rangle_{0}$. In order to estimate
$\langle{N}\rangle_{i}$ from (5) we need to provide a good estimate for
$\langle{Z}\rangle_{i}$. For this purpose let us first define
$\mathcal{X}_{1}$ as the set of strings $\mathbf{x}$ such that $b<Z_{j}<a$ for
all $j<n$ _and_ $Z_{n}\geq a$, and $\mathcal{X}_{0}$ as the set of strings
$\mathbf{x}$ such that $b<Z_{j}<a$ for all $j<n$ _and_ $Z_{n}\leq b$. Then,
the following relations hold:

$\displaystyle\alpha=$ $\displaystyle P_{0}(Z\geq
a)=\sum_{\mathbf{x}\in\mathcal{X}_{1}}p(\mathbf{x})\leq\sum_{\mathbf{x}\in\mathcal{X}_{1}}\frac{q(\mathbf{x})}{A}=\frac{1-\beta}{A}$
(6) $\displaystyle\beta=$ $\displaystyle P_{1}(Z\leq
b)=\sum_{\mathbf{x}\in\mathcal{X}_{0}}q(\mathbf{x})\leq\sum_{\mathbf{x}\in\mathcal{X}_{0}}p(\mathbf{x})B=(1-\alpha)B$

where in the first (second) inequality we used that
$\frac{q(\mathbf{x})}{p(\mathbf{x})}\geq A$ for strings in $\mathcal{X}_{1}$
($\frac{q(\mathbf{x})}{p(\mathbf{x})}\leq B$ for strings in
$\mathcal{X}_{2}$), and in the last equality we have used that
$\lim_{n\to\infty}P(Z_{n}\in(b,a))=0$ Wald and Wolfowitz (1948), i.e. the
walker eventually stops. The above equations are an instance of so-called
Wald’s likelihood ratio identity Lai (2004). We note that the above
inequalities can be taken to be approximate equalities if we assume that the
process ends close to the prescribed boundary, i.e. there is no
_overshooting_. In particular, this will be valid in our asymptotically small
error settings where the boundaries are far relative to the (finite) step size
$z_{k}$. This allows us to establish a one-to-one correspondence between the
thresholds $A,B$ and the type I & II errors:
$\alpha\approx\frac{1-B}{A-B}=\frac{\epsilon_{1}(\eta_{1}-\epsilon_{0})}{(1-\epsilon_{0}-\epsilon_{1})\eta_{0}}$
and
$\beta\approx\frac{B(A-1)}{A-B}=\frac{\epsilon_{0}(\eta_{0}-\epsilon_{1})}{(1-\epsilon_{0}-\epsilon_{1})\eta_{1}}$.
Gendra  _et al._ (2012); Audenaert and Eisert (2005) Neglecting the
overshooting also allows us to consider $Z$ as a stochastic variable that
takes two values $Z\in\\{a,b\\}$. Under hypothesis $H_{0}$, $a$ occurs with
probability $P_{0}(Z=a)=\alpha$ and $b$ with $P_{0}(Z=b)=1-\alpha$; while
under hypothesis $H_{1}$, $a$ and $b$ occur with probabilities
$P_{1}(Z=a)=1-\beta$ and $P_{1}(Z=b)=\beta$. So,

$\displaystyle\langle{Z}\rangle_{0}=a\alpha+b(1-\alpha)$ $\displaystyle\;{\rm
and}$ $\displaystyle\langle{Z}\rangle_{1}=a(1-\beta)+b\beta.$ (7)

Making use of (5) one can now write a closed expression for
$\langle{N}\rangle_{0}$ and $\langle{N}\rangle_{1}$ in terms of
$\epsilon_{1},\epsilon_{0}$ and the priors. A remarkable property of the SPRT
with error probabilities $\alpha$ and $\beta$ is that it minimizes _both_
$\langle{N}\rangle_{0}$ and $\langle{N}\rangle_{1}$ among all tests
(sequential or otherwise) with bounded type I and type II errors. This
optimality result due to Wald and Wolfowitz Wald and Wolfowitz (1948) allows
us to extend the above results to the asymmetric scenario. For the symmetric
scenario, the SPRT has also been shown Simons (1976) to be optimal among all
tests respecting a bounded mean error
$\bar{\epsilon}^{\prime}\leq\bar{\epsilon}$. In the asymptotic limit of small
error bounds, $\epsilon_{0},\epsilon_{1}\ll 1$, the threshold values are
$a\leavevmode\nobreak\ \sim-\log\epsilon_{1}$ and $b\leavevmode\nobreak\
\sim\log\epsilon_{0}$, which correspond to
$\alpha\sim\frac{\eta_{1}}{\eta_{0}}\epsilon_{1}$ and
$\beta\sim\frac{\eta_{0}}{\eta_{1}}\epsilon_{0}$, yielding

$\langle{N}\rangle_{0}\sim-\frac{\log\epsilon_{0}}{D(p\|q)}\;\;\mathrm{and}\;\;\langle{N}\rangle_{1}\sim-\frac{\log\epsilon_{1}}{D(q\|p)}.$
(8)

The same expressions hold at leading order in the asymmetric scenario when the
type I & II errors are vanishingly small, replacing $\log\epsilon_{1}$ and
$\log\epsilon_{0}$ by $\log\alpha$ and $\log\beta$ respectively—and in the
symmetric scenario replacing both quantities by $\log\bar{\epsilon}$. If one
of the error thresholds, say $\alpha$, is kept finite while the second is made
vanishingly small $\beta\ll 1$, $\langle{N}\rangle_{1}$ remains finite, while
the other conditional mean scales as
$\langle{N}\rangle_{0}\sim-\frac{(1-\alpha)\log\beta}{D(p\|q)}$.

In the supplemental material SM  we apply these results to the discrimination
of qubit states using projective measurements and give closed expressions for
the optimal Bayesian mean number of copies
$\langle{N}\rangle:=\eta_{0}\langle{N}\rangle_{0}+\eta_{1}\langle{N}\rangle_{1}$.
Figure 2 shows that in the symmetric setting these restricted sequential
strategies already require on average between 25-50% less resources than the
best deterministic strategy that uses a fixed number of copies $N_{\rm
Ch}\sim-\log\bar{\epsilon}/\xi_{\rm Ch}$ Calsamiglia  _et al._ (2008);
Audenaert  _et al._ (2007), and requires non-trivial collective measurements
Calsamiglia  _et al._ (2010).

Figure 2:  Left: ratio between the number of copies required by the best
deterministic strategy, $N_{\text{Ch}}$, and the Bayesian mean number of
copies for a sequential strategy based on fixed local unbiased measurements,
$\langle{N}\rangle_{\text{local}}$, for pairs of states of purity $r$ and
relative angle $\theta$ SM . Right: ratio between $N_{\text{Ch}}$ and the
worst-case $N_{\text{wc}}$, for pairs of states of different purities $r_{0}$,
$r_{1}$. The thin lines use the expression (12) for $N_{\text{wc}}$, whereas
the thick lines represent the cases for which this ultimate limit of
$N_{\text{wc}}$ is attained by a block-sampling strategy.

#### Ultimate quantum limit.

Quantum mechanics allows for much more sophisticated strategies. For a start,
performing a non-projective generalized measurement already gives important
advantages (see below). One can also adapt the measurements depending on the
previous measurement outcomes and, importantly, measurements may be weak so
that each new measurement acts on a fresh copy but also on the preceding,
already measured, copies. Without loss of generality we can assume that at
every step $k$ we perform a measurement with three outcomes
$x_{k}\in\\{0,1,2\\}$: the first two must fulfill conditions (2) and (3) and
trigger the corresponding guess ($H_{0}$ or $H_{1}$ respectively), while the
third outcome signals to continue measuring having an additional fresh copy
available. The measurement at step $k$ is characterized by a quantum
instrument
$\mathcal{M}^{k}=\\{\mathcal{M}^{k}_{0},\mathcal{M}^{k}_{1},\mathcal{M}^{k}_{2}\\}$,
and the sequential strategy is given by a sequence of instruments
$\mathcal{M}=\\{\mathcal{M}^{k}\\}_{k=1}^{\infty}$. With this, given
hypothesis $\nu=\\{0,1\\}$, the probability of getting outcome $x_{k}$ at step
$k$ can be written as

$P_{\nu}(x_{k}):={\rm
tr}[\mathcal{M}^{k}_{x_{k}}\circ\mathcal{M}^{k-1}_{2}\ldots\circ\mathcal{M}^{1}_{2}(\rho^{\otimes
k}_{\nu})]={\rm tr}(E_{x_{k}}^{k}\rho^{\otimes k}_{\nu})$ (9)

where we have used that in order to arrive to step $k$ a “continue” outcome
must be triggered in all previous steps, and in the last equality we have
defined the effective POVM $E^{k}=\\{E_{i}^{k}\\}_{i=0}^{2}$. Making use of
the indicator function $\openone_{k\leq N}$, the mean number of steps under
hypothesis $\nu$ can be computed as

$\langle{N}\rangle_{\nu}=\langle{\sum_{k=1}^{N}1}\rangle_{\nu}=\langle{\sum_{k=1}^{\infty}\openone_{k\leq
N}}\rangle_{\nu}=\langle{\sum_{n=0}^{\infty}\openone_{n<N}}\rangle_{\nu}=\sum_{n=0}^{\infty}T_{\nu}^{n}$
(10)

where $T_{\nu}^{n}=P_{\nu}(n<N)$ is the probability that the sequence does not
stop at step $n$, which from (9) is given by $T^{n}_{\nu}=P_{\nu}(x_{n}=2)$.
Optimizing $\langle{N}\rangle_{\nu}$ over all quantum sequential strategies
$\mathcal{M}$ is daunting, as all terms $T_{\nu}^{n}$ are strongly
interrelated through the intricate structure of $E^{n}$. However, a lower
bound to each $T^{n}_{\nu}$ can be found by relaxing such structure and only
imposing minimal requirements on the effective POVM; namely the error bounds
(6), positivity and completeness:

$\displaystyle\min_{E^{n}}{\rm tr}(E_{2}^{n}\rho^{\otimes n}_{\nu})\;{\rm
s.t.}\;E^{n}_{i}\geq 0,\;\sum_{i=0}^{2}E^{n}_{i}=\openone,\;\mathrm{and}$ (11)
$\displaystyle{\rm tr}[E^{n}_{1}\left(\sigma^{\otimes n}-A\rho^{\otimes
n}\right)]\geq 0,\;{\rm tr}[E^{n}_{0}\left(\rho^{\otimes
n}-B^{-1}\sigma^{\otimes n}\right)]\geq 0.$

This semi-definite program, which can be considered a two-sided version of the
quantum Neyman-Pearson test Audenaert  _et al._ (2008), is an interesting open
problem in its own right. Our focus, however, is the asymptotic regime of
small error bounds. In these asymptotic scenarios we are able to show,
exploiting some recent strong converse results in hypothesis testing Cooney
_et al._ (2016); Beigi  _et al._ (2020), that for all
$n<n^{*}=-\frac{\log\epsilon_{0}(1-A^{-1})}{D(\rho\|\sigma)}$, $T^{n}_{0}\geq
1-O(\epsilon_{0}^{\kappa})$ for some $\kappa\in(0,1)$ SM , which leads to the
desired bound:

$\langle{N}\rangle_{0}\geq\sum_{n=0}^{\lfloor
n^{*}\rfloor}T_{0}^{n}\geq-\frac{\log\epsilon_{0}(1-A^{-1})}{D(\rho\|\sigma)}+O(1)\,.$
(12)

An analogous bound holds for $\langle{N}\rangle_{1}$. The bounds for
asymmetric (symmetric) scenarios (see SM ) take the same form, replacing
$\log\epsilon_{0}$ by $\log\beta$ ($\log\bar{\epsilon}$) and $A^{-1}$ by
$\alpha$ ($\bar{\epsilon}$). In the asymmetric scenario where $\epsilon_{1}$
or $\alpha$ is kept finite, it also holds that $\langle{N}\rangle_{1}=O(1)$
and $\langle{N}\rangle_{0}$ is given by the appropriate version of (12).

#### Attainability and upper bounds.

Consider a sequential strategy that involves a fixed, collective measurement
${K}=\\{K_{i}\\}$, acting on consecutive blocks of $\ell$ copies, yielding two
possible distributions $p^{\ell}_{K},q^{\ell}_{K}$. Using the classical SPRT
we get that

$\langle{N}\rangle_{0}=\ell\inf_{K}\langle{M}\rangle_{0}\sim\ell\inf_{K}\frac{-\log\epsilon_{0}}{D(p^{\ell}_{K}\|q^{\ell}_{K})}\sim\frac{-\log\epsilon_{0}}{D(\rho\|\sigma)}$
(13)

where $M$ is the number of blocks used at the stopping time. In the last
relation of (13) we have used the fact that we are in the asymptotic setting
where $\epsilon_{0}\ll 1$ and therefore we can take arbitrarily long block
lengths $\ell\gg 1$. We also exploit the following property of the measured
relative entropy Hiai and Petz (1991); Hayashi (2001):
$\sup_{K}D(q^{\ell}_{K}\|p^{\ell}_{K})\sim\ell D(\sigma\|\rho)$.

Notice, however, that for arbitrary states $\rho$ and $\sigma$ block sampling
can attain either $\langle{N}\rangle_{0}$ or $\langle{N}\rangle_{1}$, but it
is unknown whether one can attain in general both bounds simultaneously, i.e.,
whether a measurement achieving the supremum of
$\lim_{\ell\to\infty}\tfrac{1}{\ell}D(q^{\ell}_{K}\|p^{\ell}_{K})$ can also
attain the supremum of
$\lim_{\ell\to\infty}\tfrac{1}{\ell}D(p^{\ell}_{K}\|q^{\ell}_{K})$. For
instance, if we wish to optimize the Bayesian mean number of copies
$\langle{N}\rangle$, we can use block sampling to attain

$\langle{N}\rangle_{\mathrm{block}}\sim\lim_{\ell\to\infty}\inf_{K}\left(\frac{-\ell\eta_{0}\log\epsilon_{0}}{D(p_{K}^{\ell}\|q_{K}^{\ell})}-\frac{\ell\eta_{1}\log\epsilon_{1}}{D(q_{K}^{\ell}\|p_{K}^{\ell})}\right).$
(14)

However, this strategy might be sub-optimal and hence it only provides an
upper bound to the optimal Bayesian mean
$\langle{N}\rangle\leq\langle{N}\rangle_{\mathrm{block}}$. This
notwithstanding, there are at least two cases when this upper bound coincides
with the lower bound provided by (12): when $\rho$ and $\sigma$ commute, and
when the two states do not have common support. If, say,
$\operatorname{supp}(\sigma)\cap\operatorname{ker}(\rho)\neq 0$, one can use
block-sampling to attain (12) for $\langle{N}\rangle_{0}$ and always detect
$\rho$ with a finite number of copies—note that since
$D(\sigma\|\rho)=\infty$, the lower bound $\langle{N}\rangle_{1}=O(1)$ is also
attained.

We can also give achievable lower bounds for a worst-case type figure of merit
${N}_{\rm wc}:=\max\\{\langle{N}\rangle_{0},\langle{N}\rangle_{1}\\}$. If,
say, $\langle{N}\rangle_{0}>\langle{N}\rangle_{1}$, then in SM  we give some
instances of qubit pairs where a specific block-sampling strategy Hayashi
(2001) saturates (12) for $\langle{N}\rangle_{0}$, while at the same time
$\lim_{\ell\to\infty}\tfrac{1}{\ell}D(q_{K}^{\ell}\|p_{K}^{\ell})\geq
D(\rho\|\sigma)$, and hence (12) provides the ultimate attainable limit for
${N}_{\rm wc}$. In Fig. 2 we compare ${N}_{\rm wc}$ with $N_{\text{Ch}}$ for
several pairs of states, highlighting the achievable cases, and show a
consistent advantage of sequential protocols over deterministic ones 222Note
that the comparison with $N_{\text{Ch}}$ is unfavorable to sequential
strategies. Substituting $\epsilon_{0}$ and $\epsilon_{1}$ by $\bar{\epsilon}$
in Eq. (12) implies that _each_ type of error is independently constrained,
whereas $N_{\text{Ch}}$ refers to a deterministic (symmetric) protocol where
the _mean_ error is $\bar{\epsilon}$ and thus to a weaker version of the
problem. In spite of this, the sequential scenario displays a significant
advantage..

Finally, we note that, in an asymmetric scenario where $\langle{N}\rangle_{1}$
is finite and the value of $\langle{N}\rangle_{0}$ achieves the lower bound
(12), sequential protocols provide a strict advantage over Stein’s limit for
deterministic protocols by a factor $(1-\alpha)$.

#### The curious case of pure states.

If the two states are pure, the behavior of $\langle{N}\rangle_{\nu}$ changes
drastically: it is possible to reach a decision with guaranteed zero error
using a finite average number of copies. To see this, consider again Eq. (18).
Under a zero-error condition, the minimal (unrestricted) $T_{\nu}^{n}$ is
achieved by a global _unambiguous_ three-outcome POVM Ivanovic (1987); Dieks
(1988); Peres (1988) on $n$ copies, which identifies the true state with zero
error when the first or the second outcome occurs —at the expense of having a
third, inconclusive outcome. For a single-copy POVM over pure states, the
probabilities $c_{\nu}$ of the inconclusive outcome under $H_{\nu}$ are
subject to the tradeoff relation $c_{0}c_{1}\geq{\rm tr}\rho\sigma$ Sentís
_et al._ (2018), where equality can always be attained by suitable POVM that
maximizes the probability of a successful identification. Likewise, for a
global measurement on $n$ copies we have $T_{0}^{n}T_{1}^{n}\geq({\rm
tr}\rho\sigma)^{n}$. Now, it is evident that a sequence of $n$ locally optimal
unambiguous POVMs applied on every copy, for which $T_{\nu}^{n}=c_{\nu}^{n}$,
also fulfills the global optimality condition. Hence, we have

$\langle{N}\rangle_{\nu}\geq\sum_{n=0}^{\infty}T_{\nu}^{n}=\sum_{n=0}^{\infty}c_{\nu}^{n}=\frac{1}{1-c_{\nu}}=:\langle{N}\rangle_{\nu}^{\rm
local}\,.$ (15)

This shows that, for pure states, it suffices to perform local unambiguous
measurements to attain the optimal (finite) average number of copies with zero
error under hypothesis $H_{\nu}$. Note that because of the tradeoff
$c_{0}c_{1}\geq{\rm tr}\rho\sigma$ one cannot attain the minimal values of
$\langle{N}\rangle_{0}^{\rm local}$ and $\langle{N}\rangle_{1}^{\rm local}$
for general states $\rho,\sigma$, simultaneously. For instance, one can reach
the minimal value $c_{0}={\rm tr}(\rho\sigma)$ for one hypothesis, but then
having a maximal value $c_{1}=1$ for the second; or choose the optimal
symmetric setting, $c_{0}=c_{1}=\sqrt{{\rm tr}\rho\sigma}$, that achieves the
minimum value of both the worst-case $N_{\mathrm{w}c}$ and the Bayesian mean
$\langle{N}\rangle$ with equal priors (see SM ). This is in stark contrast
with the behavior found in Slussarenko  _et al._ (2017), where all strategies
considered were based on two-outcome projective measurements, for which the
average number of copies scaled as $\langle{N}\rangle\propto-\log\epsilon$.

#### Acknowledgments.

We acknowledge financial support from the Spanish Agencia Estatal de
Investigación, project PID2019-107609GB-I00, from Secretaria d’Universitats i
Recerca del Departament d’Empresa i Coneixement de la Generalitat de
Catalunya, co-funded by the European Union Regional Development Fund within
the ERDF Operational Program of Catalunya (project QuantumCat, ref.
001-P-001644), and Generalitat de Catalunya CIRIT 2017-SGR-1127. CH
acknowledge financial support from the European Research Council (ERC Grant
Agreement No. 81876), VILLUM FONDEN via the QMATH Centre of Excellence (Grant
No.10059) and the QuantERA ERA-NET Cofund in Quantum Technologies implemented
within the European Union Horizon 2020 Programme (QuantAlgo project) via
Innovation Fund Denmark, JC acknowledges from the QuantERA grant C’MON-QSENS!,
via Spanish MICINN PCI2019-111869-2, EMV thanks financial support from
CONACYT. JC also acknowledges support from ICREA Academia award.

## References

  * Lehmann and Casella (2006) E. L. Lehmann and G. Casella,  _Theory of point estimation_ , 2nd ed. (Springer Science & Business Media, 2006).
  * Helstrom (1976) C. W. Helstrom,  _Quantum Detection and Estimation Theory_ (Academic Press, 1976).
  * Tartakovsky  _et al._ (2014) A. G. Tartakovsky, I. V. Nikiforov, and M. Basseville,  _Sequential Analysis: hypothesis testing and changepoint detection_, edited by F. Bunea, V. Isham, N. Keiding, T. Louis, R. L. Smith, and H. Tong (CRC Press, Taylor and Francis, 2014).
  * Sentís  _et al._ (2016) G. Sentís, E. Bagan, J. Calsamiglia, G. Chiribella, and R. Muñoz Tapia, Phys. Rev. Lett. 117, 150502 (2016).
  * Sentís  _et al._ (2017) G. Sentís, J. Calsamiglia, and R. Muñoz Tapia, Phys. Rev. Lett. 119, 140506 (2017).
  * Sentís  _et al._ (2018) G. Sentís, E. Martínez-Vargas, and R. Muñoz Tapia, Phys. Rev. A 98, 052305 (2018).
  * Wald (1973) A. Wald,  _Sequential Analysis_, Dover books on advanced mathematics (Dover Publications, 1973).
  * Leung Lai (2001) T. Leung Lai, Statistica Sinica 11, 303 (2001).
  * Bae and Kwek (2015) J. Bae and L.-C. Kwek, Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
  * Slussarenko  _et al._ (2017) S. Slussarenko, M. M. Weston, J.-G. Li, N. Campbell, H. M. Wiseman, and G. J. Pryde, Physical Review Letters 118, 030502 (2017).
  * Note (1) By $f(\epsilon)\sim g(\epsilon)$ we mean asymptotic equivalence $\mathop{lim}\displaylimits_{\epsilon\to 0}f(\epsilon)/g(\epsilon)=1$.
  * Audenaert  _et al._ (2007) K. M. R. Audenaert, J. Calsamiglia, R. Muñoz-Tapia, E. Bagan, L. Masanes, A. Acín, and F. Verstraete, Physical Review Letters 98, 160501 (2007).
  * Nussbaum and Szkoła (2009) M. Nussbaum and A. Szkoła, Annals of Statistics 37, 1040 (2009).
  * Hiai and Petz (1991) F. Hiai and D. Petz, Communications in Mathematical Physics 143, 99 (1991).
  * Ogawa and Nagaoka (2000) T. Ogawa and H. Nagaoka, IEEE Transactions on Information Theory 46, 2428 (2000).
  * Hayashi (2007) M. Hayashi, Physical Review A 76, 062301 (2007).
  * Nagaoka (2006) H. Nagaoka, arXiv:quant-ph/0611289 (2006).
  * Wilde (2017) M. M. Wilde,  _Quantum Information Theory_ , 2nd ed. (Cambridge University Press, 2017).
  * Lloyd (2008) S. Lloyd, Science 321, 1463 (2008).
  * Audenaert  _et al._ (2008) K. M. R. Audenaert, M. Nussbaum, A. Szkola, and F. Verstraete, Communications in Mathematical Physics 279, 251 (2008).
  * Calsamiglia  _et al._ (2008) J. Calsamiglia, R. Muñoz-Tapia, L. Masanes, A. Acin, and E. Bagan, Physical Review A 77, 032311 (2008).
  * Berta  _et al._ (2017) M. Berta, F. G. Brandao, and C. Hirche, arXiv:1709.07268 (2017).
  * Wald and Wolfowitz (1948) A. Wald and J. Wolfowitz, The Annals of Mathematical Statistics 19, 326 (1948).
  * Mitzenmacher and Upfal (2005) M. Mitzenmacher and E. Upfal,  _Probability and Computing: Randomized Algorithms and Probabilistic Analysis_ (Cambridge University Press, 2005).
  * Lai (2004) T. L. Lai, Sequential Analysis 23, 467 (2004).
  * Simons (1976) G. Simons, The Annals of Statistics 4, 1240 (1976).
  * (27) See Supplemental Material [url] where we provide the proof of the lower bound for the mean number of copies under each hypothesis, we apply our general results to the case of qubit states, we compute the exact optimal mean number of copies (worst-case and Bayesian) required for the perfect discrimination of pure states, and which includes Mosonyi and Ogawa (2015); Müller-Lennert  _et al._ (2013); Wilde  _et al._ (2014); Beigi  _et al._ (2020); Acín  _et al._ (2005); Gendra  _et al._ (2012); Audenaert and Eisert (2005).
  * Mosonyi and Ogawa (2015) M. Mosonyi and T. Ogawa, Communications in Mathematical Physics 334, 1617 (2015).
  * Müller-Lennert  _et al._ (2013) M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, Journal of Mathematical Physics 54, 122203 (2013).
  * Wilde  _et al._ (2014) M. M. Wilde, A. Winter, and D. Yang, Communications in Mathematical Physics 331, 593 (2014).
  * Beigi  _et al._ (2020) S. Beigi, N. Datta, and C. Rouzé, Communications in Mathematical Physics 376, 753 (2020).
  * Acín  _et al._ (2005) A. Acín, E. Bagan, M. Baig, L. Masanes, and R. Muñoz-Tapia, Physical Review A 71, 032338 (2005).
  * Gendra  _et al._ (2012) B. Gendra, E. Ronco-Bonvehi, J. Calsamiglia, R. Muñoz-Tapia, and E. Bagan, New Journal of Physics 14, 105015 (2012).
  * Audenaert and Eisert (2005) K. M. Audenaert and J. Eisert, Journal of Mathematical Physics 46, 102104 (2005).
  * Calsamiglia  _et al._ (2010) J. Calsamiglia, J. I. de Vicente, R. Muñoz-Tapia, and E. Bagan, Physical Review Letters 105, 080504 (2010).
  * Cooney  _et al._ (2016) T. Cooney, M. Mosonyi, and M. M. Wilde, Communications in Mathematical Physics 344, 797 (2016).
  * Hayashi (2001) M. Hayashi, Journal of Physics A: Mathematical and General 34, 3413 (2001).
  * Note (2) Note that the comparison with $N_{\text{Ch}}$ is unfavorable to sequential strategies. Substituting $\epsilon_{0}$ and $\epsilon_{1}$ by $\mathaccentV{bar}016{\epsilon}$ in Eq. (12) implies that _each_ type of error is independently constrained, whereas $N_{\text{Ch}}$ refers to a deterministic (symmetric) protocol where the _mean_ error is $\mathaccentV{bar}016{\epsilon}$ and thus to a weaker version of the problem. In spite of this, the sequential scenario displays a significant advantage.
  * Ivanovic (1987) I. Ivanovic, Physics Letters A 123, 257 (1987).
  * Dieks (1988) D. Dieks, Physics Letters A 126, 303 (1988).
  * Peres (1988) A. Peres, Physics Letters A 128, 19 (1988).

##  I Supplemental Material

This supplemental material contains some technical details as well as some
extensions for the interested reader. In Sec. II we state and prove a theorem
that provides the lower bounds for the average number of copies, Eq. (12) in
the main text. In Sec. III explicit expressions for the optimal sequential
test and attainability regions of the worst case bound are provided for the
qubit case. In Sec. IV we present a second theorem that provides a general
lower bound for the deviation of the measured entropy from its maximum value
for arbitrary finite dimensions. Finally, in Sec. V we give the optimality
proof for the zero-error protocol for pure states.

##  II Converse proof

Our aim here is to prove that if one of the two error bounds is vanishingly
small, say $\epsilon_{0}\ll 1$ under the strong error condition, or $\beta\ll
1$ in the asymmetric scenario (see main text for the definitions), then the
mean number of copies under hypothesis $H_{0}$ is always lower-bounded by

$\displaystyle\langle{N}\rangle_{0}$ $\displaystyle\geq\sum_{n=0}^{\lfloor
n^{*}\rfloor}T_{0}^{n}\geq-\frac{\log\epsilon_{0}(1-1/A)}{D(\rho\|\sigma)}+O(1)\,\quad\mbox{
or }$ (16) $\displaystyle\langle{N}\rangle_{0}$
$\displaystyle\geq\sum_{n=0}^{\lfloor
n^{*}\rfloor}T_{0}^{n}\geq-\frac{\log\beta(1-\alpha)}{D(\rho\|\sigma)}+O(1)\,,$
(17)

respectively. Analogous bounds also hold for $\langle{N}\rangle_{1}$ when
$\epsilon\ll 1$ or $\alpha\ll 1$, replacing
$\epsilon_{0}\leftrightarrow\epsilon_{1}$, $A\leftrightarrow B$,
$\alpha\leftrightarrow\beta$, and $\rho\leftrightarrow\sigma$. We will first
provide the proof for the strong error condition and indicate how to adapt it
to the other hypothesis testing scenarios considered here.

In the main text (MT) we have shown that under hypothesis $H_{0}$ the mean
number of sampled copies is given by

$\langle{N}\rangle_{0}=\sum_{n=0}^{\infty}T_{0}^{n}\geq\sum_{n=0}^{n^{*}}T_{0}^{n}\,,$
(18)

where the last inequality holds for all values of $n^{*}$ since $T_{0}^{n}\geq
0$. The $n$th term in sum, $T_{0}^{n}=P_{0}(n<N)$, is the probability of
getting a “continue” outcome at step $n$, corresponding to the POVM element
$E_{2}^{n}$ implicitly defined in (12) in MT. The continue probability at a
particular step $n$ obeys a lower bound given by the following semidefinite
program (SDP)

$T_{0}^{n}\geq\tilde{T}_{0}^{n}:=\min_{E^{n}}{\rm tr}(E_{2}^{n}\rho^{\otimes
n}_{\nu})\;{\rm
s.t.}\left\\{\begin{array}[]{ll}&\mathrm{0)}\quad\\{E^{n}_{i}\geq
0\\}_{i=0}^{2}\;\mathrm{and}\sum_{i=0}^{2}E^{n}_{i}=\openone\\\ \\\
&\mathrm{1)}\quad{\rm tr}[E^{n}_{1}\left(\sigma^{\otimes n}-A\rho^{\otimes
n}\right)]\geq 0\\\ \\\ &\mathrm{2)}\quad{\rm tr}[E^{n}_{0}\left(\rho^{\otimes
n}-B^{-1}\sigma^{\otimes n}\right)]\geq 0\end{array}\right..$ (19)

The conditions in 0) have to hold for any valid POVM, while the second and
third conditions are an alternative way of writing the strong errors
conditions, (1) and (2) in the MT, as SDP constrains. For small error bounds
$\epsilon_{0}\ll 1$ (i.e.
$A=\frac{\eta_{0}}{\eta_{1}}\frac{1-\epsilon_{1}}{\epsilon_{1}}\gg 0$) the
solution of the SDP program in (19) has a characteristic dependence on $n$ as
illustrated in Figure 3.

Figure 3: Lower bound $\tilde{T}_{0}^{n}$ on the continue probability as a
function of the step number $n$ for: (Left) two qubits of equal purity $r=0.9$
and relative angle $\theta=\pi/4$, for error bounds
$\epsilon_{0}=\\{10^{-3},10^{-4},10^{-5},10^{-6}\\}$ (from bottom to top,
looking at the left side of the figure); (Right) two commuting qubits with
$r=0.5$ and $\theta=\pi$, for
$\epsilon_{0}=\\{10^{-8},10^{-12},10^{-14},10^{-16},10^{-20}\\}$ (from bottom
to top, looking at the left side of the figure). The values on the left plot
have been obtained by numerically solving the SDP program of (19), exploiting
the block-diagonal structure of iid quantum states $\rho^{\otimes n}$ and
$\sigma^{\otimes n}$ (see Section III).

When the number of sampled copies $n$ is small it is not possible to meet the
low error bound and the probability of getting a “continue” outcome is
$T_{0}^{n}=1$. This probability remains constant as $n$ increases until it
approaches the critical point $n^{*}\sim\log(1/\epsilon)/D(\rho\|\sigma)$, at
which point it rapidly drops to zero. Note that this drop becomes more abrupt
as $\epsilon_{0}$ decreases. These observations suggest that
$\sum_{n=0}^{n^{*}}\tilde{T}^{n}_{0}$ is a very tight lower bound to
$\sum_{n=0}^{\infty}\tilde{T}^{n}_{0}$ (area under the curve in Figure 3) and
is given to a very good approximation by
$\sum_{n=0}^{n^{*}}\tilde{T}^{n}_{0}\approx n^{*}$.

With this at hand we can now carry on with the formal presentation and proof
of the lower bound.

######  Theorem 1.

Given two finite-dimensional states, $\rho$ ($H_{0}$) and $\sigma$ ($H_{1}$),
occurring with prior probabilities $\eta_{0}$ and $\eta_{1}$ respectively, the
most general quantum sequential strategy that satisfies the strong error
conditions $P(H_{0}|x_{N}=0)\geq 1-\epsilon_{0}$ and $P(H_{1}|x_{N}=1)\geq
1-\epsilon_{1}$, where $x_{N}\in\\{0,1\\}$ is the output of the measurement at
the stopping time $N$, necessarily fulfills the following asymptotic lower
bound for the mean number of sampled copies when $\epsilon_{0}\ll 1$:

$\langle{N}\rangle_{0}\geq-\frac{(1-A^{-1})\log\epsilon_{0}}{D(\rho\|\sigma)}+O(1)\,,\quad\mbox{
where }\quad\,A=\frac{\eta_{0}}{\eta_{1}}\frac{1-\epsilon_{1}}{\epsilon_{1}}.$
(20)

Similarly, the most general quantum sequential strategy that satisfies the
(weak) error conditions $P(\hat{H}_{1}|\rho)\leq\alpha$ and
$P(\hat{H}_{0}|\sigma)\leq\beta$, where $\hat{H}_{0}$ and $\hat{H}_{1}$ are
the events of accepting hypothesis 0 and 1 respectively, necessarily fulfills
the following asymptotic lower bound for the mean number of sampled copies
when $\beta\ll 1$:

$\langle{N}\rangle_{0}\geq-\frac{(1-\alpha)\log\beta}{D(\rho\|\sigma)}+O(1)\,.$
(21)

###### Proof.

We start by noting that the strong error conditions [see (19)] imply

$\displaystyle{\rm tr}(E^{n}_{1}\rho^{\otimes n})$ $\displaystyle\leq$
$\displaystyle\frac{1}{A}{\rm tr}(E^{n}_{1}\sigma^{\otimes
n})\leq\frac{1}{A}=\frac{\eta_{1}}{\eta_{0}}\frac{\epsilon_{1}}{1-\epsilon_{1}}\,,$
(22) $\displaystyle{\rm tr}(E^{n}_{0}\sigma^{\otimes n})$ $\displaystyle\leq$
$\displaystyle\frac{1}{B}{\rm tr}(E^{n}_{0}\rho^{\otimes
n})\leq\frac{1}{B}=\frac{\eta_{0}}{\eta_{1}}\frac{\epsilon_{0}}{1-\epsilon_{0}}\,.$
(23)

Next we form a two-outcome POVM by binning two outcomes of the effective POVM
at step $n$, as defined in (12) in MT,
$F^{n}=\\{F^{n}_{0}=E^{n}_{0},{F}^{n}_{1}:=E^{n}_{1}+E^{n}_{2}\\}$. This
measurement can be used to discriminate between $\rho^{\otimes n}$ and
$\sigma^{\otimes n}$ and the associated type-I and type-II errors will be
denoted by $\tilde{\alpha}_{n}=\operatorname{Tr}[F^{n}_{1}\rho^{\otimes n}]$
and $\tilde{\beta}_{n}=\operatorname{Tr}[F^{n}_{0}\sigma^{\otimes n}]$. From
(23) and the above definitions it follows that
$\tilde{\beta}_{n}\leq\frac{\eta_{0}}{\eta_{1}}\epsilon_{0}+O(\epsilon_{0}^{2})$.
In addition, using (23) we find that the probability of continuing at step $n$
when $H_{0}$ holds satisfies

$T_{0}^{n}={\rm tr}[E^{n}_{2}\rho^{\otimes n}]=\tilde{\alpha}_{n}-{\rm
tr}[E^{n}_{1}\rho^{\otimes n}]\geq\tilde{\alpha}_{n}-\frac{1}{A}\,.$ (24)

Now we use Lemma 1 stated below, which uses the recently developed methods for
strong converse exponents Cooney  _et al._ (2016) in order to establish a
lower bound on $\tilde{\alpha}_{n}$ when the type-II error $\tilde{\beta}_{n}$
is bounded by $\epsilon$ and when $n$ is below a critical threshold $n^{*}$.
In particular, applying Lemma 1 to the test defined by $F_{n}$ above, with
type-I & II errors $\tilde{\alpha}_{n}$ and
$\tilde{\beta}_{n}\leq\frac{\eta_{0}}{\eta_{1}}\epsilon_{0}+O(\epsilon_{0}^{2})=:\epsilon$,
we have that (24) reads

$T^{n}_{0}\geq\tilde{\alpha}_{n}-\frac{1}{A}\geq
1-\epsilon^{\kappa_{n}(\rho,\sigma)}-\frac{1}{A}\quad\forall\;n<n^{*}\,,$ (25)

where $\kappa_{n}(\rho,\sigma)>0$. The proof for the strong error conditions
ends by inserting this lower bound in (18).

For the weak form of error bounds one can follow the same steps as above by
writing the type-I and type-II errors of the sequential strategy as
$P(\hat{H}_{1}|\rho)=\sum_{k=1}^{\infty}\tilde{\alpha}_{n}$ and
$P(\hat{H}_{0}|\sigma)=\sum_{k=1}^{\infty}\tilde{\beta}_{n}$. Since
$\tilde{\beta}_{n}\geq 0$, the error bound $P(\hat{H}_{0}|\sigma)\leq\beta$
translates to $\tilde{\beta}_{n}\leq\beta$, and similarly
$\tilde{\alpha}_{n}\leq\alpha$. The former is directly of the form required
for Lemma 1, while the latter can be used instead of (22), i.e., ${\rm
tr}(E^{n}_{1}\rho^{\otimes n})=\alpha_{n}\leq\alpha$, hence $A$ in (20)
becomes $\alpha$ in (21).

∎

######  Lemma 1.

Let $\rho$ and $\sigma$ be finite-dimensional density operators associated to
hypotheses $H_{0}$ and $H_{1}$, respectively. For any quantum hypothesis
testing strategy that uses $n$ copies of the states and that respects the
type-II error bound $\beta_{n}\leq\epsilon$, with $\epsilon\ll 1$, the type-I
error will converge to one at least as

$\alpha_{n}\geq 1-\epsilon^{\kappa_{n}(\rho,\sigma)}\quad\mbox{for all}\quad
n<n^{*}=\frac{-\log\epsilon}{D(\rho\|\sigma)}\,,$ (26)

where $0<\kappa_{n}(\rho,\sigma)<1$ is given by

$\kappa_{n}(\rho,\sigma)=\sup_{s>1}\frac{s-1}{s}\frac{\xi_{n}-\tilde{D}_{s}(\rho\|\sigma)}{\xi_{n}}=\frac{H(\xi_{n})}{\xi_{n}}\,,\quad\mathrm{with}\quad\xi_{n}=-\frac{\log\epsilon}{n}>-\frac{\log\epsilon}{n^{*}}=D(\rho\|\sigma)\,,$
(27)

where $H(\xi_{n})$ is the strong converse exponent (Mosonyi and Ogawa, 2015)
and where the sandwiched Renyi relative entropy Müller-Lennert  _et al._
(2013); Wilde  _et al._ (2014) is given by

$\tilde{D}_{s}(\rho\|\sigma)=\frac{1}{s-1}\log{\rm
tr}\\!\left(\sigma^{\frac{1-s}{2s}}\rho\sigma^{\frac{1-s}{2s}}\right)^{s}\,,$
(28)

taking $\tilde{D}_{s}(\rho\|\sigma)=\infty$ when
$\operatorname{supp}\rho\not\subseteq\operatorname{supp}\sigma$.

###### Proof.

The proof makes use of the following strong converse result by Mosonyi and
Ogawa Mosonyi and Ogawa (2015) that relates the type I and type II errors for
an arbitary $n$ by means of the sandwiched Renyi relative entropy:

$\frac{1}{n}\log(1-{\alpha_{n}})\leq\frac{s-1}{s}(\tilde{D}_{s}(\rho\|\sigma)+\frac{1}{n}\log\beta_{n}),\leavevmode\nobreak\
\leavevmode\nobreak\ s>1\,.$ (29)

Note that in order to avoid confusion with the type-I error, here we use $s$
instead of the traditional $\alpha$ used in the Renyi entropies. Among the
number of properties that make the sandwiched Renyi relative entropy such a
formidable quantity, here we will use two: i) it increases monotonically with
$s$, and ii) $\lim_{s\to 1}\tilde{D}_{s}(\rho\|\sigma)=D(\rho\|\sigma)$.

Since $\beta_{n}\leq\epsilon$,

$1-{\alpha_{n}}\leq{\rm
e}^{n\frac{s-1}{s}(\tilde{D}_{s}(\rho\|\sigma)+\frac{1}{n}\log\epsilon)}\,.$
(30)

Observe that $\forall n<n^{*}$ we can define $\xi_{n}>D(\rho\|\sigma)$ such
that

$n=-\frac{\log\epsilon}{\xi_{n}}\,.$ (31)

Using this parametrization of $n$ in (30), we have

${\alpha_{n}}\geq
1-\epsilon^{\frac{s-1}{s}\frac{\xi_{n}-\tilde{D}_{s}(\rho\|\sigma)}{\xi_{n}}}\,.$
(32)

Hence, if we define the supremum of the exponent

$\kappa_{n}(\rho,\sigma):=\sup_{s>1}\frac{s-1}{s}\frac{\xi_{n}-\tilde{D}_{s}(\rho\|\sigma)}{\xi_{n}}\,,\quad\mathrm{with}\quad\xi_{n}=-\frac{\log\epsilon}{n}>-\frac{\log\epsilon}{n^{*}}=D(\rho\|\sigma)\,,$
(33)

we arrive to the desired result

$\alpha_{n}\geq 1-\epsilon^{\kappa_{n}(\rho,\sigma)}\leavevmode\nobreak\
\quad\forall\leavevmode\nobreak\ n<n^{*}\,.$ (34)

Taking into account that $0<\frac{s-1}{s}=1-\frac{1}{s}<1$ for all $s>1$, that
$\xi_{n}>D(\rho\|\sigma)$ for $n<n^{*}$, and from conditions i) and ii) above
that $\tilde{D}_{s}(\rho\|\sigma)>D(\rho\|\sigma)$, it follows that there will
always be an $s^{\prime}$ realizing the supremum in (33) such that
$\xi_{n}>\tilde{D}_{s^{\prime}}(\rho\|\sigma)$, and therefore
$0<\kappa_{n}(\rho,\sigma)<1$. ∎

An alternative way to arrive to the result in Lemma 1 is provided in Beigi et
al. Beigi  _et al._ (2020) where, using quantum reverse hypercontractivity, a
second order strong converse result on hypothesis testing is derived.

We finally note that Lemma 1 assures that, below $n^{*}$, the continue
probability is $T^{n}\sim 1$. On the other hand, from Stein’s Lemma we know
that, for fixed (large) $n$, the optimal type-II error rate is given by the
relative entropy, i.e., $\beta_{n}\sim{\rm e}^{-nD(\rho\|\sigma)}$. This
explains why one does not need to continue measuring after
$n>n^{*}=-\log\epsilon/D(\rho\|\sigma)$, and $T^{n>n^{*}}\sim 0$ (see Fig. 3),
and why we may expect the lower bound to be tight, in the sense that we are
not dropping significant contributions by truncanting the sum in (18). Of
course, this still does not imply the attainability of the lower bound, and
even less the simultaneous attainability of the bound for
$\langle{N}\rangle_{0}$ and the analogous bound for $\langle{N}\rangle_{1}$.

##  III Sequential hypothesis testing for Qubits

In this section we study the discrimination of qubit states using sequential
methodologies, deriving explicit formulae for the mean number of copies using
different measurement strategies.

###  III.1 Optimal sequential test for fixed projective measurements

We will first study the optimal performance under the simplest type of
measurement apparatus, i.e. a fixed Stern-Gerlach-type measurement. The main
purpose of this section is to show that using sequential strategies a simple
projective measurement can determine the correct hypothesis with guaranteed
bounded error requiring an expected number of copies significantly lower than
the most general collective measurement acting on a fixed number of copies. In
addition, we provide closed expressions for the optimal asymptotic
performance.

Without loss of generality we characterize the two hypotheses by

$\begin{split}\rho&=r_{0}\left|{\psi_{0}}\rangle\\!\langle{\psi_{0}}\right|+(1-r_{0})\openone/2\\\
\sigma&=r_{1}\left|{\psi_{1}}\rangle\\!\langle{\psi_{1}}\right|+(1-r_{1})\openone/2\,,\end{split}$
(35)

where
$\left|{\psi_{i}}\right\rangle=\cos\frac{\theta}{4}\left|{0}\right\rangle+(-1)^{i}\sin\frac{\theta}{4}\left|{1}\right\rangle$,
$0\leq\theta\leq\pi$, $0\leq r_{i}\leq 1$ and the (fixed) local measurement as
$E_{0}=\left|{\phi}\rangle\\!\langle{\phi}\right|$ and $E_{1}=\openone-E_{0}$,
with
$\left|{\phi}\right\rangle=\cos{\frac{\phi}{2}}\left|{0}\right\rangle+\sin{\frac{\phi}{2}}\left|{1}\right\rangle$,
and $0\leq\phi\leq\pi$. With these parametrizations, the probabilities of
obtaining outcome $i=0,1$ are
$p_{\phi}(i)=P(i|H_{0})=\frac{1}{2}[1+(-1)^{i}\cos({\theta/2-\phi})]$ and
$q_{\phi}(i)=P(i|H_{1})=\frac{1}{2}[1+(-1)^{i}\cos({\theta/2+\phi})]$,
depending on which hypothesis is true. For simplicity we take equal priors
$\eta_{0}=\eta_{1}=1/2$ and study the Bayesian mean number of copies under the
same strong error bounds $\epsilon_{0}=\epsilon_{1}=\epsilon\ll 1$. In the
main text we show that the optimal test for a given choice of measurement
angle is given by Wald’s SPRT strategy, which according to (11) in MT leads to

$\langle{N}\rangle=\eta_{0}\langle{N}\rangle_{0}+\eta_{1}\langle{N}\rangle_{1}\sim-\frac{1}{2}\log\epsilon\left(\frac{1}{D(p_{\phi}\|q_{\phi})}+\frac{1}{D(q_{\phi}\|p_{\phi})}\right)\,.$
(36)

Figure 4: Bayesian mean number of copies $\langle{N}\rangle$ as a function of
the measurement angle $\phi$ for different pairs of pure states: from bottom
to top
$\theta=\\{\pi,\frac{\pi}{2},\frac{\pi}{3},\frac{\pi}{4},\frac{\pi}{5}\\}$.
The vertical lines show the corresponding optimal measurement angles
$\phi=\theta/2$. The inset shows in more detail the case with
$\theta=\frac{\pi}{8}$, including the curves for noisy states with
$1-r=\\{10^{-2},10^{-3},10^{-4}\\}$ (dashed lines, from top to bottom).

In Figure 4 we show the Bayesian mean number of copies required to have a
guaranteed, asymptotically small bounded error $\epsilon$ for all outcomes of
the experiment. For pure states ($r=1$), we observe that the optimal angle is
a singular point located at $\phi=\theta/2$, that corresponds to the fully
biased measurement for which outcome 1 can only occur under hypothesis
$H_{1}:p(1|H_{0})=0$ while $p(1|H_{1})=\cos^{2}(\theta/2)>0$. Hence, $H_{1}$
is detected with certainty after a small number of steps
$\langle{N}\rangle_{1}\sim\cos^{-2}(\theta/2)$ (independent of the error bound
$\epsilon$), and therefore the leading contribution to the expected number of
copies when hypothesis $H_{0}$ is true is

$\langle{N}\rangle_{\text{local}}\sim\frac{\log\epsilon}{2\log(\cos^{2}\\!\frac{\theta}{2})}\,.$
(37)

Note that this is exactly half of the number of copies that the most general
collective deterministic strategy would require to attain this error bound,
since
$\epsilon=\frac{1}{2}(1-\sqrt{1-\cos^{2N}(\theta/2)})\sim\cos^{2N}(\theta/2)$.
This error bound can be attained with local adaptive measurements for finite
$N$ Acín  _et al._ (2005) and fixed local measurements for asymptotically
large $N$. The result in (37) is in agreement with that derived in Slussarenko
_et al._ (2017) for the fully biased strategy, which we have shown to be
optimal in the limit of small error bounds (among fixed local measurement
strategies). In Figure 4 we also note that a small change around the optimal
value $\phi=\theta/2$ produces a very rapid increase of the effective number
of copies while the local minimum at $\phi=\pi/2$, which corresponds to the
fully unbiased measurement, is much more shallow and hence more robust to a
possible measurement misalignment.

We now proceed to study what happens in the presence of noise, when both
states are mixed, in particular when $r_{0}=r_{1}=r$. As shown in the inset of
Figure 4, the presence of noise makes the two states more indistinguishable
and a higher number of samples are required to meet the error bound. It is
also apparent that in presence of noise the fully unbiased measurement,
$\phi=\pi/2$, becomes optimal (except for extremely high values of the purity
$1-r\sim 10^{-5}$ for which fully biased performs slightly better). The
unbiased measurement is straightforward to compute:

$\langle{N}\rangle_{\mathrm{local}}\sim\frac{\log\epsilon}{r\sin\theta\log\left(\frac{1-r\sin\frac{\theta}{2}}{1+r\sin\frac{\theta}{2}}\right)}\,.$
(38)

We can again compare $\langle{N}\rangle$ reached by the local measurements
(38)with the sample size, $N$, required by the optimal deterministic protocol
using a predetermined number of copies to achieve the same error $\epsilon$.
When $N$ is large, i.e. $\epsilon$ is small, this can be obtained from the
asymptotic error exponent in the quantum Chernoff bound Calsamiglia  _et al._
(2008); Audenaert  _et al._ (2007). We find

$N_{\rm
Ch}\sim\frac{\log\epsilon}{\log\left(1-(1-\sqrt{1-r^{2}})\sin^{2}\frac{\theta}{2}\right)}\,.$
(39)

In Figure 2 in MT we compare Eqs. (38) and (39) and observe a reduction of the
required number of copies of at least 50% on average if we employ the
sequential test instead of the deterministic one. The reduction goes up to 75%
if $\rho$ and $\sigma$ are very mixed.

(a)  (b)

(c)

Figure 5:  (a) Behaviour of the likelihood ratio $Z_{n}$ using unbiased local
measurements as a function of the step $n$, for 3000 realizations of the
hypothesis test with $\theta={\pi\over 10}$, $r_{0}=0.7$, $r_{1}=0.9$,
$\epsilon_{0}=10^{-6}$, $\epsilon_{1}=10^{-9}$, under hypotheses $H_{0}$
(green) and $H_{1}$ (orange). The solid lines show the mean trajectory, and
the shaded areas correspond to the 2${}^{\text{nd}}$ and 3${}^{\text{rd}}$
quartiles (25% above and below the mean). The decision boundaries $a$ and $b$
are also plotted. (b) Histogram of stopping times under each hypothesis. The
vertical lines mark the mean of each distribution. (c) The mean number of
copies $\langle{N}\rangle_{0}$ as a function of $\log\epsilon$, for the same
state parameters as in (a) and equal error bounds
$\epsilon_{0}=\epsilon_{1}=\epsilon$. The solid line represents the mean
trajectory of 500 runs, the shaded area shows the 2${}^{\text{nd}}$ and
3${}^{\text{rd}}$ quartiles, and the dashed line is the analytic expression
$\langle{Z}\rangle_{0}/D(p_{\phi}\|q_{\phi})$, where recall that
$\langle{Z}\rangle_{0}\sim-\log\epsilon$ for $\epsilon\ll 1$.

For illustration purposes, in Figure 5 we show explicitly the results of
several runs of a SPRT using unbiased local measurements. We observe how the
mean trajectories that the cummulative log-likelihood ratio $Z_{n}$ follows
point upwards or downwards depending on the underlying hypothesis. In this
simulation, the state $\rho$, corresponding to $H_{0}$, is identified quicker
than $\sigma$ (the decision boundary $b$ is closer than $a$), despite being
more mixed. A histogram of stopping times under each hypothesis shows us that
the distributions of $N$ are well-centered around their empirical mean, with
right tails that are slightly longer; this is also apparent on the left figure
from the cross-sections of the trajectories with the decision boundaries.
Finally, we observe that the mean number of copies increases linearly with
$\log\epsilon$ for $\epsilon\ll 1$, as predicted.

###  III.2 Block-sampling and irrep projection

Here we study the mean number of copies under both hypotheses using a block-
sampling strategy where the same collective measurement is repeated on batches
of $\ell$ copies. In particular we will consider a collective measurement for
which Hayashi Hayashi (2001) showed that the (classical) relative entropy of
the distributions that arise from it, attains the quantum relative entropy
when the block length $\ell$ is large. Denoting by $M=\\{M_{k}\\}$ such
collective POVM and by $p^{\ell}_{M},q^{\ell}_{M}$ the probability
distributions of the outcomes, i.e., $\\{p^{\ell}_{M}(k)={\rm
tr}(\rho^{\otimes\ell}M_{k})\\}$ and $\\{q^{\ell}_{M}(k)={\rm
tr}(\sigma^{\otimes\ell}M_{k})\\}$, in Ref. Hayashi (2001) it is shown that

$\frac{D\left(p^{\ell}_{M}\|q^{\ell}_{M}\right)}{\ell}\leq
D(\rho\|\sigma)\leq\frac{D\left(p^{\ell}_{M}\|q^{\ell}_{M}\right)}{\ell}+(d-1)\frac{\log(\ell+1)}{\ell}\,,$
(40)

where $d$ is the dimension of the underlying Hilbert space, from where

$\frac{D\left(p^{\ell}_{M}\|q^{\ell}_{M}\right)}{\ell}\rightarrow
D(\rho\|\sigma)\quad\mbox{ as }\ell\rightarrow\infty\,.$ (41)

Quite remarkably, the measurement $M$ in Eq. (40) depends solely on state
$\sigma$.

As explained in the MT such a strategy allows one to attain the lower bound
for one of the hypotheses, say
$\langle{N}\rangle_{0}\sim-\log\epsilon_{0}(1-A^{-1})/D(\rho\|\sigma)$ for the
strong error bounds [cf. Eq. (15) in MT], or

$\langle{N}\rangle_{0}\sim\frac{\log\beta(1-\alpha)}{D(\rho\|\sigma)}$ (42)

for the asymmetric setting.

In what follows we compute the (sub-optimal) performance of this very same
measurement under the other hypothesis, i.e., $\langle{N}\rangle_{1}$.

For qubit systems, the POVM that achieves the quantum relative entropy Hayashi
(2001) corresponds to the simultaneous measurement of the total angular
momentum $J^{2}$ (eigenspaces labeled by $j$) and its component along the axis
$J_{z}$ (eigenspaces labeled by $m$), where $\hat{z}$ is picked to be the axis
along which the state $\sigma$ points, i.e.,
$\sigma=1/2(\openone+r_{1}\sigma_{z})$. The quantum number $j$ labels the
$SU(2)$ irreducible representations (irreps), and since it is invariant under
the action of any rigid rotation $U^{\otimes n}$ it will only provide
information about the spectra of $\rho$ or $\sigma$ —which we denote
$\lambda_{i}^{\pm}=\frac{1}{2}(1\pm r_{i})$ for $i=0,1$ respectively. The
second measurement $J_{z}$ is clearly not $SU(2)$ invariant and provides
information about relative angle between both hypotheses, and additional
information on their spectrum.

Due to the permutational invariance of the $\ell$ copies it is possible to
write the states in a block-diagonal form in terms of the $\\{j,m\\}$ quantum
numbers (see e.g. Gendra  _et al._ (2012)):

$\sigma^{\otimes\ell}=\sum_{j=j_{\min}}^{\ell/2}q_{j}\sigma_{j}\otimes\frac{\openone_{{j}}}{\nu_{j}}\quad\text{with}\quad\sigma_{j}=\sum_{m=-j}^{j}q(m|j)\left|{j,m}\rangle\\!\langle{j,m}\right|\mathrm{,}$
(43)

where $\openone_{{j}}$ are projectors over the subspaces of dimension
$\nu_{j}={\ell\choose\ell/2-j}{2j+1\over\ell/2+j+1}$ that host the irreps of
the permutation group (i.e. multiplicity space of spin $j$), $j_{\min}=0$ for
$\ell$ even ($j_{\min}=1/2$ for $\ell$ odd) and

$\displaystyle q_{j}$ $\displaystyle=$
$\displaystyle\left(\frac{1-r_{1}^{2}}{4}\right)^{\ell/2}\nu_{j}Z_{j}\,,$ (44)
$\displaystyle q(m|j)$ $\displaystyle=$
$\displaystyle\frac{1}{Z_{j}}R_{1}^{m}\quad\mathrm{with}\quad
Z_{j}=\frac{R_{1}^{j}-R_{1}^{-j}}{R_{1}-1}\quad\mbox{and}\quad
R_{1}=\frac{1+r_{1}}{1-r_{1}}>1$ (45)

are normalized probability distributions.

Under hypothesis $H_{0}$ the state has exactly the same structure except for a
global rotation around the $\hat{z}$ axis by an angle $\theta$,

$\rho^{\otimes\ell}=\sum_{j=j_{\min}}^{\ell/2}p_{j}\rho_{j}\otimes\frac{\openone_{{j}}}{\nu_{j}}\quad\text{with}\quad\rho_{j}=\sum_{m=-j}^{j}p(m|j)\;U_{\theta}\left|{j,m}\rangle\\!\langle{j,m}\right|U^{\dagger}_{\theta}\mathrm{,}$
(46)

where $p_{j}$ and $p(m|j)$ take the form of (44) and (45) replacing $r_{1}$
and $R_{1}$ by $r_{0}$ and $R_{0}$.

The outcomes of the $J^{2}$ and $J_{z}$ measurements lead to probability
distributions

$\displaystyle p(j,m)$
$\displaystyle=p_{j}\,\tilde{p}(m|j)\quad\mathrm{with}\quad\tilde{p}(m|j)=\sum_{m^{\prime}=-j}^{j}p(m^{\prime}|j)|\\!\left\langle{j,m}\right|U_{\theta}\left|{j,m^{\prime}}\right\rangle\\!|^{2}\,,$
(47) $\displaystyle q(j,m)$ $\displaystyle=q_{j}\,q(m|j)\,,$ (48)

whose relative entropy can be written as

$\displaystyle D(q^{\ell}\|p^{\ell})=$ $\displaystyle\sum_{j=j_{\rm
min}}^{\ell/2}q_{j}\sum_{m=-j}^{j}q(m|j)\log\frac{q_{j}\,q(m|j)}{p(j,m)}\sim\log\frac{q_{j^{*}}\,q(j^{*}|j^{*})}{p(j^{*},j^{*})}$
(49)

where we have used the fact that for $\ell\gg 1$, $q_{j}$ is strongly peaked
at $j^{*}=r_{1}\ell/2$ and $q(m|j^{*})$ decays exponentially, and hence it is
peaked at $m=j^{*}$. In addition we note that

$\displaystyle p(j,m=j)$
$\displaystyle=p_{j}\sum_{m^{\prime}=-j}^{j}p(m^{\prime}|j)|\\!\left\langle{j,j}\right|U_{\theta}\left|{j,m^{\prime}}\right\rangle\\!|^{2}$
$\displaystyle=\left\langle{j,j}\right|\left(p_{j}\sum_{m^{\prime}=-j}^{j}p(m^{\prime}|j)U_{\theta}\left|{j,m^{\prime}}\rangle\\!\langle{j,m^{\prime}}\right|U_{\theta}^{\dagger}\right)\left|{j,j}\right\rangle=\left(\frac{1-r_{0}^{2}}{4}\right)^{l/2-j}\nu_{j}\left\langle{j,j}\right|\rho^{\otimes
2j}\left|{j,j}\right\rangle$
$\displaystyle=\left(\frac{1-r_{0}^{2}}{4}\right)^{l/2-j}\nu_{j}\left\langle{\uparrow}\right|\rho\left|{\uparrow}\right\rangle^{2j}=\left(\frac{1-r_{0}^{2}}{4}\right)^{l/2-j}\nu_{j}\left(\frac{1+r_{0}\cos\theta}{2}\right)^{2j}\,,$
(50)

where we used the general decomposition of (46), and
$\left|{\uparrow}\right\rangle$ is short-hand notation for
$\left|{j=1/2,m=1/2}\right\rangle$. Inserting this expression in (49) and
using the definitions in (44) and (45) we finally arrive at

$\displaystyle D_{M_{\sigma}}(\sigma\|\rho)$
$\displaystyle:=\lim_{\ell\to\infty}\frac{1}{\ell}D(q^{\ell}\|p^{\ell})=\frac{1}{2}(1-r_{1})\log\frac{1-r_{1}^{2}}{1-r_{0}^{2}}+r_{1}\log\frac{1+r_{1}}{1+r_{0}\cos\theta}$
$\displaystyle=D(\lambda_{1}\|\lambda_{0})+r_{1}\log\frac{1+r_{0}}{1+r_{0}\cos\theta}\,,$
(51)

where the symbol $M_{\sigma}$ recalls that we have chosen $M$ as a measurement
over the eigenbasis of $\sigma$, which maximizes the relative entropy
$D(q^{l}\|p^{l})$, and

$D(\lambda_{1}\|\lambda_{0})=\frac{1}{2}(1+r_{1})\log\frac{1+r_{1}}{1+r_{0}}+\frac{1}{2}(1-r_{1})\log\frac{1-r_{1}}{1-r_{0}}$
(52)

is the relative entropy between the spectra of $\sigma$ and $\rho$. Hence, the
second term in (51) can be associated to the distinguishability caused by the
different orientation (non-commutativity) of the states.

On the other hand, from (41) it follows

$\displaystyle D_{M_{\sigma}}(\rho\|\sigma)$
$\displaystyle:=\lim_{\ell\to\infty}\frac{1}{\ell}D(p^{\ell}\|q^{\ell})=D(\rho\|\sigma)$
$\displaystyle=\frac{1}{2}(1+r_{0})\log\frac{1+r_{0}}{1+r_{1}}+\frac{1}{2}(1-r_{0})\log\frac{1-r_{0}}{1-r_{1}}+r_{0}\log\frac{1+r_{0}}{1-r_{1}}\sin^{2}\frac{\theta}{2}$
$\displaystyle=D(\lambda_{0}\|\lambda_{1})+r_{0}\log\frac{1+r_{0}}{1-r_{1}}\sin^{2}\frac{\theta}{2}\,.$
(53)

From the above results we conclude that applying the measurement that reaches
the ultimate bound for one hypothesis

$\langle{N}\rangle_{0}=-\frac{\log\beta}{D(\rho\|\sigma)}$ (54)

will result in a sub-optimal value

$\langle{N}\rangle_{1}\sim-\frac{\log\alpha}{D_{M_{\sigma}}(\sigma\|\rho)}$
(55)

for the other hypothesis, with $D_{M_{\sigma}}(\sigma\|\rho)$ given in (51).

We observe that, as expected, when the states commute we can reach the
ultimate bound for both $\langle{N}\rangle_{0},\langle{N}\rangle_{1}$. We also
note that, when $\rho$ is pure, one can also preserve asymptotic optimality
for both means, since when $\lambda_{0}^{\pm}\in\\{1,0\\}$,
$D_{M_{\sigma}}(\sigma\|\rho)$ diverges and the leading contribution in
$\langle{N}\rangle_{1}$ vanishes, while $\langle{N_{0}}\rangle$ reaches the
optimal value. These results hold for the block-sampling strategy that uses
blocks of large length $l\gg 1$, so one needs to find other ways to compute
the finite $O(1)$ contribution to $\langle{N}\rangle_{1}$, as we shall show
next.

We have already shown [see (18) in MT] that when _both_ states are pure we can
detect both hypotheses with a finite mean number of copies. If only one of the
states is pure, say $\rho$, it is easy to notice that the $J^{2}$ measurement
alone guarantees a constant value for $\langle{N}\rangle_{1}$: $\rho^{\otimes
n}$ lies in the fully symmetric space (with $j=n/2$) and therefore any
measurement outcome $j<n/2$ will unambiguously identify $\sigma$. The above
block-sampling might have an important overhead when $\ell$ is large. A way of
reducing this overhead can be devised by leveraging the fact that the
measurement of $J^{2}$ on $n$ copies commutes with the measurement of $J^{2}$
on $n+1$ for all $n\geq 1$: starting at $n=2$, we measure $J^{2}$ sequentially
on all available copies until we get an outcome $j<n/2$, at which moment we
stop and accept $H_{1}$. Note that each step of this sequence uses the already
measured copies, increasing the number of jointly-measured systems by one.
Since the probability of not detecting $\sigma$ at step $n$ (continue
measuring) is given by
$T^{n}_{1}=P(j=n/2)=\left(\frac{1+r_{1}\cos\theta}{2}\right)^{n}=:q_{+}^{n}$,
we can write

$\langle{N}\rangle_{1}=\sum_{n=0}^{\infty}T^{n}_{1}=\sum_{n=0}^{\infty}q_{+}^{n}=\frac{1}{1-q_{+}}=\frac{2}{1-r_{1}\cos\theta}\,.$
(56)

Note, however, that measuring $J^{2}$ sequentially is on its own not enough to
reach the optimal mean number of copies also under hypothesis $H_{0}$,
$\langle{N}\rangle_{0}$. For this reason, after every batch of $\ell$ copies,
$\ell\gg\langle{N}\rangle_{1}$ ($\ell=o(\log 1/\epsilon)$), we interrupt the
sequence of $J^{2}$ measurements with a measurement of $J_{z}$ on the last
batch of $\ell$ copies (and then continue again with the $J^{2}$ sequential
measurement). The measurement statistics obtained by this procedure mimicks
the block-sampling method described above and hence we are guaranteed to
converge to (54).

Alternatively, in order to attain (56) one can directly measure the system in
the basis that diagonalizes
$\rho=\left|{\lambda_{0}^{+}}\rangle\\!\langle{\lambda_{0}^{+}}\right|$, so
that an $\left|{\lambda_{0}^{-}}\right\rangle$ outcome unambiguously detects
$\sigma$ with probability $q_{-}=1-q_{+}$. It is immediate to check that the
sequential application of this measurement also leads to (56). Again after
having measured a sufficiently large number of copies $\ell=o(\log
1/\epsilon)$ one can adopt the block-sampling strategy in order to achieve the
bound (54).

###  III.3 Ultimate limit for $N_{\mathrm{wc}}$. Attainability regions

In this section we study the achievability of the lower bound on the worst-
case mean number of copies,

$N_{\mathrm{wc}}:=\max\left\\{\langle{N}\rangle_{0},\langle{N}\rangle_{1}\right\\}\geq\max\left\\{-\frac{\log\epsilon}{D(\rho\|\sigma)},-\frac{\log\epsilon}{D(\sigma\|\rho)}\right\\},$
(57)

where for simplicity we assume that both error bounds are equal, i.e.,
$\epsilon_{0}=\epsilon_{1}=\epsilon\ll 1$.

In the previous section we have shown that the block-sampling with a given
POVM $M_{\sigma}$ can reach the optimal value under $H_{0}$, but it does so at
the expense of attaining a sub-optimal value under $H_{1}$. Making use of the
results of (51) and (53) one can show that there are pairs of states
$\\{\rho,\sigma\\}\in\mathcal{R}$ for which either

$D(\rho\|\sigma)\leq D_{M_{\sigma}}(\sigma\|\rho)\leq
D(\sigma\|\rho)\quad\text{or}\quad D(\sigma\|\rho)\leq
D_{M_{\rho}}(\rho\|\sigma)\leq D(\rho\|\sigma)\,.$ (58)

When this happens we can assert that the bound in (57) is attainable, since
the worst-case value is attained, i.e.,

$N_{\mathrm{wc}}\sim\max\left\\{-\frac{\log\epsilon}{D(\rho\|\sigma)},-\frac{\log\epsilon}{D(\sigma\|\rho)}\right\\}\,,$
(59)

Figure 6 shows some representative regions where (58) is fulfilled, and (59)
holds. We observe that for small relative angles $\theta$ almost all states
attain the ultimate bound, except for a region around the pairs of equal
purity. It is easy to check that for states with $r_{0}=r_{1}$,
$D(\rho\|\sigma)=D(\sigma\|\rho)$, and therefore (58) cannot be satisfied,
independently of the relative angle $\theta$. When $\theta=\pi/2$, i.e., when
the pair of states exhibits more non-classicality, only pairs comprised by a
highly pure and a highly mixed state can attain the bound.

Figure 6: Regions $\mathcal{R}$ of purities $(r_{0},r_{1})$ for different
relative angles $\theta$, where the ultimate bound for $N_{\mathrm{wc}}$ (59)
is achievable. The red region corresponds to $\theta=\pi/2$, orange and red to
$\theta=\pi/10$, yellow, orange and red to $\theta=\pi/100$, and all
admissible values of $(r_{0},r_{1})$ are achievable for commuting states
($\theta=0$).

.

##  IV The overhead for arbitrary dimensions

In this section we would like to explore how conditions (58) look when states
$\rho$ and $\sigma$ have arbitrary dimension $d>2$. In this case, exactly
quantifying $D_{M_{\rho}}(\rho\|\sigma)$ [recall that we denote by $M_{\rho}$
the block-sampling measurement on $\ell$ copies that attains $D(\sigma\|\rho)$
when $\ell\to\infty$] is more involved. Here instead we provide a general
lower bound for the deviation of $D_{M_{\rho}}(\rho\|\sigma)$ from its maximum
value $D(\rho\|\sigma)$. We follow closely Ref. Hayashi (2001).

First, consider the following operation on a state $\rho$ for a given a
projective measurement $E=\\{E_{j}\\}$ (i.e., $E_{j}^{2}=E_{j}$ and
$E_{j}E_{k}=\delta_{jk}E_{j}$),

$\varepsilon_{E}(\rho):=\sum_{j}E_{j}\rho E_{j}\,.$ (60)

When $E$ commutes with states $\rho$ and $\sigma$ we have

$\varepsilon_{E}(\rho)=\rho\,,\quad\varepsilon_{E}(\sigma)=\sigma\,.$ (61)

Then, consider a projective measurement $F(\rho)=\\{F_{k}\\}$ that consists of
rank-one projectors in the eigenbasis of $\rho$, i.e., a measurement of the
spectrum of $\rho$. Note that we have $\varepsilon_{F}(\rho)=\rho$, but
$\varepsilon_{F}(\sigma)\neq\sigma$ for a generic state $\sigma$ that does not
commute with $\rho$. Note also that $E$ (which commutes with $\rho$ and
$\sigma$) is a coarse-grained measurement of $F(\rho)$; we can then say that
$F(\rho)$ is stronger than $E$. In Hayashi (2001) this fact is denoted by
$F(\rho)\geq E$. We then have the following lemma:

######  Lemma 2.

Let $\rho$ and $\sigma$ be states and let $F(\rho)\geq E$. The quantum
relative entropy between $\rho$ and $\sigma$ can be expressed as

$D(\rho\|\sigma)=D(\varepsilon_{F}(\rho)\|\varepsilon_{F}(\sigma))+\operatorname{Tr}\rho(\log\varepsilon_{F}(\sigma)-\log\sigma)\,.$
(62)

###### Proof.

Recalling that $\varepsilon_{F}(\rho)=\rho$, we have
$\operatorname{Tr}\varepsilon_{F}(\rho)\log\varepsilon_{F}(\sigma)=\operatorname{Tr}\rho\log\varepsilon_{F}(\sigma)$,
thus

$\displaystyle
D(\varepsilon_{F}(\rho)\|\varepsilon_{F}(\sigma))-D(\rho\|\sigma)=\operatorname{Tr}\varepsilon_{F}(\rho)(\log\varepsilon_{F}(\rho)-\log\varepsilon_{F}(\sigma))-\operatorname{Tr}\rho(\log\rho-\log\sigma)=\operatorname{Tr}\rho(\log\sigma-\log\varepsilon_{F}(\sigma))\,.$
(63)

Hence, it follows that

$D(\varepsilon_{F}(\rho)\|\varepsilon_{F}(\sigma))=D(\rho\|\sigma)-\operatorname{Tr}\rho(\log\varepsilon_{F}(\sigma)-\log\sigma)\,.$
(64)

∎

We also need the following lemma:

######  Lemma 3.

For a given projective measurement $E$ such that $E\leq F$, if $E$ commutes
with $\sigma$ and $\rho$ we have that

$\operatorname{Tr}\rho(\log\varepsilon_{F}(\sigma)-\log\sigma)\leq\sup_{i}\\{\operatorname{Tr}\rho_{i}(\log\varepsilon_{F}(\sigma_{i})-\log\sigma_{i})\\}\,,$
(65)

where we define $\rho_{i}:=\frac{1}{a_{i}}E_{i}\rho E_{i}$,
$\sigma_{i}:=\frac{1}{b_{i}}E_{i}\sigma E_{i}$,
$a_{i}:=\operatorname{Tr}E_{i}\rho E_{i}$, and
$b_{i}:=\operatorname{Tr}E_{i}\sigma E_{i}$.

###### Proof.

Starting from the left side of inequality (65), the following steps hold:

$\displaystyle\operatorname{Tr}\rho(\log\varepsilon_{F}(\sigma)-\log\sigma)$
$\displaystyle=\operatorname{Tr}[\sum_{i}E_{i}\rho(\log\varepsilon_{F}(\sigma)-\log\sigma)]=\operatorname{Tr}[\sum_{i}E_{i}\rho
E_{i}(E_{i}\log\varepsilon_{F}(\sigma)E_{i}-E_{i}\log\sigma E_{i})]$ (66)
$\displaystyle=\operatorname{Tr}[\sum_{i}a_{i}\rho_{i}(\log\varepsilon_{F}(\sigma_{i})-\log\sigma_{i})]\leq\sup_{i}\\{\operatorname{Tr}\rho_{i}(\log\varepsilon_{F}(\sigma_{i})-\log\sigma_{i})\\}=:\omega(\sigma).$
(67)

∎

We are now ready to derive a bound on $D_{M_{\rho}}(\rho\|\sigma)$ with the
following theorem:

######  Theorem 2.

Let us define the projective measurement $M_{\rho}=F(\rho^{\otimes\ell})\times
E^{\ell}$ acting on $\ell$ copies, where $E^{\ell}$, applied first, is a
measurement that projects onto the irreps of $SU(d)^{\otimes\ell}$. Then,
$F(\rho^{\otimes\ell})$ is a spectral measurement of $\rho^{\otimes\ell}$,
i.e., a projective measurement on the basis that diagonalizes $\rho$. For this
measurment, we have

$D(\rho\|\sigma)-\frac{\omega(\sigma)}{\ell}\leq\frac{1}{\ell}D_{M_{\rho}}(\rho^{\otimes\ell}\|\sigma^{\otimes\ell})\leq
D(\rho\|\sigma)\,.$ (68)

###### Proof.

We simply use Lemma 2 and Lemma 3 with the change
$\rho\rightarrow\rho^{\otimes\ell}$ and
$\sigma\rightarrow\sigma^{\otimes\ell}$, and we recall the property of the
quantum relative entropy $D(\rho^{\otimes\ell}\|\sigma^{\otimes\ell})=\ell
D(\rho\|\sigma)$. The result follows from applying Lemma 2 to all the terms in
Lemma 3. ∎

A very generous bound can be obtained by dropping the negative term
$\log\varepsilon_{F}(\sigma_{i})$ in $\omega(\sigma)$ Audenaert and Eisert
(2005):

$\displaystyle\omega(\sigma)\leq\sup_{i}-\operatorname{Tr}[\rho_{i}(\log\sigma_{i})]\leq\max_{i}-\log[\lambda_{\min}(\sigma_{i})]\,.$
(69)

##  V Zero-error protocol for pure states

As we have seen in the MT, as the error $\epsilon$ goes to $0$, the average
number of copies goes to infinity. However, for pure states
$\\{\rho=\left|{\psi_{0}}\rangle\\!\langle{\psi_{0}}\right|,\sigma=\left|{\psi_{1}}\rangle\\!\langle{\psi_{1}}\right|\\}$
there are sequential strategies with local measurements that give a strictly
zero error with a finite average number of samples. Here we detail the
protocol already mentioned in the MT and prove its optimality for equal priors
for the Bayesian mean and worst-case number of copies.

To this end, consider a sequence of fixed unambiguous measurements on each
copy with inconclusive probabilities $c_{\nu}$ if the given state is
$\left|{\psi_{\nu}}\right\rangle$, $\nu=0,1$. We notice that these
probabilities satisfy the ’uncertainty’ relation $c_{0}c_{1}\geq s^{2}$, where
$s=|\langle{\psi_{0}}|{\psi_{1}}\rangle|$ sentis2018online. The protocol stops
only if one of the states is identified with no error. Hence, at each step $n$
there are only two possibilities: continue, with conditional probability
(after having arrived at step $n$) $c_{\nu}$, or stop, with conditional
probability $1-c_{\nu}$. The probability of exactly stopping at step $n$ is
$P^{n}_{\nu}=c_{\nu}^{n-1}(1-c_{\nu})$. Then, the average number of copies
required to get a zero-error outcome is

$\displaystyle\langle{N}\rangle_{\nu}=$
$\displaystyle\sum_{n=1}^{\infty}nc_{\nu}^{n-1}(1-c_{\nu})=\sum_{n=0}^{\infty}c_{\nu}^{n}=\frac{1}{1-c_{\nu}}\,.$
(70)

Notice that both means are finite if one performs an unambiguous measurement
with $c_{0}<1$ and $c_{1}<1$, which is allowed by the relation $c_{0}c_{1}\geq
s^{2}$.

In the case of equal priors, we now show that the symmetric choice
$c_{0}=c_{1}=s$ gives the optimal Bayesian mean
$\langle{N}\rangle=(\langle{N}\rangle_{0}+\langle{N}\rangle_{1})/2$. We
observe that the inconclusive probability attained by the optimal global
measurement on $n$ copies of $\left|{\psi_{\nu}}\right\rangle$, $T_{\nu}^{n}$,
cannot be beaten by any local strategy, hence, using (70) we have

$\displaystyle\langle{N}\rangle=\frac{1}{1-s}=\sum_{n=0}^{\infty}s^{n}\geq\sum_{n=0}^{\infty}\frac{1}{2}\left(T_{0}^{n}+T_{1}^{n}\right)=:\langle{N^{*}}\rangle\,.$
(71)

Analogously to the derivation of (15) in MT, the r.h.s. of (71) corresponds to
a relaxation of the original problem in which we have independently optimized
each term in the sum, considering the action of optimal $n$-copy unambiguous
measurements for each $n$, hence $\langle{N^{*}}\rangle$ is a lower bound to
the most general protocol. Since $n$-copy pure states are simply pure states
of larger dimension, we have $|\langle{\psi_{0}^{\otimes
n}}|{\psi_{1}^{\otimes n}}\rangle|=s^{n}$, and the equivalent relation
$T_{0}^{n}T_{1}^{n}\geq s^{2n}$ holds for global strategies. Then, the
symmetric choice $T_{0}^{n}=T_{1}^{n}=s^{n}$ minimizes each summand in (71),
and we obtain
$\langle{N^{*}}\rangle=\sum_{n=0}^{\infty}s^{n}=(1-s)^{-1}=\langle{N}\rangle$.

Finally, we also note that the symmetric choice also optimizes the figure of
merit given by the worst-case number of copies
$N_{\mathrm{wc}}=\max\\{\langle{N}\rangle_{0},\langle{N}\rangle_{1}\\}$.
Because of the relation $T_{0}^{n}T_{1}^{n}\geq s^{2n}$, if $T_{0}^{n}>s^{n}$
then $T_{1}^{n}<s^{n}$ and $N_{\mathrm{wc}}=\langle{N}\rangle_{0}>1/(1-s)$.
The same argument applies if $T_{1}^{n}>s^{n}$, hence it follows that the
optimal measurement has $T_{0}^{n}=T_{1}^{n}=s^{n}$ and
$N_{\mathrm{wc}}=1/(1-s)$.