ON ALMOST RANDOMIZING CHANNELS WITH A SHORT KRAUS DECOMPOSITION

GUILLAUME AUBRUN

Abstract. For large d, we study quantum channels on C^{d} obtained by selecting randomly N independent Kraus operators according to a probability measure μ on the unitary group U(d). When μ is the Haar measure, we show that for N ≽ d/ε^{2}, such a channel is ε-randomizing with high probability, which means that it maps every state within distance ε/d (in operator norm) of the maximally mixed state. This slightly improves on a result by Hayden, Leung, Shor and Winter by optimizing their discretization argument. Moreover, for general μ, we obtain a ε-randomizing channel provided N ≽ d(log d)^{6}/ε^{2}. For d = 2^{k} (k qubits), this includes Kraus operators obtained by tensoring k random Pauli matrices. The proof uses recent results on empirical processes in Banach spaces.

1. Introduction

The completely randomizing quantum channel on C^{d} maps every state to the maximally mixed state ρ_{∗}. This channel is used to construct perfect encryption systems (see [1] for formal definitions). However it is a complex object in the following sense: any Kraus decomposition must involve at least d^{2} operators. It has been shown by Hayden, Leung, Shor and Winter [12] that this “ideal” channel can be efficiently emulated by lower-complexity channels, leading to approximate encryption systems. The key point is the existence of good approximations with much shorter Kraus decompositions. More precisely, say that a quantum channel Φ on C^{d} is ε-randomizing if for any state ρ, ∥Φ(ρ)−ρ_{∗}∥_{∞} ⩽ ε/d. The existence of ε-randomizing channels with o(d^{2}) Kraus operators has several other implications [12], such as counterexamples to multiplicativity conjectures [17].

It has been proved in [12] that if (U_{i}) denote independent random matrices Haar-distributed on the unitary group U(d), then the quantum channel

(1)  Φ : ρ ↦ \frac{1}{N} ∑_{j=1}^{N} U_{i}ρU_{i}^{†}

is ε-randomizing with high probability provided N ⩾ Cd log d/ε^{2} for some constant C. The proof uses a discretization argument and the fact that the Haar measure satisfies subgaussian estimates. We show a simple trick that allows to drop a log d factor: Φ is ε-randomizing when N ⩾ Cd/ε^{2}, this is our theorem 1.

The Haar measure is a nice object from the theoretical point of view, but is often too complicated to implement for concrete situations. Let us say that a measure μ on U(d) is isotropic when ∫ UρU^{†}dμ(U) = ρ_{∗} for any state ρ. When d = 2^{k}, an example of isotropic measure is given by assigning equal masses at k-wise tensor products of Pauli operators.

The following question was asked in [12]: is the quantum channel Φ defined as (1) ε-randomizing when (U_{i}) are distributed according to any isotropic probability measure on U(d) ? We answer positively this question when N ⩾ Cd log^{6} d/ε^{2}. This is our main result and appears as theorem 2. Note that for non-Haar measures, previous results appearing in the literature [12, 2, 8] involved the weaker trace-norm approximation ∥Φ(ρ) − ρ_{∗}∥_{1} ⩽ ε.

As opposed to the Haar measure, the measure μ need not have subgaussian tails, and we need more sophisticated tools to prove theorem 2. We use recent results on suprema of empirical processes in Banach spaces. After early work by Rudelson [15] and Guédon–Rudelson [11], a general sharp inequality was obtained by Guédon, Mendelson, Pajor and Tomczak–Jaegermann [10]. This inequality is valid in any Banach space with a sufficiently regular equivalent norm, such as ℓ_{1}^{d}. The problem of ε-randomizing channels involves the supremum of an empirical process in the trace-class space S_{1}^{d} (non-commutative analogue of ℓ_{1}^{d}), which enters perfectly this setting.

The paper is organized as follows. Section 2 contains background and precise statements of the theorems. Theorem 1 (for Haar measure) is proved in section 3. Theorem 2 (for a general measure) is proved in section 4. An appendix contains the needed facts about geometry and probability in Banach spaces.

Acknowledgement. I thank Andreas Winter for several e-mail exchanges on the topic, and I am very grateful to Alain Pajor for showing me that the results of [10] can be applied here.

2. Background and presentation of results

Thoughout the paper, the letter C and c denote absolute constants whose value may change from occurrence to occurrence. We usually do not pay too much attention to the value of these constants.

2.1. Schatten classes. We write M(C^{d}) for the space of complex d × d matrices. If A ∈ M(C^{d}), let s_{1}(A), …, s_{d}(A) denote the singular values of A (defined as the square roots of the eigenvalues of AA^{†}). For 1 ⩽ p ⩽ ∞, the Schatten p-norm is defined as

∥A∥_{p} = (∑_{i=1}^{d} s_{i}(A)^{p})^{1/p} .

