# Stability Verification of Quantum non-i.i.d. sources

Esteban Martínez Vargas<EMAIL_ADDRESS>Calle centella 3, Smza 18
Mza 3, 77505 Cancún México

(August 28, 2024)

###### Abstract

We introduce the problem of stability verification of quantum sources which
are non-i.i.d.. The problem consists in ascertaining whether a given quantum
source is stable or not, in the sense that it produces always a desired
quantum state or if it suffers deviations. Stability is a statistical notion
related to the sparsity of errors. This problem is closely related to the
problem of quantum verification first proposed by Pallister et. al. Pallister
et al. (2018), however, it extends the notion of the original problem. We
introduce a family of states that come from these non-i.i.d. sources which we
call a Markov state. These sources are more versatile than the i.i.d. ones as
they allow statistical deviations from the norm instead of the more coarse
previous approach. We prove in theorem 1 that the Markov states are not well
described with tensor products over a changing source. In theorem 30 we
further provide a lower bound on the trace distance between two Markov states,
or conversely, an upper bound on the fidelity between these states. This is a
bound on the capacity of determining the stability property of the source,
which shows that it is exponentially easier to ascertain this with respect to
$n$, the number of outcomes from the source.

##  I Introduction

Quantum tomography is the process of reconstructing a quantum state from a
series of observations Nielsen and Chuang (2011). This is a very costly
process Häffner et al. (2005) as it normally requires an exponential amount of
measurements with the dimension of the system Huang et al. (2020), which
implies an exponential amount of copies of the state. Alternative approaches
have been invented to circumvent this issue: using compressed sensing for
example Gross et al. (2010). Recently, there have been interesting lines of
research whose objective is less ambitious than full-state tomography, but to
calculate functionals of states that take a polynomial amount of resources
Huang et al. (2020); Aaronson (2018).

Close to this topic is the task of quantum verification Pallister et al.
(2018), whose objective is to ascertain if a source yields a desired state, or
if it incurs an error. The question to answer is if a machine that produces
identical copies of the state $\left|{\psi}\right\rangle$ and whose details
are hidden from us (is a black box) is producing the state it should. Here one
does not deal with the full tomographical problem and therefore number of
required measurements can be lower.

Pallister et. al. Pallister et al. (2018) define verification as a quantum
hypotheses testing problem, which consists in guessing a given quantum state
from two possible hypotheses with the lowest probability of error Bae and Kwek
(2017); Barnett and Croke (2009). The task is simple to state: suppose a
machine produces states $\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\\}$ which
should be $n$ copies of $\left|{\psi}\right\rangle$. Hypothesis 0 is that
$\sigma_{i}=\left|{\psi}\rangle\\!\langle{\psi}\right|$ for all $i$ and
hypothesis 1 is that
$\left\langle{\psi}\right|\sigma_{i}\left|{\psi}\right\rangle\leq 1-\epsilon$
for all $i$ for $0\leq\epsilon\leq 1$. The objective is that the verifier
passes the test with a worst-case probability of $\delta$. They consider
independent online measurements Sentís et al. (2022).

Despite making considerable advances, their approach is an oversimplification
as it restricts to detect very specific situations: the source produced all
the time the correct state or all the time a wrong one. Perhaps one would
qualify as not so bad a machine that produces a desired state
$\left|{\psi}\right\rangle$ _most_ of the time, but here and there, in a
sparse manner, allow an error.

Part of the oversimplification of the problem lies in the fact that its
definition uses i.i.d. sources that limit the abstract notions that one would
like to address. Here, we extend the notion of verification of Pallister from
identifying outputs of an i.i.d. source. Instead of aiming for detecting a
perfectly consistent source, we allow deviations as long as they are
statistically negligible. We introduce the formalism of a family of mixed
states that describe rigorously this situation. These states are prepared by a
source that is non-i.i.d. but has temporal correlations between the produced
states. We shall call the sources we study “Markov sources” as their
definition depends on Markov chains.

