# Maximal intrinsic randomness of a quantum state

Shuyang Meng  Department of Physics, National University of Singapore, 2
Science Drive 3, Singapore 117542  Fionnuala Curran  ICFO-Institut de Ciències
Fotòniques, The Barcelona Institute of Science and Technology, Av. Carl
Friedrich Gauss 3, 08860 Castelldefels (Barcelona), Spain  Gabriel Senno
Quside Technologies S.L., C/Esteve Terradas 1, 08860 Castelldefels, Barcelona,
Spain  Victoria J. Wright  ICFO-Institut de Ciències Fotòniques, The Barcelona
Institute of Science and Technology, Av. Carl Friedrich Gauss 3, 08860
Castelldefels (Barcelona), Spain  Máté Farkas  ICFO-Institut de Ciències
Fotòniques, The Barcelona Institute of Science and Technology, Av. Carl
Friedrich Gauss 3, 08860 Castelldefels (Barcelona), Spain  Valerio Scarani
Centre for Quantum Technologies, National University of Singapore, 3 Science
Drive 2, Singapore 117543  Department of Physics, National University of
Singapore, 2 Science Drive 3, Singapore 117542  Antonio Acín  ICFO-Institut de
Ciències Fotòniques, The Barcelona Institute of Science and Technology, Av.
Carl Friedrich Gauss 3, 08860 Castelldefels (Barcelona), Spain  ICREA -
Institució Catalana de Recerca i Estudis Avançats, 08010 Barcelona, Spain

###### Abstract

One of the most counterintuitive aspects of quantum theory is its claim that
there is ‘intrinsic’ randomness in the physical world. Quantum information
science has greatly progressed in the study of intrinsic, or secret, quantum
randomness in the past decade. With much emphasis on device-independent and
semi-device-independent bounds, one of the most basic questions has escaped
attention: how much intrinsic randomness can be extracted from a given state
$\rho$, and what measurements achieve this bound? We answer this question for
two different randomness quantifiers: the conditional min-entropy and the
conditional von Neumann entropy. For the former, we solve the min-max problem
of finding the measurement that minimises the maximal guessing probability of
an eavesdropper. The result is that one can guarantee an amount of conditional
min-entropy $H^{*}_{\textrm{min}}=-\log_{2}P_{\textnormal{guess}}^{*}(\rho)$
with
$P_{\textnormal{guess}}^{*}(\rho)=\frac{1}{d}\,\left(\tr\sqrt{\rho}\right)^{2}$
by performing suitable projective measurements. For the latter, we find that
its maximal value is $H^{*}=\log_{2}d-S(\rho)$, with $S(\rho)$ the von Neumann
entropy of $\rho$. Optimal values for $H^{*}_{\textrm{min}}$ and $H^{*}$ are
achieved by measuring in any basis that is unbiased to the eigenbasis of
$\rho$, as well as by other less intuitive measurements.

##  I Introduction

One of the core differences between classical and quantum physics is the
latter’s probabilistic character, which is irreducible to ignorance of
underlying variables. This difference has fundamental implications for our
worldview, but it is also attractive as a natural source of randomness for
practical uses. Indeed, Geiger counting was already used as a source of
physical randomness in the second half of the 20th century. In the past two
decades, with the development of quantum information science, a large number
of quantum random number generators (QRNGs) have been designed, and many have
been implemented, usually with light (see [1, 2] for comprehensive reviews).
The amount of randomness is naturally captured by the guessing probability
$P_{\textnormal{guess}}$: the higher the probability that the random variable
is guessed, the smaller the randomness. This intuitive characterisation was
found to have operational meaning: the min-entropy
$H_{\textrm{min}}=-\log_{2}P_{\textnormal{guess}}$ quantifies (informally) the
fraction of perfect coin tosses that can be extracted from a string generated
by the available source. But randomness is not an absolute notion: one has to
specify for whom the source should be partly unpredictable. For mere sampling
purposes, it might be sufficient to take the observed probabilities at face
value; for cryptographic applications, however, one needs to estimate the
probability that an adversary, Eve, guesses the outcomes. The resulting
randomness is called secret randomness, or intrinsic randomness.

The computation of intrinsic randomness using quantum resources and against a
quantum adversary has been studied from different perspectives. When
considering a user with classical data correlated with quantum information in
the hands of an adversary, the min-entropy quantifies the amount of perfect
random bits that the user can establish [3]. The question was also addressed
for the task of quantum key distribution, which is the extraction of secret
shared randomness. It was in this context that the idea of device-independent
certification was born: the possibility of bounding the amount of randomness
in a black-box setting, based on the observation of Bell-nonlocal correlations
[4]. Next, it was noticed that device-independent certification can be
performed for randomness as well [5, 6], providing the first disruptive case
for quantum randomness in a non-shared setting 111As long as _process
randomness_ requires characterised devices, classical and quantum RNGs compete
on the same grounds for speed, stability, practicality etc. But, given an
alleged RNG as a black box, on classical devices, one can only test product
randomness with statistical tests. While process randomness implies product
randomness, the opposite is certainly not true: one could have recorded a long
enough list of random numbers, and the device under study may just be reading
deterministically from that record.. This breakthrough happened as the race to
demonstrate loophole-free Bell tests was taking up speed. There followed an
explosion of designs and implementations of QRNGs certifiable under various
assumptions, from device-independent (disruptive, but hard to implement), to
semi-device-independent in various forms, to fully characterised (practical
and fast, but requiring a precise modelling of the setups). For these
developments, we refer to the reviews [1, 8, 9, 2].

In this flurry of activity, one of the most basic questions was somehow left
out: how much secret randomness can be extracted from a known state $\rho$. In
this paper, we solve this problem for two of the most natural and operational
measures of randomness: the conditional min-entropy and the conditional von
Neumann entropy. For the first, we show that the answer is
$H^{*}_{\textrm{min}}=-\log_{2}P_{\textnormal{guess}}^{*}(\rho)$, with

$\displaystyle
P_{\textnormal{guess}}^{*}(\rho)=\frac{1}{d}\,\big{(}\tr\sqrt{\rho}\big{)}^{2}\,,$
(1)

where $d$ is the dimension of the Hilbert space of the system, assumed to be
finite. We find a family of measurements that generate this amount of
randomness, which is closely related to the concept of ‘pretty good
measurements’ [10], originally used as a close-to-optimal way to distinguish
an ensemble of states. For the second, we find the maximal value

$\displaystyle H^{*}=\log_{2}d-S(\rho)\,,$ (2)

where $S(\rho)=-\tr\Big(\rho\log_{2}\rho\Big{missing})$ is the von Neumman
entropy of $\rho$. Interestingly, for $d>2$, we find that some measurements
that maximise $H$ do not maximise $H_{\textrm{min}}$ and vice versa.

##  II Qubit example

A case study will help to introduce the main ideas. Alice has a source that
produces a qubit. She has characterised its state to the best of her knowledge
and found it to be

$\rho=\frac{1}{2}(\mathbb{1}+m\sigma_{z})=\frac{1+m}{2}\outerproduct{0}{0}+\frac{1-m}{2}\outerproduct{1}{1}$
(3)

for some $0\leq m\leq 1$. If she measures $\sigma_{x}$, her observed
statistics will be those of a perfect unbiased coin:
$P_{A}(+1)=P_{A}(-1)=\frac{1}{2}$. Suppose now that what the source really
does is produce a pure state in each round, specifically half of the rounds
$\ket{\chi_{+}}$ and half of the rounds $\ket{\chi_{-}}$, with

$\ket{\chi_{\pm}}=\sqrt{\frac{1\pm\sqrt{1-m^{2}}}{2}}\ket{+x}+\sqrt{\frac{1\mp\sqrt{1-m^{2}}}{2}}\ket{-x}$
(4)

(indeed,
$\frac{1}{2}\ket{\chi_{+}}\bra{\chi_{+}}+\frac{1}{2}\ket{\chi_{-}}\bra{\chi_{-}}=\rho$).
If Eve knows the working of the source exactly, she will guess $i=+1$ ($i=-1$)
in the rounds when the source sent out $\ket{\chi_{+}}$ ($\ket{\chi_{-}}$).
Her guess will then be correct with probability

$P_{\textnormal{guess}}=\frac{1}{2}\Big{(}1+\sqrt{1-m^{2}}\Big{)}\,,$ (5)

which is strictly larger than $\frac{1}{2}$ when $m<1$ (i.e. when $\rho$ is
mixed). Thus, the intrinsic randomness of Alice’s protocol is less than her
apparent perfect randomness. In particular, there is no secret randomness in
the state $\rho=\frac{1}{2}\mathbb{1}$, since $P_{\textnormal{guess}}=1$ for
$m=0$.