For p = ∞, the definition should be understood as ∥A∥_{∞} = max s_{i}(A) and coincides with the usual operator norm. It is well-known (see [5], section IV.2) that (M(C^{d}), ∥ · ∥_{p}) is a complex normed space, denoted S_{p}^{d} and called Schatten class. The space S_{p}^{d} is the non-commutative analogue of the space ℓ_{p}^{d}. We write B(S_{p}^{d}) for the unit ball of S_{p}^{d}.

The Schatten 2-norm (sometimes called Hilbert–Schmidt or Frobenius norm) is a Hilbert space norm associated to the inner product ⟨A, B⟩ = Tr A^{†}B. This Hermitian structure allows to identify M(C^{d}) with its dual space. Duality on Schatten norms holds as in the commutative case: if p and q are conjugate exponents (i.e. 1/p + 1/q = 1), then the normed space dual to S_{p}^{d} coincides with S_{q}^{d}.

2.2. Completely positive maps. We write M_{sa}(C^{d}) (resp. M_{+}(C^{d})) for the set of self-adjoint (resp. positive semi-definite) d × d matrices. A linear map Φ : M(C^{d}) → M(C^{d}) is said to preserve positivity if Φ(M_{+}(C^{d})) ⊂ M_{+}(C^{d}). Moreover, Φ is said to be completely positive if for any k ∈ N, the map

Φ ⊗ Id_{M(C^{k})} : M(C^{d} ⊗ C^{k}) → M(C^{d} ⊗ C^{k})

preserves positivity. We use freely the canonical identification M(C^{d}) ⊗ M(C^{k}) ≈ M(C^{d} ⊗ C^{k}).

If (e_{i})_{0⩽i⩽d−1} denotes the canonical basis of C^{d}, let E_{ij} = |e_{i}⟩⟨e_{j}|. To Φ : M(C^{d}) → M(C^{d}) we associate A_{Φ} ∈ M(C^{d} ⊗ C^{d}) defined as

A_{Φ} = ∑_{i,j=1}^{d} E_{ij} ⊗ Φ(E_{ij}).

The matrix A_{Φ} is called the Choi matrix of Φ ; it is well-known [7] that Φ is completely positive if and only if A_{Φ} is positive. Therefore, the set of completely positive operators on M(C^{d}) is in oneto-one correspondence with M_{+}(C^{d} ⊗ C^{d}). This correspondence is known as the Choi–Jamiołkowski isomorphism.

The spectral decomposition of A_{Φ} implies now the following: any completely positive map Φ on M(C^{d}) can be decomposed as

(2)  Φ : X ↦ ∑_{i=1}^{N} V_{i}XV_{i}^{†}.

Here V_{1}, …, V_{N} are elements of M(C^{d}). This decomposition is called a Kraus decomposition of Φ of length N. The minimal length of a Kraus decomposition of Φ (called Kraus rank) is equal to the rank of the Choi matrix A_{Φ}. In particular it is always bounded by d^{2}.

2.3. States and the completely depolarizing channel. A state on C^{d} is a element of M_{+}(C^{d}) with trace 1. We write D(C^{d}) for the set of states ; it is a compact convex set with (real) dimension d^{2} − 1. If x ∈ C^{d} is a unit vector, we write P_{x} = |x⟩⟨x| for the associated rank one projector. The state P_{x} is called a pure state, and it follows from spectral decomposition that any state is a convex combination of pure states. A central role is played by the maximally mixed state ρ_{∗} = Id/d (ρ_{∗} is sometimes called the random state).

A quantum channel Φ : M(C^{d}) → M(C^{d}) is a completely positive map which preserves trace: for any X ∈ M(C^{d}), Tr Φ(X) = Tr X. Note that a quantum channel maps states to states. The trace-preserving condition reads on the Kraus decomposition (2) as

∑_{i=1}^{N} V_{i}^{†}V_{i} = Id.

An example of quantum channel that plays a central role in quantum information theory is the (completely) randomizing channel (also called completely depolarizing channel) R : M(C^{d}) → M(C^{d}).

R : X → Tr X · \frac{Id}{d}.

The randomizing channel maps every state to ρ_{∗}. The Choi matrix of R is A_{R} = \frac{1}{d}Id_{C^{d}⊗C^{d}}. Since A_{R} has full rank, any Kraus decomposition of R must have length (at least) d^{2}. An explicit decomposition can be written using Fourier-type unitary operators: let ω = exp(2iπ/d) and A and B the matrices defined as

(3)  A(e_{j}) = e_{j+1 mod d}  B(e_{j}) = ω^{j}e_{j}.

For 1 ⩽ j, k ⩽ d, define V_{j,k} as the product B^{j}A^{k}. Note that V_{j,k} belongs to the unitary group U(d). A routine calculation (see also section 2.5) shows that for any X ∈ M(C^{d}),

\frac{1}{d^{2}} ∑_{j,k=1}^{d} V_{j,k}XV_{j,k}^{†} = Tr X · \frac{Id}{d}.