We investigate how the family of states that we introduce behaves and we find
that the tensor product of states after each iteration does not apply in this
case. In some sense, the Markov sources we introduce here generalize the
notion of a Markov chain to quantum systems, although studied through other
approaches Sutter (2018). We show in section II.1 the relationship between the
sparsity of errors for the Markov source and two parameters $\epsilon\in[0,1]$
and $\delta\in[0,1]$. Then, we arrive at theorem 1, which shows the difference
between the Markov source and a similar one is exponential in the number of
instances of the Markov source.

Having defined the Markov sources and their respective output after $n$
instances, we address the problem of verification which can be translated into
a quantum discrimination problem. Pallister’s approach uses individual
measurements for several copies, therefore their measuring scheme has no
horizon. By contrast, our approach presupposes that a fixed number of
instances of the Markov source is given. We observe that this problem can be
translated into two hypotheses: $H_{0}$ is that we were given a state
$\mathfrak{M}_{0}=f(\delta_{0})$ and $H_{1}$ that
$\mathfrak{M}_{1}=g(\delta_{1})$ where $0\leq\delta_{0}<\delta_{1}\leq 1$. We
have two quantum states, therefore the problem reduces to find the Helstrom
bound between $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$. We give a lower bound
for the trace distance between these states in theorem 30, or conversely, an
upper bound on the fidelity between these states. We end this paper with a
discussion.

##  II Quantum Markov sources

Here we introduce the formalism for describing the non-i.i.d. sources that we
study here. This kind of sources can be defined in analogy with iid sources of
mixed states. Suppose that we have a pair of orthogonal states
$\left|{0}\right\rangle$ and $\left|{1}\right\rangle$. Also, suppose that a
source yields the state $\left|{0}\right\rangle$ with probability $p$, and the
state $\left|{1}\right\rangle$ with probability $1-p$. An iid source would
produce after $n$ instances a state given by $\rho^{\otimes n}$ with

$\rho=p\left|{0}\rangle\\!\langle{0}\right|+(1-p)\left|{1}\rangle\\!\langle{1}\right|.$
(1)

Let us denote $\textbf{x}_{n}$ a string of size $n$ composed of $k$ $0$’s and
$n-k$ $1$’s. Observe that

$\left\langle{\textbf{x}_{n}}\right|\rho^{\otimes
n}\left|{\textbf{x}_{n}}\right\rangle=p^{k}(1-p)^{n-k}.$ (2)

For a different string $\left|{\textbf{y}_{n}}\right\rangle$ we have
$\left\langle{\textbf{y}_{n}}\right|\rho^{\otimes
n}\left|{\textbf{x}_{n}}\right\rangle=0$. Then, we can think of $\rho^{\otimes
n}$ as a convex combination of pure states projectors:

$\rho^{\otimes
n}=\sum_{\textbf{x}_{i}\in\mathcal{S}_{i}}\mathcal{T}(\textbf{x}_{i})\left|{\textbf{x}_{i}}\rangle\\!\langle{\textbf{x}_{i}}\right|$
(3)

where $\mathcal{S}_{i}$ denotes the set of permutations of $0$’s and $1$’s in
strings of size $i$ and $\mathcal{T}(\textbf{x}_{i})=p^{k}(1-p)^{i-k}$.

We note that the state $\rho^{\otimes n}$ depends on the function
$\mathcal{T}(\textbf{x}_{i})$ that assigns a probability to the string
$\textbf{x}_{i}$.

Consider now a source of quantum states that produces a concatenation of the
states $\left|{0}\right\rangle$ and $\left|{1}\right\rangle$ following the
outcome of a 2-state Markov chain. This means that we have a machine with an
interior state $\\{0\\}$ or $\\{1\\}$ which produces a state accordingly. This
machine is analogous to the one illustrated in Fig. (1) with
$0\leq\varepsilon\leq 1$ and $0\leq\delta\leq 1$.

Figure 1: Diagram of a non-i.i.d. source governed by a two-state Markov chain.

At the start, we are given the state $|0\rangle$ with probability $p_{0}$ and
the state $|1\rangle$ with probability $1-p_{0}$. Therefore, we are given the
mixed state

$\mu_{1}=p_{0}\left|{0}\rangle\\!\langle{0}\right|+(1-p_{0})\left|{1}\rangle\\!\langle{1}\right|.$
(4)