As will be expanded on in what follows, two things are already known about
this case study and its generalisation to higher dimensions. First: we
presented this example with Eve having perfect classical information about the
source, in the sense that she knows at each instance which state has been
prepared and accordingly makes her guess on Alice’s measurement outcome.
However, the result is unchanged if Eve holds quantum side-information. Eve
then holds a purification of Alice’s state, and she measures her own system to
guess Alice’s result. Since the two scenarios are equivalent in terms of the
guessing probability, we will move from one to the other when convenient for
the argumentation. Second: having fixed Alice’s protocol (both the state and
the measurement), the maximisation of $P_{\textnormal{guess}}$ over all
decompositions of $\rho$ is a known semidefinite program (SDP) [13]; in the
case study, we have presented the optimal decomposition. What is not known is
whether $\sigma_{x}$ is the best measurement for Alice, even in the presence
of Eve: could another measurement on the same state $\rho$ decrease Eve’s
guessing probability, at the expense of biasing the observed $P_{A}$? We set
out to solve this min-max problem, and thus determine the maximal amount of
secret randomness that can be extracted from $\rho$.

##  III Setting of the problem

Alice holds a quantum state $\rho$ from a Hilbert space of dimension $d$, to
which she applies a measurement $\mathcal{M}=\\{M_{i}\\}_{i}$. We want to
determine how intrinsically random, that is, how unpredictable, the
measurement outcome is to an eavesdropper Eve, who has a more detailed
knowledge than Alice about the process, but cannot actively influence it (she
is ‘outside the lab’). Concretely, in every round, Eve knows the true state
$\rho_{c}$ produced by the source. Given this knowledge, she guesses the most
likely outcome $i=i(c)$ for that round. Without loss of generality, we can
group together all of Eve’s states that lead to the same guessed outcome,
since Eve does not gain anything in treating them as distinct. We denote by
$\rho_{i}$ the states seen by Eve, sub-normalised such that
$q_{i}=\tr\rho_{i}$ is the probability that Eve’s most likely outcome is $i$.
These states must satisfy $\sum_{i}\rho_{i}=\rho$.

Having set this stage, Eve’s average guessing probability is
$P_{\textrm{guess}}\big{(}\\{\rho_{i}\\},\mathcal{M}\big{)}=\sum_{i}\tr(M_{i}\rho_{i})$.
Since we don’t know the true states $\rho_{i}$, we need to consider the worst
case scenario, i.e. the decomposition that maximises Eve’s guessing
probability,

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})$ $\displaystyle=$
$\displaystyle\max_{\\{\rho_{i}\\}}\sum_{i}\tr(M_{i}\rho_{i})$ s.t.
$\displaystyle\rho_{i}\geq 0\,,\;\sum_{i}\rho_{i}=\rho\,.$

This optimisation is an SDP, and so can be solved efficiently. Our goal is to
compute the maximal amount of secret randomness that can be extracted from a
known state $\rho$. This requires further optimising Alice’s measurement, i.e.
computing

$P_{\textrm{guess}}^{*}(\rho)=\min_{\mathcal{M}}P_{\textrm{guess}}(\rho,\mathcal{M})\,.$
(7)

Our main result is to show that Eq. (1) is the solution to the optimisation
(7) when $\mathcal{M}$ is rank-one and projective,

$\displaystyle M_{i}=\outerproduct{m_{i}}{m_{i}}\,\,\,\,$ with
$\displaystyle\innerproduct{m_{i}}{m_{j}}=\delta_{ij}\,,\;$ $\displaystyle
i,j\in\\{1,...,d\\}\,.$ (8)

The optimisation in (7) can also be posed for general measurements, defined by
Positive Operator-Valued Measures (POVMs), but the operational interpretation
in our context is unclear. Recall that our goal is to quantify the secret
randomness in the state $\rho$. When implementing a POVM, however, the
projective measurement acts on the given state $\rho$ plus an auxiliary
system, so part of the obtained randomness may come from the latter. In fact,
to minimise the guessing probability, the auxiliary in the POVM should be in a
pure state, say $\ket{a}$, of dimension $d_{A}$. It follows from our main
result that the maximal amount of randomness obtained when implementing a
projective measurement on the global state is
$P_{\textnormal{guess}}^{*}\big{(}\rho\otimes\outerproduct{a}{a}\big{)}$. It
is easy, however, to see that
$P_{\textnormal{guess}}^{*}\big{(}\rho\otimes\outerproduct{a}{a}\big{)}=\frac{1}{d_{A}}P_{\textnormal{guess}}^{*}(\rho)$,
that is, the optimal guessing probability is that obtained by performing the
corresponding optimal projective measurements independently on the system and
the auxiliary.

##  IV Main results

######  Theorem 1.

The maximal amount of secret randomness that can be extracted from a quantum
state $\rho$ using a projective measurement is given by
$H^{*}_{\textrm{min}}=-\log_{2}P_{\textnormal{guess}}^{*}(\rho)$ with
$P_{\textnormal{guess}}^{*}(\rho)=\frac{1}{d}\,\left(\tr\sqrt{\rho}\right)^{2}$.

Without loss of generality, one can restrict the optimisation to rank-one
projective measurements (see Appendix B.1). In what follows, we outline a
proof that uses notions from state discrimination and the resource theory of
coherence, with full details in Appendix C. An alternative proof using
properties of the min-entropy and semidefinite programming is provided in
Appendix D. We prove the theorem by first proving the lower bound
$P_{\textnormal{guess}}^{*}(\rho)\geq\frac{1}{d}\,\left(\tr\sqrt{\rho}\right)^{2}$
(Lemma 1) and then showing that there exist measurements that achieve that
bound (Lemma 2).

######  Lemma 1.

The lower bound
$P_{\textnormal{guess}}^{*}(\rho)\geq\frac{1}{d}\,\left(\tr\sqrt{\rho}\right)^{2}$
holds for every state $\rho$.

###### Proof.

Using the fact that rank-one measurements are optimal for Alice, from [14,
Theorem 1, (iii)], we find

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})=$
$\displaystyle\max_{\\{\sigma\in\mathcal{I}_{\mathcal{M}}\\}}F(\rho,\sigma)\,,$
(9)

where $F$ is the Uhlmann fidelity and $\mathcal{I}_{\mathcal{M}}$ is the set
of states that are diagonal in the measurement basis $\\{\ket{m_{i}}\\}$.
Notice that $\mathbb{1}/d\in\mathcal{I}_{\mathcal{M}}$ for all $\mathcal{M}$,
so $P_{\textrm{guess}}(\rho,\mathcal{M})\geq
F(\rho,\mathbb{1}/d)=\frac{1}{d}(\tr\sqrt{\rho})^{2}$ for all $\mathcal{M}$.
Hence, $P_{\textnormal{guess}}^{*}(\rho)$ cannot be smaller than
$\frac{1}{d}(\tr\sqrt{\rho})^{2}$. ∎

######  Lemma 2.

For any state $\rho$, there exist measurements such that
$P_{\textnormal{guess}}(\rho,\mathcal{M})=\frac{1}{d}(\tr\sqrt{\rho})^{2}$.

###### Proof.

The details missing here are provided in Appendix C.1. In the quantum-side
information scenario, any $k$-outcome rank-one measurement, $\mathcal{M}$, by
Alice steers $k$ pure states on Eve. To optimise her guess, Eve has to measure
her system to optimally discriminate among these $k$ states. It is known [15]
that the best discrimination of a set of pure states is obtained with rank-one
measurements: thus, Eve will also perform a rank-one measurement. In turn,
Eve’s measurement defines an ensemble realising the mixed state $\rho$. This
ensemble consists of $k$ pure states
$\rho_{i}=\outerproduct{\tilde{\psi_{i}}}{\tilde{\psi_{i}}}$. If $\mathcal{M}$
is projective, we have $k=d$ and it follows from [16] that any decomposition
of $\rho$ in $d$ pure states is defined by the choice of an orthonormal basis
$\\{\ket{i}\\}$ through

$\displaystyle\tilde{\ket{\psi_{i}}}=\sqrt{\rho}\ket{i}$ with
$\displaystyle\innerproduct{i}{i^{\prime}}=\delta_{ii^{\prime}}\,,\;i,i^{\prime}=1,...,d\,.$
(10)

Inserting all these observations in (III), we obtain

$\displaystyle
P_{\textrm{guess}}(\rho,\mathcal{M})=\max_{\\{\ket{i}\\}}\sum_{i}\absolutevalue{\matrixelement{m_{i}}{\sqrt{\rho}}{i}}^{2}\,.$
(11)

The r.h.s. has been called the geometric coherence of $\rho$ [17] and was
shown in [18] to be equivalent to
$\max_{\\{\sigma\in\mathcal{I}_{\mathcal{M}}\\}}F(\rho,\sigma)$, with
$\mathcal{I}_{\mathcal{M}}$ the set of states diagonal in the basis
$\\{\ket{m_{i}}\\}$. If we rewrite (11) as

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})$ $\displaystyle=$
$\displaystyle\max_{\\{\Pi_{i}\\}_{i}}\sum_{i}\tr\big(\Pi_{i}\outerproduct{\tilde{\gamma_{i}}}{\tilde{\gamma_{i}}}\big{missing})$
(12) s.t. $\displaystyle\Pi_{i}\geq 0\,,\;\sum_{i}\Pi_{i}=\mathbb{1}\,,$

the r.h.s defines the optimal discrimination of the sub-normalised states
$\ket{\tilde{\gamma_{i}}}\equiv\sqrt{\rho}\ket{m_{i}}$ with a projective
measurement $\Pi_{i}=\outerproduct{i}{i}$. One then checks (see Appendix C.2)
that, under the assumption that