This is a Kraus decomposition of the randomizing channel.

2.4. ε-randomizing channels. We are interested in approximating the randomizing channel R by channels with low Kraus rank. Following Hayden, Leung, Shor and Winter [12], a quantum channel Φ is called ε-randomizing if for any state ρ ∈ D(C^{d}),

∥Φ(ρ) − ρ_{∗}∥_{∞} ⩽ \frac{ε}{d}.

It is equivalent to say that the spectrum of Φ(ρ) is contained in [(1 − ε)/d, (1 + ε)/d] for any state ρ. It has been proved in [12] that there exist ε-randomizing channels with Kraus rank equal to Cd log d/ε^{2} for some constant d. This is much smaller that d^{2} (the Kraus rank of R). The construction is simple: generate independent random Kraus operators according to the Haar measure on U(d) and show that the induced quantum channel is ε-randomizing with nonzero probability. A key step in the proof is a discretization argument. We show that a simple trick improves the efficiency of the argument from [12] to prove the following

Theorem 1 (Haar-generated ε-randomizing channels). Let (U_{i})_{1⩽i⩽N} be independent random matrices Haar-distributed on the unitary group U(d). Let Φ : C^{d} → C^{d} be the quantum channel defined by

Φ(ρ) = \frac{1}{N} ∑_{i=1}^{N} U_{i}ρU_{i}^{†}.

Assume that 0 < ε < 1 and N ⩾ Cd/ε^{2}. Then the channel Φ is ε-randomizing with nonzero probability.

As often with random constructions, we actually prove that the conclusion holds true with large probability: the probability of failure is exponentially small in d.

It is clear that the way N depends on d is optimal: if Φ is a ε-randomizing channel with ε < 1, its Kraus rank must be at least d. This is because for any pure state P_{x}, Φ(P_{x}) must have full rank. The dependence in ε is sharp for channels as constructed here, since lemma 2 below is sharp. However, it is not clear whether families of ε-randomizing channels with a better dependence in ε can be found using a different construction, possibly partially deterministic.

One checks (using the value c = 1/6 from [12] in lemma 3 and optimizing over the net size) that the constant in theorem 1 can the chosen to, e.g., C = 150. This is presumably far from optimal.

2.5. Isotropic measures on unitary matrices. Although the quantum channels constructed in theorem 1 have minimal Kraus rank, it can be argued that Haar-distributed random matrices are hard to generate in real-life situations. We introduce a wide class of measures on U(d) that may replace the Haar measure.

Definition. Say that a probability measure μ on U(d) is isotropic if for any X ∈ M(C^{d}),

∫_{U(d)} UXU^{†}dμ(U) = Tr X · \frac{Id}{d}.

Similarly, a U(d)-valued random vector is called isotropic if its law is isotropic.

Lemma 1. Let U = (U_{ij}) be a U(d)-valued random vector. The following assertions are equivalent (1) U is isotropic.

(2) For any X ∈ M(C^{d}), E| Tr UX^{†}|^{2} = \frac{1}{d}∥X∥_{2}^{2}.

(3) For any indices i, j, k, l, EU_{ij}\overline{U_{kl}} = \frac{1}{d}δ_{i,k}δ_{j,l}.

Proof. Implications (3) ⇒ (1) and (3) ⇒ (2) are easily checked by expansion. For (1) ⇒ (3), simply take X = |e_{j}⟩⟨e_{k}|. Identity (2) implies after polarization that for any A, B ∈ M(C^{d}),

E [\overline{Tr(UA^{†})} Tr(UB^{†})] = \frac{1}{d} Tr(AB^{†}),

from which (3) follows. □

Condition (3) of the lemma means that the covariance matrix of U — which is an element of M(M(C^{d})) — is a multiple of the identity matrix.

Of course the Haar measure is isotropic. Other examples are provided by discrete measures. Let 𝒰 = {U_{1}, …, U_{d^{2}}} be a family of unitary matrices, which are mutually orthogonal in the following sense: if i ≠ j, then Tr U_{i}^{†}U_{j} = 0. For example, one can take 𝒰 = {B^{j}A^{k}}_{1⩽j,k⩽d}, A, B defined as (3). Then the uniform probability measure on 𝒰 is isotropic. Indeed, any X ∈ M(C^{d}) can be decomposed as X = ∑ x_{i}U_{i} and condition (2) of lemma 1 is easily checked.

If we specialize to d = 2, we obtain a random Pauli operator: assign probability 1/4 to each of the following matrices to get a isotropic measure

σ_{0} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , σ_{1} = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) , σ_{2} = ( \begin{matrix}0 & −i \\ i & 0 \end{matrix} ) , σ_{3} = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) .

