All entangled states can generate certified randomness
Xing Chen1, ∗

arXiv:1706.03528v4 [quant-ph] 19 Sep 2017

1

Institute of Physics, Beijing National Laboratory for Condensed Matter Physics,
Chinese Academy of Sciences, Beijing 100190, China

Random number has many applications, it plays an important role in quantum information processing. It’s not difficult to generate true random numbers, the main difficulty is how to certify
the random numbers generated by untrusted devices. In [Nature(London) 464, 1021 (2010)], the
authors provided us a way to generate certified random number by Bell’s theorem. In their scheme,
we can use the nonlocal behavior of entangled states to generate certified randomness. But there are
entangled states, which admit a local hidden variable model, could not be used in their scheme. We
show in our paper that the nonlocal correlations in every entangled state can be used to generate
certified randomness, and we use Werner states as an example to show how to quantify the output
randomness.
I.

INTRODUCTION
A.

Background

Random number has many important applications
nowadays, such as quantum key distribution and the test
of Bell’s theorem. It is believed that we can’t generate true random numbers by classical processes. On the
other hand, the random numbers generated by quantum
physics are truly random because of the superposition
of quantum states. There are three kinds of quantum
random number generators(QRNG)[1], the first kind is
practical QRNG, which is built on trusted devices; the
second kind is self-testing QRNG, which can generate
true random numbers without trusting the measurement
devices; the last kind of QRNG is called semi-self-testing
QRNG, which partially combines the advantages of the
first two QRNGs.
It is not difficult to generate true random numbers by
tools of quantum physics currently. In the first kind of
QRNG, we can actually generate random numbers at a
very satisfied speed[2][3][4][5]. But these true random
numbers are not easy to be certified, because the adversaries may use memory-stick attack[6]. The so called
memory-stick attack is implemented in the following way:
the adversaries may generate a very long true random
numbers and store them in the devices, when the users
use this devices to generate random numbers, the generated random numbers are exactly what the adversaries
stored in the devices.
Nonlocality can be used to generate certified random
numbers [7][8]. In [7][8] the authors connected Bell’s theorem with randomness, the violation of Bell’s inequality
guarantees that the generated random numbers contain
true randomness, and this randomness is measurement
device independent. Especially in [8], a lower bound of
the output randomness was derived by the nonlocality in
entangled states. However, not all entangled states can

∗

xingchenphy@gmail.com

violate Bell’s inequality, and those who admit a local hidden variable model can not be used in their randomness
certification system. In order to take advantage of all
entangled states, we need a new certification scheme. Inspired by previous work [7][8], with the method provided
by [9][10][11], we connect randomness with entanglement.
In our paper, we can generate certified private randomness by any entangled state, the output randomness in
our protocol is measurement device independent and it
only needs some fresh randomness as input.

B.

Related work

Similar randomness generation protocol was also mentioned in Chaturvedi and Banik’s paper[12], but there
are some major differences between their paper and our
paper.
In their paper, Chaturvedi and Banik only gave a very
specific entangled state’s output randomness. Also, in
their paper, they claimed that the output randomness
was safe even local operations and classical communication(LOCC) was allowed between two measurement
devices. However, the untrusted measurement devices
could share some extra entangled states which are not
known by Alice and Bob, and we show in our paper that
these extra entangled states have the potential to damage
the output randomness without being detected.

C.

The result of our paper

In our paper, we give a general lower bound for our
randomness generation protocol. The same as[8], the
classical communication between different measurement
devices is forbidden in our protocol. Moreover, the lower
bound derived in our paper takes the secret entangled
states shared between untrusted measurement devices
into consideration.
Generally, the certified randomness in our scheme is
different from the randomness verified by Bell’s theorem. This is because the random numbers in these two

2
protocols are not generated in the same way. In Bell’s
scenario, the randomness is created by measuring entangled states with optimal positive operator valued measure(POVM)(in order to obtain the maximum Bell value
I), and the guessing probability of the measurement results is increasing with the decreasing of I, only when
I > 2, the guessing probability is less than 1, so this protocol needs the violation of Bell’s inequality to guarantee
the randomness in the measurement results. While in our
protocol, the inputs are nonorthogonal states, the maximum guessing probability has an upper bound which is
always less than 1, and the measurement results in our
protocol can be verified by any entangled state, so every
entangled state is a useful resource in our protocol.
Our paper is organised in the following way. In section II we give a brief introduction to the randomness
generation protocol mentioned in [8]. In section III, the
main part of our paper, we show how to construct the
protocol in our paper, and we give an example to show
how to quantify the output randomness. Section IV is a
brief conclusion.