Now, as our source follows the Markov chain of the figure (1) the state after
another output is

$\displaystyle\mu_{2}$
$\displaystyle=p_{0}(\varepsilon\left|{01}\rangle\\!\langle{01}\right|+(1-\varepsilon)\left|{00}\rangle\\!\langle{00}\right|)$
$\displaystyle+(1-p_{0})(\delta\left|{10}\rangle\\!\langle{10}\right|+(1-\delta)\left|{11}\rangle\\!\langle{11}\right|).$
(5)

From equation (5) it is straightforward to see that
$\mu_{2}=\mu_{1}\otimes\mu_{1}$ if and only if $\varepsilon+\delta=1$ and
$\delta=p_{0}$ which is a special case of the parameters at hand.

It is simple to construct the density matrix that is the output of $n$ steps
of the source from equation (5). We denote the state of the output of $N$
instances of a Markov source as in figure (1) as
$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{1}\right\rangle,n]$.
Therefore, analogously to equation (3) we have

$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{1}\right\rangle,n]:=\sum_{\textbf{x}_{i}\in\mathcal{S}_{i}}\mathcal{M}(\textbf{x}_{i})\left|{\textbf{x}_{i}}\rangle\\!\langle{\textbf{x}_{i}}\right|$
(6)

for a suitable function $\mathcal{M}(\textbf{x}_{i})$, that follows the
probabilities of the Markov chain for a given string $\textbf{x}_{i}$. Being
more general, we have the following definition

######  Definition 1.

We denote an $n$-length Markov state that is the mix of the pure states
$\left|{0}\right\rangle$ and $\left|{\varphi}\right\rangle$ with
$\langle{0}|{\varphi}\rangle=c$, $0\leq c\leq 1$ as

$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]:=\sum_{\chi_{i}\in\mathcal{S}_{i}}\mathcal{M}(\chi_{i})\left|{\chi_{i}}\rangle\\!\langle{\chi_{i}}\right|,$
(7)

where the states $\left|{\chi^{\prime}_{i}}\right\rangle$ are (tensored)
strings of $0$’s and $\varphi$’s that correspond to all the permutations of
$n$ of n instances of 2 symbols. The function $\mathcal{M}(\chi_{i})$
correspond to the probabilities from a Markov chain as in Fig. (1).

Observe that
$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]\in\mathcal{H}^{\otimes
n}$ however clearly in general
$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]\neq\mu_{1}^{\otimes
n}$.

###  II.1 Sparsity: Bound on $k-$size windows with $l$ errors

A question arises when using the states defined by Eq. (7). We want to assign
meaning to the values $\epsilon$ and $\delta$. We want to verify that the
non-i.i.d. source does not accumulate too many errors.

Suppose that for a string of $N$ instances of the Markov source we want for
any possible set of $k$ consecutive states to have $l$ errors or less. This
can be done probabilistically, with a probability $\alpha$.

For example, we want that any consecutive set of $k=3$ to have at most $l=1$
error. We have to consider cases of consecutive sets which overlap.
Considering the full string of size $N$ we have that the string with the
maximum possible number of errors that start with a 0 is given by

$0\leavevmode\nobreak\ \varphi\leavevmode\nobreak\ 0\leavevmode\nobreak\
0\leavevmode\nobreak\ \varphi\leavevmode\nobreak\ 0\leavevmode\nobreak\
0\varphi\leavevmode\nobreak\ 0\leavevmode\nobreak\ 0\leavevmode\nobreak\
\varphi\ldots$ (8)

Any other string which fulfills the stable requirement would have more $0$’s
between the $\varphi$’s. Analyzing the probability of the string (8) we have
that it is given by

$p_{0}\epsilon\delta(1-\epsilon)\epsilon\delta(1-\epsilon)\epsilon\delta(1-\epsilon)\ldots=p_{0}(\epsilon\delta)^{\lfloor(N-1)/3\rfloor}(1-\epsilon)^{\lfloor(N-1)/3\rfloor}.$
(9)