It is straightforward to check that isotropic vectors tensorize: if X_{1} ∈ U(d_{1}) and X_{2} ∈ U(d_{2}) are isotropic, so is X_{1} ⊗ X_{2} ∈ U(d_{1}d_{2}). If we work on M((C^{2})^{⊗k}), which corresponds to a set of k qubits, a natural isotropic measure is therefore obtained by choosing independently a Pauli matrix on each qubit, i.e. assigning mass 1/4^{k} to the matrix σ_{i_{1}} ⊗ ⋯ ⊗ σ_{i_{k}} for any i_{1}, …, i_{k} ∈ {0, 1, 2, 3}^{k}.

2.6. ε-randomizing channels for an isotropic measure. We can now state our main theorem asserting that up to logarithmic terms, the Haar measure can be replaced in theorem 1 by simpler notions of randomness. We first state our result

Theorem 2 (General ε-randomizing channels). Let μ be an isotropic measure on the unitary group U(d). Let (U_{i})_{1⩽i⩽N} be independent μ-distributed random matrices, and Φ : C^{d} → C^{d} be the quantum channel defined as

(4)  Φ(ρ) = \frac{1}{N} ∑_{i=1}^{N} U_{i}ρU_{i}^{†}.

Assume that 0 < ε < 1 and N ⩾ Cd(log d)^{6}/ε^{2}. Then the channel Φ is ε-randomizing with nonzero probability.

Theorem 2 applies in particular for product of random Pauli matrices as described in the previous section. It is of interest for certain cryptographic applications to know that ε-randomizing channels can be realized using Pauli matrices.

As opposed to theorem 1, the conclusion of theorem 2 is not proved to hold with exponentially large probability. Applying the theorem with εη instead of ε and using Markov inequality shows that Φ is ε-randomizing with probability larger than 1 − η provided N ⩾ Cd log^{6} d/(ε^{2}η^{2}).

Theorem 2 could be quickly deduced from a theorem appearing in [10]. However, the proof of [10] is rather intricate and uses Talagrand’s majorizing measures in a central way. We give here a proof of our theorem which uses the simpler Dudley integral instead, giving the same result. We however rely an a entropy lemma from [10], which appears as lemma A5 in the appendix.

The log^{6} d appearing in theorem 2 is certainly non optimal (see remarks at the end of the paper). However, some power of log d is needed, as shown by the next proposition.

Proposition. Let A, B defined as (3) and μ be the uniform measure on the set {B^{j}A^{k}}_{1⩽j,k⩽d}. Consider (X_{i}) independent μ-distributed random unitary matrices. If the quantum channel Φ defined as (4) is \frac{1}{2}-randomizing with probability larger than 1/2, then N ⩾ cd log d.

Proof. We will rely on the following standard result in elementary probability theory known as the coupon collector’s problem (see [9], Chapter 1, example 5.10): if we choose independently and uniformly random elements among a set of d elements, the mean (and also the median) number of choices before getting all elements at least once is equivalent to d log d for large d.

In our case, remember that ω = exp(2iπ/d) and for 0 ⩽ j ⩽ d − 1, define x_{j} ∈ C^{d} as

x_{j} = (\frac{1}{\sqrt{d}}, \frac{ω^{j}}{\sqrt{d}}, \frac{ω^{2j}}{\sqrt{d}} , …, \frac{ω^{(d−1)j}}{\sqrt{d}} ) .

Note that ℬ = (x_{j})_{0⩽j⩽d−1} is an orthonormal basis of C^{d} and that B^{j}A^{k}x_{0} = x_{j}. Consequently, if U is μ-distributed, the random state UP_{x_{0}}U^{†} equals P_{x_{j}} with probability 1/d. In the basis ℬ, the matrix Φ(P_{x_{0}}) is diagonal. Note that if Φ is \frac{1}{2}-randomizing, then Φ(P_{x_{0}}) must have full rank. The reduction to the coupon collector’s problem is now immediate. □

3. Proof of theorem 1: Haar-distributed unitary operators.

The scheme of the proof is similar to [12]. We need two lemmas from there. The first is a deviation inequality sometimes known as Bernstein’s inequality. The second is proved by a volumetric argument.

Lemma 2 (Lemma II.3 in [12]). Let φ, ψ be pure states on C^{d} and (U_{i})_{1⩽i⩽N} be independent Haardistributed random unitary matrices. Then for every 0 < δ < 1,

P (|\frac{1}{N} ∑_{i=1}^{N} Tr(U_{i}φU_{i}^{†}ψ) − \frac{1}{d}| ⩾ \frac{δ}{d}) ⩽ 2 exp(−cδ^{2}N)

Lemma 3 (Lemma II.4 in [12]). For 0 < δ < 1 there exists a set N of pure states on C^{d} with |N | ⩽ (5/δ)^{2d}, such that for every pure state φ on C^{d}, there exists φ_{0} ∈ N such that ∥φ − φ_{0}∥_{1} ⩽ δ. Such a set N is called a δ-net.