$\displaystyle\matrixelement{m_{i}}{\sqrt{\rho}}{m_{i}}=\frac{1}{d}\tr\sqrt{\rho}$
for all $\displaystyle i=1,...,d\,,$ (13)

the choice $\ket{i}=\ket{m_{i}}$ fulfills all the conditions for optimal
discrimination of the $\ket{\tilde{\gamma_{i}}}$ [19, 20, 21]. Thus, for
measurements satisfying (13), it holds that
$P_{\textrm{guess}}(\rho,\mathcal{M})=\sum_{i}\absolutevalue{\matrixelement{m_{i}}{\sqrt{\rho}}{m_{i}}}^{2}=\frac{1}{d}(\tr\sqrt{\rho})^{2}$.
What remains to be proven is that there exist measurements satisfying
condition (13). An example of such a measurement valid for any state is the
one defined by a basis $\\{\ket{m_{i}}\\}$ that is unbiased to the eigenbasis
of $\rho$, that is, all moduli of inner products between elements of the two
different bases equal $\frac{1}{\sqrt{d}}$. However, as we discuss in Section
V, one can find other measurements satisfying condition (13) when $d>2$. ∎

Notice that, when Alice uses measurements satisfying (13), the decomposition
(10) that is optimal for Eve is
$\tilde{\ket{\psi}_{i}}=\sqrt{\rho}\ket{m_{i}}$. If $\rho$ is full rank,
$M_{i}=\rho^{-1/2}\rho_{i}\rho^{-1/2}$ is the ‘pretty good measurement’ [10]
for the ensemble $\\{q_{i},\rho_{i}/q_{i}\\}$ steered by Eve. This measurement
is known to be optimal when special symmetries like (13) are present in the
problem [22] (in the notation of that work, the Gram matrix has entries
$G_{ij}=\matrixelement{m_{i}}{\rho}{m_{j}}$).

After solving the problem for the guessing probability, we now move to the von
Neumann entropy of the measurement outcomes conditioned on Eve’s side
information, a quantity of relevance in the multi-round setting [11, 12].

######  Theorem 2.

The maximal conditional entropy that can be extracted from a quantum state
$\rho$ using a projective measurement is $H^{*}=\log_{2}d-S(\rho)$, where
$S(\rho)=-\tr\rho\log_{2}{\rho}$ is the von Neumann entropy.

###### Proof.

From [14, Theorem 1, (i)], we have that the entropy $H(Z|E)$ of Alice’s
measurement outcomes $Z$ conditioned on Eve’s side information $E$ is

$\displaystyle H(Z|E)=D\big{(}\rho\,||\sum_{z}M_{z}\rho M_{z}\big{)}\,,$ (14)

where $\\{M_{z}\\}_{z}$ is Alice’s projective measurement and
$D(\rho||\sigma)$ is the quantum relative entropy between the states $\rho$
and $\sigma$,

$\displaystyle
D(\rho||\sigma)=\tr\Big(\rho\big{(}\log_{2}{\rho}-\log_{2}{\sigma}\big{)}\Big{missing})\,,$
(15)

which is defined when the support of $\rho$ is contained within the support of
$\sigma$. In Appendix B.2, we show that: 1) a rank-one measurement is optimal
for Alice to maximise $H(Z|E)$ for a given $\rho$, and 2) that

$\displaystyle D\big{(}\rho\,||\sum_{z}M_{z}\rho
M_{z}\big{)}=S\big{(}\sum_{z}M_{z}\rho M_{z}\big{)}-S(\rho)\,.$ (16)

In [23], the r.h.s. is shown to be equivalent to the relative entropy of
coherence of $\rho$ with respect to the measurement basis, which is used as a
quantifier of randomness.

The maximum von Neumann entropy of a state of dimension $d$ is $\log_{2}d$ and
is achieved only for maximally mixed states, so we can upper bound Eq. (16)
with

$\displaystyle H(Z|E)\leq\log_{2}d-S(\rho)\,,$ (17)

with equality reached if and only if Alice’s measurement basis
$\\{\ket{m_{z}}\\}_{z}$ leaves her system in the maximally mixed state, i.e.
if the condition

$\displaystyle\matrixelement{m_{z}}{{\rho}}{m_{z}}=\frac{1}{d}$ for all
$\displaystyle i=1,...,d\,$ (18)

is satisfied. As in the case for the condition (13) for
$H^{*}_{\textrm{min}}$, suitable measurements satisfying (18) include bases
$\\{\ket{m_{z}}\\}$ that are unbiased to the eigenbasis of $\rho$, implying
the tightness of (17). However, again, when $d>2$ we can find other suitable
measurements, as discussed in Section V. ∎

##  V Two case studies

Let us now study measurements that satisfy (13) or (18) but are not unbiased
to the eigenbasis of $\rho$. For one qubit, it is quickly verified that all
measurements that satisfy (13) are unbiased, so our first case study is for
one qutrit. Consider $\rho=\sum_{i=1}^{3}\lambda_{i}\outerproduct{i}{i}$ with
$\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}$, and the measurement basis
$\\{M_{i}=\outerproduct{m_{i}}{m_{i}}\\}_{i=1,2,3}$, with

$\displaystyle\ket{m_{1}}$
$\displaystyle=\sqrt{\frac{1+a}{3}}\ket{1}+\sqrt{\frac{1+b}{3}}\ket{2}+\sqrt{\frac{1+c}{3}}\ket{3}\,,$
$\displaystyle\ket{m_{2}}$ $\displaystyle=\sqrt{\frac{1+a}{3}}\
e^{i\theta_{1}}\ket{1}+\sqrt{\frac{1+b}{3}}\ket{2}+\sqrt{\frac{1+c}{3}}\
e^{i\theta_{2}}\ket{3}\,,$ (19)

and $\ket{m_{3}}$ defined by the normalization condition
$\sum_{i}M_{i}=\mathbb{1}$, where
$a=-({\gamma_{2}}-{\gamma_{3}})k,\,b=({\gamma_{1}}-{\gamma_{3}})k,\,c=-({\gamma_{1}}-{\gamma_{2}})k,\,k\in\mathbb{R}$
and each $\gamma_{i}\geq 0$ with $\gamma_{1}\geq\gamma_{2}\geq\gamma_{3}$. We
show in Appendix E.1 that when $k$ is in the range $-\frac{1}{2}\leq
k\leq\frac{1}{2}$, suitable parameters $\theta_{1}$ and $\theta_{2}$ can
always be chosen such that (V) defines a valid rank-one projective
measurement.

For $k\neq 0$, this measurement basis is unbiased to the eigenbasis of $\rho$
if and only if $a=b=c=0$ i.e. when $\rho$ is the maximally mixed state. When
we set $\\{\gamma_{i}\\}=\\{\sqrt{\lambda_{i}}\\}$, it is easy to show that
$\matrixelement{m_{i}}{\sqrt{\rho}}{m_{i}}=\frac{1}{3}\tr\sqrt{\rho}$ for
$i=1,2,3$, so we see that, for qutrits at least, there exist non-maximally
unbiased measurements that achieve the maximal $H^{*}_{\textrm{min}}$ for
every $\rho$. However, this measurement does not satisfy the necessary and
sufficient condition (18) to maximise the conditional entropy, except in the
special case where

$\displaystyle\lambda_{1}(\sqrt{\lambda_{2}}-\sqrt{\lambda_{3}})-\lambda_{2}(\sqrt{\lambda_{1}}+\sqrt{\lambda_{3}})-\lambda_{3}(\sqrt{\lambda_{1}}-\sqrt{\lambda_{2}})=0\,.$
(20)

Moreover, we can also consider this qutrit measurement taking
$\\{\gamma_{i}\\}=\\{\lambda_{i}\\}$. Similarly, it is straightforward to see
that this measurement satisfies (18) and thus achieves the maximal conditional
entropy $H^{*}$. To show that this measurement does not in general maximise
$H_{\textrm{min}}$, we bound Alice’s optimal guessing probability using (11)
with the basis $\\{\ket{m_{i}}\\}$,

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})=$
$\displaystyle\max_{\\{\ket{i}\\}}\sum_{i}\absolutevalue{\matrixelement{m_{i}}{\sqrt{\rho}}{i}}^{2}$
$\displaystyle\geq\sum_{i}\absolutevalue{\matrixelement{m_{i}}{\sqrt{\rho}}{m_{i}}}^{2}\,.$
(21)

After a straightforward calculation, one finds the bound

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})$
$\displaystyle\geq\frac{(\tr\sqrt{\rho})^{2}}{3}-\frac{2k^{2}}{3}\prod_{i\,>j}\big{(}\lambda_{i}-\lambda_{j}\big{)}^{2}\,,$
(22)

where $i,j\in\\{1,2,3\\}$, and we see that, at least in the case where the
eigenvalues of $\rho$ are not degenerate, this measurement cannot maximise
$H_{\textrm{min}}$.

The second case study uses two qubits. It is based on the observation (proved
in Appendix E.2) that there is no product basis unbiased to the basis