II.

RANDOMNESS CERTIFIED BY BELL’S
THEOREM

Before the illustration of our randomness generation protocol, we first give a brief introduction to the
scheme mentioned in [8], the authors used Clauser-HorneShimony-Holt (CHSH)[13][14]correlation function
I=

X

(−1)xy [P (a = b|xy) − P (a 6= b|xy)]

(1)

x,y

as an example to show how to generate certified randomness. Where x and y represent certain type of measurement, such as the different polarization directions of
polarizers. a and b are the measurement results of Alice and Bob. Choosing certain x and y to measure the
entangled state between Alice and Bob could make the
Bell value I > 2, which means the violation of CHSH
inequality, and the violation of CHSH inequality guarantees the randomness in the measurement results a, b.
The randomness generation structure is shown in FIG.1
In this randomness generation protocol we can use
the random seed x and y to generate certified random
strings a and b if their correlation violate CHSH inequality, or more generally Bell’s inequality.(One thing we
should note here is that the input x and y should both be
true random numbers, if they can be predicted by some
adversaries, the adversaries may pre-create some correlated random numbers and store them into Alice and
Bob’s measurement devices to implement memory-stick
attack.) The private randomness in the output strings a
and b is quantified by min-entropy, and the details could
be find in the supplementary information of [8].

y

x

ρAB

Alice

Bob

a

b

FIG. 1. Randomness certified by Bell nonlocality

III.

RANDOMNESS CERTIFIED BY ANY
ENTANGLED STATE

This section is the main part of our paper. It shows
how to generate certified randomness by any entangled
state, and how to quantify the output randomness.
The randomness generation protocol mentioned in section II takes advantage of the Bell nonlocality in entangled states. However, some entangled states may admit
a local hidden variable model, and they do not contain
Bell nonlocality[15][16]. In order to make every entangled
state useful in certified randomness generation protocol,
we must use other property of entangled states instead
of Bell nonlocality. In [9], the author proved that with
nonorthogonal states as input, the measurement correlation in every entangled state cannot be created by any
separate state with local operations and shared randomness(LOSR). The protocol introduced in our paper uses
this property of entangled state. For simplicity, we use
bipartite scenario to illustrate our protocol.
First, we introduce a Bell-like inequality[10]. In bipartite scenario, Alice and Bob are two separated parties,
they share an entangled state ρAB , then they both input some quantum states {τs } and {ωt } into the measurement devices, the measurement devices then output
measurement results a and b. The correlation between a
and b is represented as P (a, b|τs , ωt ).
0

0

0

0

B
P (a, b|τs , ωt ) = T r[(PaA A ⊗QB
)(τsA ⊗ρAB ⊗ωtB )] (2)
b

where A, B is the Hilbert space of state ρAB , A0 , B 0
is the
Hilbert
space of nonorthogonal states τs , ωt , and
0
0
B
PaA A , QB
are the POVMs chosen by Alice and Bob.
b
By making suitable joint measurement on their respective part0 of ρAB0 and on the input quantum states τs , ωt
B
with PaA A , QB
, Alice and Bob can obtain the correb
lation P (a, b|τs , ωt ), which cannot be explained without
entanglement[9][11]. This allows the existence of the following linear combination of P (a, b|τs , ωt ) :
X
IρAB =
βs,t,a,b P (a, b|τs , ωt ) < 0
(3)
a,b,s,t

where βs,t,a,b are some real coefficients. The coefficients

3
βs,t,a,b could be obtained from the decomposition of entanglement witness. Because of the completeness of {τs }
and {ωt }, the entanglement witness W of ρAB could be
decomposed as
X
W =
βs,t τs> ⊗ ωt>
(4)

τs

ωt

Alice

s,t

with βs,t,1,1 = βs,t , and βs,t,a,b = 0, (a, b) 6= (1, 1), formula 3 becomes:
X
IρAB =
βs,t P (1, 1|τs , ωt ) < 0
(5)

a

ρAB

Bob