The improvement on the result of [12] will follow from the next lemma

Lemma 4 (Computing norms on nets). Let Δ : B(C^{d}) → B(C^{d}) be a Hermitian-preserving linear map. Let A be the quantity

A = sup_{φ∈D(C^{d})} ∥Δ(φ)∥_{∞} = sup_{φ,ψ∈D(C^{d})} |Tr ψΔ(φ)|

Let 0 < δ < 1/2 and N be a δ-net as provided by lemma 3. We can evaluate A as follows

A ⩽ \frac{1}{1 − 2δ} B,

where

B = sup_{φ_{0},ψ_{0}∈N} |Tr ψ_{0}Δ(φ_{0})|

Proof of lemma 4. First note that for any self-adjoint operators a, b ∈ B(C^{d}), we have

(5)  |Tr bΔ(a)| ⩽ A∥a∥_{1}∥b∥_{1}.

By a convexity argument, the supremum in A can be restricted to pure states. Given pure states φ, ψ ∈ D(C^{d}), let φ_{0}, ψ_{0} ∈ N so that ∥φ − φ_{0}∥_{1} ⩽ δ, , ∥ψ − ψ_{0}∥_{1} ⩽ δ. Then

|Tr ψΔ(φ)| ⩽ |Tr(ψ − ψ_{0})Δ(φ)| + |Tr ψ_{0}Δ(φ − φ_{0})| + |Tr ψ_{0}Δ(φ_{0})|

Using twice (5) and taking supremum over φ, ψ gives A ⩽ δA + δA + B, hence the result. □

Proof of the theorem. Let R be the randomizing channel. Fix a \frac{1}{4}-net N with |N | ⩽ 20^{2d}, as provided by lemma 3. Let Δ = R − Φ and A, B as in lemma 4. Here A and B are random quantities and it follows from lemma 4 that

P (A ⩾ \frac{ε}{d}) ⩽ P (B ⩾ \frac{ε}{2d}) .

Using the union bound and lemma 2, we get

P (B ⩾ \frac{ε}{2d}) ⩽ 20^{4d} · 2 exp(−cε^{2}N/4).

This is less that 1 if N ⩾ Cd/ε^{2}, for some constant C. □

4. Proof of theorem 2: general unitary operators.

A Bernoulli random variable is a random variable ε so that P(ε = 1) = P(ε = −1) = 1/2. Recall that C denotes an absolute constant whose value may change from occurrence to occurrence. We will derive theorem 2 from the following lemma.

Lemma 5. Let U_{1}, …, U_{N} ∈ U(d) be deterministic unitary operators and let (ε_{i}) be a sequence of independent Bernoulli random variables. Then

(6)  E_{ε} sup_{ρ∈D(C^{d})} ∥∑_{i=1}^{N} ε_{i}U_{i}ρU_{i}^{†}∥_{∞} ⩽ C(log d)^{5/2}\sqrt{log N} sup_{ρ∈D(C^{d})} ∥∑_{i=1}^{N} U_{i}ρU_{i}^{†}∥_{∞}^{1/2} .

Proof of theorem 2 (assuming lemma 5). Let μ be an isotropic measure on U(d) and (U_{i}) be independent μ-distributed random unitary matrices. Let M be the random quantity

M = sup_{ρ∈D(C^{d})} ∥\frac{1}{N} ∑_{i=1}^{N} U_{i}ρU_{i}^{†} − \frac{Id}{d}∥_{∞}

We are going to show that EM is small. The first step is a standard symmetrization argument. Let (U′_{i}) be independent copies of (U_{i}) and (ε_{i}) be a sequence of independent Bernoulli random variables. We explicit as a subscript the random variables with repsect to which expectation is taken

EM ⩽ E_{U,U′} sup_{ρ∈D(C^{d})} ∥\frac{1}{N} ∑_{i=1}^{N} U_{i}ρU_{i}^{†} − U′_{i}ρU_{i}^{′†}∥_{∞}

= E_{U,U′,ε} sup_{ρ∈D(C^{d})} ∥\frac{1}{N} ∑_{i=1}^{N} ε_{i}(U_{i}ρU_{i}^{†} − U′_{i}ρU_{i}^{′†})∥_{∞}

⩽ 2E_{U,ε} sup_{ρ∈D(C^{d})} ∥\frac{1}{N} ∑_{i=1}^{N} ε_{i}U_{i}ρU_{i}^{†}∥_{∞}

The inequality of the first line is Jensen’s inequality for E_{U′}, while the equality on the second line holds since the distribution of ρ ↦ U_{i}ρU_{i}^{†} − U′_{i}ρU_{i}^{′†} is symmetric (as a M(M(C^{d}), M(C^{d}))-valued random vector). We then decouple the expectations using lemma 5 for fixed (U_{i}).

