Approximate unitary $n^{2/3}$-designs give rise to quantum channels with super additive classical Holevo capacity
Aditya Nema Pranab Sen

Linear Algebraic Techniques for Weighted Spanning Tree Enumeration
    Steven Klee and Matthew T. Stamps
    
==================================================================




In a breakthrough, Hastings <cit.> showed that there
exist quantum channels whose classical Holevo capacity is 
superadditive i.e.
more classical information can be transmitted by quantum
encoding strategies entangled across multiple channel uses as compared to
unentangled quantum encoding strategies. Hastings' proof used Haar
random unitaries to exhibit superadditivity. In this paper
we show that a unitary chosen uniformly at random from an approximate 
n^2/3-design gives rise to a quantum channel with superadditive
classical Holevo capacity, where n is the dimension of the unitary 
exhibiting the Stinespring dilation of the channel superoperator.

We do so by showing that the 
minimum output von Neumann entropy of a quantum channel 
arising from an approximate unitary n^2/3-design is subadditive, which
by Shor's work <cit.> implies superadditivity of 
classical Holevo capacity of quantum channels.


We follow the geometric functional analytic approach 
of Aubrun, Szarek and 
Werner <cit.>
in order to prove our result. More precisely we prove a sharp 
Dvoretzky-like theorem stating that, with high probability under the
choice of a unitary from an approximate t-design, random 
subspaces of large dimension make a Lipschitz function take almost 
constant value. 
Such theorems were known earlier only for Haar random unitaries.
We obtain our result by appealing to Low's 
technique <cit.> for proving concentration of measure for
an approximate t-design, combined with a stratified analysis of
the variational behaviour of Lipschitz functions on the unit sphere in 
high 
dimension. The stratified analysis is the main echnical advance
of this work.

Haar random unitaries require at least Ω(n^2) random bits
in order to describe them with good precision. In contrast, there exist
exact n^2/3-designs using only O(n^2/3log n) random
bits <cit.>. Thus, 
our work can be viewed as 
a partial derandomisation of Hastings' result, and a step towards the
quest of finding an explicit quantum channel with superadditive classical
Holevo capacity.

Finally we also show that for any p > 1, approximate unitary 
(n^1.7log n)-designs
give rise to channels violating subadditivity of Rényi
p-entropy. In addition to stratified analysis, the proof of this
result uses a new technique of approximating a
monotonic differentiable function defined on a closed bounded interval
and its derivative by moderate 
degree polynomials which
should be of independent interest.




§ INTRODUCTION
 
For the past two decades, additivity conjectures have been extensively 
studied in quantum information theory e.g. 
<cit.>.
In this paper, we concentrate on the issue of additivity of classical
Holevo capacity of a quantum channel Φ, denoted henceforth by 
C(Φ). 
The quantity C(Φ)
is the number of classical bits of information per channel use that
can reliably be transmitted in the limit of infinitely many independent
uses of Φ. Capacities of classical memoryless 
channels are known to be additive, that is, the capacity of two
channels Φ and Ψ, used independently, is the sum of the 
individual capacities. In other words,
C(Φ⊗Ψ) = C(Φ) + C(Ψ).
This additivity property leads to 
a single letter characterization of the capacity of classical channels
viz. the capacity is nothing but the mutual information between the
input and channel output maximised over all possible input distributions
for one channel use
<cit.>.
For a long time, in analogy with the classical setting, it was generally 
believed that the classical Holevo capacity of a quantum channel is
additive. In fact, this belief was proven to be true for several classes
of quantum channels e.g.
<cit.>. Thus, it came as a major surprise to 
the community
when Hastings, in a major breakthrough, showed that there are indeed
quantum channels with superadditive classical Holevo capacity 
<cit.> i.e. there are quantum channels 
Φ, Ψ such that C(Φ⊗Ψ) > C(Φ) + C(Ψ).

Hastings' proof proceeds by showing that a
Haar random unitary leads to such channels with high probability,
in the sense that the unitary, when viewed suitably, is the 
Stinespring dilation of a quantum channel with superadditive classical
Holevo capacity.
The drawback of using Haar random unitaries is that they are inefficient
to implement. In fact, it takes at least 
Ω(n^2 log (1/ϵ))
random bits in order to pick an n × n Haar random unitary to 
within a precision of ϵ in the ℓ_2-distance 
<cit.>. Hence, it is of considerable interest to find an explicit
efficiently implementable unitary that gives rise to a quantum channel
with superadditive classical Holevo capacity. 

In this paper, we take the first 
step in this direction. We show that with high probability 
a uniformly random n × n unitary from an 
approximate n^2/3-design
leads to a quantum channel with 
superadditive classical Holevo capacity. Though no efficient algorithms for
implementing  approximate n^2/3-designs are known, nevertheless,
it is known that a uniformly random unitary from an exact
n^2/3-design can be sampled using
only O(n^2/3log n) random bits <cit.>.
Also, efficient constructions of approximate (log n)^O(1)-designs
are known <cit.>.
Thus, our work can be viewed as 
a partial derandomisation of Hastings' result, and a step towards the
quest of finding an explicit quantum channel with superadditive classical
Holevo capacity.

Hastings' proof was considerably simplified by Aubrun, Szarek and
Werner <cit.> who showed that existence
of channels with subadditive minimum output von Neumann entropy follows
from a sharp Dvoretzky-like theorem which states that, under the
Haar measure, random subspaces of large dimension make a Lipschitz function
take almost constant value. 
Dvoretzky's original theorem <cit.> 
stated that any centrally
symmetric convex body can be embedded with low distortion into a
section of a high dimensional unit ℓ_2-sphere. 
Milman <cit.> extended Dvoretzky's theorem by proving that,
with high probability, Haar random subspaces of an appropriate dimension
make a Lipschitz function take almost constant value. Dvoretzky's theorem
becomes the special case of Milman's theorem where the Lipschitz 
function happens to be norm induced by the centrally symmetric convex
body i.e. the norm under which the convex body becomes the unit ball.
Milman's work started a whole body of research sharpening the various
parameters of the extended Dvoretzky theorem 
e.g. <cit.> etc. However, all these works
use Haar random subspaces. A Haar random subspace of ^n of
dimension d
can be obtained by applying a Haar random unitary to a fixed subspace
of dimension d e.g. the subspace spanned by the first d standard
basis vectors of ^n. Our work is the first one to replace the
Haar random unitary in any Dvoretzky-type theorem by a uniformly 
random unitary chosen from an
approximate t-design for a suitable value of t. In other words,
our main technical result is an Aubrun-Szarek-Werner style result for
approximate t-designs instead of Haar random unitaries.
As a corollary, we obtain the subadditivity of minimum output von
Neumann entropy for unitaries chosen from an approximate n^2/3-design.
As another corollary, we obtain the subadditivity
of minimum output Rényi p-entropy for all p > 1 for 
quantum channels arising from unitaries
chosen from an approximate unitary 
(n^1.7log n)-design. 
Such a unitary can in fact be chosen from an exact 
(n^1.7log n)-design using only 
n^1.7 (log n)^2 random
bits <cit.>, which is
much less than Ω(n^2) random bits required to choose a
Haar random unitary. Subadditivity
of minimum output Rényi p-entropy for all p > 1 
was originally proved for Haar random unitaries
by Hayden and Winter <cit.>.

