By H ̈older inequality
∫DNdΩrN(^2) − 1
≤
(∫
DNdΩr(N(^2) −1)p
) 1 /p(∫
DN
dΩ 1q
) 1 /q
(6.12)
Picking
p=
N^2 + 1
N^2 − 1
, q=N^2 + 1
2
gives
∫
dΩrN
(^2) − 1
≤
(∫
dΩrN(^2) +1
) 1 /p(∫
dΩ
) 1 /q
(6.13)
And hence,
r^20 =
1
N− 1
=
∫
dΩrN(^2) +1
∫
dΩrN^2 −^1
≥
(∫
dΩrN(^2) +1
∫
dΩ
) 1 /q
It follows that
rN
(^2) +1
0 ≥
∫
dΩrN(^2) +1
∫
dΩ
≥aN
(^2) +1
Prob(r≥a)
This gives Eq. (6.6).
Remark 6.2.The inequality Eq. (6.6) gives an upper bound onrt:
r^2 t< r 02 +O(1/N^3 )
which is independent of random matrix theory, but weaker by factor 2.
7 Separable and entangled states
7.1 Why separability is hard
Testing whetherρis a state involves testing the positivity of its eigenvalues. The
cost of this computation is polynomial inN. Testing whetherρis separable is
harder. Properly formulated, it is known to be NP-hard, see e.g. the review [25].
Algorithms that attempt to decide whetherρis separable or not have long running
times.
A pedestrian way to see why separability might be a hard decision problem
is to consider the toy problem of deciding whether a given point x ∈ Rd lies
inside a polygon. The polygon is assumed to contain the origin and is given as