b

s,t

It is proved in [11] that this inequality is greater than
or equal to zero for any separated state with any possible POVM. For any entangled state, with the following
POVMs,
0

0

0

+
AA
P1A A = |Φ+
= I − P1A A
dA ihΦdA |, P0

Q1B

0

B

+
B
= |Φ+
dB ihΦdB |, Q0

0

B

= I − QB
1

0

B

FIG. 2. Randomness certified by any entangled state. In
this protocol, the input τs , ωt are nonorthogonal states, and
the measurement devices of Alice and Bob are not allowed to
communicate with each other. As long as the Bell-like value
IρAB is less than zero, Alice and Bob could extract certified
randomness from the measurement results a and b.

(6)

√
PdA −1
where
=
|ii ⊗ |ii/ dA , and |Φ+
dB i =
√ i=0
PdB −1
j=0 |ji ⊗ |ji/ dB . The Bell-like value IρAB will be:
X
IρAB =
βs,t P (1, 1|τs , ωt )
|Φ+
dA i

The input quantum states τs and ωt are nonorthogonal,
they could be any nonorthogonal state which forms a
complete basis. Without losing generality, they could
be:
τs = (I + v~s · ~σ )/2
ωt = (I + v~t · ~σ )/2,

s,t

T r(W ρAB )
dA dB
<0

=

(7)

which is less than zero for entangled states, this
means the measurement results a, b must be unpredictable, otherwise there would be contradiction in quantum theory[11].
With the above Bell-like correlation 5, we can design
a certified randomness generation protocol, where any
entangled state is useful to generate certified randomness. The protocol is shown in FIG.2 . In this protocol, Alice and Bob randomly input some nonorthogonal
states τs , ωt to the measurement devices, and they measure these nonorthogonal states jointly with their respective part of ρAB by the POVM 6. If the linear combination IρAB of the correlation P (1, 1|τs , ωt ) is less than zero,
then the output strings a, b contain randomness which
could not be predicted by the untrusted measurement
devices. The certified randomness in a, b is quantified by
min-entropy H∞ (AB|ST ).
We take Werner states as an example to show how to
get the lower bound of H∞ (AB|ST ). For Werner states,
1−z
I + z|Φ+ ihΦ+ |
(8)
4
√
where |Φ+ i is Bell state (|00i + |11i)/ 2. The entanglement witness is:
ρz =

Wρ z =

1
I − |Φ+ ihΦ+ |
2

(9)

(10)