$\displaystyle\ket{\psi_{1}}$ $\displaystyle=\ket{00}$ (23)
$\displaystyle\ket{\psi_{2}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\ket{10}+\ket{11})$
$\displaystyle\ket{\psi_{3}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\omega\ket{10}+\omega^{2}\ket{11})$
$\displaystyle\ket{\psi_{4}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\omega^{2}\ket{10}+\omega\ket{11})\,,$

where $\omega=e^{i\,2\pi/3}$. Consider a state
$\rho=\sum_{k=1}^{4}\lambda_{k}\outerproduct{\psi_{k}}{\psi_{k}}$ diagonal in
this basis. To extract the maximal randomness with an unbiased measurement,
one must be able to perform entangled measurements. This is not a conceptual
problem in our setting, since there is no reason why the two qubits should be
far apart; nonetheless, such measurements may be more challenging to perform
than basic single-qubit measurements. The question is: can one extract maximal
randomness from $\rho$ by using a product basis? The answer seems to be
positive. While we do not have an analytical proof, for a large number of
choices of $\lambda$, we performed a heuristic optimisation over product
bases, both general
($\\{\ket{a,b},\ket{a,b^{\perp}},\ket{a^{\perp},c},\ket{a^{\perp},c^{\perp}}\\}$,
with six free parameters) and restricted to proper product measurements
($\\{\ket{a,b},\ket{a,b^{\perp}},\ket{a^{\perp},b},\ket{a^{\perp},b^{\perp}}\\}$,
with four free parameters). In both cases and for all states that we probed,
we numerically found measurements satisfying $\sum_{i}\Big{(}\langle
m_{i}|\sqrt{\rho}|m_{i}\rangle-\frac{\tr\sqrt{\rho}}{4}\Big{)}^{2}\leq
10^{-15}$ and others that satisfy $\sum_{i}\Big{(}\langle
m_{i}|{\rho}|m_{i}\rangle-\frac{1}{4}\Big{)}^{2}\leq 10^{-15}$, which suggests
that there exist product measurements satisfying the conditions (13) and (18).
In this family of examples, therefore, the freedom to choose a measurement
basis that is not unbiased leads to a practical advantage: it allows one to
obtain maximal randomness with product measurements.

##  VI Conclusion

It is well known that quantum physics contains an intrinsic form of
randomness, but, somewhat surprisingly, given a quantum state, it is unknown
what is the optimal measurement to extract from it the maximum amount of such
randomness. In this work, we concentrate on two different quantifiers of the
amount of randomness in a measurement’s outcomes conditioned on an adversary’s
side information: the conditional min-entropy and the conditonal von Neumann
entropy. As one might have expected, all measurements in a basis that is
unbiased to the eigenbasis of $\rho$ maximise both these conditional
entropies. However, we also find other measurements that achieve the optimal
values, providing a flexibility that may have practical implications, as in
the second case study reported. In fact, beyond its fundamental motivation,
our analysis is also relevant for the design of device-dependent QRNGs, for
which the quantum state is fully characterised. Interestingly, we find
measurements in the qutrit case that maximise either the conditional von
Neumann entropy or the conditional min-entropy, but not both quantities
simultaneously. We leave as an open question whether the sufficient condition
(13) for a measurement to minimise the guessing probability is also a
necessary one.

## Acknowledgments

This work is supported by the National Research Foundation, Singapore and
A*STAR under its CQT Bridging Grant, the Government of Spain (Severo Ochoa
CEX2019-000910-S, Torres Quevedo PTQ2021-011870, TRANQI and European Union
NextGenerationEU PRTR-C17.I1), Fundació Cellex, Fundació Mir-Puig, Generalitat
de Catalunya (CERCA program), the European Union (QSNP, 101114043 and Quantera
project Veriqtas), the ERC AdG CERQUTE, the AXA Chair in Quantum Information
Science, and the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No. 754510.

## References

  * Herrero-Collantes and Garcia-Escartin [2017] M. Herrero-Collantes and J. C. Garcia-Escartin, Quantum random number generators, Rev. Mod. Phys. 89, 015004 (2017).
  * Vaisakh Mannalath [2022] A. P. Vaisakh Mannalath, Sandeep Mishra, A comprehensive review of quantum random number generators: Concepts, classification and the origin of randomness (2022), arXiv:arXiv:2203.00261 [quant-ph] .
  * Konig  _et al._ [2009] R. Konig, R. Renner, and C. Schaffner, The operational meaning of min- and max-entropy, IEEE Transactions on Information Theory 55, 4337 (2009).
  * Acín  _et al._ [2007] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-independent security of quantum cryptography against collective attacks, Phys. Rev. Lett. 98, 230501 (2007).
  * Colbeck [2006] R. Colbeck,  _Quantum And Relativistic Protocols For Secure Multi-Party Computation_ , Ph.D. thesis, University of Cambridge (2006).
  * Pironio  _et al._ [2010] S. Pironio, A. Acín, S. Massar, A. B. de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random numbers certified by Bell’s theorem, Nature 464, 1021 (2010).
  * Note [1] As long as the process randomness needs characterised devices, classical and quantum RNGs compete on the same grounds for speed, stability, practicality etc. But, given an alleged RNG as a black box, on classical devices, one can only test product randomness with statistical tests. While process randomness implies product randomness, the opposite is certainly not true: one could have recorded a long enough list of random numbers, and the device under study may just be reading deterministically from that record.
  * Bera  _et al._ [2017] M. N. Bera, A. Acín, M. Kuś, M. W. Mitchell, and M. Lewenstein, Randomness in quantum mechanics: philosophy, physics and technology, Reports on Progress in Physics 80, 124001 (2017).
  * Acín and Masanes [2016] A. Acín and L. Masanes, Certified randomness in quantum physics, Nature 540, 213 (2016).
  * Hausladen and Wootters [1994] P. Hausladen and W. K. Wootters, A ‘pretty good’ measurement for distinguishing quantum states, Journal of Modern Optics 41, 2385 (1994).
  * Tomamichel  _et al._ [2009] M. Tomamichel, R. Colbeck, and R. Renner, A fully quantum asymptotic equipartition property, IEEE Transactions on information theory 55, 5840 (2009).
  * Dupuis  _et al._ [2020] F. Dupuis, O. Fawzi, and R. Renner, Entropy accumulation, Communications in Mathematical Physics 379, 867 (2020).
  * Law  _et al._ [2014] Y. Z. Law, L. P. Thinh, J.-D. Bancal, and V. Scarani, Quantum randomness extraction for various levels of characterization of the devices, Journal of Physics A: Mathematical and Theoretical 47, 424028 (2014).
  * Coles [2012] P. J. Coles, Unification of different views of decoherence and discord, Physical Review A 85, 10.1103/physreva.85.042103 (2012).
  * Eldar  _et al._ [2003] Y. C. Eldar, A. Megretski, and G. C. Verghese, Designing optimal quantum detectors via semidefinite programming, IEEE Transactions on Information Theory 49, 1007 (2003).
  * Hughston  _et al._ [1993] L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix, Physics Letters A 183, 14 (1993).
  * Streltsov  _et al._ [2015] A. Streltsov, U. Singh, H. S. Dhar, M. N. Bera, and G. Adesso, Measuring quantum coherence with entanglement, Physical review letters 115, 020403 (2015).
  * Xiong and Wu [2018] C. Xiong and J. Wu, Geometric coherence and quantum state discrimination, Journal of Physics A: Mathematical and Theoretical 51, 414005 (2018).
  * Holevo [1973] A. S. Holevo, Statistical decision theory for quantum systems, Journal of multivariate analysis 3, 337 (1973).
  * Helstrom [1969] C. W. Helstrom, Quantum detection and estimation theory, Journal of Statistical Physics 1, 231 (1969).
  * Yuen  _et al._ [1975] H. Yuen, R. Kennedy, and M. Lax, Optimum testing of multiple hypotheses in quantum detection theory, IEEE transactions on information theory 21, 125 (1975).
  * Dalla Pozza and Pierobon [2015] N. Dalla Pozza and G. Pierobon, Optimality of square-root measurements in quantum state discrimination, Physical Review A 91, 042334 (2015).
  * Yuan  _et al._ [2019] X. Yuan, Q. Zhao, D. Girolami, and X. Ma, Quantum coherence and intrinsic randomness, Advanced Quantum Technologies 2, 1900053 (2019).
  * Renner [2006] R. Renner, Security of quantum key distribution (2006), arXiv:quant-ph/0512258 [quant-ph] .
  * Senno  _et al._ [2022] G. Senno, T. Strohm, and A. Acín, Quantifying the intrinsic randomness of quantum measurements, arXiv preprint arXiv:2211.03581 (2022).
  * D'Ariano  _et al._ [2005] G. M. D'Ariano, P. L. Presti, and P. Perinotti, Classical randomness in quantum measurements, Journal of Physics A: Mathematical and General 38, 5979 (2005).
  * Tomamichel [2016] M. Tomamichel,  _Quantum Information Processing with Finite Resources_ (Springer International Publishing, 2016).
  * Nielsen and Chuang [2000] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2000).
  * Note [2] In [24, Lemma 3.1.13], on which Lemma 5 is based, Eq. (46) is stated in terms of $H_{\textrm{min}}(\rho^{AE}|\sigma^{E})$ and $\geq H_{\textrm{min}}(\tilde{\rho}^{AE}|\sigma^{E})$, and for any $\sigma_{E}$ (c.f. Eq. (27)). It is easy to see that (46) also holds by letting $\sigma_{E}$ be one state achieving the maximum in $H_{\textrm{min}}(A|E)_{\tilde{\rho}^{AE}}$.
  * Skrzypczyk and Cavalcanti [2023] P. Skrzypczyk and D. Cavalcanti,  _Semidefinite Programming in Quantum Information Science_, 2053-2563 (IOP Publishing, 2023).