Where $p_{0}$ is the probability that we are given $0$ at the beginning.
Therefore, the probability that we get all the stable strings is given by the
sum

$\displaystyle S(\delta,\epsilon)\equiv\sum_{j=0}^{\lfloor(N-1)/3\rfloor}$
$\displaystyle\binom{\frac{N-1}{3}}{\frac{N-1}{3}-j}p_{0}(\epsilon\delta)^{\lfloor(N-1)/3-j\rfloor}$
$\displaystyle\times(1-\epsilon)^{\lfloor(N-1)/3+2j\rfloor},$ (10)

because if we substract $j$ errors then we add two transitions from $0$ to
$0$. Observe that we consider all the possible combinations that come from
taking $(N-1)/3-j$ errors away. We can graph the function (10) and maximize
it. Numerical maximization reveals something that we could have guessed: the
maximum is attained when $\epsilon\rightarrow 0$ and $\delta\rightarrow 1$. In
Fig. (2) we have a graph for $S(\delta,\epsilon)$ defined in Eq. (10).

Figure 2: Graph of $S(\delta,\epsilon)$ for $N=20$ and we got $0$ at the
start, i.e. $p_{0}=1$.

The generalization of this procedure to any $k$-size window with $l$-errors is
straightforward. We have to find the limiting cases for the number of errors
first. Then we can obtain the probabilities of all other cases that fulfill
this stability criterion and the sum is the searched probability.

###  II.2 Consistency

The Markov sources we just described ask for a different relationship between
each iteration of the machine. We note that the i.i.d. source produces a
_tensored_ state. However, the tensor product will not describe accurately the
Markov source. Let us investigate how the Markov source would work.

Suppose we have the state $\left|{0}\right\rangle$ with probability $p$ and
the state $\left|{\varphi}\right\rangle$ with probability $1-p$. This would be
equivalent to begin with a vector distribution

$\mu=\begin{pmatrix}p\\\ 1-p\end{pmatrix}.$ (11)

Then, depending on being on the state $\\{0\\}$ or $\\{\varphi\\}$ in the
machine, it will jump with probabilities $\varepsilon$ and $\delta$ to be in
the aforementioned states. The distribution for the states of the machine is
given by $\mu\mathbf{P}$ where

$\mathbf{P}=\begin{pmatrix}1-\varepsilon&\varepsilon\\\
\delta&1-\delta\end{pmatrix}.$ (12)

After 2 iterations we would have the distribution $\mu\mathbf{P}^{2}$ etc. Let
us call $\rho_{k}$ the state that has the distribution $\mu\mathbf{P}^{k}$. A
$n$ output of the source is then
$\rho_{1}\otimes\rho_{2}\otimes\ldots\otimes\rho_{n}$. We will call these last
kind of sources _tensored_ Markov sources. Observe then that
$\rho_{k}\rightarrow\rho_{st}$ when $k\rightarrow\infty$ where

$\rho_{st}=\frac{\delta}{\varepsilon+\delta}\left|{0}\rangle\\!\langle{0}\right|+\frac{\varepsilon}{\varepsilon+\delta}\left|{\varphi}\rangle\\!\langle{\varphi}\right|.$
(13)

We will call “stationary” the density matrix $\rho_{st}$ in terms of
$\varepsilon$ and $\delta$. In the beginning, we would have some density
matrix that would evolve into the stationary density matrix in a finite number
of steps and then stay in that state, therefore the difference becomes
constant while the number of states can be arbitrarily large. We observe in
the following lemma that the output of $n$ instances of the tensored Markov
source should be similar to $\rho_{st}^{\otimes n}$ when $n\rightarrow\infty$.

######  Lemma 1.

The fidelity between the output of $n$ instances of the tensored Markov source
and the correspondent stationary density matrix is constant for
$n\rightarrow\infty$.

###### Proof.

Because of the multiplicativity over tensor products of the fidelity (property
9.2.5 in Wilde (2013)) then,

$\mathcal{F}(\rho_{1}\otimes\rho_{2}\otimes\ldots\otimes\rho_{n},\rho_{st}^{\otimes
n})=\prod_{i=1}^{n}\mathcal{F}(\rho_{i},\rho_{st}).$ (14)