To prove our main technical result, we use a concentration of 
measure result by 
Low <cit.> for approximate unitary t-designs,
combined with a stratified analysis of the variational
behaviour of Lipschitz functions on the unit sphere in high 
dimension. 
We need such a fine grained stratified analysis for the
following reason. Aubrun, Szarek and 
Werner <cit.> worked with the function
f(M) := ‖ MM^† - (I/k) ‖_2, where the argument M
is a k^3-tuple rearranged to form a k × k^2 matrix. They
found subspaces of dimension k^2 where f took almost constant value.
For this, they had to do a two step analysis. The global Lipschitz
constant of f was 2 which, under naive Dvoretzky type arguments,
would only guarantee the existence of subpaces of dimension 
k^2/log k where f is almost constant. This does not
suffice to find a counter example to minimum output von Neumann
entropy. In order to shave off the log k term in the denominator,
they had to use several sophisticated arguments. One of them was the
observation that there is a high probablity subset T of 
_^k^3
on which the Lipschitz constant of f was k^-1/2. They exploited
this by their two step analysis, where they separately analysed the
behaviour of f on T and on T^c, and managed to shave off 
the log k term. For us, since we are working with designs, we
need the function to be a polynomial. Hence, instead of f, we have
to work with f^2. This seemingly trivial change introduces severe
technical difficulties. The main reason behind them is that the Lipschitz
constant of f^2 is about twice the Lipschitz constant for f
but the variation that we are looking to bound is around square of the
earlier variation! This contradiction lies at the heart of the technical
difficulty. In order to overcome this, we have to partition 
_^k^3 into a number of sets 
Ω_1, Ω_2, …, Ω_log k,
called `layers',
with local Lipschitz constants for f^2 running as 
k^-3/2, 2^3 k^-3/2, 3^3 k^-3/2, …, (log k)^3 k^-3/2. 
We have to bound
the variation of f^2 individually on Ω_i as well as put
them together to bound the variation on large subspheres of 
_^k^3. This leads to a challenging stratified 
analysis, which 
forms the main technical advance of this paper. 

Another tool developed in this work which should find use in other
situations also, is a systematic way to approximate a monotonic
differentiable function and its derivative using moderate degree
polynomials. This tool is crucially used to prove strict subadditivity
of Rényi p-entropy for any p > 1 for channels whose unitary
Stinespring dilation is chosen from an approximate design instead of
a Haar random unitary.

The power of our 
stratified analysis shows up in the consequence that the dimension of 
the subspace on which the Lipschitz function is almost constant depends
only on the smallest local Lipschitz constant, provided some mild
niceness conditions are satisfied. This gives larger dimensional subspaces
than a naive analysis which would depend on the global Lipschitz 
constant. In fact, the stratified analysis
allows us to prove a sharper Dvoretzky-type theorem even for the 
Haar measure. As a result, we can recover Aubrun, Szarek and Werner's
result for the function f directly and elegantly
instead of applying their Dvoretzky-type result twice which is rather
messy. Another powerful consequence of our stratified analysis is that 
with probability
exponentially close to one random, over Haar measure or t-design
measure, large subspaces 
make the Lipschitz function almost constant. In contrast,
Aubrun, Szarek and Werner could only guarantee constant probability close
to one for the Haar measure, and they did not consider t-designs. 
They  also stated without providing details that the existence probability
could be made exponentially close to one using a deep Levy-type lemma for
unitary matrices. In contrast our stratified analysis uses only 
the elementary Levy lemma for the unit sphere, yet it manages to prove
existence with probability exponentially close to one.

The rest of the paper is organised as follows. Section <ref>
contains notations, symbols 
definitions and preliminary tools required for the 
paper. 
Section <ref> states and proves the main technical theorems viz.
the stratified analyses for Haar measure and approximate t-designs.
Section <ref> describes the 
application to subadditivity of minimum output von Neumann entropy.
Section <ref> describes the 
application to subadditivity of minimum output Rényi p-entropy 
for p > 1. Section <ref> concludes the paper and states
some open problems for future work.



§ PRELIMINARIES


All Hilbert spaces used in this paper are finite dimensional.
The n dimensional space over complex numbers, ^n, is endowed
with the standard inner product aka the dot product:
⟨ x, y ⟩ := ∑_i=1^n x_i^* y_i.
The unit radius sphere in ^n is denoted by _^n.
The symbol _k,d 
denotes the Hilbert space of k × d linear operators over the 
complex field under the Hilbert-Schmidt inner product
⟨ M, N ⟩ :=  [M^† N], 
and _d := _d,d. 
Let (n) denote the set of n × n unitary matrices with
complex entries.
For a composite Hilbert space
^k ⊗^d, 
the notation _^d[·] denotes the operation of 
taking partial trace i.e.
tracing out the mentioned subsystem ^d. We use [·] 
to denote  the trace of the underlying operator.
Fix standard bases for Hilbert spaces A ≅^k, B ≅^d. 
Let |e_i⟩^A, |e_i⟩^B denote standard basis vectors of
A, B respectively. Any vector x ∈ A ⊗ B can be
written as x = ∑_i,jα_ij|e_i⟩^A ⊗|e_j⟩^B.
We use _d → k(x) to denote the operator
∑_i,jα_ij|e_i⟩^A ⊗⟨e_j|^B
in _k, d. Conversely, given an operator 
M = ∑_ij m_ij|e_i⟩^A ⊗⟨e_j|^B in 
_k,d, we let 
(M) := ∑_ij m_ij|e_i⟩^A ⊗|e_j⟩^B denote
the vector in ^k ⊗^d.

For Hermitian positive semidefinite operators M, we define
M^α for any α > 0 to be the unique Hermitian
operator obtained by keeping the eigenbasis same and
taking the αth power of the eigenvalues. We can define
log M similarly.
For p > 1, the notation
‖ M ‖_p denotes the Schatten p-norm 
of the matrix M, which is
nothing but the ℓ_p-norm of the vector of its singular values. 
Alternatively, ‖ M ‖_p = ( [(M^† M )^p/2])^1/p.
Then p=2 gives the Hilbert Schmidt 
norm aka the Frobenius norm which is nothing but 
‖ M ‖_2 = ‖(M) ‖_2.
Also, p = ∞ gives the operator norm aka spectral norm
which is nothing but 
‖ M ‖_∞ = 
max_v: ‖ v ‖_2 = 1‖ M v ‖_2.

Unless stated otherwise, the symbol ρ denotes a quantum 
state aka density matrix which is nothing but a Hermitian, positive
semidefinite matrix with unit trace. A rank one density matrix is called
a pure state. By the spectral theorem, any density matrix is a convex
combination of pure states.
The notation (^d) denotes the convex 
set of all d × d density matrices. We use |·⟩ to denote 
a unit vector. By a slight abuse of notation, we shall often use a unit
vector |ψ⟩ to denote a pure state |ψ⟩⟨ψ|.
A linear mapping Φ: _m →_d is called 
a superoperator. A superoperator is trace preserving if 
Φ(M) =  M for all M ∈_m. It is said to be 
positive if Φ(M) is positive semidefinite for all positive 
semidefinite M. Furthermore, Φ is said to be completely positive
if Φ⊗ is a positive superoperator for identity
superoperators  of all dimensions.
Completely positive and trace preserving (CPTP) superoperators
are referred to as quantum channels.
Unless stated otherwise, Φ, Ψ are used to denote 
quantum channels. 

A compact convex set  in ^n is called a convex body. 
The radius r() of a convex body  is defined as

    r() := min_x ∈max_y ∈‖ x - y ‖_2.

Any point x ∈ achieving the minimum above is said to be a
centre of .
The convex body  is said
to be centrally symmetric iff for every x ∈^n,
x ∈↔ -x ∈. The zero vector is a centre
of a centrally symmetric convex body. A centrally symmetric convex body
lying in ^n
can be thought of as the unit sphere of a suitable notion of norm
in ^n. Conversely for any norm in ^n, the unit sphere under
the norm forms a centrally symmetric convex body. 



 §.§ Entropies and norms


The von Neumann entropy of a  quantum state 
ρ is defined as 

    S(ρ) := - [ρlogρ].

For all p > 1, the Rényi p-entropy of a quantum state 
ρ is defined as 

    S_p(ρ) := 1/1-plogρ^p =
    -p/p-1log‖ρ‖_p.


It turns out that
S(ρ) = lim_p ↓ 1 S_p(ρ) =: S_1(ρ).
Also, it can be shown that for p ≥ 1, S_p(·) 
is concave in its argument.

For p ≥ 1, the minimum output Rényi p-entropy of 
a quantum channel Φ is defined as :

    S_p^min(Φ) :=
    min_ρ∈(^m) S_p(Φ(ρ))


By an easy concavity argument it can be seen that above 
minimum is achieved on a pure state.
Equivalently, to obtain S_p^min(Φ) for p > 1 
we must maximise 
‖Φ(ρ) ‖_p for all input states ρ. This quantity is
also known as the 
1 → p superoperator norm of superoperator 
Φ: _m →_d:

    ‖Φ‖_1 → p 
    := max_M ∈_m: ‖ M ‖_1 = 1‖Φ(M) ‖_p.

By an easy convexity argument it can be seen that the above
maximum is achieved on a pure state i.e.

    ‖Φ‖_1 → p = 
    max_x ∈^m: ‖ x ‖_2 = 1‖|x⟩⟨x|‖_p.

Thus, the additivity conjecture for minimal output p-Rényi p-entropy,
p > 1, 
for quantum channels Φ and Ψ is equivalent to 
multiplicativity of 1 → p-norms of quantum channels viz.
‖Φ⊗Ψ‖_1 → p?=‖Φ‖_1 → p·‖Ψ‖_1 → p.
This equivalence will be used in Section <ref> to 
give a counter example to additivity 
conjecture for all p > 1 where the Stinespring dilation of the
quantum channel will be described 
from a unitary chosen uniformly at random from an approximate t-design.
The equivalent result for Haar random unitaries was originally 
proved by Hayden and Winter <cit.>.

We heavily use the one-one correspondence between quantum channels and 
subspaces of 
composite Hilbert spaces, originally proved by  Aubrun, Szarek and Werner 
<cit.>, in this paper. 
Let  be a subspace of 
^k ⊗^d of dimension m. Identify  with
^m through an isometry 
V : ^m →^k ⊗^d whose range is 
. Then, the corresponding quantum channel 
Φ_ : _m →_k is defined by
Φ_(ρ) := _^d(V ρ V^†).
Using this equivalence and the fact that for p > 1 the 
1 → p-superoperator norm is achieved on pure input
states, we can write <cit.>

    ‖Φ_‖_1 → p = 
    max_x ∈: ‖ x ‖_2 = 1‖_^d|x⟩⟨x|‖_p =
    max_x ∈: ‖ x ‖_2 = 1‖_d → k(x) ‖_2p^2.


In an important paper, Shor <cit.> proved that several 
additivity conjectures
for quantum channels were in fact equivalent to the additivity
of minimum output von Neumann entropy of a quantum channel.
More specifically, Shor showed that if there is a quantum channel Φ
whose minimum output von Neumann entropy is subadditive, then there
are quantum channels Ψ_1, Ψ_2 exhibiting superadditive
classical Holevo capacity viz.
C(Ψ_1 ⊗Ψ_2) > C(Ψ_1) + C(Ψ_2). This equivalence
was used as a starting point by Hastings <cit.> in his 
proof that there are
channels with superadditive classical Holevo capacity. Aubrun, Szarek and
Werner <cit.>, as well as this paper
also have the same starting point. For this, we need the following
fact.
[] 

Let a quantum
channel Φ_: _m →_k be described by a subspace
≤^k ⊗^d of dimension m. Then,

    S_min(Φ_) 
        =    log k -
    k ·max_ρ∈(^m)‖Φ(ρ) - /k‖_2^2 
        =    log k -
    k ·max_x ∈: ‖ x ‖_2 = 1‖ 
    (_d → k(x)) (_d → k(x))^† 
    - /k‖_2^2.



We will need the following result proved by Hayden and 
Winter <cit.> 
that upper bounds S_p^min(Φ⊗Φ̅) where
Φ̅ denotes the CPTP superoperator obtained by taking complex 
conjugate of the CPTP superoperator Φ. 


Let V : ^m →^k ⊗^d be an 
isometry describing the quantum channel 
Φ: ρ↦_^d [V ρ V^†]. Let 
|ϕ⟩ denote the maximally entangled state in 
^m ⊗^m. Suppose m ≤ d.
Then (Φ⊗Φ̅)(|ϕ⟩⟨ϕ|) has a 
singular value 
not less than m/kd. 
Hence for all p > 1,

    ‖Φ⊗Φ̅‖_1 → p≥‖Φ⊗Φ̅‖_1 →∞≥m/kd.

Moreover,

    S_min(Φ⊗Φ̅) ≤ 
    2 log k - m/kdlog k + 
    O (m/kdlogd/m + 1/k).





 §.§ Polynomial approximation of monotonic functions

We will need the following facts about step functions and their analytic
and polynomial approximations when we prove our result on strict
subadditivity of minimum output Rényi p-entropy for 
channels chosen from approximate t-designs.


The (Heaviside) step function is a function 
→ [0, 1] defined as follows:

    s(x) :=
    [   0    ; 1/2    ;   1   . ]




The error function is a function → (-1, 1) defined
as follows:

    (x) :=
    2/√(π)∫_0^x e^-t^2  dt.



The error function is a monotonically increasing function. 
For positive x, (x) is nothing but the probability that the
normal distribution with mean 0 and variance 1/2 gives a point in
the interval [-x, x]. From the error function,
we get the so-called sigmoid function
Φ(x) := 1/2 + 1/2(x) which is nothing but
the cumulative distribution function of the above normal distribution.
The sigmoid function is a monotonically increasing function approximating
the step function in the following sense. Let 0 < ϵ < 1.

    Φ(x)  [                =       s(x) = 1/2                ,;                >         s(x) = 0                ,;                <              1/2                ,;                <         s(x) = 1                ,;                >              1/2                ,;                > s(x) - ϵ = 1 - ϵ                ,;                <     s(x) + ϵ = ϵ                , ]   Φ'(x)  [      = 1/√(π)      ,;      < 1/√(π)      ,;      >      0      ,;      <      ϵ      . ]

The last two statements for Φ(x) above hold for 
small ϵ and follow from 
the bound
1 - Φ(x) ≤1/2 x √(π) e^-x^2.

The error function has the following rapidly converging Maclaurin
series:

    (x) =
    2/√(π)∑_i=0^∞ (-1)^i x^2i+1/i! (2i+1).

It is obtained by integrating termwise the Maclaurin series
e^-x^2 =
∑_i=0^∞ (-1)^i x^2i/i!.
Since both the above series are  alternating series of positive and 
negative terms,
truncating the Maclaurin expansion of Φ(x) at i = n for 
odd n > x^2 gives us 
a polynomial p_n(x) of degree 2n+1 such that

    p_n(x)  [          = Φ(x) = 1/2          ,;          >       Φ(x)          ,;          <       Φ(x)          ,;          >   Φ(x) - ϵ          ,;          <   Φ(x) + ϵ          . ]

Moreover, the derivative p'_n(x) is a polynomial of degree 2n 
satisfying

    p'_n(x)  [              = Φ'(x) = 1/√(π)              ,;              ≤          Φ'(x)              ,;              >      Φ'(x) - ϵ              . ]

For the last two claims in Equation <ref> and the last claim in 
Equation <ref>, 
we used Stirling's approximation
n^n e^-n < n!
which holds for all positive integers n.

We will also need to upper bound the sum of absolute values   of the
coefficients of p_n(x), denoted by α(p_n(x)). For this we
observe that
α(p_n(x)) = 
|p_n(√(-1))| ≤1/2 +  e/√(π).
We can now conclude that for m > 0, 0 ≤ q ≤ A, 

    [                                                                                                     α(p_n(m(x-q)))                                                                                                                  = 1/2 +  1/√(π)α(
    ∑_i=0^n (-1)^i
    (m(x-q))^2i+1/i! (2i + 1)
    ) 
     ≤ 1/2 +  1/√(π)α(
    ∑_i=0^n
    (m(x+q))^2i+1/i! (2i + 1)
    );                                                                                                                                                                                                                                     =                              1/2 +  1/√(π)∑_i=0^n
    (m(1+q))^2i+1/i! (2i + 1) ≤ 1/2 +  1/√(π)∑_i=0^∞(m(1+A))^2i+1/i!;                                                                                                                                                                                                                                     =                                                                 1/2 +  m(1+A) e^(m(1+A))^2/√(π) ≤ 
    e^2 (m(1+A))^2. ]


Let f: [0, A] → be a continuous non-decreasing function.
The global Lipschitz constant of f is defined by

    L := 
    sup_x,y ∈ [0, A], x < yf(y) - f(x)/y - x.

If L is finite, then we say that f is L-Lipschitz.
Let ϵ > 0.
For an element x ∈ [0, A], the ϵ-smoothed local
Lipschitz constant of f at x is defined by

    L^ϵ_x :=
    sup_x,y ∈ f^-1((f(x) - ϵ, f(x) + ϵ)), x < yf(y) - f(x)/y - x.

It is obvious that L_x^ϵ≤ L. If f is differentiable,
then f'(x) ≤ L^ϵ_x.

We now give a general proposition showing how to approximate
a continuous non-decreasing Lipschitz function by a polynomial 
of moderate degree.


Let f: [0,A] → [0,1] be a continuous non-decreasing onto 
function with global Lipschitz constant L.
Fix 0 < ϵ < 1. 
Let L_x^ϵ denote the ϵ-smoothed local Lipschitz 
constant of f at x.
Let n be the minimum positive odd integer satisfying
m A ≤ϵ^1/n√(n)/2,
where
m := 2 L/ϵ√(lnϵ^-2).
Define 
m_x := 2 L_x^ϵ/ϵ√(lnϵ^-2).
Then there is a polynomial p(x) of degree at most 2n + 1
such that 

    p(x) - 2 ϵ≤ f(x) ≤ p(x) + 3 ϵ,    
    -m ϵ^2 < p'(x) < ϵ m_x + m ϵ^2,    ∀ x ∈ [0,A].

Moreover the sum of absolute values of the coefficients of p(x),
denoted by α(p(x)), is at most 
e^2 ((A+1)m)^2. 


Subdivide the range [0,1] into t := ⌈ 1/ϵ⌉ many 
closed subintervals each of length ϵ except possibly the last one
whose length ϵ' may be less than ϵ. 
Denote their inverse images 
under f by I_1, I_2, …, I_t.
For 1 ≤ i < t, let p_i be the single
point intersection of closed subintervals I_i and I_i+1; define
p_0 := 0, p_t := A.
The subinterval I_i, 1 ≤ i < t is of length at least 
ϵ/2 L_p_i^ϵ/2 +
ϵ/2 L_p_i-1^ϵ/2,
I_t is of length at least 
ϵ'/2 L_p_t^ϵ/2 +
ϵ'/2 L_p_t-1^ϵ/2.
Observe that max_i L_p_i^ϵ/2≤  L.
Define the function

    g_1(x) := 
    ϵ∑_i=1^t - 1 s(x - p_i).

Then g_1(x) ≤ f(x) ≤ g_1(x) + ϵ for all x ∈ [0,A].

Define 
m_i := 2 L_p_i^ϵ/2/ϵ√(lnϵ^-2),
1 ≤ i ≤ t. Then m ≥max_i m_i.
Approximate the step function s(x - p_i) by the sigmoid function
Φ(m_i (x - p_i)). By Equation <ref>,

    Φ(m_i (x-p_i))  [                          =           s(x - p_i) = 1/2                          ,;                          >             s(x - p_i) = 0                          ,;                          <                        1/2                          ,;                          <            s(x - p_i)  = 1                          ,;                          >                        1/2                          ,;                          > s(x - p_i) - ϵ^2 = 1 - ϵ^2                          ,;                          <    s(x - p_i) + ϵ^2  = ϵ^2                          . ]

Define the function

    g_2(x) := 
    ϵ∑_i=1^t - 1Φ(m_i (x - p_i)).

It is now easy to see that
g_2(x) - ϵ≤ g_1(x) ≤ g_2(x) + ϵ
for all x ∈ [0, A]. Thus,

    g_2(x) - ϵ≤ f(x) ≤ g_2(x) + 2 ϵ   ∀ x ∈ [0,A].

Also,

    0 < g'_2(x) < ϵ m_i + m ϵ^2,    
    x ∈ 
    [
    p_i - ϵ/2 L_p_i^ϵ/2, 
    p_i + ϵ/2 L_p_i^ϵ/2
    ]
    ,

and 
0 < g'_2(x) < m ϵ^2
otherwise.

We now approximate the sigmoid function Φ(m_i (x-p_i)) by 
the polynomial p_n(m_i (x - p_i)) for 
m_i A ≤ m A < ϵ^1/n√(n)/2, n odd.
From Equations <ref>, <ref> we get

    p_n(m_i (x-p_i))  [                      =   Φ(m_i (x-p_i)) = 1/2                      ,;                      >       Φ(m_i (x - p_i))                      ,;                      <      Φ(m_i (x -  p_i))                      ,;                      > Φ(m_i (x - p_i)) - ϵ^2                      ,;                      < Φ(m_i (x - p_i)) + ϵ^2                      , ]


    p'_n(m_i (x-p_i))  [                          = Φ'(m_i (x-p_i)) = m_i/√(π)                          ,;                          ≤         Φ'(m_i (x -  p_i))                          ,;                          >    Φ'(m_i (x - p_i)) - ϵ^2                          . ]

Define the degree 2n+1 polynomial

    p(x) := 
    ϵ∑_i=1^t - 1 p_n(m_i (x - p_i)).

It is now easy to see that

    p(x) - ϵ^2 ≤ g_2(x) ≤ p(x) + ϵ^2,
       
    p'(x) ≤ g'_2(x) ≤ p'(x) + m ϵ^2,

for all x ∈ [0, A]. Thus,

    p(x) - 2 ϵ≤ f(x) ≤ p(x) + 3 ϵ   ∀ x ∈ [0,A],

and

    -m ϵ^2 < p'(x) < ϵ m_i + m ϵ^2,    
    x ∈ 
    [
    p_i - ϵ/2 L_p_i^ϵ/2, 
    p_i + ϵ/2 L_p_i^ϵ/2
    ]
    ,

and 
-m ϵ^2 < p'(x) < m ϵ^2
otherwise. Now observe that if
x ∈ 
[
p_i - ϵ/2 L_p_i^ϵ/2, 
p_i + ϵ/2 L_p_i^ϵ/2
],
m_x ≥ m_i. Hence we can always say that

    -m ϵ^2 < p'(x) < ϵ m_x + m ϵ^2    ∀ x ∈ [0, A].


Finally by Equation <ref>,

    α(p(x)) ≤ϵ∑_i=1^t-1α(p_n(m_i (x-p_i))) ≤ϵ∑_i=1^t-1 e^2((A+1)m_i)^2≤
    e^2((A+1)m)^2.

This completes the proof of the proposition.




  
Remarks:
 


1.  
Any continuous non-decreasing Lipschitz
function on a closed bounded interval can be converted into a function
of the above type by translating the domain and the range and scaling
the range.

2.  
A similar proposition can be proved for approximating a monotonically 
non-increasing Lipschitz function by a polynomial.



 §.§ Concentration results for Lipschitz functions

We now state some basic definitions and facts from geometric functional
analysis that will be used in the proof of our main result.

A function f:X → defined over a metric 
space X is said to 
be L-Lipschitz if
∀ x, y ∈ X it satisfies the following inequality:

    | f(x)-f(y) |≤ L · d(x,y).



Let X be a compact metric space. An ϵ-net 𝒩 of
X is a finite set of points such that for any point x ∈ X, there is
a point x' ∈𝒩 such that d(x,x') ≤ϵ.

Note that compactness guarantees that finite sized ϵ-nets exist
for all ϵ > 0.

We will need the following definition and fact from 
<cit.>.

A function f:X → defined over a normed linear 
space X is said to be circled if
f(e^iθ x) = f(x) for all
θ∈ and x ∈ X. 



Let f: X → be a function defined on a metric space X.
Suppose there exists a subset Y ⊆ X such that f restricted
to Y is L-Lipschitz. Then there is a function 
f̂: X →
that is L-Lipschitz on all of X satisfying f̂(y) = f(y) for all
y ∈ Y. If X is a normed linear space over real or complex numbers
and f is circled
then the extension f̂ is also circled. 


(Sketch)
Define 
f̂(x) := inf_y ∈ Y [f(y) + L d(x, y)].


In this paper, we endow ^n with the ℓ_2-metric and 
(n) with the Schatten ℓ_2-metric aka Frobenius metric. The 
following fact gives a reasonably tight upper bound on the 
size of an ϵ-net of _^n.
[]

Let ϵ > 0.  There exists an ϵ-net of _^n of
size less than
(3/ϵ)^2n.


A fundamental result about concentration of Lipschitz functions defined
on the unit sphere or the unitary group, known as Levy's lemma, lies at 
the heart of all
proofs of Dvoretzky-type theorems via the probabilistic method.
We now state the version of Levy's lemma that will be used in this
paper.
[Levy's lemma, ]

Consider the Haar probability measure on _^n.
Let f: _^n→ be an L-Lipshitz function. 
Let μ := _x[f(x)] and λ > 0. Then

    _x(| f(x) - μ|≥λ) ≤ 
    2 exp(-n λ^2/4 L^2).


An elementary proof of the above fact, without explicitly calculated 
constants, can be found in <cit.>.

For our work, we need a measure concentration inequality like Levy's 
lemma for difference of function values on two distinct arbitrary 
points which is sensitive to the distance between those points.
Such an inequality is stated in the following fact.
[]

Let f: _^n→ be a circled L-Lipschitz 
function.
Consider the Haar probability measure on (n).
Then for any 
x, y ∈_^n, x ≠ y and for 
any λ > 0,

    _U[| f(Ux) - f(Uy) | > λ] 
    ≤ 2 exp(-λ^2 n/8 L^2 ‖ x-y ‖_2^2).

 

The derandomisation in our paper is carried out by replacing the 
Stinespring dilation unitary of a quantum channel,
 which is chosen  from the Haar measure in 
<cit.>, 
with a unitary chosen uniformly at random
from a finite cardinality approximate unitary t-design for a 
suitable value of t. The next few statements lead us to the definition
of an approximate unitary t-design.

A monomial in the entries of a matrix U is of degree (r,s) if 
it contains r conjugated elements and s unconjugated elements. The
evaluation of monomial M at the entries of a matrix U is denoted
by M(U). We call a monomial balanced if r = s, 
and say that it has degree t if it is of degree (t,t). 
A polynomial is said to be balanced  of degree 
t if it is a sum of balanced monomials of degree at most t.


A probability distribution ν supported on a finite set of d × d
unitary matrices is said to be an exact unitary t-design if 
for all balanced monomials M of degree at most t, 
_U ∼ν[M(U)] = _U ∼[M(U)].


A probability distribution ν supported on a finite set of d × d 
unitary matrices is said to be 
an ϵ-approximate unitary t-design if for all 
balanced monomials M of degree at most t

    |_U ∼ν(M(U)) - 
    _U ∼(M(U)) 
    |≤ϵ/d^t.



We will need the following fact.
[]

Let Y: (n) → be a balanced polynomial of
degree a in the entries of the unitary matrix U that is provided
as input. Let
α(Y) denote the sum of absolute values of the coefficients of Y.
Let r, t be  positive integers satisfying 2ar < t. 
Let ν be an ϵ-approximate unitary t-design. Then 

    _U ∼ν[| Y_U|^2r]  ≤_U ∼[| Y_U |^2r]+
    ϵα(Y)^2r/n^t.





§ SHARP DVORETZKY-LIKE THEOREMS VIA STRATIFIED ANALYSIS


In this section, we prove our main technical results viz. sharp
Dvoretzky-like theorems for Haar measure as well as approximate 
t-designs using stratified analysis.
We start by proving the following two lemmas which are `baby stratified'
analogues of Fact <ref> for Haar measure and 
approximate unitary t-designs.
 
 
Let Y: _^n→ be a circled function with
global Lipschitz constant L_1. Suppose that  
there exists a subset Ω⊆_^n such that
Y restricted to Ω
has a smaller Lipschitz constant L_2. 
Let x, y ∈_^n.
Let Y_x := Y(Ux), Y_y := Y(Uy) be two correlated random variables, 
under the choice of a Haar random unitary U. Let λ > 0.
Then 

    _U ∼[| Y_x - Y_y| > λ] ≤ 
    2 exp(-n λ^2/8 L_2^2 ‖ x - y‖_2^2) +
    2 _z ∼[z ∈Ω^c].

 
 