##  Appendix A Entropy definitions

Since we will use them in more than one section of this Appendix, here we
state the definitons of the von Neumann conditional entropy and the min- and
max-entropies of bipartite states $\rho_{AE}$ [24].

######  Definition 1.

The conditional entropy of $\rho_{AE}$ is defined by

$\displaystyle H(A|E)_{\rho_{AE}}:=S(\rho_{AE})-S(\rho_{E})\,,$ (24)

where $S(\rho)=-\tr\big(\rho\log_{2}\rho\big{missing})$ is the von Neumann
entropy of $\rho$ and $\rho_{E}:=\tr_{A}{\rho_{AE}}$.

######  Definition 2.

The conditional min-entropy of $\rho_{AE}$ is defined by

$\displaystyle
H_{\min}(A|E)_{\rho_{AE}}:=\max_{\sigma_{E}}\,\,H_{\min}(\rho_{AE}|\sigma_{E})\,$
(25)

with

$\displaystyle
H_{\min}(\rho_{AE}|\sigma_{E}):=-\min\\{\lambda~{}|~{}2^{\lambda}(\mathbb{1}_{A}\otimes\sigma_{E})\geq\rho_{AE}\\}\,.$
(26)

######  Definition 3.

The conditional max-entropy of $\rho_{AE}$ is

$\displaystyle
H_{\max}(A|E)_{\rho_{AE}}:=\max_{\sigma_{E}}\,\,\log_{2}\tr\Big((\mathbb{1}_{A}\otimes\sigma_{E})\Pi_{AE}\Big{missing})\,,$
(27)

where $\Pi_{AE}$ is the projector onto the support of $\rho_{AE}$.

Notice that when the system $E$ is trivial (i.e. its Hilbert space is one-
dimensional),
$H_{\max}(A|E)_{\rho_{AE}}=H_{\max}(A)_{\rho_{A}}=\log_{2}\textrm{rank}(\rho_{A})$.
In the following, when the state $\rho_{AE}$ to which we refer is clear from
the context, we will drop the corresponding subscript in the notation for the
conditional entropies.

In our state discrimination scenario where Alice and Eve share a bipartite
state $\rho_{AE}$, given any POVM $\mathcal{M}=\\{M_{x}\\}_{x}$ for Alice, one
can define a classical-quantum state (cq-state) $\rho_{XE}$ to model the
correlations between the measurement outcomes (classical information) and the
corresponding post-measurement states $\rho_{E}^{x}$ on Eve’s subsystem,

$\displaystyle\rho_{XE}=\sum_{x}p_{x}\outerproduct{x}{x}\otimes\rho_{E}^{x}\,,$
(28)

where $p_{x}=\tr[M_{x}\rho_{A}]$,
$\rho_{E}^{x}=\tr_{A}[(M_{x}\otimes\mathbb{1}_{E})\rho_{AE}]/p_{x}$ and
$\\{\ket{x}\\}_{x}$ is some orthonormal basis representing Alice’s outcomes.
When the POVM $\mathcal{M}$ is extremal, we have the following relation
between $H_{\textrm{min}}(X|E)$ and Eve’s optimal guessing probability given
$\rho$ and $\mathcal{M}$ [3, 25]:

$\displaystyle
H_{\textrm{min}}(X|E)=-\textrm{log}_{2}P_{\textrm{guess}}(\rho,\mathcal{M})\,.$
(29)

##  Appendix B Proof of optimality of rank-one measurement operators

###  B.1 Optimality of rank-one measurements for $H^{*}_{\textrm{min}}$

We show that Alice’s optimal measurement can be assumed to be rank-one. First,
notice that any measurement can be obtained by coarse-graining a rank-one
measurement, since, given some coarse-grained (i.e. not rank-one) measurement
$\mathcal{M}_{\textrm{coarse}}=\\{M_{i}\\}_{i}$, we can represent each of its
elements in its spectral decomposition as
$M_{i}=\sum_{j}\lambda_{ij}\outerproduct{f^{i}_{j}}{f^{i}_{j}}$, with
$\lambda_{ij}\geq 0$ for all $i$, $j$. $\mathcal{M}_{\textrm{coarse}}$ can
then be seen as a coarse-graining of the fine-grained measurement
$\mathcal{M}_{\textrm{fine}}=\\{\outerproduct{f^{i}_{j}}{f^{i}_{j}}\\}_{i,j}$.
From [26], we have that the POVM $\mathcal{M}_{\textrm{coarse}}$ is extremal
if and only if the set $\\{\ket{f_{k}^{i}}\bra{f_{l}^{i}}\\}_{i,k,l}$ is
linearly independent. Therefore, the fine-grained measurement
$\mathcal{M}_{\textrm{fine}}$ corresponding to any extremal
$\mathcal{M}_{\textrm{coarse}}$ is also extremal. Furthermore, if we restrict
Alice to performing some projective measurement
$\mathcal{M}_{\textrm{coarse}}$ (a special case of an extremal measurement),
the corresponding $\mathcal{M}_{\textrm{fine}}$ will also be projective.

The coarse-graining of $\mathcal{M}_{\textrm{coarse}}$ can be seen as a
deterministic post-processing of the outcomes of
$\mathcal{M}_{\textrm{fine}}$. Consider the classical-quantum state (28)
formed by the classical information of Alice’s measurement outcomes and Eve’s
quantum states in the case of $\mathcal{M}_{\textrm{fine}}$. The cq-state for
any coarse-graining of $\mathcal{M}_{\textrm{fine}}$ can be found by applying
a deterministic function $f(x)$ to the classical register $X$,

$\displaystyle\rho_{XE}^{\textrm{coarse}}=\sum_{x}p_{x}\outerproduct{f(x)}{f(x)}\otimes\rho_{E}^{x}\,.$
(30)

Applying a function to a classical register cannot increase the conditional
min-entropy (see, e.g., [27, Proposition 6.20]). Therefore,

$\displaystyle H_{\textrm{min}}(X|E)_{\rho_{XE}^{\textrm{coarse}}}\leq
H_{\textrm{min}}(X|E)_{\rho_{XE}^{\textrm{fine}}}\,.$ (31)

Then, by (29), it is optimal for Alice to choose a rank-one measurement in
order to minimise Eve’s guessing probability.

###  B.2 Optimality of rank-one measurements for $H^{*}$

We know from [14, Theorem 1, (i)] that the conditional entropy of the
classical-quantum state formed by Alice’s outcomes $Z$ and Eve’s post-
measurement states is

$\displaystyle H(Z|E)=D\big{(}\rho\,||\sum_{i}M_{i}\rho M_{i}\big{)}\,,$ (32)

where $\\{M_{i}\\}_{i}$ is Alice’s projective measurement and
$D(\rho||\sigma)$ is the quantum relative entropy between the states $\rho$
and $\sigma$,

$\displaystyle
D(\rho||\sigma)=\tr\Big(\rho\big{(}\log_{2}{\rho}-\log_{2}{\sigma}\big{)}\Big{missing})\,,$
(33)

and is defined when the support of $\rho$ is contained within the support of
$\sigma$. $D\big{(}\rho\,||\sum_{i}M_{i}\rho M_{i}\big{)}$ can be written as

$\displaystyle D\big{(}\rho\,||\sum_{i}M_{i}\rho
M_{i}\big{)}=-S(\rho)+\tr\Big(\rho\log_{2}\big{(}\sum_{i}M_{i}\rho
M_{i}\big{)}\Big{missing})\,.$ (34)

Since $\\{M_{i}\\}_{i}$ is projective, we have
$\log_{2}\big{(}\sum_{i}M_{i}\rho
M_{i}\big{)}=\sum_{i}\log_{2}\big{(}M_{i}\rho M_{i}\big{)}$ and
$\Big{(}\log_{2}\big{(}{M_{i}\rho
M_{i}}\big{)}\Big{)}M_{j}=\delta_{ij}\log_{2}\big{(}{M_{i}\rho M_{i}}\big{)}$,
so the second term on the r.h.s. of (34) is

$\displaystyle\tr\Big(\rho\sum_{i}\log_{2}\big{(}M_{i}\rho
M_{i}\big{)}\Big{missing})$ $\displaystyle=\tr\Big(\sum_{j}M_{j}\rho
M_{j}\sum_{i}\log_{2}\big{(}M_{i}\rho M_{i}\big{)}\Big{missing})$
$\displaystyle=-S\big{(}\sum_{i}M_{i}\rho M_{i}\big{)}\,,$ (35)