Clearly, for any $\tau>0$ there exist an $n_{0}$ large enough so that the
right-hand side of eq. (14)

$|\prod_{i=1}^{n}\mathcal{F}(\rho_{i},\rho_{st})-\prod_{i=1}^{n+1}\mathcal{F}(\rho_{i},\rho_{st})|<\tau$
(15)

for any $n>n_{0}$. ∎

We show in theorem 1 that the fidelity between the Markov source and
$\rho_{st}^{n}$ decays exponentially and the Markov source is therefore not
well described by the formalism of the tensor product. First, we state a lemma
for the Fidelity Wilde (2013).

######  Lemma 2.

The fidelity between the states $\rho$ and $\sigma$ defined as

$\mathcal{F}(\rho,\sigma)=\left({\rm
tr}\,\left(\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}\right)\right)^{2}.$ (16)

is equal to the minimum Bhattacharya distance between two probability
distributions $p_{m}$ and $q_{m}$ resulting from a measurement
$\\{\Gamma_{m}\\}$ of the states $\rho$ and $\sigma$:

$\mathcal{F}(\rho,\sigma)=\min_{\\{\Gamma_{m}\\}}\left(\sum_{m}\sqrt{p_{m}q_{m}}\right)^{2},$
(17)

with

$p_{m}={\rm tr}\,[\Gamma_{m}\rho],\quad q_{m}={\rm tr}\,[\Gamma_{m}\sigma].$
(18)

We can then prove the following theorem,

######  Theorem 1.

For any $\tau$, $0\leq\tau\leq 1$ there exist $n$ sufficiently large such
that,

$\displaystyle\log_{2}$
$\displaystyle(\mathcal{F}(\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n],\rho_{st}^{\otimes
n}))\leq$
$\displaystyle-n(H(\delta/(\delta+\varepsilon))+H(\mathfrak{M})-2\tau$
$\displaystyle-2*|H(\delta/(\delta+\varepsilon))-H(\mathfrak{M})+2\tau|).$
(19)

where $H(\delta/(\delta+\varepsilon))$ denotes the entropy for the binomial
distribution with parameter $p=\delta/(\delta+\varepsilon)$ and we have the
entropy rate

$H(\mathfrak{M}):=\frac{\delta}{\varepsilon+\delta}H(\varepsilon)+\frac{\varepsilon}{\varepsilon+\delta}H(\delta).$
(20)

###### Proof.

The distribution of the state (13) corresponds to a binomial distribution and
asymptotically, the set of strings that correspond to the typical set
$A_{\tau}^{(n)}$ will be given by

$2^{-n(H(\delta/(\delta+\varepsilon))+\tau)}\leq p(\textbf{x}_{n})\leq
2^{-n(H(\delta/(\delta+\varepsilon))-\tau)}.$ (21)

The Markov state
$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]$
instead will be discribed by an entropy rate $H(\mathfrak{M})$. Therefore, the
typical set $B^{(n)}_{\tau}$ of sequences for these strings will have a
probability between

$2^{-n(H(\mathfrak{M})+\tau)}\leq q(\textbf{x}_{n})\leq
2^{-n(H(\mathfrak{{M}})-\tau)}.$ (22)

Therefore, following theorem 3.1.2 from Cover and Thomas (2006) the
intersection of the typical sets has a cardinality

$|A^{(n)}_{\tau}\cap
B^{(n)}_{\tau}|=2^{n|H(\delta/(\delta+\varepsilon))-H(\mathfrak{M})+2\tau|}.$
(23)

Using lemma (18) we can calculate the Fidelity by optimizing over POVMs
$\\{\Gamma_{m}\\}$. If we do not optimize over POVMs and take a specific
measurement, then we have an upper bound for the fidelity. The specific POVM
we take is a von Neumann measurement on the Hilbert space
$\mathcal{H}^{\otimes n}$: the projectors
$\left|{\textbf{x}_{n}}\rangle\\!\langle{\textbf{x}_{n}}\right|$. Note that
the set $\left|{\textbf{x}_{n}}\right\rangle$ forms an orthonormal basis of
$\mathcal{H}^{\otimes n}$, nevertheless there is no reason for this to be the
optimal POVM, so in general we got an upper bound for the Fidelity. Using the
asymptotic behavior of the typical sets we can see how the Fidelity behaves in
the large $n$ limit Cover and Thomas (2006). Let us define the function
$g(\chi_{n})$ as the number of $\varphi$’s in the string $\chi_{n}$. Using the
right-hand side of equations (21) and (22) we have that