By Fact <ref>, there is a circled function Y' that
agrees with Y on Ω and is L_2-Lipschitz on all
of _^n.
Define correlated random variables Y'_x,
Y'_y in the natural manner. Then
using Fact <ref>, we get 

    _U ∼[| Y_x - Y_y| > λ]
        =    _U ∼[(Ux, Uy) ∈Ω×Ω] ·_U ∼[
    | Y_x - Y_y| > λ|(Ux, Uy) ∈Ω×Ω
    ] 
           + 
    _U ∼[
    (Ux, Uy) ∉Ω×Ω
    ] ·_U ∼[
    | Y_x - Y_y| > λ|(Ux, Uy) ∉Ω×Ω
    ] 
        =    _U ∼[(Ux, Uy) ∈Ω×Ω] ·_U ∼[
    | Y'_x - Y'_y| > λ|(Ux, Uy) ∈Ω×Ω
    ] 
           + 
    _U ∼[
    (Ux, Uy) ∉Ω×Ω
    ] ·_U ∼[
    | Y_x - Y_y| > λ|(Ux, Uy) ∉Ω×Ω
    ] 
       ≤   _U ∼[| Y'_x - Y'_y| > λ] + 
    2 _z ∼[z ∈Ω^c] 
       ≤   
    2 exp(-n λ^2/8 L_2^2 ‖ x - y‖_2^2) +
    2 _z ∼[z ∈Ω^c].
 