and we recover Equation (16). To show that it is optimal for Alice to perform
a rank-one measurement
$\\{M^{\textrm{fine}}_{ij}=\outerproduct{f^{i}_{j}}{f^{i}_{j}}\\}_{i,j}$
rather than a coarse-grained one
$\\{M^{\textrm{coarse}}_{i}=\sum_{j}\lambda_{ij}\outerproduct{f^{i}_{j}}{f^{i}_{j}}\\}_{i}$,
denoting $\rho_{\textrm{fine}}=\sum_{i,j}M_{ij}\rho M_{ij}$ and
$\rho_{\textrm{coarse}}=\sum_{i}M^{\textrm{coarse}}_{i}\rho
M^{\textrm{coarse}}_{i}$, it is sufficient to show that

$\displaystyle S(\rho_{\textrm{fine}})\geq S(\rho_{\textrm{coarse}})\,.$ (36)

Note that the state $\rho^{\textrm{fine}}$ is the average state after
performing the measurement $\\{M^{\textrm{fine}}_{ij}\\}_{i,j}$ on
$\rho_{\textrm{coarse}}$. Projective measurements cannot increase the von
Neumann of a state (see, e.g., [28, Theorem 11.9]), so the inequality (36)
holds and it is optimal for Alice to perform a rank-one measurement to
maximise the conditional entropy.

##  Appendix C Technical steps in the proof of Theorem 1

###  C.1 Proof of Lemma 2 sketched in the main text

The main steps of the proof of Lemma 2 sketched in the text are given here in
the form of two lemmas.

######  Lemma 3.

Since $\mathcal{M}$ is rank-one, the $d$ states $\rho_{i}$ can be taken pure,
$\rho_{i}=q_{i}\outerproduct{\psi_{i}}{\psi_{i}}\equiv|\tilde{\psi}_{i}\rangle\langle\tilde{\psi}_{i}|$.
Hence,

$\displaystyle
P_{\textnormal{guess}}(\rho,\mathcal{M})=\max_{\\{\ket{\tilde{\psi}_{i}}\\}}\sum_{i}|\langle{m_{i}}|{\tilde{\psi_{i}}}\rangle|^{2}\,,$
(37)

with the constraint that
$\rho=\sum_{i=1}^{d}|\tilde{\psi}_{i}\rangle\langle\tilde{\psi}_{i}|$.

###### Proof.

We consider that Alice and Eve share a pure state $\ket{\Phi}_{AE}$ such that
$\textrm{Tr}_{E}\outerproduct{\Phi}{\Phi}=\rho_{A}:=\rho$, and Eve performs a
measurement $\mathcal{N}=\\{N_{i}\\}_{i}$. If assume that Eve performs her
measurement before Alice, we find that she steers Alice’s state $\rho_{i}$
with probability $p_{i}=\matrixelement{\Phi}{\mathbb{1}\otimes N_{i}}{\Phi}$
and we recover (III). But, because this is a no-signalling scenario, the order
of their measurements does not matter, so we could equally think of Alice as
measuring first. When Alice measures outcome $i$, since every $M_{i}$ is rank-
one, she steers the pure state
$\ket{\phi_{i}}\propto\tr_{A}(M_{i}\otimes\mathbb{1}\ket{\Phi})$. Thus

$\displaystyle P_{\textrm{guess}}(\rho,\mathcal{M})$ $\displaystyle=$
$\displaystyle\max_{\mathcal{N}}\sum_{i}\textrm{Tr}(\rho
M_{i})\matrixelement{\phi_{i}}{N_{i}}{\phi_{i}}$ s.t. $\displaystyle N_{i}\geq
0\,,\;\sum_{i}N_{i}=\mathbb{1}\,.$

The SDP (C.1) describes the optimal discrimination by Eve of an ensemble
compatible with her reduced state. It was shown in [15] that the optimal
measurement to distinguish an ensemble of pure states is made of $d$ rank-one
operators. Thus, Eve will also be performing a rank-one measurement on her
system, and the states $\rho_{i}$ steered on Alice’s side will be pure.∎

######  Lemma 4.

We will show that one can always write
$\tilde{\ket{\psi}_{i}}=\sqrt{\rho}\ket{i}$, with $\\{\ket{i}\\}$ an
orthonormal basis [Eq. (10) of the main text], and that Eq. (11) follows as a
consequence, namely

$\displaystyle P_{\textnormal{guess}}(\rho,\mathcal{M})$ $\displaystyle=$
$\displaystyle\max_{\\{\ket{i}\\}}\sum_{i}\absolutevalue{\matrixelement{m_{i}}{\sqrt{\rho}}{i}}^{2}\,.$
(39)

###### Proof.

Following [16], given two density matrices $\rho^{\prime}$ and $\rho$, there
is a one-to-one map

$\displaystyle\tilde{\ket{\psi_{i}^{\prime}}}=\rho^{\prime
1/2}\rho^{-1/2}\tilde{\ket{\psi_{i}}}\,,\ i=1,...,n$ (40)

between any two sub-normalised decompositions
$\\{\tilde{\ket{\psi_{i}^{\prime}}}\\}$ and $\\{\tilde{\ket{\psi_{i}}}\\}$
into the same number $n$ of pure states. Choosing
$\rho^{\prime}=\mathbb{1}/d$, we obtain
$\tilde{\ket{\psi_{i}}}=\rho^{1/2}\tilde{\ket{i}}$, where
$\sum_{i}\outerproduct{\tilde{i}}{\tilde{i}}=\mathbb{1}$. Since we start with
a decomposition of $\rho$ into $n=d$ pure states, and since any decomposition
of $\mathbb{1}$ into $d$ pure states defines an orthonormal basis, we find
that

$\tilde{\ket{\psi_{i}}}=\sqrt{\rho}\ket{i}$ (41)

for some $\\{\ket{i}\\}$ forming an orthonormal basis. Plugging this into
(37), we prove (39). ∎

###  C.2 Optimisation (12) in the proof of Lemma 2

The optimisation (12) is a special case of the following: given two
orthonormal bases $\\{\ket{i}\\}_{i=1,...,d}$ and
$\\{\ket{m_{i}}\\}_{i=1,...,d}$ and an operator $A$ ($\sqrt{\rho}$ in our
case) satisfying $A=A^{\dagger}\geq 0$ such that

$\displaystyle\matrixelement{m_{i}}{A}{m_{i}}=\frac{1}{d}\tr(A)\;\textrm{for
all }i=1,...,d\,,$ (42)

we want to compute

$\displaystyle P$ $\displaystyle=$
$\displaystyle\max_{\\{\ket{i}\\}}\sum_{i}|\matrixelement{i}{A}{m_{i}}|^{2}\,.$
(43)

This expression is equivalent to the probability of correct state
discrimination of an ensemble
$\sigma_{i}=\outerproduct{\tilde{\gamma_{i}}}{\tilde{\gamma_{i}}}$, with
$\ket{\tilde{\gamma}_{i}}=A\ket{m_{i}}$, using the measurement
$\\{\Pi_{i}\\}_{i=1,...,d}$. A measurement $\\{\Pi_{i}\\}_{i=1,...,d}$ is
optimal to distinguish a set of states $\\{\sigma_{i}\\}_{i=1,...d}$ if and
only if $Y\equiv\sum_{i}\sigma_{i}\Pi_{i}\geq\sigma_{j}$ for all $j=1,...,d$
[19, 20, 21]. In our case, $\\{\ket{i}\\}$ achieves the maximisation (43) if
and only if

$\displaystyle\sum_{i}A\outerproduct{m_{i}}{m_{i}}A\outerproduct{i}{i}-A\outerproduct{m_{j}}{m_{j}}A\geq
0$ $\displaystyle\,\,\textrm{for all $j$}\,.$ (44)

Let us make the guess that, under the condition (42), the optimal measurement
is given by $\ket{i}=\ket{m_{i}}$. With this, conditions (44) read

$\displaystyle\frac{\tr(A)}{d}\,A\,-\,A\outerproduct{m_{j}}{m_{j}}A:=B_{j}\geq
0$ $\displaystyle\textrm{for all $j$}\,.$ (45)

It is clear that $B_{j}=B_{j}^{\dagger}$. Moreover, using (42) we see that

$\displaystyle\matrixelement{\phi}{B_{j}}{\phi}$ $\displaystyle=$
$\displaystyle\matrixelement{m_{j}}{A}{m_{j}}\matrixelement{\phi}{A}{\phi}-\matrixelement{\phi}{A}{m_{j}}\matrixelement{m_{j}}{A}{\phi}$

for any vector $\ket{\phi}$. The r.h.s. is always non-negative when
$A=A^{\dagger}\geq 0$, because of the Cauchy-Schartz inequality applied to the
vectors $\sqrt{A}\ket{\phi}$ and $\sqrt{A}\ket{m_{j}}$. This proves that
$B_{j}\geq 0$ for all $j$, which is the desired condition, vindicating our
guess.

##  Appendix D Alternative proof of Theorem 1

###  D.1 Proof of the bound (1) on $P_{\textnormal{guess}}$