$\displaystyle\left\langle{\textbf{x}_{n}}\right|$
$\displaystyle\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]\left|{\textbf{x}_{n}}\right\rangle\left\langle{\textbf{x}_{n}}\right|\rho^{\otimes
n}_{st}\left|{\textbf{x}_{n}}\right\rangle\leq$ $\displaystyle
c^{4*g(\chi_{n})}2^{-n(H(\delta/(\delta+\varepsilon))+H(\mathfrak{M})-2\tau)}$
(24)

Using the Lemma (18) we thus have the following upper bound for the Fidelity,

$\displaystyle\mathcal{F}$ $\displaystyle\leq\left(\sum_{\chi_{n}\in
A^{(n)}_{\tau}\cap
B^{(n)}_{\tau}}c^{4*g(\chi_{n})}2^{-\frac{n}{2}(H(\delta/(\delta+\varepsilon))+H(\mathfrak{M})-2\tau)}\right)^{2}$
(25) $\displaystyle\leq\left(\sum_{\chi_{n}\in A^{(n)}_{\tau}\cap
B^{(n)}_{\tau}}2^{-\frac{n}{2}(H(\delta/(\delta+\varepsilon))+H(\mathfrak{M})-2\tau)}\right)^{2}$
(26)
$\displaystyle=2^{-n(H(\delta/(\delta+\varepsilon))+H(\mathfrak{M})-2\tau-2*|H(\delta/(\delta+\varepsilon))-H(\mathfrak{M})+2\tau|)}.$
(27)

Where we have used that the typical set is uniformly distributed. ∎

In summary, in the limit $n\rightarrow\infty$ the Fidelity between the Markov
state (7) and the stationary state (13) decays exponentially. The reason is
that the typical set of a binary distribution with
$p=\delta/(\epsilon+\delta)$ is different then the typical set of the outcome
of a Markov chain after $n$ instances. In Fig. (3) we have an numerical graph
for the nonorthogonal state $\left|{\varphi}\right\rangle$ such that
$\arccos(c)=2\pi/3$.

Figure 3: Fidelity in the vertical axis, the number of instances in the
horizontal axis. Here $p_{0}=0.5$, $\varepsilon=0.3$, $\delta=0.5$ and
$\theta=\pi/3$.

##  III Stability verification of non-i.i.d. sources

The problem of stability verification of a non-i.i.d. source can be easily
stated now. Given
$\mathfrak{M}[\varepsilon,\delta,\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]$
infer the value of $\varepsilon$ and $\delta$. Perhaps the full estimation of
this density matrix is somewhat costly and we can restrict ourselves to a
simpler task. We fix the value of $\varepsilon=\varepsilon_{0}$ and have two
hypotheses, $\\{\delta\leq\delta_{0},\delta\geq\delta_{1}\\}$. The optimal
worst-case scenario probability of success is given by the Helstrom bound
Wiseman and Milburn (2009) between the states
$\mathfrak{M}_{0}:=\mathfrak{M}[\varepsilon_{0},\delta_{0},\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]$
and
$\mathfrak{M}_{1}:=\mathfrak{M}[\varepsilon_{0},\delta_{1},\left|{0}\right\rangle,\left|{\varphi}\right\rangle,n]$.

To calculate the Helstrom bound we need to calculate the trace distance
between the states $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$. We further show
that the trace distance can be bounded analytically. The following
relationship between the trace distance and the fidelity will be useful Wilde
(2013)

$1-\sqrt{\mathcal{F}(\rho,\sigma)}\leq\frac{1}{2}\left\|\rho-\sigma\right\|_{1}.$
(28)

######  Theorem 2.