where ~σ
= √
(σx , σy , σz ), s, t
∈ √
{0, 1, 2, 3},
−1,
−1)/
3, v~2 =
v~0 = (1,√1, 1)/ 3, v~1 = (1,
√
(−1, 1, −1)/ 3, v~3 = (−1, −1, 1)/ 3.
Next, we discuss the guessing probability of the measurement results. It is illustrated in the Appendix that
the average guessing probability of the measurement results a, b can be written as:
pguess =

Iρ0 − Iρz
Iρ
× 1 + z × maxPρ0 (a, b|τs , ωt ) (11)
Iρ0
Iρ0

And the upper bound of this average guessing probability
pguess is
pguess ≤

Iρoptimal − Iρz
Iρz
+
× Pρmax (a, b|τs , ωt )
Iρoptimal
Iρoptimal

For Werner states ρz , Iρz = (1 − 3z)/16, Iρoptimal =
I|Φ+ i = −1/8. Pρmax (a, b|τs , ωt ) is the maximum guessing probability with input 10 and POVM 6, it√is proved
in the Appendix that Pρmax (a, b|τs , ωt ) ≤ 9+16 3 . Then
the upper bound of the average guessing probability is
√
Iρ|Φ+ i − Iρz
Iρz
9+ 3
pguess ≤
+
×
Iρ|Φ+ i
Iρ|Φ+ i
16
√
−1/8 − (1 − 3z)/16 (1 − 3z)/16 9 + 3
=
+
×
−1/8
−1/8
16
√
7 − 3 3z − 1
=1 −
×
16
2
(12)

4
the measurement devices[11], so the generating devices
of the nonorthogonal states should be trusted. Thirdly,
any classical communication between the measurement
devices is forbidden.

b
a
a
FIG. 3. The lower bound of output randomness for Werner
states ρz . The analytical upper bound
of the average guessing
√
probability is pguess ≤ 1 − 7−16 3 × 3z−1
, and this average
2
guessing probability is the optimal one allowed by√ quantum
theory. Then we can generate at least −log2 (1− 7−16 3 × 3z−1
)
2
bits of certified randomness, and this randomness is the curve
a in the figure. Curve b represents the lower bound obtained
from semidefinite programs(SDP).

According to the definition of min-entropy, the lower
bound of the output randomness for Werner states ρz is
√
7 − 3 3z − 1
×
)
(13)
H∞ (AB|ST ) ≥ −log2 (1 −
16
2
This lower bound is shown in FIG.3.
From FIG.3 we can see that, for any entangled Werner
state, the output randomness is greater than zero, which
means any entanglement is useful in our randomness generation protocol.
Comparing the lower bound of our randomness generation protocol with the analytical lower bound of the output randomness in [8], our randomness generation protocol could take advantage of all entangled states by introducing nonorthogonal states as input, and in low degree
entanglement, our protocol could generate more secured
randomness. The compare of the output randomness is
shown in FIG.4
There are some constrains in our randomness generation protocol. Firstly, the corresponding entanglement witness must be decomposable by the nonorthogonal states and the nonorthogonal states cannot be distinguished by the measurement devices. These conditions
require that the input quantum states τs and ωt must
be nonorthogonal states which form a complete basis,
and the labels of these nonorthogonal states must not
be revealed to the measurement devices. Secondly, it is
more reasonable to trust the source devices other than

c

FIG. 4. The compare of output certified randomness of ρz in
our protocol and in Bell protocol[8]. The lower bound
of our
√
protocol is given by H∞ (AB|ST ) ≥ −log2 (1 − 7−16 3 × 3z−1
),
2
and is represented as blue line(curve a) in the figure. The
red line(curve c) is the lower bound of output randomness
certified by Bell’s
p theorem, and its formula is H∞ (AB|XY ) ≥
[1 − log2√(1 + 2 − I 2 /4)], the relationship between z and I
is I = 2 2z.

IV.

CONCLUSION

In this article, we construct a protocol to generate certified randomness by any entangled state. Similar protocol was also presented in [12], but the authors didn’t give
a general lower bound of their protocol, and the lower
bound obtained in[12] is not convincing without considering the secret entanglement shared between untrusted
measurement devices. In our article, we take this situation into consideration and we obtain a general lower
bound for this kind of randomness generation protocol.
Comparing to the protocol in [8], our protocol can
take advantage of any entangled state, and our protocol is based on entanglement theory, the correctness of
our protocol is guaranteed by the validity of quantum
physics. The randomness generation protocol in our paper shows us the deep connection between entanglement
and randomness, and further open questions may arise,
such as what’s the relationship between randomness and
entanglement, are they equal to each other? How do
nonorthogonal states assist entangled states, which admit a local hidden variable model, to generate certified
randomness?

5

[1] X. Ma, X. Yuan, Z. Cao, B. Qi, and Z. Zhang, Nature
Publishing Group , 1 (2016).
[2] F. Xu, B. Qi, X. Ma, H. Xu, H. Zheng, and H.-K. Lo,
Opt. Express 20, 12366 (2012).
[3] Z. L. Yuan, M. Lucamarini, J. F. Dynes, B. Frhlich,
A. Plews, and A. J. Shields, Applied Physics Letters 104,
261112 (2014), http://dx.doi.org/10.1063/1.4886761.
[4] Y.-Q. Nie, L. Huang, Y. Liu, F. Payne, J. Zhang, and
J.-W. Pan, Review of Scientific Instruments 86, 063105
(2015), http://dx.doi.org/10.1063/1.4922417.
[5] D. G. Marangon, G. Vallone, and P. Villoresi, Phys. Rev.
Lett. 118, 060503 (2017).
[6] A. Acı́n and L. Masanes, Nature 540, 213 (2016).
[7] R. Colbeck, arXiv preprint arXiv:0911.3814 (2009).
[8] 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, et al., Nature 464, 1021 (2010).
[9] F. Buscemi, Phys. Rev. Lett. 108, 200401 (2012).
[10] D. Rosset, C. Branciard, N. Gisin, and Y.-C. Liang, New
Journal of Physics 15, 053025 (2013).
[11] C. Branciard, D. Rosset, Y.-C. Liang, and N. Gisin,
Phys. Rev. Lett. 110, 060405 (2013).
[12] A. Chaturvedi and M. Banik, EPL (Europhysics Letters)
112, 30003 (2015).
[13] J. S. Bell, “On the einstein podolsky rosen paradox,”
(1964).
[14] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt,
Phys. Rev. Lett. 23, 880 (1969).
[15] R. F. Werner, Phys. Rev. A 40, 4277 (1989).
[16] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and
S. Wehner, Rev. Mod. Phys. 86, 419 (2014).
[17] X. Chen, X. Hu, and D. L. Zhou, Phys. Rev. A 95,
052326 (2017).
[18] A. Horn, Pacific J. Math. 12, 225 (1962).
[19] L. Vandenberghe and S. Boyd, SIAM review 38, 49
(1996).
[20] M. Navascués, S. Pironio, and A. Acı́n, Phys. Rev. Lett.
98, 010401 (2007).
[21] C. C. W. Lim, Phys. Rev. A 93, 020101 (2016).

APPENDIX

In this Appendix, we will show how to get the lower
bound of the output randomness in our randomness generation protocol.

Appendix A: The average guessing probability of
measurement results

The POVMs in our protocol are:
0

0

0

+
AA
P1A A = |Φ+
= I − P1A A
dA ihΦdA |, P0

QB
1

0

B

+
B
= |Φ+
dB ihΦdB |, Q0

0

B

= I − QB
1

0

B

(A1)

and the input nonorthogonal states are
τs = (I + v~s · ~σ )/2
ωt = (I + v~t · ~σ )/2,

(A2)

where ~σ
= √(σx , σy , σz ), s, t
= √ 0, 1, 2, 3,
−1,
−1)/
3, v~2 =
v~0 = (1,√1, 1)/ 3, v~1 = (1,
√
(−1, 1, −1)/ 3, v~3 = (−1, −1, 1)/ 3.
The average guessing probability of the measurement
results is :
Iρ0 − IρAB
Iρ
× 1 + AB × maxPρ0 (a, b|τs , ωt )
Iρ0
Iρ0
Iρoptimal − IρAB
IρAB
≤
+
× maxPρ0 (a, b|τs , ωt )
Iρoptimal
Iρoptimal
Iρ
− IρAB
IρAB
+
× Pρmax (a, b|τs , ωt )
≤ optimal
Iρoptimal
Iρoptimal

pguess =

where Iρ0 is the Bell-like value of entangled state ρ0 , which
shares the same given entanglement witness W of ρAB .
Pρ0 (a, b|τs , ωt ) is the correlation of the measurement results. We have Iρ0 ≤ IρAB < 0 and maxPρ0 (a, b|τs , ωt ) ≥
maxPρAB (a, b|τs , ωt ), otherwise, it’s meaningless for the
measurement devices to forge the measurement results.
Iρoptimal is the minimum Bell-like value for entanglement
witness W . Pρmax (a, b|τs , ωt )) is the maximum measurement correlation for any two-qubit state with POVM
(A1) and with nonorthogonal inputs (A2)
Next, we give an example to show the meaning of
the average guessing probability. Suppose the entangled
state shared between Alice and Bob is
ρz =