Here we provide an alternative derivation of the lower bound (1) for Eve’s
optimal guessing probability. We make use of the min- and max-entropies
defined in Appendix A and of the following lemma, which is a slight variation
222In [24, Lemma 3.1.13], on which Lemma 5 is based, Eq. (46) is stated in
terms of $H_{\textrm{min}}(\rho^{AE}|\sigma^{E})$ and $\geq
H_{\textrm{min}}(\tilde{\rho}^{AE}|\sigma^{E})$, and for any $\sigma_{E}$
(c.f. Eq. (27)). It is easy to see that (46) also holds by letting
$\sigma_{E}$ be one state achieving the maximum in
$H_{\textrm{min}}(A|E)_{\tilde{\rho}^{AE}}$. of [24, Lemma 3.1.13]:

######  Lemma 5.

Let $\\{\ket{x}\\}_{x}$ be an orthonormal basis on $\mathcal{H}_{X}$, let
$\\{\ket{\psi^{x}}\\}_{x}$ be a family of unnormalized vectors on
$\mathcal{H}_{A}\otimes\mathcal{H}_{E}$, and define

$\displaystyle\rho_{AE}$ $\displaystyle:=\outerproduct{\psi}{\psi}\textnormal{
with }\ket{\psi}=\sum_{x}\ket{\psi_{x}}\,,$ $\displaystyle\tilde{\rho}_{XAE}$
$\displaystyle:=\sum_{x}\outerproduct{x}{x}\otimes\outerproduct{\psi_{x}}{\psi_{x}}\,.$

Then,

$\displaystyle H_{\textnormal{min}}(A|E)_{\rho_{AE}}\geq
H_{\textnormal{min}}(A|E)_{\tilde{\rho}_{AE}}-H_{\textnormal{max}}(X)\,.$ (46)

Consider a pure bipartite state $\rho_{AE}=\ket{\psi}\bra{\psi}$. Given any
orthogonal basis $\\{\ket{u_{x}}\\}_{x}$ for $\mathcal{H}_{A}$, some
orthogonal basis $\\{\ket{v_{y}}\\}_{y}$ of $\mathcal{H}_{E}$ can always be
found such that the state vector $\ket{\psi}$ can be written as

$\displaystyle\ket{\psi}=\sum_{x,y}\alpha_{xy}\ket{u_{x}}\ket{v_{y}}=\sum_{x}\ket{u_{x}}\sum_{y}\alpha_{xy}\ket{v_{j}}:=\sum_{x}\ket{\psi^{x}}\,.$
(47)

If the rank-one projective measurement $\\{\outerproduct{u_{x}}{u_{x}}\\}_{x}$
is performed on $A$ and the outcome $x$ is obtained, the (unnormalized) post-
measurement state of $AE$ is

$\displaystyle\Big{(}\outerproduct{u_{x}}{u_{x}}\otimes\mathbb{1}\Big{)}\rho^{AE}\Big{(}\outerproduct{u_{x}}{u_{x}}\otimes\mathbb{1}\Big{)}$
$\displaystyle=\outerproduct{\psi^{x}}{\psi^{x}}.$

Therefore, the cq-state representing the correlations between the outcomes and
the post-measurement states on $\mathcal{H}_{A}\otimes\mathcal{H}_{E}$ is,
precisely as in Lemma 5,

$\displaystyle\tilde{\rho}_{AEX}=\sum_{x}\outerproduct{\psi^{x}}{\psi^{x}}\otimes\outerproduct{x}{x}\,..$

To prove our target bound (1), we let $\rho_{AE}$ be the initial pure state
shared by Alice and Eve and
$\mathcal{M}=\\{\outerproduct{u_{x}}{u_{x}}\\}_{x}$ be Alice’s rank-one
projective measurement. Noting that
$H_{\textrm{max}}(X)=\log_{2}\textrm{rank}(\tilde{\rho}_{X})\leq\log_{2}d$ and
that for any pure state $\rho_{AE}$

$\displaystyle H_{\textrm{min}}(A|E)=-2\log_{2}\sqrt{\rho_{A}}\,,$ (48)

returning to our usual notation with $\rho_{A}=\rho$ and $d_{A}=d$, we get
from Lemma 5 the following upper bound on
$H_{\textrm{min}}(A|E)_{\tilde{\rho}_{AE}}$,

$\displaystyle\log_{2}d-2\log_{2}\tr\sqrt{\rho}\geq
H_{\textrm{min}}(A|E)_{\tilde{\rho}_{AE}}\,.$ (49)

Finally, notice that, since Alice’s post-measurement states form an
orthonormal basis, the states $\tilde{\rho}_{XE}$ and $\tilde{\rho}_{AE}$ are
related by a unitary on the first subsystem. Therefore, using twice the data
processing inequality for conditional min-entropies [24], one can replace
$H_{\textrm{min}}(A|E)_{\tilde{\rho}_{AE}}$ with
$H_{\textrm{min}}(X|E)_{\tilde{\rho}_{XE}}$ in (49) and, together with (29),
obtain

$\displaystyle
P_{\textrm{guess}}(\rho,\mathcal{M})\geq\frac{1}{d}\Big{(}\tr\sqrt{\rho}\Big{)}^{2}.$
(50)

###  D.2 Proof that the bound (1) can be reached

Here, we provide an alternative proof using semidefinite programming that the
lower bound (1) for Eve’s optimal guessing probability can be reached when
Alice performs measurements satisfying (13). We consider the maximisation
problem (III) for the guessing probability and reduce our study to the set of
projective rank-one measurements $M_{i}=\outerproduct{m_{i}}{m_{i}}$ in
dimension $d$ that satisfy
$\tr\Big(\outerproduct{m_{i}}{m_{i}}\sqrt{\rho}\Big{missing})=\frac{1}{d}\tr\sqrt{\rho}$
for all $\ket{m_{i}}$ (the set is certainly not empty, since all measurements
in a basis that is unbiased with the eigenbasis of $\rho$ satisfy this
condition). From hereon, we assume without loss of generality that $\rho$ is
full-rank, as we note that only the projection of the measurement elements
$M_{i}$ onto the support of $\rho$ plays a role in (III). More precisely,
defining $\Pi_{\rho}$ as the orthogonal projector onto the support of $\rho$
and $M_{i}^{\prime}:=\Pi_{\rho}M_{i}\Pi_{\rho}$, we have

$\displaystyle\max_{\\{\rho_{i}\\}}\sum_{i}\tr(M_{i}\rho_{i})$
$\displaystyle=\max_{\\{\rho_{i}\\}}\sum_{i}\tr(M_{i}\,\Pi_{\rho}\rho_{i}\Pi_{\rho})$
$\displaystyle=\max_{\\{\rho_{i}\\}}\sum_{i}\tr(M_{i}^{\prime}\rho_{i})\,.$
(51)

Note too that

$\displaystyle\tr\Big(M_{i}\sqrt{\rho}\Big{missing})=\tr\Big(M_{i}^{\prime}\sqrt{\rho}\Big{missing})=\frac{1}{d}\tr\sqrt{\rho}\,.$
(52)

Then, in the case where $\rho$ is not rank-one, we can consider the problem
projected onto the support of $\rho$, using the rank-one (not necessarily
projective) measurement with elements
$M_{i}^{\prime}=\outerproduct{m_{i}^{\prime}}{m_{i}^{\prime}}$ in (III), where
$M_{i}^{\prime}$ is in dimension $r=\textrm{rank}(\rho)$, has $d$ outcomes and
satisfies
$\tr\Big(M_{i}^{\prime}\sqrt{\rho}\Big{missing})=\frac{1}{d}\tr\sqrt{\rho}$.

Now with the full-rank $\rho$ assumption, we note that, since (III) is a
semidefinite programming problem, we can define its corresponding minimisation
(or dual) problem, which is given by

$\displaystyle\beta(\rho,\mathcal{M})$
$\displaystyle=\underset{X}{\textrm{min}}\tr\big(X\rho\big{missing})\,,\qquad\textrm{s.t.}\,\,\,X\geq
M_{i}\,.$ (53)

The set of states $\\{\rho_{i}=\rho/d\\}$ and the matrix $X=2\mathbb{1}$
define strongly feasible points (i.e. points that satisfy the necessary
constraints with strict inequalities) on the dual and primal problems
respectively, so (III) and (53) both return
$P_{\textrm{guess}}(\rho,\,\mathcal{M})$. For further details on semidefinite
programming problems, see, for example, [30]. Given the measurement
$\mathcal{M}$, we can use the primal and dual problems to set upper and lower
bounds respectively on Eve’s optimal guessing probability,

$\displaystyle\sum_{i}\tr\Big(\rho_{i}M_{i}\Big{missing})\leq
P_{\textnormal{guess}}(\rho,\mathcal{M})\leq\tr\Big(X\rho\Big{missing})\,,$
(54)

where $\\{\rho_{i}\\}$ is any set of subnormalised states satisfying
$\sum_{i}\rho_{i}=\rho$ and $X$ is any positive-semidefinite matrix satisfying
$X-M_{i}\geq 0$ for all $M_{i}$. The set of states
$\rho_{i}=\sqrt{\rho}\outerproduct{m_{i}}{m_{i}}\sqrt{\rho}$ recovers the
lower bound (1). We now show that the matrix
$X=\frac{\tr\sqrt{\rho}}{d}\rho^{-\frac{1}{2}}$ satisfies