The trace distance between the states $\mathfrak{M}_{0}$ and
$\mathfrak{M}_{1}$ is lower bounded by

$\frac{1}{2}\left\|\mathfrak{M}_{0}-\mathfrak{M}_{1}\right\|\geq
1-\sqrt{\mathcal{B}(\mathfrak{M}_{0},\mathfrak{M}_{1})}.$ (29)

where

$\mathcal{B}(\mathfrak{M}_{0},\mathfrak{M}_{1}):=2^{-n(H(\mathfrak{M}_{0})+H(\mathfrak{M}_{1})-2\tau-2*|H(\mathfrak{M}_{0})-H(\mathfrak{M}_{1})+2\tau|)}.$
(30)

###### Proof.

From Lemma (18) we can obtain an upper bound for fidelity using the same
arguments as for theorem (1), which means picking a specific POVM.

$\displaystyle\left\langle{\textbf{x}_{n}}\right|$
$\displaystyle\mathfrak{M}_{0}\left|{\textbf{x}_{n}}\right\rangle\left\langle{\textbf{x}_{n}}\right|\mathfrak{M}_{1}\left|{\textbf{x}_{n}}\right\rangle\leq$
$\displaystyle
c^{4*g(\chi_{n})}2^{-n(H(\mathfrak{M_{0}})+H(\mathfrak{M_{1}})-2\tau)}$ (31)

Following analogous steps of the proof of theorem 1 we have

$\displaystyle\mathcal{F}$ $\displaystyle\leq\left(\sum_{\chi_{n}\in
A^{(n)}_{\tau}\cap
B^{(n)}_{\tau}}c^{4*g(\chi_{n})}2^{-\frac{n}{2}(H(\mathfrak{M}_{0})+H(\mathfrak{M}_{1})-2\tau)}\right)^{2}$
(32) $\displaystyle\leq\left(\sum_{\chi_{n}\in A^{(n)}_{\tau}\cap
B^{(n)}_{\tau}}2^{-\frac{n}{2}(H(\mathfrak{M}_{0})+H(\mathfrak{M}_{1})-2\tau)}\right)^{2}$
(33)
$\displaystyle=2^{-n(H(\mathfrak{M}_{0})+H(\mathfrak{M}_{1})-2\tau-2*|H(\mathfrak{M}_{0})-H(\mathfrak{M}_{1})+2\tau|)}.$
(34)

Using relationship (28) we finally arrive at the lower bound for the trace
distance

$\frac{1}{2}\left\|\mathfrak{M}_{0}-\mathfrak{M}_{1}\right\|\geq
1-\sqrt{\mathcal{B}(\mathfrak{M}_{0},\mathfrak{M}_{1})}.$ (35)

∎

As in the case of theorem 1 here the fidelity decays exponentially but with a
different exponent. Observe that our bound tells us that when the fidelity is
very small then the trace distance goes to 1.

We can calculate numerically the trace distance between the operators
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$. Fixing the values of
$p_{0}=0.5,\leavevmode\nobreak\ \varepsilon=0.3,$ $\delta_{0}=1-\delta$ and
$\delta_{1}=\delta$ we have the behavior for the trace distance in Fig. (4)
for $N=7$.

Figure 4: We show the trace distance between two Markov states with
$p_{0}=0.5,\leavevmode\nobreak\ \varepsilon=0.3,$ $\delta_{0}=1-\delta$,
$\delta_{1}=\delta$ and the number of instances is $N=7$.

##  IV Discussion

We introduce the stability verification of quantum non-i.i.d. sources problem
which is closely related to the verification of states introduced by Pallister
et. al Pallister et al. (2018). The stability verification problem requires
the introduction of a type of non-i.i.d. sources that we study here. We state
and show a theorem that shows that the Markov sources are not well described
by the tensor product of a source that gradually goes to a stationary output
state. We then turn to the problem of stability verification of quantum
non-i.i.d. sources which consists of a quantum state discrimination problem.
We obtain a lower bound on the trace distance between the quantum hypotheses
in this problem. Conversely, this is an upper bound on the fidelity of such
states, this is obtained in theorem (2).