1−z
I + z|Φ+ ihΦ+ |
4

(A3)

the corresponding entanglement witness will be
Wρz =

1
I − |Φ+ ihΦ+ |
2

(A4)

6
deceive Alice and Bob. The entanglement witness of |Φ+ i
and ρz0 could both be Wρz , the corresponding Bell-like
value of |Φ+ i is −1/8, it’s much less than that of ρz0 .
Pρz (a, b|τs , ωt ) = zP|Φ+ i (a, b, |τs , ωt ) + (1 − z)PI (a, b|τs , ωt ) As long as the Bell-like value of the measurement results
are equal to Iρz0 , Alice and Bob will not detect any in(3 − 2a)(3 − 2b)
7 − 5a − 5b + 4ab
+ (1 − z)
=z
security in the measurement results. By using this fact,
12
16
the measurement devices can fake about 99% of the mea(3 − 2a)(3 − 2b)
(1 − 2a)(1 − 2b)
=
+z
surement results. These fake measurement results can be
16
48
stored in the measurement devices without being known
and the maximum Pρz (a, b|τs , ωt ) is
by Alice and Bob, and the Bell-like value of this fake part
can be as less as zero. For the rest 1%, the measurement
maxa,b Pρz (a, b|τs , ωt )
devices choose to jointly measure (A2) with the built-in
= Pρz (0, 0|τs , ωt )
state |Φ+ i, the Bell-like value of these measurement results is I|Φ+ i = −1/8. From the view of Alice and Bob,
1
9
(A5)
+z
=
the average Bell-like value of the whole measurement re16
48
sults would be
27 + z
=
48
1
1
Iavaerage = 0 × 99% + − × 1% = −
This equation shows that the guessing probability is be8
800
coming larger with the increasing of z. It seems without
entanglement, the output randomness is better. Actuwhich is the same as Iρz0 . The fake part of the measureally, this is not the case. From formula (A5), the guessment results is known by the measurement devices, the
ing probability is maximum when the shared entangled
guessing probability could be 1. For the measurement
state is Bell state, so the optimal cheating strategy for
results of the built-in state |Φ+ i, the maximum guessing
the measurement devices is to fake the measurement reprobability is 7/12. Then the average guessing probabilsults with built-in state |Φ+ i. Here is the detail, suppose
ity of the whole measurement results for the measurement
z = 0.34, then
devices should be 0.99×1+0.01×7/12 = 0.9958, and the
corresponding lower bound of the output randomness is
I
−log2 (0.9958) = 0.006.
ρz0 = 0.66 × + 0.34 × |Φ+ ihΦ+ |
(A6)
4
One thing we should note here is that, the untrusted
If the measurement devices do the corresponding meameasurement devices could not forge all the measurement
surement honestly, the maximum guessing probability of
results, there must be some truly random measurement
the measurement results will be
results from the shared entanglement between measurement devices to make sure the average Bell-like value is
maxa,b Pρz0 (a, b|τs , ωt )
less than zero. Otherwise, without sharing entanglement,
the measurement devices could make Iρz < 0, which is
= Pρz0 (0, 0|τs , ωt )
(A7)
contradict with quantum physics[11].
27 + 0.34
=
According to the analysis above, the average guessing
48
probability of the measurement results for Werner states
the output randomness is −log2 ( 27+0.34
) = 0.812, it’s
A3 should be:
48
quite large for a low degree entangled state like (A6).
However, most part of the output randomness cannot
I|Φ+ i − Iρz
Iρz
pguess =
×1+
× maxP|Φ+ i (a, b|τs , ωt )
be certified, the untrusted measurement devices could
I|Φ+ i
I|Φ+ i
use the following trick to jeopardize the security in the
measurement results:
The measurement correlation maxP|Φ+ i (a, b|τs , ωt ) may
When Alice and Bob used entangled state (A6) to
not be the optimal one, as there are some entangled
generate certified random number, the expected Bell-like
states’ measurement correlation larger than Bell state.
value Iρz0 is
We use Pρmax (a, b|τs , ωt )) to represent the maximum correlation allowed by quantum physics, then the upper
T r(W ρz0 )
Iρz0 =
bound of the average guessing probability is
4
1 − 3 × 0.34
(A8)
=
I|Φ+ i − Iρz
Iρz
16
pguess =
×1+
× maxP|Φ+ i (a, b|τs , ωt )
1
I|Φ+ i
I|Φ+ i
=−
800
I|Φ+ i − Iρz
Iρz
≤
+
× Pρmax (a, b|τs , ωt ))
I|Φ+ i
I|Φ+ i
Without being detected, the measurement devices
could take advantage of their built-in Bell state |Φ+ i to
(A9)
With the POVM (A1) and with nonorthogonal inputs
(A2),the correlations of measurement results are