EM ⩽ \frac{C}{\sqrt{N}} (log d)^{5/2}\sqrt{log N}E sup_{ρ∈D(C^{d})} ∥\frac{1}{N} ∑_{i=1}^{N} U_{i}ρU_{i}^{†}∥_{∞}^{1/2}

⩽ \frac{C}{\sqrt{N}} (log d)^{5/2}\sqrt{log N}E\sqrt{M + \frac{1}{d}}
⩽ \frac{C}{\sqrt{N}} (log d)^{5/2}\sqrt{log N}\sqrt{EM + \frac{1}{d}}

Using the elementary implication

X ⩽ α\sqrt{X + β} ⟹ X ⩽ α^{2} + α\sqrt{β}

we find that EM ⩽ ε/d provided N ⩾ Cd log^{6} d/ε^{2}. □

It remains to prove lemma 5. We will use several standard concepts from geometry and probability in Banach spaces. All the relevant definitions and statements are postponed to the next section.

Proof of lemma 5. Let Z be the quantity appearing in the left-hand side of (6). By a convexity argument, the supremum is attained for an extremal ρ, i.e. a pure state P_{x} = |x⟩⟨x| for some unit vector x. Since the operator norm itself can be written as a supremum over unit vectors, we get

Z = sup_{|x|=|y|=1} |∑_{i=1}^{N} ε_{i}|⟨y|U_{i}|x⟩|^{2}| = sup_{|x|=|y|=1} |∑_{i=1}^{N} ε_{i}| Tr U_{i}|x⟩⟨y||^{2}| ⩽ sup_{A∈B(S_{1}^{d})} |∑_{i=1}^{N} ε_{i}| Tr U_{i}A|^{2}| .

The last inequality follows from the fact that B(S_{1}^{d}) = conv{|x⟩⟨y|, |x| = |y| = 1}. Let Φ : B(S_{1}^{d}) → R^{N} defined as

Φ(A) = (| Tr U_{1}A|^{2}, …, | Tr U_{N}A|^{2}).

We now apply Dudley’s inequality (theorem A2 in the next section) with K = Φ(B(S_{1}^{d})) to estimate EZ using covering numbers. This yields

EZ ⩽ C ∫_{0}^{∞} \sqrt{log N(Φ(B(S_{1}^{d})), | · |, ε)}dε

where | · | denotes the Euclidean norm on R^{N}. Define a distance δ on B(S_{1}^{d}) as

δ(A, B) = |Φ(A) − Φ(B)| = (∑_{i=1}^{N} || Tr U_{i}A|^{2} − | Tr U_{i}B|^{2}|^{2})^{1/2} .

We are led to the estimate

EZ ⩽ C ∫_{0}^{∞} \sqrt{log N(B(S_{1}^{d}), δ, ε)}dε.

Using the inequality ||a|^{2} − |b|^{2}| ⩽ |a − b| · |a + b|, the metric δ can be upped bounded as follows

δ(A, B)^{2} ⩽ (∑_{i=1}^{N} | Tr U_{i}(A + B)|^{2}) sup_{1⩽i⩽N} | Tr U_{i}(A − B)|^{2}.

Let us introduce a new norm ||| · ||| on M(C^{d})

|||A||| = sup_{1⩽i⩽N} | Tr U_{i}A|.

Let θ be the number equal to

θ := sup_{A∈B(S_{1}^{d})} ∑_{i=1}^{N} | Tr U_{i}A|^{2} = sup_{ρ∈D(C^{d})} ∥∑_{i=1}^{N} U_{i}ρU_{i}^{†}∥_{∞} .

We get that for A, B ∈ B(S_{1}^{d}), δ(A, B) ⩽ 2θ|||A − B|||, and therefore

EZ ⩽ Cθ ∫_{0}^{∞} \sqrt{log N(B(S_{1}^{d}), ||| · |||, ε)}dε.

It remains to bound this new entropy integral. We split it into three parts, for ε_{0} to be determined. If ε is large (ε > 1), since ∥U_{i}∥_{∞} = 1, we get that ||| · ||| ⩽ ∥ · ∥_{1}. This means that N(B(S_{1}^{d}), ||| · |||, ε) = 1 and the integrand is zero. If ε is small (0 < ε < ε_{0}), we use the volumetric argument of lemma A1

N(B(S_{1}^{d}), ||| · |||, ε) ⩽ N(B(S_{1}^{d}), ∥ · ∥_{1}, ε) ⩽ (3/ε)^{2d^{2}}.

In the intermediate range (ε_{0} ⩽ ε ⩽ 1), let q = log d and p = 1 + 1/(log d − 1) be the conjugate exponent. We are going to approximate the Schatten 1-norm by the Schatten p-norm. It is elementary to check that for A ∈ M(C^{d}), ∥A∥_{q} ⩽ e∥A∥_{∞}. By dualizing

∥A∥_{1} ⩽ e∥A∥_{p} ⟹ N(B(S_{1}^{d}), ||| · |||, ε) ⩽ N(B(S_{p}^{d}), ||| · |||, ε/e).