The family of states that we study here is versatile as the problem of change
point Sentís et al. (2016) can be written in terms of these states. The kind
of sources we introduce would be those that self-regulate somehow, we would be
detecting a servo system that corrects a faulty output. A full study
(parametrization) of the Markov states introduced here is the subject of
future study.

Notice that theorem (1) implies that there is a mathematical difference
between the two ways of looking at a source. First, we might think the source
momentaneously produces a density matrix that is changing at each step it
outputs a state. The other kind of states considers all the strings possible
by following the simple rule of a Markov chain and then weights the strings
according to a Markov chain. Theorem (1) tells us that these two kind of
states differ. What is happening is that there are temporal correlations that
are ignored when the formalism of tensor products is taken but that becomes
evident in the Markov state formalism.

An interesting perspective would be to think about quantum algorithms that
involve Markov states. One might speculate that there can be algorithms that
use states from definition (1) that show quantum advantages over classical
computers. These would constitute a new family of algorithms with quantum
advantage.

##  V Acknowledgements

I thank Gael Sentís for giving the idea from which this research originates
and for useful discussions on this topic. I thank Ramón Muñoz-Tapia for useful
discussions on this topic.

## References

  * Pallister et al. (2018) S. Pallister, N. Linden, and A. Montanaro, Physical Review Letters 120 (2018), URL http://dx.doi.org/10.1103/physrevlett.120.170502.
  * Nielsen and Chuang (2011) M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, New York, NY, USA, 2011), 10th ed.
  * Häffner et al. (2005) H. Häffner, W. Hänsel, C. F. Roos, J. Benhelm, D. Chek-al kar, M. Chwalla, T. Körber, U. D. Rapol, M. Riebe, P. O. Schmidt, et al., Nature 438, 643 (2005), URL http://dx.doi.org/10.1038/nature04279.
  * Huang et al. (2020) H.-Y. Huang, R. Kueng, and J. Preskill, Nature Physics 16, 1050 (2020), URL http://dx.doi.org/10.1038/s41567-020-0932-7.
  * Gross et al. (2010) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Physical Review Letters 105 (2010), URL http://dx.doi.org/10.1103/physrevlett.105.150401.
  * Aaronson (2018) S. Aaronson, in _STOC ’18: Symposium on Theory of Computing_ (ACM, 2018), URL http://dx.doi.org/10.1145/3188745.3188802.
  * Bae and Kwek (2017) J. Bae and L.-C. Kwek (2017), j. Phys. A: Math. Theor. 48 083001 (2015), eprint 1707.02571v2, URL http://arxiv.org/abs/1707.02571v2.
  * Barnett and Croke (2009) S. M. Barnett and S. Croke, Adv. Opt. Photon. 1, 238 (2009), URL http://opg.optica.org/aop/abstract.cfm?URI=aop-1-2-238.
  * Sentís et al. (2022) G. Sentís, E. Martínez-Vargas, and R. Muñoz-Tapia, Quantum 6, 658 (2022), ISSN 2521-327X, URL https://doi.org/10.22331/q-2022-02-21-658.
  * Sutter (2018) D. Sutter, _Approximate quantum markov chains_ (2018), cite arxiv:1802.05477Comment: 110 pages; PhD thesis, ETH Zurich; to appear as SpringerBriefs in Mathematical Physics; contains material from arXiv:1507.00303, arXiv:1509.07127, arXiv:1604.03023, and arXiv:1705.06749, URL http://arxiv.org/abs/1802.05477.
  * Wilde (2013) M. M. Wilde, _Quantum Information Theory_ (Cambridge University Press, 2013).
  * Cover and Thomas (2006) T. Cover and J. Thomas, _Elements of Information Theory_ (John Wiley and Sons, 2006).
  * Wiseman and Milburn (2009) H. M. Wiseman and G. J. Milburn, _Quantum Measurement and Control_ (Cambridge University Press, 2009).
  * Sentís et al. (2016) G. Sentís, E. Bagan, J. Calsamiglia, G. Chiribella, and R. Muñoz Tapia, Physical Review Letters 117 (2016), URL http://dx.doi.org/10.1103/physrevlett.117.150502.