This finishes the proof of the lemma.
 

 
 
Let Y: _^n→ be a 
balanced polynomial of degree a in entries of the vector x ∈^n 
that is
provided as input. Let
α(Y) denote the sum of absolute values of the coefficients of Y.
Suppose Y has global Lipschitz constant L_1.
Suppose that  
there exists a subset Ω⊆_^n such that
Y restricted to Ω
has a smaller Lipschitz constant L_2. 
Let x, y ∈_^n.
Let Y_x := Y(Ux), Y_y := Y(Uy) be two correlated random variables, 
under the choice of a unitary U chosen uniformly at random from an 
ϵ-approximate unitary t-design ν. 
Let r be a positive integer satisfying 2ar ≤ t.
Let 
0 < ϵ < 

n^t-r (4 r L_2^2 ‖ x - y ‖_2^2)^r
/α(Y)^2r.
Then 

    _U ∼ν[| Y_x - Y_y|^2r] ≤ 
    3 (4 r L_2^2 ‖ x - y‖_2^2/n)^r +
    2 _z ∼[z ∈Ω^c] · 
    (L_1^2‖ x- y ‖_2^2)^r.

 
 
Since 
Y_x -Y_y is a balanced  polynomial in the entries of the unitary
matrix U, from  Fact <ref> we have

    _U ∼ν[| Y_x - Y_y|^2r] 
    a≤_U ∼[| Y_x - Y_y|^2r] +
    ϵα(Y)^2r/n^t.

By choosing 
ϵ small enough to satisfy the constraint above, we get 
ϵα(Y)^2r/n^tb≤(4 r L_2^2 ‖ x - y ‖_2^2/n)^r. 
Combining (a) and (b) gives 

    _U ∼ν[| Y_x - Y_y|^2r] 
    c≤_U ∼(| Y_x - Y_y|^2r) +
    (4 r L_2^2 ‖ x - y ‖_2^2/n)^r.


Now we find 
_U ∼[| Y_x - Y_y|^2r].
Since Y is a balanced polynomial, it is circled.
By Fact <ref>, there is a circled function Y' such that
Y' agrees with Y on Ω and Y' is L_2-Lipschitz on all
of _^n.
Define correlated random variables Y'_x,
Y'_y in the natural manner. Then

    _U ∼[| Y_x - Y_y|^2r]
        =    _U ∼[(Ux, Uy) ∈Ω×Ω] ·_U ∼[
    | Y_x - Y_y|^2r|(Ux, Uy) ∈Ω×Ω
    ] 
           + 
    _U ∼[(Ux, Uy) ∉Ω×Ω] ·_U ∼[
    | Y_x - Y_y|^2r|(Ux, Uy) ∉Ω×Ω]
        =    _U ∼[(Ux, Uy) ∈Ω×Ω] ·_U ∼[
    | Y'_x - Y'_y|^2r|(Ux, Uy) ∈Ω×Ω
    ] 
           + 
    _U ∼[(Ux, Uy) ∉Ω×Ω] ·_U ∼[
    | Y_x - Y_y|^2r|(Ux, Uy) ∉Ω×Ω]
       d≤   _U ∼ Haar[| Y'_x - Y'_y|^2r]+
    2 _z ∼[z ∈Ω^c] · 
    (L_1^2‖ x- y ‖_2^2)^r.
 

Now we find 
_U ∼[| Y'_x - Y'_y|^2r]
using Fact <ref> and 
Low's method <cit.>. 

    _U ∼[| Y'_x - Y'_y|^2r]
        =    ∫_0^∞_U ∼[| Y'_x - Y'_y|^2r>λ]   
    dλ =  ∫_0^∞_U ∼[| Y'_x - Y'_y|>λ^1/(2r)]  
    dλ
       ≤   
    2 ∫_0^∞exp(-n λ^1/r/8 L_2^2 ‖ x - y‖_2^2)  
    dλ e≤ 
    2 (4 r L_2^2 ‖ x - y‖_2^2/n)^r.
 

Combining inequalities (d) and (e), we have

    _U ∼[| Y_x - Y_y|^2r] ≤ 
    2 (4 r L_2^2 ‖ x - y‖_2^2/n)^r +
    2 _z ∼[z ∈Ω^c] · 
    (L_1^2‖ x- y ‖_2^2)^r.

Further combining with (c) gives us the desired conclusion of the lemma. 
 

We also need a so-called chaining inequality for probability 
similar to Dudley's 
inequality in geometric functional analysis 
<cit.>. The original
Dudley's inequality bounds the expectation of the supremum, over pairs
of correlated random variables, of the difference between them
in terms of an integral, over η, of
a certain function of the size of an η-net of _^n.
Our chaining lemma differs from it in two important respects. 
First, instead of the expectation it bounds a tail probability of 
the supremum, over pairs
of correlated random variables, of the difference between them.
Second, it replaces the integral by a finite summation
over η-nets of _^n with geometrically decreasing
η. Despite the fancy name, our chaining lemma is a simple consequence
of the union bound of probabilities. Nevertheless, it is crucial to 
proving our main result as it allows us to efficiently invoke
powerful measure concentration results in order to bound the variation of a
Lipschitz function on subspaces of ^n.