We are now in position to apply lemma A5 to the space E = S_{p}^{d}. By theorems A3 and A4, the 2-convexity constant of S_{p}^{d} and the type 2 constant of S_{q}^{d} (see next section for definitions) are bounded as follows

T_{2}(S_{q}^{d}) ⩽ λ(S_{p}^{d}) ⩽ \sqrt{q − 1} ⩽ \sqrt{log d}.

Since ∥U_{i}∥_{q} ⩽ e, the inequality given by lemma A5 is

\sqrt{log N(B(S_{1}^{d}), ||| · |||, ε)} ⩽ \frac{C}{ε} (log d)^{3/2}\sqrt{log N}.

We now gather all the estimations

∫_{0}^{∞} \sqrt{log N(B(S_{1}^{d}), ||| · |||, ε)}dε ⩽ ∫_{0}^{ε_{0}} \sqrt{2d^{2}} log(3/ε)dε + C(log d)^{3/2}\sqrt{log N} ∫_{ε_{0}}^{1} \frac{1}{ε}dε.

Choosing ε_{0} = 1/d, an immediate computation shows that

∫_{0}^{∞} \sqrt{log N(B(S_{1}^{d}), ||| · |||, ε)}dε ⩽ C(log d)^{5/2}\sqrt{log N}.

This concludes the proof of the lemma. □

Appendix : Geometry of Banach spaces

In this last section, we gather several definitions and results from geometry and probability in Banach spaces. We denote by (E, ∥ · ∥) a real or complex Banach space (actually, in our applications E will be finite-dimensional). We denote by (E^{∗}, ∥ · ∥_{∗}) the dual Banach space.

4.1. Covering numbers.

Definition. If (K, δ) is a compact metric space, the covering number or entropy number N(K, δ, ε) is defined to be the smallest cardinality M of a set {x_{1}, …, x_{M}} ⊂ K so that

K ⊂ ⋃_{i=1}^{M} B(x_{i}, ε)

where B(x, ε) = {y ∈ K s.t. δ(x, y) ⩽ ε}.

An especially important case is when K is a subset of R^{n} and δ is induced by a norm. The next lemma is proved by a volumetric argument (see [13], Lemma 9.5).

Lemma A1. If ∥·∥ is a norm on R^{n} with unit ball K, then for every ε > 0, N(K, ∥·∥, ε) ⩽ (1+2/ε)^{n}.

The following theorem gives upper bounds on Bernoulli averages involving covering numbers. For a proof, see Lemma 4.5 and Theorem 11.17 in [13].

Theorem A2 (Dudley’s inequality). Let (ε_{i}) be independent Bernoulli random variables and K be a compact subset of R^{n}. Denote by (x_{1}, …, x_{n}) the coordinates of a vector x ∈ R^{n}. Then for some absolute constant C,

E max_{x∈K} ∑_{i=1}^{n} ε_{i}x_{i} ⩽ C ∫_{0}^{∞} \sqrt{log N(K, | · |, ε)}dε

where | · | denotes the Euclidean norm on R^{n}.

4.2. 2-convexity.

Definition. A Banach space (E, ∥ · ∥) is said to be 2-convex with constant λ if for any y, z ∈ E, we have

∥y∥^{2} + λ^{−2}∥z∥^{2} ⩽ \frac{1}{2}(∥y + z∥^{2} + ∥y − z∥^{2}).

The smallest such λ is called the 2-convexity constant of E and denoted by λ(E).

We say shortly that “E is 2-convex” while the usual terminology should be “E has a modulus of convexity of power type 2”. This should not be confused with the notion of 2-convexity for Banach lattices [14].

It follows from the parallelogram identity that a Hilbert space is 2-convex with constant 1. Other examples are ℓ_{p} and S_{p}^{d} for 1 < p ⩽ 2. The next theorem has been proved by Ball, Carlen and Lieb [4], refining on early work by Tomczak–Jaegermann [16].

Theorem A3. For p ⩽ 2, the following inequality holds for A, B ∈ M(C^{d})

∥A∥_{p}^{2} + (p − 1)∥B∥_{p}^{2} ⩽ \frac{1}{2} (∥A + B∥_{p}^{2} + ∥A − B∥_{p}^{2}) .

Therefore, S_{p}^{d} is 2-convex with constant 1/\sqrt{p − 1}.

This property nicely dualizes. Indeed, it is easily checked (see [4], lemma 5) that E is 2-convex with constant λ if any only if, for every y, z ∈ E^{∗},

∥y∥_{∗}^{2} + λ^{2}∥z∥_{∗}^{2} ⩾ \frac{1}{2}(∥y + z∥_{∗}^{2} + ∥y − z∥_{∗}^{2}).

In this case, E^{∗} is said to be 2-smooth with constant λ.

4.3. Type 2.