7
each basis:

Appendix B: The maximum measurement
correlation Pρmax (a, b|τs , ωt ))

0

In this appendix, we calculate Pρmax (a, b|τs , ωt )). It is
said in [17] that any two-qubit density matrix ρAB is an
element in the linear space expanded by {σi ⊗ σj , i, j ∈
0, 1, 2, 3}(σ0 = I2×2 ). T r(ρAB ) = 1, so the coefficient
of σ0 ⊗ σ0 is 14 . Thus all the two-qubit density matrices has 15 different coefficients, they are c3i +j , i, j ∈
{0, 1, 2, 3}, (i, j) 6= {0, 0}. ρAB could be written as:

0

B
P (a, b|τs , ωt ) = T r[(PaA A ⊗ QB
)(τs ⊗ ρAB ⊗ ωt )]
b
X
0
0
B
=T r[(PaA A ⊗ QB
)(τs ⊗ (
c3i +j σi ⊗ σj ) ⊗ ωt )]
b
i,j=0,1,2,3

X
9
c3i +j P (σi ⊗ σj ))]
= +(
16
i,j=0,1,2,3
(i,j)6=(0,0)

≤

X
9
+
c i maxP (σi ⊗ σj )
16 i,j=0,1,2,3 3 +j
(i,j)6=(0,0)

ρAB =

X
1
σ0 ⊗ σ0 +
c3i +j σi ⊗ σj
4
i,j=0,1,2,3

(B1)

ρAB is a quantum state, which means the minimum
eigenvalue λminAB ≥ 0. From the property of eigenvalue,
the eigenvalue of ρAB is less than the eigenvalue sum of
its each part [18]:
X

c3i +j λ3i +j

i,j=0,1,2,3

The eigenvalues of σ0 ⊗ σ0 are {1, 1, 1, 1}, the eigenvalues
of σi ⊗ σj (i, j) 6= (0, 0) are {−1, −1, 1, 1}. We already
know the coefficient of σ0 ⊗ σ0 is 41 , then the range of
ρAB ’s eigenvalues could be represented as
X

λAB1 ≤ 1/4 −

λAB2 ≤ 1/4 −

X

c3i +j ,
(B2)
c3i +j ,

X

where Ioptimal is the minimum Bell-like value for the
given entanglement witness of entangled state ρAB .

From the perspective of the measurement devices,
searching for the optimal guessing probability pguess is
equal to solve the next optimization problem:
max pguess

i,j=0,1,2,3
(i,j)6=(0,0)

λAB4 ≤ 1/4 +

The similar analysis could be applied to any entangled state ρAB shared between Alice and Bob, thus the
upper bound of the average guessing probability in our
randomness generation protocol is:
√
Iρoptimal − IρAB
IρAB
9+ 3
pguess ≤
+
×
Iρoptimal
Iρoptimal
16

Appendix C: SDP output randomness

i,j=0,1,2,3
(i,j)6=(0,0)

λAB3 ≤ 1/4 +

0

B
where P (σi ⊗σj ) = T r[(PaA A ⊗QB
)(τs ⊗(σi ⊗σj )⊗ωt )].
b
With the given POVM(A1) and with nonorthogonal
states(A2), we can get maxP (σi ⊗ σj ) =
√
3
measurement correlation is
4 , and the maximum
√
Pρmax (a, b|τs , ωt ) = 9+16 3 . Then the upper bound of the
average guessing probability (A9) is
√
Iρ|Φ+ i − Iρz
Iρz
9+ 3
pguess ≤
+
×
Iρ|Φ+ i
Iρ|Φ+ i
16

c3i +j ,

i,j=0,1,2,3
(i,j)6=(0,0)

X

9
maxP (σi ⊗ σj )
+
16
4
0

(i,j)6=(0,0)

λAB ≤

≤

subject to
c3i +j

pguess =

i,j=0,1,2,3
(i,j)6=(0,0)

Iρ0 − IρAB
Iρ
+ AB × maxPρ0 (a, b|τs , ωt )
Iρ0
Iρ0
X
IρAB =
βs,t PρAB (1, 1|τs , ωt )
s,t

Because the minimum element of λAB is greater than or
equal to zero, we have

Iρ0 =

X

βs,t Pρ0 (1, 1|τs , ωt )

s,t

−1/4 ≤

X

c3i +j ≤ 1/4

(B3)

i,j=0,1,2,3
(i,j)6=(0,0)

The correlation P (a, b|τs , ωt ) is the correlation sum of

Iρ0 ≤ IρAB < 0
maxPρ0 (a, b|τs , ωt ) ≥ maxPρAB (a, b|τs , ωt )
This problem can be formulating as semidefinite
programs(SDP)[19][20][21], the lower bound of the output randomness obtained from SPD is shown as curve b
in FIG.3.