Let {X_s}_s ∈ be a family of correlated complex valued
random variables indexed
by elements of a compact metric space . 
Let λ, L_1 > 0. The family is said to be L_1-Lipschitz if
for all s, t ∈, |X_s - X_t| ≤ L_1 d(s,t) for
all points of the sample space.
Define i_0 to be the unique
integer such that the radius of  lies in the interval
(2^-i_0-1, 2^-i_0]. Define 
i_1 := max{i_0, ⌈log2 L_1/λ⌉}. 
Let p : →_+ be a non-decreasing 
function. Suppose the infinite series
∑_i > i_0√(|i| p(i))/2^i is convergent with
value C.
Then,

    [sup_s,t ∈| X_s-X_t| > λ] ≤∑_i = i_0+1^i_1+1∑_
    (u,u^') ∈_i-1×_i: 
    d(u, u^') < 2^-i+2 [| X_u - X_u^'| > 
    	λ√(|i| p(i))/4C · 2^i 
    ],

for a sequence of 2^-i-nets _i, i_0 ≤ i ≤ i_1,
|_i_0| = 1, of . 


For every i ∈, let _i be a 2^-i-net of .
Let i_0 be such that radius of  
lies in (2^-(i_0+1),2^-i_0]. The net _i_0 
consists of a single element, say s_0. For every s ∈ and 
i ∈, let π_i(s) be an element of _i satisfying 
d(s,π_i(s)) ≤ 2^-i. We have the following chaining equation
for every s ∈:

    X_s = 
    X_s_0 +
    (∑_i = i_0^i_i (X_π_i+1(s)-X_π_i(s))) +
    (X_s - X_π_i_1 + 1(s)).

Lipschitz property of the family implies that

    sup_s,t ∈| X_s-X_t|   ≤   
    2 ∑_i = i_0^i_1sup_s ∈| X_π_i+1(s)-X_π_i(s)| +
    L_1 2^-i_1
       ≤   
    2 ∑_i = i_0^i_1sup_(u,u^') ∈_i×_i+1 : d(u,u')<2^-i+1| X_u - X_u'| +
    L_1 2^-i_1
       ≤   
    2 ∑_i = i_0+1^i_1+1sup_(u,u^') ∈_i-1×_i : d(u,u')<2^-i+2| X_u - X_u'| +
    λ/2.


Now if 
sup_s,t ∈| X_s-X_t| > λ, there must
exist an i, i_0 + 1 ≤ i ≤ i_1 + 1 such that

    sup_(u,u^') ∈_i-1×_i : d(u,u')<2^-i+2| X_u - X_u'| > 
    λ√(|i| p(i))/4C · 2^i.

Applying the union bound on probability leads us to the conclusion
of the lemma.


We now prove our sharp Dvoretzky-like theorem for subspaces chosen
from the Haar measure using stratified analysis.


Let p : →_+ be a non-decreasing 
function. Suppose the infinite series
∑_i > 0√(i p(i))/2^i is convergent with
value C.
Let f: _^n→ have
global Lipschitz constant L_1. 
Let L_2, c_1, c_2, c_3, λ > 0. 
Define m := ⌈c_1 n λ^2/L_2^2⌉.
Suppose there is an increasing sequence of subsets 
Ω_1 ⊆Ω_2 ⊆⋯ of _^n 
such that with probability at least 1 - c_2 e^-c_3 m i,
a Haar random subspace of dimension 
m lies in Ω_i and f restricted to Ω_i has Lipschitz 
constant L_2 √(p(i)). 
Then there exists a constant c depending on c_3, C,
0 < c < 1, such that for
m^' := c m
with probability at least 1- (c_2 + 1) 2^-m', a
subspace W of dimension 
m^' chosen with respect to Haar measure
satisfies the property that
| f(w)- μ| < λ 
for all points w ∈ W ∩_^n. 


In this proof _^n denotes the unit ℓ_2-length sphere in
^n together with the origin point 0. The radius of 
_^n is one which makes i_0 = 0 in 
Lemma <ref>.
Consider a canonical embedding of _^m' into 
_^m and further into _^n.  Define 

    B_i := {U ∈(n): ∀ z ∈_^m, Uz ∈Ω_i}.

For s ∈_^m', define the random variable 
Y_s := f(Us) - μ,
where the randomness arises solely from the choice of U ∈(n).
Then _U ∼[B_i] ≥ 1 - c_2 e^-c_3 m i.

Let i_1 := ⌈log2 L_1/λ⌉. 
Let _i, i = 0, 1, …, i_1 be a sequence of 
2^-i-nets in _^m' of minimum cardinality, 
where _0 := {0}
and Y_0 := 0. We can take |_i| a≤ 2^2 (i+2) m' by
Fact <ref>. By Lemma <ref>

    _U ∼[
    sup_s,t ∈_^m'| Y_s -Y_t | > λ
    ] ≤ 
    2 ∑_i=1^i_1+1∑_
    (u,u^') ∈_i-1×_i: 
    ‖ u- u^'‖_2 < 2^-i+2_U ∼[
    | Y_u - Y_u^'| > 
    λ√(i p(i))/4C · 2^i
    ].


Applying Lemma <ref> to the set B_i gives, for
u, u' satisfying ‖ u- u^'‖_2 < 2^-i+2,

    _U ∼[
    | Y_u - Y_u^'| > 
    λ√(i p(i))/4C · 2^i
    ]
    
       ≤    
    2 exp(-n λ^2 i p(i)/2^7 C^2 2^2i L_2^2 p(i) 
    ‖ u -u^'‖_2^2) +
    2 _z ∼ [z ∈Ω_i^c] 
       ≤   
    2 exp(-n i λ^2 /2^9 C^2 L_2^2) + 
    2 _z ∼ [z ∈Ω_i^c] 
    
       ≤   
    2 exp(-im/2^9 C^2) +
    2 c_2 exp(-c_3 m i) 
     ≤ 
    2 (c_2 + 1) exp(-c_4 m i),

for a constant c_4 depending only on C and c_3.

This gives us

    _U ∼[
    sup_s,t ∈_^m'| Y_s -Y_t | > λ
    ] 
    
       ≤    
    4 (c_2 + 1) ∑_i=1^i_1+1∑_
    (u,u^') ∈_i-1×_i:
    ‖ u- u^'‖_2 < 2^-i+2  
    e^-c_4 m i ≤  
    4 (c_2 + 1) ∑_i=1^i_1+1 
    |_i-1| · |_i| · e^-c_4 m i
       ≤   
    4 (c_2 + 1) ∑_i=1^i_1+1 
    2^4 m' (i+2) 
    e^-c_4 m i ≤ 
    (c_2 + 1) 2^-m',

where the third inequality follows from (a) and the fourth inequality
follows from the definition m' := c m for an appropriate choice
of c depending only on c_4. In other words, c depends only on
C and c_3.

Taking t = 0, we see that
with probability at least 1 - (c_2 + 1) 2^-m' over
the choice of a Haar random unitary, we have
that for all s ∈_^m', |Y_s| ≤λ.
This completes the proof of the theorem.




  
Remark:
The sets Ω_i and the Lipschitz constants L_2 √(p(i))
for 1 ≤ i ≤⌈log2 L_1/λ⌉ + 1
formalise the idea of stratified analysis mentioned intuitively in the
introduction. As i increases the relevant Lipschitz constant increases.
So we need a finer net i.e. a 2^-i-net for the ith layer 
Ω_i in order to control the variation of f for subspaces 
lying inside Ω_i.
With exponentially high probability, we thus get a 
Haar random subspace of dimension m^', slightly smaller than m,
where f is almost constant.
Note that the definition of m involves only the smallest local 
Lipschitz constant L_2. Thus the dimension of the space m' that
we obtain is larger than what would be obtained by a naive 
analysis which would be constrained by the
global Lipschitz constant L_1. Moreover, a naive analysis would not
give exponentially high probability, just an arbitrary constant close
one. These two properties underscore the power of our stratified
analysis. However, applying the stratified analysis to a concrete
function is not always straightforward. We need to define the
layers Ω_1, Ω_2, …, properly and show separately that
Haar random subspaces of dimension m lie in Ω_i with
probability 1 - c_2 e^-c_3 m i. But for several interesting functions
this can be done without much difficulty. 
This will become clearer in
Section <ref> where we will show how to
recover Aubrun, Szarek and Werner's result for the Haar measure directly 
from 
Theorem <ref>, without having to apply a Dvoretzky-style
theorem twice in a messy fashion as in the original paper
<cit.>. Moreover, we get success probability
exponentially close to one  unlike Aubrun, Szarek and Werner who could
get only a constant close to one. Furthermore, our
methods extend to approximate t-designs and allows us to prove
exponentially close to one probability even for that setting.

We now prove our sharp Dvoretzky-like theorem for subspaces chosen
from approximate t-designs using stratified analysis. 
 
 
Let p : →_+ be a non-decreasing 
function. Suppose the infinite series
∑_i > 0√(i p(i))/2^i is convergent with
value C.
Let f: _^n→ be a balanced degree `a' 
polynomial with global Lipschitz constant L_1. 
Let 0 ≤ L_2 ≤ 1, c_1, c_2, c_3, λ > 0. 
Define m := ⌈c_1 n λ^2/L_2^2⌉.
Suppose there is an increasing sequence of subsets 
Ω_1 ⊆Ω_2 ⊆⋯ of _^n 
such that with probability at least 1 - c_2 e^-c_3 m i,
a Haar random subspace of dimension 
m lies in Ω_i and f restricted to Ω_i has Lipschitz 
constant L_2 √(p(i)). 
Suppose 

    0 < ϵ < 
    (λ/4 L_1)^2m·n^(2a-1)m (L_2^2 p(1))^m/max{α(f)^2m,1}.

Then there exists a constant c depending on c_1, c_3, C, p(1), 
0 < c < 1 such that for

    m^' := 
    c m 
    loglogC^2 L_1^2/λ^2 p(1)/⌈logC^2 L_1^2/λ^2 p(1)⌉,

with probability at least 1- (c_2+1) 2^-m', a 
subspace W of dimension 
m^' chosen under an ϵ-approximate (2am)-design ν
satisfies the property that
| f(w)- μ| < λ 
for all points w ∈ W ∩_^n. 


In this proof _^n denotes the unit ℓ_2-length sphere in
^n together with the origin point 0. The radius of 
_^n is one which makes i_0 = 0 in 
Lemma <ref>.
Consider a canonical embedding of _^m' into 
_^m and further into _^n.  Define 

    B_i := {U ∈(n): ∀ z ∈_^m, Uz ∈Ω_i}.

For s ∈_^m', define the random variable 
Y_s := f(Us) - μ,
where the randomness arises solely from the choice of U ∈(n).
Then _U ∼[B_i] ≥ 1 - c_2 e^-c_3 m i.

Let i_1 := ⌈log2 L_1/λ⌉. 
Let _i, i = 0, 1, …, i_1 be a sequence of 
2^-i-nets in _^m' of minimum cardinality, 
where _0 := {0}
and Y_0 := 0. We can take |_i| a≤ 2^2 (i+2) m' by
Fact <ref>. By Lemma <ref>

    _U ∼ν[
    sup_s,t ∈_^m'| Y_s -Y_t | > λ
    ] ≤ 
    2 ∑_i=1^i_1+1∑_
    (u,u^') ∈_i-1×_i: 
    ‖ u- u^'‖_2 < 2^-i+2_U ∼ν[
    | Y_u - Y_u^'| > 
    λ√(i p(i))/4C · 2^i
    ].


Let r be a positive integer such that r (i_1+1) < m.
Applying Lemma <ref> to the set B_i gives, for
u, u' satisfying ‖ u- u^'‖_2 < 2^-i+2,

    _U ∼ν[
    | Y_u - Y_u^'| > 
    λ√(i p(i))/4C · 2^i
    ]
    
        =    _U ∼ν[
    | Y_u - Y_u^'|^2 r i > 
    (λ^2 i p(i)/2^4 C^2 2^2i)^r i
    ] 
     ≤ (2^2i+4 C^2/λ^2 i p(i))^r i_U ∼ν[| Y_u - Y_u^'|^2 r i] 
       ≤   
    3 (2^2i+4 C^2/λ^2 i p(i))^r i(
    (
    4 r i L_2^2 p(i) ‖ u - u^'‖_2^2/n)^r i 
    + c_2 e^-c_3 m i· (L_1^2 ‖ u- u^'‖_2^2)^r i) 
       ≤   
    3 ( 
    2^2i+6 C^2 r  L_2^2 ‖ u- u^'‖_2^2/n λ^2)^r i + 
    3 c_2 e^-c_3 m i(
    2^2i+4 C^2 L_1^2 ‖ u- u^'‖_2^2/λ^2 i p(i))^r i
       ≤   
    3 ( 
    2^10 C^2 r L_2^2/n λ^2)^r i_=: I + 
    
    3 c_2 e^-c_3 m i(
    2^8 C^2 L_1^2/λ^2 p(1))^r i_=: II.


We now analyse the two terms in the above expression.
Take 

    r := 
    c_4 n λ^2/2^10 C^2 L_2^2·1/⌈log2^8 C^2 L_1^2/λ^2 p(1)⌉

for a constant c_4, 0 < c_4 < 1, c_4 depending only on
C, c_1, c_3, p(1) chosen to be small enough so that 
r (i_1+1) < m and
c_4 n λ^2/2^10 C^2 L_2^2≤c_3 m/2.
Substitute r back in I and II to get

    I≤ 
    3 · 2^-r i loglog2^8 C^2 L_1^2/λ^2 p(1),
       II≤ 
    3 c_2 e^-c_3 m i 2^c_3 m i/2
    <
    3 c_2 e^-c_3 m i / 2.

We choose 

    m” :=
    r  loglog2^8 C^2 L_1^2/λ^2 p(1) <
    c_3 m/2.

This gives us

    I≤ 
    3 · 2^-m” i,
       II≤
    3 c_2 e^-m” i.

Thus, we have shown that

    _U ∼ν[
    | Y_u - Y_u^'| > 
    λ√(p(i))/4 C · 2^i 
    ] ≤ 3 (c_2 + 1) 2^-m” i.

Substituting above in Equation <ref>, we get

    _U ∼ν[
    sup_s,t ∈_^m^'| Y_s -Y_t | > λ
    ]  
    
       ≤   
    2 ∑_i=1^i_1+1∑_u,u^'∈_i-1×_i: 
    ‖ u- u^'‖ < 2^-i+2 3 (c_2 + 1) 2^-m” i
       ≤   
    6 (c_2+1) ∑_i=1^i_1+1 
    |_i-1| · |_i| ·
    2^-m” i ≤ 
    6 (c_2+1) ∑_i=1^i_1+1 
    2^4 m'(i+2) 2^-m” i ≤ 
    (c_2 + 1) 2^-m',

if m' is chosen as indicated above for a small enough constant
c, 0 < c < 1, c depending only on c_4, c_1, C i.e.
c depending only on C, c_1, c_3, p(1).

Taking t = 0, we see that
with probability at least 1 - (c_2 + 1) 2^-m^' over
the choice of a uniformly random unitary from the approximate 
(2am)-design, we have
that for all s ∈_^m', |Y_s| ≤λ. 
This completes the proof of the theorem.




§ STRICT SUBADDITIVITY OF MINIMUM OUTPUT VON NEUMANN ENTROPY FOR
APPROXIMATE T-DESIGNS


We first apply Theorem <ref>
in order to directly recover Aubrun, Szarek and Werner's result
<cit.>
that channels with Haar random unitary Stinespring dilations
exhibit strict subadditivity of minimum output von Neumann entropy. In 
fact, we
go beyond their result in the sense that we obtain exponentially
high probability close to one as opposed to constant 
probability. After this warmup, we apply Theorem <ref>
in order to show that channels with approximate n^2/3-design 
unitary Stinespring dilations exhibit strict
subadditivity of minimum output von Neumann entropy with exponentially high
probability close to one.

Let k be a positive integer. 
Consider the sphere _^k^3. Define the k × k^2
matrix M to be the rearrangment of a k^3-tuple from
_^k^3. Note that the ℓ_2-norm on ^k^3 is
the same as the Frobenius norm on ^k × k^2.

In Step I, we define the 
function f: _^k^3→ as 
f(M) := ‖ M ‖_∞. The function f has global Lipschitz
constant L_1 = 1 since

    |f(M) - f(N)| ≤‖ M - N ‖_∞≤‖ M - N ‖_2.

For large enough k the mean μ of f, under the Haar measure, is less
than 2 k^-1/2 <cit.>.
We use the notation of Theorem <ref>.
Define L_2 := 1, p(i) := 1 for all i ∈. Then C < 2.
Define the layers Ω_1, Ω_2, …, to be all of
_^k^3. Let j, 4 ≤ j ≤ k be a positive integer. 
Let λ_j := √(j/k). Define c_1 := 1,
m = k^2, c_2 := 0, c_3 := 1. Trivially,
a Haar random subspace of dimension m j lies in Ω_i with
probability at least 1 - c_2 e^-c_3 m j i. Theorem <ref>
tells us that there is a universal constant ĉ_1 such that
for m' := ĉ_1 k^2, with probability at least
1 - 2^-m' j, a Haar random subspace W of dimension m' j
satisfies 

    ‖ M ‖_∞ < 
    2/√(k) + √(j/k) <
    2 √(j/k)

for all M ∈ W.

In  Step II, we define the 
function f: _^k^3→ as 
f(M) := ‖ M M^† - /k‖_2. 
The function f has global Lipschitz
constant L_1 = 2 since

    |f(M) - f(N)| 
       ≤   ‖ M M^† - N N^†‖_2 
     ≤ ‖ M M^† - M N^†‖_2 +
    ‖ M N^† - N N^†‖_2 
       ≤   ‖ M ‖_∞‖ M^† - N^†‖_2 +
    ‖ N^†‖_∞‖ M - N ‖_2 
          =     
    (‖ M ‖_∞ + ‖ N ‖_∞)
    ‖ M - N ‖_2 
     ≤ 
    2 ‖ M - N ‖_2.

The mean μ of f, under the Haar measure, is less
than c_0 k^-1 for a universal constant c_0 
<cit.>.
We use the notation of Theorem <ref>.
Let j, c_0 < j ≤ k be a positive integer.
Define L_2 := 4 √(j/k), p(i) := i+3 for all i ∈. 
Then C ≤ 4.
Define the layers Ω_1, Ω_2, …, to be 
the subsets

    Ω_i := 
    {
    M ∈_^k^3: 
    ‖ M ‖_∞≤ 2 √(j(i+3)/k)}.

It is easy to see that f restricted to Ω_i has local
Lipschitz constant at most L_2 √(p(i)).
Let λ := j/k. Define c_1 := 16 ĉ_1,
m = ĉ_1 j k^2, c_2 := 1, c_3 := ln 2. By the previous
paragraph,
a Haar random subspace of dimension m (i+3) lies in Ω_i with
probability at least 
1 - c_2 e^-c_3 m (i+3)≥ 1 - c_2 e^-c_3 m i. 
Theorem <ref>
tells us that there is a universal constant ĉ_2 such that
for m' := ĉ_2 k^2, with probability at least
1 - 2^-m' j, a Haar random subspace W of dimension m' j
satisfies 

    f(M) = ‖ M M^† - /k‖_2 <
    c_0/k + j/k <
    2j/k

for all M ∈ W. Setting j = 1 allows us to recover Aubrun, Szarek
and Werner's technical result <cit.> with
probability exponentially close to one viz.
with probability at least
1 - 2^-m', a Haar random subspace W of dimension m'
satisfies 
‖ M M^† - /k‖_2 <
2/k
for all M ∈ W. We will now see how this implies the existence
of a channel with strictly subadditive minimum output von Neumann
entropy.


Let k be a positive integer.
Let W be a Haar random subspace of dimension m := ĉ_2 k^2 
chosen from the Hilbert space ^k^3, where ĉ_2 is a
universal constant. Let Φ be the channel with output dimension
k corresponding to the
subspace W. Then with probability at least 1 - 2^-m over the
choice of W,

    S_min(Φ)≥log k - 4/k, 
       
    S_min(Φ⊗Φ̅) ≤
    2 log k - ĉ_2 log k/k + 
    O (1/k).

In other words,
S_min(Φ⊗Φ̅) <
S_min(Φ) + S_min(Φ̅)
for large enough k.


The input dimension of the channel Φ is W = m. The 
Stinespring dilation
of the channel Φ is the k^3 × k^3 unitary matrix 
that defines the subspace W. The subspace W is obtained by
taking the first m columns of a Haar random unitary matrix. 
Let M be a unit ℓ_2-norm vector in ^k^3 rearranged as
a k × k^2 matrix.
From Fact <ref>, we get

    S_min(Φ)≥log k - k max_M ∈ W‖ M M^† - /k‖_2^2 ≥log k - 4/k.

And from Fact <ref>, with d = k^2, we get

    S_min(Φ⊗Φ̅) 
       ≤    
    2 log k - 
    m/kdlog k + 
    O ( m/kdlogd/m + 1/k) 
        =    
    2 log k - ĉ_2 log k/k + 
    O (1/k) 
        <    
    S_min(Φ) + S_min(Φ̅),

for large enough k.

Thus we have shown
that for large enough n, Haar random n × n unitaries give rise 
to channels
exhibiting strict subadditivity of minimum output von Neumann
entropy implying that classical Holevo capacity of quantum channels can
be superadditive.

In Step III, we define the 
function f: _^k^3→ as 
f(M) := ‖ M M^† - /k‖_2^2 i.e.
this f is the square of the f defined in Step II above.
Now, f is a balanced polynomial of degree a = 2 and
1 < α(f) < k^6 as can be seen by considering
f(J) where J is the k × k^2 all ones matrix.
The function f has global Lipschitz
constant L_1 = 4 since

    |f(M) - f(N)| 
       ≤   
    |‖ M M^† - /k‖_2 -
     ‖ N N^† - /k‖_2| ·
    |‖ M M^† - /k‖_2 +
     ‖ N N^† - /k‖_2| 
       ≤   
    (‖ M ‖_∞ + ‖ N ‖_∞)
    (‖ M M^† - /k‖_2 +
    ‖ N N^† - /k‖_2)
    ‖ M - N ‖_2 
       ≤   
    4 ‖ M - N ‖_2.

The mean μ of f under the Haar measure is less
than c_0^2 k^-2 for the same universal constant c_0 
<cit.>.
We use the notation of Theorem <ref>.
Define L_2 := 16 k^-3/2, p(i) := i^3 for all i ∈. 
Then C ≤ 5.
Define the layers Ω_1, Ω_2, …, to be 
the subsets

    Ω_i := 
    {
    M ∈_^k^3: 
    ‖ M ‖_∞≤ 2 √(i/k),
    ‖ M M^† - /k‖_2 < 2i/k}.

It is easy to see that f restricted to Ω_i has local
Lipschitz constant at most L_2 √(p(i)).
Let λ := k^-2. Define c_1 := 2^8 ĉ_2,
m = ĉ_2 k^2 < ĉ_1 k^2, c_2 := 2, 
c_3 := ln 2. By the previous two
paragraphs,
a Haar random subspace of dimension m i lies in Ω_i with
probability at least 
1 - c_2 e^-c_3 m i.
In particular, 
a Haar random subspace of dimension m lies in Ω_i with
probability at least 
1 - c_2 e^-c_3 m i.
Let 

    0 ≤ϵ < 
    (1/16 k^2)^2mk^9m k^-3m/k^12m =
    (4 k)^-10 ĉ_2 k^2.

Theorem <ref>
tells us that there is a universal constant ĉ_3 such that
for 

    m' := ĉ_3 k^2 loglog k/log k,

with probability at least
1 - 3 · 2^-m', a subspace W of dimension m' chosen from an
ϵ-approximate (4 ĉ_2 k^2)-design ν satisfies

    f(M) = ‖ M M^† - /k‖_2^2 <
    c_0^2/k^2 + 1/k^2 =
    c_0^2 + 1/k^2

for all M ∈ W.
We shall now see how this result gives us a channel with strict
subadditivity of minimum output von Neumann entropy. 


Let k be a positive integer.
Let W be a subspace of dimension 
m' := ĉ_3 k^2 loglog k/log k
chosen with uniform probability from a 
k^-8 ĉ_2 k^2-approximate unitary (4 ĉ_2 k^2)-design 
from the Hilbert space ^k^3, where ĉ_2, ĉ_3 are
universal constants. Let Φ be the channel with output dimension
k corresponding to the
subspace W. Then with probability at least 1 - 3 · 2^-m' over the
choice of W,

    S_min(Φ)≥log k - c_0/k, 
       
    S_min(Φ⊗Φ̅) ≤
    2 log k - ĉ_3 loglog k/k + 
    O ((loglog k)^2/k log k + 1/k),

for a universal  constant c_0.
In other words,
S_min(Φ⊗Φ̅) <
S_min(Φ) + S_min(Φ̅)
for large enough k.


The input dimension of the channel Φ is W = m'. The 
Stinespring dilation
of the channel Φ is the k^3 × k^3 unitary matrix 
that defines the subspace W. The subspace W is obtained by
taking the first m' columns of the unitary matrix. This unitary
matrix is chosen uniformly at random from a 
k^-8 ĉ_2 k^2-approximate
unitary (4 ĉ_2 k^2)-design. 
Let M be a unit ℓ_2-norm vector in ^k^3 rearranged as
a k × k^2 matrix.
From Fact <ref>, we get

    S_min(Φ)≥log k - k max_M ∈ W‖ M M^† - /k‖_2^2 ≥log k - c_0^2 + 1/k.

And from Fact <ref>, with d = k^2, we get

    S_min(Φ⊗Φ̅) 
       ≤    
    2 log k - 
    m^'/kdlog k + 
    O ( m'/kdlogd/m' + 1/k) 
        =    
    2 log k - ĉ_3 loglog k/k + 
    O ( (loglog k)^2/k log k + 1/k) 
        <    
    S_min(Φ) + S_min(Φ̅),

for large enough k.

Thus we have shown
that for large enough n, approximate unitary n^2/3-designs give rise 
to channels
exhibiting strict subadditivity of minimum output von Neumann
entropy, implying that classical Holevo capacity of quantum channels can
be superadditive.



  
Remark:
Observe that the counter example we get for additivity conjecture for 
classical Holevo capacity of quantum channels, when the channel is chosen 
from an approximate unitary t-design has weaker parameters 
than a channel chosen from Haar random unitaries.
Nevertheless, as explained in the introduction our work 
is the first partial derandomisation of a construction of quantum
channels violating additivity of classical Holevo capacity.



§ STRICT SUBADDITIVITY OF MINIMUM OUTPUT RÉNYI P-ENTROPY FOR
APPROXIMATE T-DESIGNS


In this section, we apply Proposition <ref> and 
Theorem <ref>
in order to show that channels with approximate 
(n^1.7log n)-design 
unitary Stinespring dilations exhibit strict
subadditivity of minimum output Rényi p-entropy for
p > 1 with exponentially high
probability close to one.

Let k be a positive integer. 
Consider the sphere _^k^3. Define the k × k^2
matrix M to be the rearrangment of a k^3-tuple from
_^k^3. Note that the ℓ_2-norm on ^k^3 is
the same as the Frobenius norm on ^k × k^2. 
Let 1 < p ≤ 1.1. 

In Step I, we define the function f: _^k^3→
as f(M) := ‖ M ‖_2p. The function f has global Lipschitz
constant L_1 = 1 since

    |f(M) - f(N)| ≤‖ M - N ‖_2p≤‖ M - N ‖_2.

For large enough k the mean μ of f, under the Haar measure,
is less than 2  k^1/2p - 1/2 
<cit.>, 
<cit.>. We use the notation
of Theorem <ref>.
Define L_2 := 1, p(i) := 1 for all i ∈. Then C < 2.
Define the layers Ω_1, Ω_2, …, to be all of
_^k^3. Let j, 4 ≤ j ≤ k be a positive integer. 
Let λ_j := j^1/2 k^1/2p - 1/2. 
Define c_1 := 1,
m = k^2 + 1/p, c_2 := 0, c_3 := 1. Trivially,
a Haar random subspace of dimension m j lies in Ω_i with
probability at least 1 - c_2 e^-c_3 m j i. Theorem <ref>
tells us that there is a universal constant ĉ_1 such that
for m' := ĉ_1 k^2 + 1/p, with probability at least
1 - 2^-m' j, a Haar random subspace W of dimension m' j
satisfies 

    ‖ M ‖_∞≤‖ M ‖_2p < 
    2  k^1/2p - 1/2 +
    j^1/2 k^1/2p - 1/2 <
    2 j^1/2 k^1/2p - 1/2

for all M ∈ W. In particular, with probability at least 
1 - 2^-ĉ_1 j k^4/3p + 5/3 (log k)^-1, 
a Haar random 
subspace W of dimension
ĉ_1 j k^4/3p + 5/3 (log k)^-1 satisfies 

    ‖ M ‖_∞≤‖ M ‖_2p < 
    2 j^1/2 k^1/2p - 1/2

for all M ∈ W.

Let j, 4 ≤ j ≤ k be a positive integer.
Define the function f: [0, 1] → [0, 1] as 
f(x) := x^p.
Set ϵ := k^-p in Proposition <ref>.  Let
n be the minimum positive odd integer satisfying 
2 p k^p √(ln k^2p)≤k^-p/n√(n)/2;
n < 2^7 p^3 k^2plog k.  
Proposition <ref> implies
that there is a polynomial p(x) of degree at most 
2n + 1 < 2^9 p^3 k^2plog k such that

    [                  p(x) - 2 k^-p≤ x^p ≤ p(x) + 3  k^-p,                                         ∀ x ∈ [0, 1],; |p'(x)| < 
    4 p (j+1)^p-1√(ln k^2p) 
    k^5/3 - 2/3p - p,                              ∀ x ∈ [0, j k^2/3p - 1],;     |p'(x)| < 
    4 p (5j)^p-1√(ln k^2p) 
    k^2 - p - 1/p,                  ∀ x ∈ (j k^2/3p - 1, 5 j k^1/p - 1],;                            |p'(x)| < 
    4 p √(ln k^2p),                             ∀ x ∈ (5 j k^1/p - 1, 1]. ]

Also, Proposition <ref> guarantees that
α(p(x)) < e^2^7 p^3 k^2plog k.

In Step II, we define the function f: _^k^3→
as f(M) :=   [p(M M^†)], where p is the polynomial defined in 
Equation <ref>.
Now, f is a balanced polynomial of degree 
a = 2n + 1 < 2^9 p^3 k^2plog k and

    α(f) =  [p(J J^†)] = k^3 α(p(x)) <  
    e^2^8 p^3 k^2plog k,

where J is the k × k^2 all ones matrix.
For a  k × k matrix X, define 
(X) to be  the k ×  k diagonal  matrix consisting of the 
singular values of X arranged in decreasing order.
The function f has global Lipschitz
constant L_1 = 2^4 p^3/2√(log k) since

    |f(M) - f(N)| 
          =     
    | [p((M)^2)] -  [p((N)^2)]| 
       =  
    | [p((M)^2)-p((N)^2)]| 
       ≤   
    8 p^3/2√(log k)·‖(M)^2 - (N)^2 ‖_1 
       ≤   
    8 p^3/2√(log k)·‖(M) - (N) ‖_2 ·‖(M) + (N) ‖_2 
    `
       ≤   
    2^7/2 p^3/2√(log k)·‖(M) - (N) ‖_2 ·√(‖ M ‖_2^2 + ‖ N ‖_2^2)
       ≤   
    2^4 p^3/2√(log k)·‖ M  - N ‖_2.

Above, the first inequality follows from Equation <ref>,
the second inequality is Cauchy-Schwarz and the last inequality
follows from <cit.>.
By setting j = 4 in Step I, we conclude that
the mean μ of f under the Haar measure is less
than 2^4p k^1-p. 
We use the notation of Theorem <ref>.
Let λ := k^1 - p. 
Define 

    L_2 := 
    2^4p+3 p^3/2√(log k)· 
    k^5/3 - p - 2/3p,

p(i) := (i+4)^2p-1 for all i ∈. 
Then C ≤ p^2p.
Define the layers Ω_1, Ω_2, …, to be 
the subsets

    Ω_i := 
    {
    M ∈_^k^3: 
    ‖ M ‖_2p≤ 
    2 (i+3)^1/2 k^1/2p-1/2}.

We will now show that f restricted to Ω_i has local
Lipschitz constant at most L_2 √(p(i)). Note that for any
M ∈Ω_i, 
‖ M ‖_∞≤ 
2 (i+3)^1/2 k^1/2p - 1/2.
Let B denote the number of singular values of M larger than
(i+3)^1/2 k^1/3p - 1/2. 
Let b_1, … b_k be the singular values of M in descending order.
Then

    2^2p (i+3)^p k^1-p≥‖ M ‖_2p^2p≥∑_i=1^B b_i^2p≥(∑_i=1^B b_i^2) 
    (i+3)^p-1 k^5/3 - 2/3p - p,

which gives
∑_i=1^B b_i^2≤
2^2p (i+3) k^2/3p - 2/3.
Let C denote the number of singular values of N larger than
(i+3)^1/2 k^1/3p - 1/2. 
Without loss of generality, B ≥ C. Restricting M, N
to belong to Ω_i, we get from Equation <ref> that

    |f(M) -  f(N)|
    
        =    
    |
     [
    p((M)^2) - p((N)^2)
    ]
    |  
       ≤   ∑_i=1^C |p(b_i^2) - p(c_i^2)| +
    ∑_i=C+1^B |p(b_i^2) - p(c_i^2)| +
    ∑_i=B+1^k |p(b_i^2) - p(c_i^2)| 
       ≤   
    8 p^3/2 (5 (i+3))^p-1√(log k)· k^2 - p - 1/p∑_i=1^C |b_i^2 - c_i^2| 
           +
    8 p^3/2 (5 (i+3))^p-1√(log k)· k^2 - p - 1/p∑_i=C+1^B |b_i^2 - c_i^2| 
           +
    8 p^3/2 ((i+4))^p-1√(log k)· 
    k^5/3 - p - 2/3p∑_i=B+1^k |p(b_i^2) - p(c_i^2)| 
       ≤   
    8 p^3/2 (5 (i+3))^p-1√(log k)· k^2 - p - 1/p√(∑_i=1^C (b_i - c_i)^2)·√(∑_i=1^C (b_i + c_i)^2)
           +
    8 p^3/2 (5 (i+3))^p-1√(log k)· k^2 - p - 1/p√(∑_i=C+1^B (b_i - c_i)^2)·√(∑_i=C+1^B (b_i + c_i)^2)
           +
    8 p^3/2 ((i+4))^p-1√(log k)· 
    k^5/3 - p - 2/3p√(∑_i=B+1^k (b_i - c_i)^2)·√(∑_i=B+1^k (b_i + c_i)^2)
       ≤   
    2^7/2 p^3/2 
    (5 (i+3))^p-1√(log k)· k^2 - p - 1/p√(∑_i=1^k (b_i - c_i)^2)·√(∑_i=1^C (b_i^2 + c_i^2))
           +
    2^7/2 p^3/2 
    (5 (i+3))^p-1√(log k)· k^2 - p - 1/p√(∑_i=1^k (b_i - c_i)^2)·√(∑_i=C+1^B (b_i^2 + c_i^2))
           +
    2^7/2 p^3/2 
    ((i+4))^p-1√(log k)· 
    k^5/3 - p - 2/3p√(∑_i=1^k (b_i - c_i)^2)·√(∑_i=1^k (b_i^2 + c_i^2))
       ≤   
    2^4 p^3/2 2^p
    5^p-1 (i+3)^p - 1/2√(log k)· k^2 - p - 1/p·
    k^1/3p - 1/3·‖(M) - (N) ‖_2 
           +
    2^4 p^3/2 2^p
    5^p-1 (i+3)^p - 1/2√(log k)· k^2 - p - 1/p·
    k^1/3p - 1/3·‖(M) - (N) ‖_2 
           +
    2^4 p^3/2 
    ((i+4))^p-1√(log k)· 
    k^5/3 - p - 2/3p‖(M) - (N) ‖_2 
       ≤   
    2^6 p^3/2 2^p
    5^p-1 (i+4)^p - 1/2√(log k)· 
    k^5/3 - p - 2/3p·‖(M) - (N) ‖_2 
       ≤   
    2^4p+3 p^3/2 
    (i+4)^p - 1/2√(log k)· 
    k^5/3 - p - 2/3p·‖ M - N ‖_2.

This completes the proof of the claim above that f restricted to
Ω_i has local Lipschitz constant at most L_2 √(p(i)).
Define c_1 := 2^8p+6 p^3 ĉ_1,
m = ĉ_1 k^4/3p+5/3 (log k)^-1, c_2 := 1, 
c_3 := ln 2. By Step I,
a Haar random subspace of dimension m i lies in Ω_i with
probability at least 1 - c_2 e^-c_3 m i.
Let 

    0 ≤ϵ < 
    k^ĉ_1 k^2p + 3 (log k)^-1/2  <
    (k^1 - p/4 L_1)^2mk^3 (2a-1) m 5^(2p-1)m L_2^2m/α(f)^2m.

Theorem <ref>
tells us that there is a universal constant ĉ_3 such that
for 

    m' := 
    ĉ_3 k^4/3p + 5/3loglog k/(log k)^2,

with probability at least
1 - 2 · 2^-m', a subspace W of dimension m' chosen from an
ϵ-approximate (2am)-design ν 
satisfies

    f(M) =  [p(M M^†)] <
    2^4p k^1-p + k^1-p <
    2^4p+1 k^1-p

for all M ∈ W. By Equation <ref>, this implies that

    [(M M^†)^p] < 
     [p(M M^†)] + 3 k^1-p <
    2^4p+3 k^1-p

for all M ∈ W. In other words,
‖ M ‖_2p^2 < 2^7 k^1/p - 1
for all M ∈ W.
We shall now see how this result gives us a channel with strict
supermultiplicativity of the ‖·‖_1 → p-norm
or equivalently, strict
subadditivity of minimum output Rényi p-entropy for any p > 1.


Let k be a positive integer. Let 1 < p ≤ 1.1.
Let W be a subspace of dimension 
m' := 
ĉ_3 k^4/3p + 5/3loglog k/(log k)^2
chosen with uniform probability from a 
k^ĉ_1 k^5 (log k)^-1/2-approximate unitary 
(2^11ĉ_1 k^5.1)-design 
from the Hilbert space ^k^3, where ĉ_1, ĉ_3 are
universal constants. Let Φ be the channel with output dimension
k corresponding to the
subspace W. Then with probability at least 1 - 2 · 2^-m' over the
choice of W,

    ‖Φ‖_1 → p≤
    2^7 k^1/p - 1, 
       ‖Φ⊗Φ̅‖_1 → p≥ĉ_3 k^4/3p - 4/3.

In other words,
‖Φ⊗Φ̅‖_1 → p >
‖Φ‖_1 → p·‖Φ̅‖_1 → p·
for large enough k. For p > 1.1, the  channel Φ obtained
for p = 1.1 suffices to show supermultiplicativity.


The input dimension of the channel Φ is W = m'. The 
Stinespring dilation
of the channel Φ is the k^3 × k^3 unitary matrix 
that defines the subspace W. The subspace W is obtained by
taking the first m' columns of the unitary matrix. This unitary
matrix is chosen uniformly at random from a
k^ĉ_1 k^5 (log k)^-1/2-approximate unitary 
(2^11ĉ_1 k^5.1)-design. Note that
2 a m < 2^11ĉ_1 k^5.1,
ϵ > k^ĉ_1 k^5 (log k)^-1/2,
where a, m and ϵ are defined in Step III above.
Let M be a unit ℓ_2-norm vector in ^k^3 rearranged as
a k × k^2 matrix.
From Equation <ref>, we get

    ‖Φ‖_1 → p =
    max_M ∈ W: ‖ M ‖_2 = 1‖ M ‖_2p^2 ≤
    2^7 k^1/p - 1.

From Fact <ref>, 

    ‖Φ⊗Φ̅‖_1 → p≥‖Φ⊗Φ̅‖_1 →∞≥m'/k^3 =
    ĉ_3 k^4/3p - 4/3loglog k/(log k)^2 >
    (‖Φ‖_1 → p)^2

for large enough k.
This shows the supermultiplicativity of the 
‖·‖_1 → p-norm for 1 < p ≤ 1.1. For
p > 1.1, we use the fact that 
‖·‖_1 →∞≤‖·‖_1 → p≤‖·‖_1 → 1.1
to  conclude the supermultiplicativity of 
‖·‖_1 → p.

Thus by setting p = 1.1, we see
that for large enough n approximate unitary 
(n^1.7log n)-designs give 
rise to channels
exhibiting strict subadditivity of minimum output Rényi p-entropy
for any p > 1. Combined with the result  of the previous section,
we can furthermore state 
that for large enough n approximate unitary 
(n^1.7log n)-designs give 
rise to channels
exhibiting strict subadditivity of minimum output Rényi p-entropy
for any p ≥ 1. 



  
Remarks:

1. 
In <cit.>, for channels obtained from
Haar random subspaces the lower bound on 
‖Φ⊗Φ̅‖_1 → p
was of the order of
k^1/p - 1,
whereas in our work it is 
of the order of
k^4/3p - 4/3,
for channels obtained from approximate t-designs.
Hence the counter example we get for additivity of minimum output
Rényi p-entropy of quantum channels, when the channel is 
chosen 
from an approximate unitary t-design has weaker parameters 
than the Haar random channels of
<cit.>. Nevertheless, our work 
is the first partial derandomisation of a construction of quantum
channels violating additivity of minimum output
Rényi p-entropy, since it is possible to uniformly
sample a unitary from an exact
(n^1.7log n)-design 
using of the order of
n^1.7 (log n)^2
random bits versus Ω(n^2) random bits required to choose 
a Haar random unitary to constant precision.



2.  
It is possible to do the above counterexample on a sphere in ^k^2. 
However
in that case the number of random bits required to choose a
unitary from an exact design is larger than k^4 log k, which is what a
Haar random unitary would require! 



3. 
It is worthwhile to note that, for channels Φ and Φ̅, with output dimension k, gap between the upper bound to S_min(Φ⊗Φ̅) and the lower bound to S_min(Φ)+S_min(Φ̅) is of the order O(log k/k - 1/k) when channel Φ is chosen from Haar measure, 
whereas this gap is O(loglog k/k - 1/k) when channel is chosen uniformly from an approximate unitary t-design. So as the output dimension of the channels increase, the counter example for p=1, becomes weak as the above mentioned gap of O(log k/k - 1/k)  or  O(loglog k/k - 1/k) decreases with increasing k. Also, in order to keep the constants showing up in the bound under control, one has to optimize over k, the output dimension of the channels. However, our counter example and for instance the existing counter example of Aubrun, Szarek and Werner <cit.> are still good enough even for arbitrarily large output dimensions. To see this, let channels Φ and Φ̅ violate the additivity of minimum output von Neumann entropy for an optimised output dimension k. This fixes the gap between the upper bound to S_min(Φ⊗Φ̅) and the lower bound to S_min(Φ)+S_min(Φ̅), according to whether the channels are chosen in a Haar random fashion or uniformly from an approximate t-design. In order to show that the counter example does not deteriorate with random channels of higher dimension, we define new channel as Φ' := Φ⊗Φ_Deopolarising where Φ_Depolarising is the completely depolarising channel given by Φ_Depolarising^A → B (ρ^A):= π^B and (Φ_Depolarising^A → B⊗^C) (ρ^AC):= π^B ⊗ρ^C, for all density operators ρ^A, ρ^AC. Hence the output dimension of the channel Φ' is k.d_Depolarising, where d_Depolarising is the output dimension of Φ_Depolarising. This trick works as S_min(ϕ')=log d_Depolarising+S_min(Φ). This ensures that the gap between the upper bound to S_min(Φ' ⊗Φ̅'̅) and the lower bound to S_min(Φ')+S_min(Φ̅'̅) is still the same as that for channels Φ and Φ̅.   
Due to the small magnitude of this gap coming up with an explicit formula or an efficient construction for additivity of minimum output von Neumann entropy is a much harder task than that for minimum output Rényi p entropy for p ≠ 1, as evident from <cit.>, which shows that in order to achieve “almost” one bit violation to additivity the output dimension of the channel should be at least 183.



4.On the other hand, the gap between the upper bound for S_p^min(Φ⊗Φ̅) and the lower bound for S_p^min(Φ)+S_p^min(Φ̅) is O(log k) for p>1 , when the channels Φ, Φ̅ are chosen according to Haar measure and O(2/3 log k) for channels being chosen from an approximate t-design. Here also k is the output dimension of the channels. There are two things to note:


  * This gap is much larger than that for the case when p=1 or for counter example to minimum output von Neumann entropy.

  * This gap does not decrease with increasing k
  
These points suggests that it is more feasible to come up with an explicit formula for channels violating additivity of minimum output Rényi p entropy, for p>1. Moreover, some known and efficient examples are that of the so-called Werner-Holevo channel <cit.> for p > 4.79 and channels arising from an antisymmetric subspace in <cit.> for p>2. An efficient counter for p close to and equal to 0, is also given in <cit.>, for a channel with input dimension 4 and output dimension 3. We note that we do not have a unique pair of channels Φ, Ψ that serves as counter example to additivity for Rényi p-entropy for all p ≥ 0.

Standard continuity arguments can be used to show that there exists 1> ϵ > 0 that violates the additivity conjecture for Rényi p-entropy for 1<p<1+ϵ, for the channel being described by a random unitary operator from an approximate k^2-design. However this ϵ is not explicitly known and depends on k. Finding this ϵ shall involve, restricting the value of k to be small so that the gap between the bounds is large enough. But for keeping constants in the several bounds tractable demands k to be large enough and hence there is no way to derandomise Aubrun, Szarek and Werner counter example for p>1 as in <cit.>. 
We thus take a first step towards this goal of derandomisation.  Our construction, via polynomial approximation of a monotonous function, in theorem <ref> gives an explicit value of ϵ=0.1 and guarantees that the gap between the upper bound for S_p^min(Φ⊗Φ̅) and the lower bound for S_p^min(Φ)+S_p^min(Φ̅) is O(2/3 log k), which is larger than that for von Neumann entropy. This comes at the cost of a larger value of t=k^5.1 for an approximate unitary t-design.
This restriction on the value of ϵ and the higher value of t, stems from approximating the square of Schatten 2p-norm  with a moderate degree polynomial, in order to replace a Haar random unitary via a t-design unitary operator. Hence, even for p>1 we have only partial derandomisation.



§ CONCLUSION


In this paper we have shown that a unitary chosen from an approximate 
unitary n^2/3-design leads
to a quantum channel with superadditive classical Holevo capacity. In the 
process of coming up
with such a channel we developed two new technical tools viz. 
stratified analysis 
of a sphere in ^n for Haar measure and unitary designs
(Theorems <ref>, <ref>),
and approximation of any continuous monotonic function by
a polynomial of moderate degree (Proposition <ref>). 
The stratified analysis for the Haar measure was used to
recover in a simple fashion Aubrun, Szarek and Werner's counterexample
<cit.> for
additivity of minimum output Von Neumann entropy. The stratified
analysis for unitary designs was used to prove
counterexamples for additivity of minimum output von Neumann entropy and
Rényi p-entropy for p > 1, when the unitary Stinespring dilation
of the channel is chosen from approximate unitary t-design for
suitable values of t. Choosing a unitary from these t-designs requires
less random bits than choosing from  the Haar measure. 
However the value of t required is much larger than what is known to
be efficiently implementable by quantum circuits.
We believe our work results in a better understanding of the interplay
between geometric functional analysis and additivity questions in
quantum information theory, and our technical tools will find applications
to other problems in quantum information theory.

Our  work represents a step in the  quest for an efficient explicit 
channel violating additivity of minimum output von Neumann entropy. This
is the major open problem in the area. Another problem left open is
whether there is a single channel that violates additivity of
minimum output Rényi p-entropy for all p ≥ 1.