Definition. A Banach space (E, ∥ · ∥) is said to have type 2 if there exists a constant T_{2} so that for any finite sequence y_{1}, …, y_{N} of vectors of E, we have

(7)  (E ∥∑_{i=1}^{N} ε_{i}y_{i}∥^{2})^{1/2} ⩽ T_{2} (∑_{i=1}^{N} ∥y_{i}∥^{2})^{1/2} .

The smallest possible T_{2} is called the type 2 constant of E and denoted T_{2}(E). Here, the expectation E is taken with respect to a sequence (ε_{i}) of independent Bernoulli random variables.

It follows from the (generalized) parallelogram identity that a Hilbert space has type 2 with constant 1, and there is actually equality in (7). If a Banach space E is 2-convex, then E^{∗} is 2-smooth. It is easily checked (by induction on the number of vectors involved) that a 2-smooth Banach space has type 2 with the same constant. We therefore have the inequality T_{2}(E^{∗}) ⩽ λ(E). In particular, theorem A3 implies the following result, first proved by Tomczak-Jaegermann [16] with a worse constant.

Theorem A4. If q ⩾ 2, then S_{q}^{d} has type 2 with the estimate

T_{2}(S_{q}^{d}) ⩽ \sqrt{q − 1}.

4.4. An entropy lemma. The following lemma plays a key role in our proof. It appears as Lemma 1 in [10].

Lemma A5. Let E be a Banach space with unit ball B(E). Assume that E is 2-convex with constant λ(E). Let x_{1}, …, x_{N} be elements of E^{∗}, and define a norm ||| · ||| on E as

|||y||| = max_{1⩽i⩽N} |x_{i}(y)|.

Then for any ε > 0 we have for some absolute constant C

(8)  ε\sqrt{log N(B(E), ||| · |||, ε)} ⩽ Cλ(E)^{2}T_{2}(E^{∗})\sqrt{log N} max_{1⩽i⩽N} ∥x_{i}∥_{E^{∗}}.

The proof of lemma A5 is based on a duality argument for covering numbers coming from [6]. A positive answer to the duality conjecture for covering numbers (see [3] for a statement of the conjecture and recent results) would imply that the inequality (8) is valid without the factor λ(E)^{2}. This would improve our estimate in theorem 2 to N ⩾ Cd(log d)^{4}/ε^{2}.

References

[1] A. Ambainis, M. Mosca, A. Tapp and R. de Wolf, Private quantum channels. 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), 547–553, IEEE Comput. Soc. Press.

[2] A. Ambainis and A. Smith, Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption, Proceedings of RANDOM’04, 249–260.

[3] S. Artstein, V. Milman, S. Szarek and N. Tomczak–Jaegermann, On convexified packing and entropy duality. Geom. Funct. Anal. 14 (2004), no. 5, 1134–1141.

[4] K. Ball, E. Carlen and E. Lieb, Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115 (1994), no. 3, 463–482.

[5] R. Bhatia, Matrix analysis. Graduate Texts in Mathematics 169. Springer-Verlag, 1997.

[6] J. Bourgain, A. Pajor, S. Szarek and N. Tomczak-Jaegermann, On the duality problem for entropy numbers of operators. Geometric aspects of functional analysis (1987–88), 50–63, Lecture Notes in Math. 1376 (1989).

[7] M. D. Choi, Completely positive linear maps on complex matrices. Linear Algebra and Appl. 10 (1975), 285–290.

[8] P. Dickinson and A. Nayak, Approximate Randomization of Quantum States With Fewer Bits of Key, AIP Conference Proceedings 864, 18–36 (2006).

[9] R. Durrett, Probability. Theory and examples, The Wadsworth & Brooks/Cole Statistics/Probability Series, 1991.

[10] O. Guédon, S. Mendelson, A. Pajor and N. Tomczak–Jaegermann, Majorizing measures and proportional subsets of bounded orthonormal systems, preprint (2008).

[11] O. Guédon and M. Rudelson, L_{p}-moments of random vectors via majorizing measures, Adv. Math. 208 (2007), no. 2, 798–823.

[12] P. Hayden, D. Leung, P. W. Shor and A. Winter, Randomizing quantum states: constructions and applications, Comm. Math. Phys. 250 (2004), 371–391.

[13] M. Ledoux and M. Talagrand, Probability in Banach spaces. Isoperimetry and processes. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 23. Springer-Verlag, 1991.

[14] J. Lindenstrauss and L. Tzafriri, Classical Banach spaces. II. Function spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete 97. Springer-Verlag, 1979.

[15] M. Rudelson, Random vectors in the isotropic position. J. Funct. Anal. 164 (1999), no. 1, 60–72.

[16] N. Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ⩽ p < ∞). Studia Math. 50 (1974), 163–182.

[17] A. Winter, The maximum output p-norm of quantum channels is not multiplicative for any p> 2, arxiv 0707.0402