$\displaystyle
X-\outerproduct{m_{i}}{m_{i}}=\frac{\tr\sqrt{\rho}}{d}\rho^{-\frac{1}{2}}-\outerproduct{m_{i}}{m_{i}}\geq
0\qquad\forall\,\,i\,.$ (55)

We can define any vector in dimension $d$ as $\sqrt{\rho}\ket{\phi}$ for some
$\ket{\phi}$. To prove (55), it suffices to show that

$\displaystyle\matrixelement{m_{i}}{\sqrt{\rho}}{m_{i}}\matrixelement{\phi}{\sqrt{\rho}}{\phi}-\matrixelement{\phi}{\sqrt{\rho}}{m_{i}}\matrixelement{m_{i}}{\sqrt{\rho}}{\phi}\geq
0\,.$ (56)

In analogy with the proof in C.2, we see that (56) is true by applying the
Cauchy–Schwarz inequality on the vectors $\rho^{\frac{1}{4}}\ket{m_{i}}$ and
$\rho^{\frac{1}{4}}\ket{\phi}$.

Using $X=\frac{\tr\sqrt{\rho}}{d}\rho^{-\frac{1}{2}}$ in (54), we find

$\displaystyle\frac{1}{d}\Big{(}\tr\sqrt{\rho}\Big{)}^{2}\leq
P_{\textnormal{guess}}(\rho,\mathcal{M})\leq\frac{1}{d}\Big{(}\tr\sqrt{\rho}\Big{)}^{2}\,.$
(57)

This shows that the bound (1) can be saturated by measurements satisfying
(13), so we have that the optimal guessing probability for Alice given the
state $\rho$ is

$\displaystyle
P_{\textrm{guess}}^{*}(\rho)=\frac{1}{d}\Big{(}\tr\sqrt{\rho}\Big{)}^{2}\,.$
(58)

##  Appendix E Additional details from Section V

###  E.1 Valid parameters for qutrit measurement (V)

For convenience, we restate the measurement (V) in the following. Consider the
measurement basis $\\{M_{i}=\outerproduct{m_{i}}{m_{i}}\\}_{i=1,2,3}$, with

$\displaystyle\ket{m_{1}}$
$\displaystyle=\sqrt{\frac{1+a}{3}}\ket{1}+\sqrt{\frac{1+b}{3}}\ket{2}+\sqrt{\frac{1+c}{3}}\ket{3}\,,$
$\displaystyle\ket{m_{2}}$ $\displaystyle=\sqrt{\frac{1+a}{3}}\
e^{i\theta_{1}}\ket{1}+\sqrt{\frac{1+b}{3}}\ket{2}+\sqrt{\frac{1+c}{3}}\
e^{i\theta_{2}}\ket{3}\,,$ (59)

and $\ket{m_{3}}$ defined by the normalization condition
$\sum_{i}M_{i}=\mathbb{1}$, where
$a=-({\gamma_{2}}-{\gamma_{3}})k,\,b=({\gamma_{1}}-{\gamma_{3}})k,\,c=-({\gamma_{1}}-{\gamma_{2}})k,\,k\in\mathbb{R}$
and each $\gamma_{i}\geq 0$ with $\gamma_{1}\geq\gamma_{2}\geq\gamma_{3}$. To
ensure that the square root terms in the coefficients of $\ket{m_{1}}$ and
$\ket{m_{2}}$ are well-defined, we need that $1+x\geq 0$, $x\in\\{a,b,c\\}$,
which imposes the following constraint on $k$,

$\displaystyle-\frac{1}{{\gamma_{1}}-{\gamma_{3}}}\leq
k\leq\frac{1}{\max\\{{\gamma_{1}}-{\gamma_{2}},{\gamma_{2}}-{\gamma_{3}}\\}}\,.$
(60)

Furthermore, imposing $\langle{m_{1}|m_{2}}\rangle=0$ sets the following
restriction,

$\displaystyle\frac{1+a}{3}e^{i\theta_{1}}+\frac{1+b}{3}+\frac{1+c}{3}e^{i\theta_{2}}=0\,.$
(61)

Considering each of the terms in the sum as vectors in the complex plane, the
sum $\frac{1+a}{3}e^{i\theta_{1}}+\frac{1+b}{3}$ can take any absolute value
in the range $\frac{1}{3}|b-a|$ to $\frac{1}{3}|2+a+b|$ by taking an
appropriate choice of $\theta_{1}$. We then see that in order to satisfy (61),
$\frac{1+c}{3}$ must fall in this range, i.e.

$\displaystyle|b-a|\leq 1+c\leq 2+a+b\,.$ (62)

This gives the following restriction on $k$,

$\displaystyle-\frac{1}{2}\frac{1}{{\gamma_{1}}-{\gamma_{3}}}\leq
k\leq\frac{1}{2}\frac{1}{{\gamma_{1}}-{\gamma_{3}}}\,,$ (63)

which is a tighter bound than the constraint (60). Notice that the tightest
constraint is $-\frac{1}{2}\leq k\leq\frac{1}{2}$ and is obtained for pure
states.

###  E.2 A two-qubit basis that has no unbiased product basis

We will show that there is no orthonormal basis of two-qubit product states
that is unbiased to the basis:

$\displaystyle\ket{\psi_{1}}$ $\displaystyle=\ket{00}$ (64)
$\displaystyle\ket{\psi_{2}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\ket{10}+\ket{11})$
$\displaystyle\ket{\psi_{3}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\omega\ket{10}+\omega^{2}\ket{11})$
$\displaystyle\ket{\psi_{4}}$
$\displaystyle=\frac{1}{\sqrt{3}}(\ket{01}+\omega^{2}\ket{10}+\omega\ket{11}),$

where $\omega=e^{2\pi i/3}$. Firstly, we note that any orthonormal two-qubit
product basis can be expressed as either

  1. (i)

$\left\\{\ket{a}\ket{A},\ket{a}\ket{A^{\perp}},\ket{a^{\perp}}\ket{B},\ket{a^{\perp}}\ket{B^{\perp}}\right\\}$
or

  2. (ii)

$\left\\{\ket{a}\ket{A},\ket{a^{\perp}}\ket{A},\ket{b}\ket{A^{\perp}},\ket{b^{\perp}}\ket{A^{\perp}}\right\\}$

for some single qubit states $\ket{a},\ket{A},\ket{b},\ket{B}$, where $\perp$
denotes the unique orthogonal state to a given qubit state. Consider Case (i).
If this basis is unbiased to the vectors (64), we have

$\absolutevalue{\innerproduct{00}{aA}}^{2}=\absolutevalue{\innerproduct{00}{aA^{\perp}}}^{2}=\frac{1}{4}.$
(65)

Letting $\ket{A}=A_{0}\ket{0}+A_{1}\ket{1}$, etc, with $A_{0}\in\mathbb{R}$,
$A_{1}\in\mathbb{C}$, it follows that $A_{0}=A^{\perp}_{0}={1}/{2a_{0}}$. In
order for $\ket{A}$ and $\ket{A^{\perp}}$ to be orthogonal and have the same
coefficient of $\ket{0}$, both states must lie on the $XY$-plane of the Bloch
sphere, i.e. $\ket{A}=\frac{1}{\sqrt{2}}(\ket{0}+e^{iy}\ket{1})$ and
$\ket{A^{\perp}}=\frac{1}{\sqrt{2}}(\ket{0}-e^{iy}\ket{1})$ for some $0\leq
y<2\pi$. The relation between $a_{0}$ and $A_{0}$ implies that $\ket{a}$ also
lies on this plane and we can take
$\ket{a}=\frac{1}{\sqrt{2}}(\ket{0}+e^{ix}\ket{1})$ for some $0\leq x<2\pi$.
Similar reasoning shows that all the states $\ket{a},\ket{A},\ket{b},\ket{B}$
must lie in the $XY$-plane, in both Cases (i) and (ii).

We now show the states $\ket{aA}$ and $\ket{aA^{\perp}}$ cannot be mutually
unbiased to both $\ket{\psi_{2}}$ and $\ket{\psi_{3}}$. Firstly, the
equalities
$\absolutevalue{\innerproduct{\psi_{2}}{aA}}^{2}=\absolutevalue{\innerproduct{\psi_{2}}{aA^{\perp}}}^{2}=1/4$
give

$\displaystyle\cos(x)+\cos(y)+\cos(x-y)=$
$\displaystyle\cos(x)-\cos(y)-\cos(x-y)=0\,.$ (66)

Thus, we find $\cos(x)=0$, giving four possibilities for the values of
$(x,y)$: either $(\pi/2,3\pi/4)$, $(\pi/2,7\pi/4)$, $(3\pi/2,\pi/4)$, or
$(3\pi/2,5\pi/4)$. Substitution shows that none of these pairs give
$\absolutevalue{\innerproduct{\psi_{3}}{aA}}^{2}=1/4$. A similar argument
shows that bases of the form in Case (ii) also cannot be mutually unbiased to
the vectors (64).