Estimating operator norms using covering nets

arXiv:1509.05065v1 [quant-ph] 16 Sep 2015

Fernando G.S.L. Brandão

∗

Aram W. Harrow

†

Abstract
We present several polynomial- and quasipolynomial-time approximation schemes for a large class of
generalized operator norms. Special cases include the 2 → q norm of matrices for q > 2, the support
function of the set of separable quantum states, finding the least noisy output of entanglement-breaking
quantum channels, and approximating the injective tensor norm for a map between two Banach spaces
whose factorization norm through `n
1 is bounded.
These reproduce and in some cases improve upon the performance of previous algorithms by BrandãoChristandl-Yard [BCY11] and followup work, which were based on the Sum-of-Squares hierarchy and
whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering
nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Net-based algorithms for similar problems were also presented by
Shi-Wu [SW12] and Barak-Kelner-Steurer [BKS13], but in each case with a run-time that is exponential
in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much
smaller nets that exist in `1 spaces. This principle has been used in learning theory, where it is known
as Maurey’s empirical method.

1

Introduction

Given a n × m matrix M , its operator norm is given by kM k = maxx∈Cm kM xk2 /kxk2 , with kxk2 =
P
1
( i |xi |2 ) 2 the Euclidean norm. The operator norm is also given by the square root of the largest eigenvalue
of M † M and thus can be efficiently computed. There are numerous ways of generalizing the operator norm,
e.g. by considering tensors instead of matrices, by changing the Euclidean norm to another norm, or by
considering other vector spaces instead of Cm . Although such generalizations are very useful in applications,
they can be substantially harder to compute than the basic operator norm, and in many cases we still do
not have a good grasp of the computational complexity of computing, or even only approximating, them.
In some cases quasipolynomial algorithms are known, usually based on semidefinite programming (SDP)
hierarchies, and in other cases quasipolynomial hardness results are known. These are partially overlapping
so that some problems have sharp bounds on their complexity and for others there are exponential gaps
between the best upper and lower bounds. As we will discuss below, the complexity of these problems is not
only a basic question in the theory of algorithms, but also is closely related to the unique games conjecture
and the power of multiprover quantum proof systems.
In this paper we give new algorithms for several variants of the basic operator norm of interest in quantum
information theory, theoretical computer science, and the theory of Banach spaces. Unlike most past work
which was based on SDP hierarchies, our algorithms simply enumerate over a carefully chosen net of points.
This yields run-times that often match the SDP hierarchies and sometimes improve upon them. Besides
improved performance, our algorithms have the advantage of being based on simple geometric properties of
spaces we are optimizing over, which may help explain which types of norms are amenable to quasipolynomial
optimization. In particular we consider the following four optimization problems in this work:
Optimization over Separable States: An important problem in quantum information theory is
to optimize a linear function over the set of separable (i.e. non-entangled) states, defined as bipartite
∗ (a) Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA and (b) Department of Computer
Science, University College London WC1E 6BT. email: fbrandao@microsoft.com
† Center for Theoretical Physics, Massachusetts Institute of Technology. email: aram@mit.edu

1

density matrices that can be written as a convex combination of tensor product states. This problem is
closely related to the task of determining if a given quantum state is entangled or not (called the quantum
separability problem) and to the computation of several other quantities of interest in quantum information,
including the optimal acceptance probability of quantum Merlin-Arthur games with unentangled proofs,
optimal entanglement witnesses, mean-field ground-state energies, and measures of entanglement; see [HM13]
for a review of many of these connections.
Given an operator M acting on the bipartite vector space Cd1 ⊗ Cd2 the support function of M on the
set of separable states is given by
hSep(d1 ,d2 ) (M ) :=

max

α∈Dd1 ,β∈Dd2

tr[M (α ⊗ β)],

(1)

with Dd the set of density matrices on Cd (d × d positive semidefinite matrices of unit trace). Our goal is to
n
approximate hSep(d1 ,d2 ) (M ). For M ∈ L(Cd ), define
hSepn (d) (M ) =

max

α1 ,...,αn ∈Dd

tr[M (α1 ⊗ · · · ⊗ αn )].

(2)

The first result on the complexity of computing hSep(d1 ,d2 ) was negative: Gurvits showed that the problem
is NP-hard for sufficiently small additive error (inverse polynomial in d1 d2 ) [Gur03]. Then [HM13] showed
there is no exp(O(log2−Ω(1) (d1 d2 ))) time algorithm even for a constant error additive approximation of the
quantity, assuming the exponential time hypothesis (ETH1 ). This left open the question whether there are
quasipolynomial-time algorithms (i.e. of time exp(polylog(d1 , d2 ))).
In [BCY11] it was shown that this is indeed the case at least for a class of linear functions: namely those
corresponding to quantum measurements that can be implemented by local operations and one-directional
classical communication (one-way LOCC or 1-LOCC). For thisparticular class of measurements the problem
can be solved with error δ in time exp O δ −2 log(d1 ) log(d2 ) . The proof was based on showing that the
hierarchy of semidefinite programs for the problem introduced in 2004 by Doherty, Parrilo and Spedalieri
[DPS04] (which is an application of the more general Sum-of-Squares (SoS) hierarchy, also known as the
Lasserre hierarchy, to the separability problem) converges quickly. The approach of [BCY11] was to use ideas
from quantum information theory (monogamy of entanglement, entanglement measures, hypothesis testing,
etc) to find good bounds on the quality of the SoS hierarchy. Since then several follow-up work gave different
proofs of the result, but always using quantum information-theoretic ideas [BH13, LW14, BC11, Yan06].
A corollary of [BCY11] and the other results on 1-LOCC M is that hSep(d1 ,d2 ) (M ) can also be approxi1
mated for a different class of operators M : those with small Hilbert-Schmidt norm kM kHS := tr(M † M ) 2 .
Ref. [BaCY11] showed that also in this case there is a quasipolynomial-time algorithm for estimating Eq.
(1). An interesting subsequent development was the work of Shi and Wu [SW12] (see also [BKS13]), who
gave a different algorithm for the problem based on enumerating over nets. It was left as an open question
whether a similar approach could be given for the case of one-way LOCC measurements (which is more
relevant both physically 2 and in terms of applications; see again [HM13]).
Estimating the Output Purity of Quantum Channels: Another important optimization problem
in quantum information theory consists of determining how much noise a quantum channel introduces. A
quantum channel models a general physical evolution and is given mathematically by a completely positive
trace preserving map Λ : Dd1 → Dd2 . One way to measure the level of noise of the channel is to compute
the maximum over states of the output Schatten-α norm, for a given α > 1:
kΛk1→α := max kΛ(ρ)kα ,
ρ∈Dd1

1 The

(3)

ETH is the conjecture that 3-SAT instances of length n require time 2Ω(n) to solve. This is a plausible conjecture for
deterministic, randomized or quantum computation, and each version yields a corresponding lower bound on the complexity of
estimating hSep .
2 The one-way LOCC norm gives the optimal distinguishably of two multipartite quantum states when only local measurements can be done, and the parties can coordinate by one-directional communication. See [MWW09] for a discussion of its
power.

2

−1

1

with kZkα = tr(|Z|α ) α . The quantity kΛk1→α varies from one, for an ideal channel, to d2−1+α for the
depolarizing channel mapping all states to the maximally mixed state. This optimization problem has been
extensively studied, in particular because for α ≈ 1 it is related to the Holevo capacity of the channel, whose
regularization gives the classical capacity of the channel (i.e. how many reliable bits can be transmitted per
use of the channel).
It was shown in [HM13] that, assuming ETH, there is no algorithm that runs in time exp(O(log2−Ω(1) (d)))
and can decide if kΛk1→α is one or smaller than δ (for any fixed δ > 0 and α > 1) for a general quantum
channel Λ : Dd → Dd . On the algorithmic side, nothing better than exhaustive search over the input space
(taking time exp(Ω(d1 ))) is known.
An interesting subclass of quantum channels, lying somewhere between classical channels and fully quantum channels, are the so-called entanglement-breaking channels, which are the channels that cannot be used
to distribute entanglement. Any entanglement-breaking quantum channel Λ can be written as [HSR04]:
X
Λ(ρ) :=
tr(Xi ρ)Yi ,
(4)
i

P
with Yi ≥ 0, tr(Yi ) = 1 quantum states and Xi ≥ 0, and i Xi = I a quantum measurement. Because
of their simpler form, one can expect that there are more efficient algorithms for computing the maximum
output norm of entanglement-breaking channels. However until now no algorithm better than exhaustive
search was known either (apart from the case α = ∞ where the Sum-of-Squares hierarchy can be used and
analyzed using [BCY11]).
Computing p → q Norms: Given a d1 × d2 matrix A we define its p → q norm by
kAkp→q

kAxkq
,
:= max
x∈Cd2 kxkp

kxkp :=

d2
X

!1/p
p

|x|

(5)

i=1

Such norms have many different applications, such as in hypercontractive inequalities and determining
if a graph is a small-set expander [BBH+ 12], to oblivious routing [BV11] and robust optimization [Ste05].
However we do not have a complete understanding of the complexity of computing them. For 2 < q ≤ p or
q ≤ p < 2, it is NP-hard to approximate them to any constant factor [BV11]. In the regime q > p (the one
relevant for hypercontractivity and small-set expansion) the only known hardness result is that to obtain any
(multiplicative) constant-factor approximation for the 2 → 4 norm of a n × n matrix is as hard as solving
3-SAT with Õ(log2 (n)) variables [BBH+ 12].
On the algorithmic side, besides the 2 → 2 and 2 → ∞ norms being exactly computable in polynomial time, Ref. [BBH+ 12] showed that one can use the Sum-of-Squares hierarchy to compute in time
exp(O(log2 (n)ε−2 )) a number X s.t.
kAk42→4 ≤ X ≤ kAk42→4 + εkAk22→2 kAk22→∞ .

(6)

Whether similar approximations can be obtained for 2 → q norms for other values of q was left as an
open problem.
Computing the Operator Norm between Banach Spaces: These problems are all special cases of
the following general question. Given a map T : A → B between Banach spaces A, B, can we approximately
compute the following operator norm?
kT kA→B := sup
x6=0

1.1

kT xkB
kxkA

(7)

Summary of Results

In this paper we give new algorithmic results for the four problems discussed above. They can be summarized
as follows.
3

Separable-state optimization by covering nets: We give a different algorithm for optimizing linear
functions over separable states (corresponding to one-way LOCC measurements) based on enumerating over
covering nets (see Algorithm 1). The complexity of the algorithm matches the time complexity of [BCY11]
(see Theorem 2). The proof does not use information theory in any way, nor the SoS hierarchy. Instead
the main technical tool is a matrix version of the Hoeffding bound (see Lemma 3). It gives new geometric
insight into the problem and gives arguably the simplest and most self-contained proof of the result to date.
It also gives an explicit rounding (as does [BH13] but in contrast to [BCY11, LW14, BC11, Yan06]).
For particular subclasses of one-way LOCC measurements our algorithm improves the run time of
[BCY11]. One example is the case where Bob’s measurement outcomes are low rank, in which we find
O(ε−2 )

a poly(d2 )d1

-time algorithm.

Generalization to arbitrary operator norms: Computing hSep is mathematically equivalent to
computing the 1 → ∞ norm of a quantum channel, or more precisely the S1 → S∞ norm where Sα denotes
the Schatten-α norm. This perspective will help us generalize the scope of our algorithm, to estimating the
S1 → B norm for a general Banach space B. The analysis of this algorithm is based on tools from asymptotic
geometric analysis, and we will see that its efficiency depends on properties of B known as the Rademacher
type and the modulus of uniform smoothness. Besides generalizing the scope of the algorithm, this also gives
more of a geometric explanation of its performance. We focus on two special cases of the problem:
1. maximum output norm: A particular case of the generalization is the problem of computing the
maximum output purity of a quantum entanglement-breaking channel (measured in the Schatten-α
O(ε−2 )

norms). We prove that for any α > 1 one can compute kΛk1→α in time poly(d2 )d1
to within
additive error ε. (see Corollary 16). In contrast known hardness results [HM10, HM13] show that no
such algorithm exists for general quantum channels (under the exponential time hypothesis). Previously
the entanglement-breaking case was not known to be easier.
2. matrix 2 → q norms: As a second particular case of the general framework we extend the approximation of [BBH+ 12] to the 2 → 4 norm, given in Eq. (6), to the 2 → q norms for all q ≥ 2 (see
Corollary 17).
Operator norms between Banach spaces: This framework can be further generalized to estimating
the operator norm of any linear map from A → B for Banach spaces A, B. Here we have replaced S1
with any finite-dimensional Banach space A whose norm can be computed efficiently. When applied to an
operator Λ, the approximation error scales with the A → `n1 → B factorization norm, which is the minimum
of kΛ1 k`n1 →B kΛ2 kA→`n1 such that Λ = Λ1 Λ2 . Factorization norms have applications to communication
complexity [LS07, LS09], Banach space theory [Pie07], and machine learning [LRS+ 10], and here we argue
that they help explain what makes the class of 1-LOCC measurements uniquely tractable for algorithms.
In Section 4 we describe an algorithm for this general norm estimation problem, which to our knowledge
previously had no efficient algorithms. This problem equivalently can be viewed as computing the injective
tensor norm of two Banach spaces.
We remark that this generalization is not completely for free, so we cannot simply derive all our other
algorithms from this final one. In the case where A = S1d (which
Pn corresponds to all of our specific applications), we are able to easily sparsify the input; i.e. given i=1 Ai ⊗ Bi , we can reduce n to be poly(d)
without loss of generality. For general input spaces A we do not know if this is possible. Also, the case of
hSep is much simpler, and so it may be helpful to read it first.

1.2

Comparison with prior work

As discussed in the introduction, previous algorithms for separable-state optimization (and as a corollary,
the 2 → 4 norm) have been obtained using SDP hierarchies. Our algorithms generally match or improve
upon their parameters, but with the added requirement for the separable-state problem that the input be
presented in a more structured form.
4

Several parallels between LP/SDP hierarchies and net-based algorithms have been developed for other
problems. The first example of this was Ref. [DKLP06a] which gave both types of algorithms for the problem
of maximizing a polynomial over the simplex, improving on a result implicit in the 1980 proof of the finite
de Finetti theorem by Diaconis and Freedman [DF80]. Besides the separable-state approximation problem
that we study, hierarchies and nets have been found to have similar performance in finding approximate
Nash equilibria [LMM03, Har15] and in estimating the value of free two-prover games [AIM14, BH13]. The
state-of-the-art run-time for solving Unique Games and Small Set Expansion have also been achieved using
both hierarchies and covering-nets. These parallels are summarized in the table:
Problem

nets

hierarchies/information theory

maxx∈∆n p(x)
approximate Nash
free games
unique games
small-set expansion
separable states

[DKLP06a]
[LMM03, ALSV13a]
[AIM14]
[ABS10]
[ABS10]
[SW12, BKS13], this work

[DF80, DKLP06a]
[Har15]
[BH13, Cor 4]
[BRS11]
[BBH+ 12, §10]
[BaCY11, BH13, BKS13, LW14, LS14]

Table 1: We briefly describe these problems here. Full descriptions can be found in the references in the
table. In maxx∈∆n p(x), ∆n is the n-dimensional probability simplex and p(x) is a low-degree polynomial.
“Approximate Nash” refers to the problem of finding a pair of strategies in a two-player non-cooperative
game for which no player can improve their welfare by more than ε. “Free games” refers to two-prover oneround proof systems where the questions asked are independent; the computational problem is to estimate
the largest possible acceptance probability. “Unique games” describes instead proof systems with “unique”
constraints; i.e. for each question pair and each answer given by one of the provers, there is exactly one
correct answer possible for the other prover. Small-set expansion asks, given a graph G and parameters
ε, δ > 0, whether all subsets with a δ fraction of the vertices have a ≥ 1 − ε fraction of edges leaving the
set or whether there exists one with a ≤ ε fraction of edges leaving the set. Finally “separable states” refers
to estimating hSep(n,n) as we will discuss elsewhere in the paper. It can also be though of as estimating
maxkxk2 =1} p(x) for some low-degree polynomial p(x).
While this paper focuses on the particular problems where we can improve upon the state-of-the-art
algorithms, we hope to be a step towards more generally understanding the connections between these two
methods. In almost every case above, the best covering-net algorithms achieve nearly the same complexity
as the best analyses of SDP hierarchies. There are a few exceptions. Ref. [BBH+ 12] shows O(1) rounds
of the SoS hierarchy can certify a small value for the Khot-Vishnoi integrality gap instances of the unique
games problem, but we do not know how to achieve something similar using nets. A more general example
is in [BKS13], which shows that the SoS hierarchy can approximate hSep (M ) in quasipolynomial time when
M is entrywise nonnegative.
The closest related paper to this work is [SW12] by Shi and Wu (as well as Appendix A of [BKS13]),
which also used enumeration over ε-nets to approximate hSep . Here we explain their results in our language.
Shi and Wu [SW12] have two algorithms: one when M has low Schmidt rank (i.e. factorizes as S1 →
d1 ×d2
`r2 → S∞ for small r) and one where M has low rank, which we can interpret as a `r2 → S∞
factorization
d1 ×d2
(here S∞
refers to the space of d1 × d2 -dimensional matrices with norm given by the largest singular
value). These correspond to their Theorems 5 and 8 respectively. In both cases they construct ε-nets for
the `r2 unit ball of size ε−O(r) (here, `2 could be replaced with any norm; see Lemma 9.5 of [LT91]). In both
cases, their results can be improved to yield multiplicative approximations, using ideas from [BKS13].
Appendix A of Barak, Kelner and Steurer [BKS13] considers fully symmetric 4-index tensors M ∈ (Rn )⊗4 ,
so that when viewed as n2 × n2 matrices their rank and Schmidt rank are the same; call them r. Their
algorithm is similar to that of [SW12], although they observe additionally (using different terminology) that
for any self-adjoint operator T : A∗ → A (i.e. satisfying hT (X), Y i = hX, T (Y )i) the A∗ → `2 → A norm is
5

equal to the A∗ → A norm. This means that constructing an ε-net for B(`2 ) actually yields a multiplicative
approximation of the A∗ → A norm (here the S1 → S∞ norm).
Achieving a multiplicative approximation is stronger than what our algorithms achieve, but it is at the
cost of a runtime that can be exponential in the input size even for a constant-factor approximation. By
contrast, our algorithms yield nontrivial approximations in polynomial or quasipolynomial time.

1.3

Notation

d
d
Define the sets of d × d real and complex semidefinite matrices by S+
, H+
respectively. For complex vector spaces V, W , define L(V, W ) to be the set of linear operators from V to W , L(V ) := L(V, V ) and
H(V ), H+ (V ) to be respectively the Hermitian and positive-semidefinite operators on V . P
For α ≥ 1 define the `α , Sα metrics on vectors and matrices respectively by kxk`α = ( i |xi |α )1/α and
kXkSα = (tr |X|α )1/α . Denote the corresponding normed spaces by `dα , Sαd . Where it is clear from context
we will refer to both norms by k · kα . We use k · k without subscript to denote the operator norm for matrices
(i.e. kXk = kXkS∞ ) and the Euclidean norm for vectors (i.e. kxk = kxk`2 ).
We use Õ(f (x)) to mean O(f (x) poly log(f (x))) and say that f (x) is “quasipolynomial” in x if f ≤
O(exp(poly log(x))).
For a normed space V , define B(V ) = {v ∈ V : kvk ≤ 1}. Two important special cases are the
probability simplex ∆n := B(`n1 ) ∩ Rn≥0 and the set of density matrices (also called “quantum states”)
d
= conv{vv † : v ∈ B(`d2 )}. Here v † is the conjugate transpose of v. For k a positive
Dd := B(S1d ) ∩ H+
integer, define also


ei1 + . . . + eik
: i1 , . . . , ik ∈ [n] ⊂ ∆n ,
(8)
∆n (k) :=
k

where ei is the vector in Rn with a 1 in position i and zeros elsewhere. For a convex set K define the
support function hK (x) := supy∈K hx, yi. For matrices h, i refers to the Hilbert-Schmidt inner product
hX, Y i := tr(X † Y ).
Banach spaces are normed vector spaces with an additional condition (completeness, i.e. convergence of
Cauchy sequences) that is relevant only in the infinite dimensional case. In this work we will consider only
finite-dimensional Banach spaces.

2

Warmup: algorithm for bipartite separability

In this section we describePa simple version of our algorithm. It contains
all the main ideas which we will
n
d1
d2 P
later generalize. Let M = i=1 Xi ⊗ Yi , where Xi ∈ S+
, Yi ∈ S+
, i Xi ≤ I, and each Yi ≤ I. In quantum
information language, M is a 1-LOCC measurement, meaning it can be implemented with local operations
and one-way classical communication 3 . In later sections we will see that M can also be interpreted in a
(mathematically) more natural way as a bounded map from S1 to S∞ . The goal of our algorithm is to
approximate hSep(d1 ,d2 ) (M ), where we define the set of separable states as
Sep(d1 , d2 ) := conv{α ⊗ β : α ∈ Dd1 , β ∈ Dd2 }.

(9)

There have been several recent proofs [BCY11, BH13, LW14], each based on quantum information theory, that SDP hierarchies can estimate hSep(d1 ,d2 ) (M ) to error εkM k in time exp(O(log2 (d)/ε2 )). Similar techniques also appeared in [BKS13, LS14] for different classes of operators M . The role of the 1LOCC conditions in these proofs was typically not completely obvious, and indeed it entered the proofs of
[BCY11, BH13, LW14] in three different ways. We now give another interpretation of it that is arguably
more geometrically natural.
3 Conventionally

these have

P

i

Xi = I, but our formulation is essentially equivalent.

6

Begin by observing that
hSep(d1 ,d2 ) (M )

=
=
=

max

α∈Dd1 ,β∈Dd2

max

α∈Dd1 ,β∈Dd2

tr[(α ⊗ β)M ],
n
X

tr[αXi ] tr[βYi ]

i=1

max kpkY .

(10)

p∈SX

In the last step we have defined
SX := {p ∈ ∆n : ∃α ∈ Dd1 , pi = tr[αXi ] ∀i ∈ [n]},

and

kakY :=

n
X

ai Yi .

(11)

i=1

The basic algorithm is the following:
Algorithm 1 (Basic algorithm for computing hSep (M ) for one-way LOCC M =

P

i

Xi ⊗ Yi ).

d2
d1
.
, {Yi }ni=1 ⊂ H+
Input: {Xi }ni=1 ⊂ H+

Output: States α ∈ Dd1 and β ∈ Dd2 .
1. Enumerate over all p ∈ ∆n (k), with k = 9 ln(d2 )/δ 2 .
(a) For each p, check (using Lemma 5) whether there exists q ∈ S with kp − qkY ≤ δ/2.
(b) If so, compute kqkY .
2. Let q be such that the kqkY is the P
maximum, and
P let α ∈ Dd1 be the state for which qi = tr[Xi α].
Output this α and β satisfying tr[β i qi Yi ] = k i qi Yi k.
The main result of this section is:
Pn
P
Theorem 2. Let M = i=1 Xi ⊗ Yi be 
such that i Xi ≤ I, Xi ≥ 0, 0 ≤ Yi ≤ I. Algorithm 1 runs in time
poly(d1 , d2 , n) exp O δ −2 log(n) log(d2 ) and outputs α ∈ Dd1 and β ∈ Dd2 such that
hSep (M ) ≥ tr[M (α ⊗ β)] ≥ hSep (M ) − δ,

(12)

For n = poly(d1 , d2 ) this is the same running time as found in [BCY11] (while for n  poly(d1 , d2 ) it is
an improvement). Later in this section we will show how we can always modify the measurement to have
n = poly(d1 , d2 ) only incurring in a small error. But before that, we now show that Theorem 2 follows easily
from two simple lemmas.
One of the lemmas is a consequence of the the well-known matrix Hoeffding bound.
Lemma 3 (Matrix Hoeffding Bound [Tro10]). Suppose Z1 , . . . , Zk are independent random d × d Hermitian
matrices satisfying E[Zi ] = 0 and kZi k ≤ λ. Then
#
"
k
kδ 2
1X
Zi ≥ δ ≤ d · e− 8λ2 .
(13)
Pr
k i=1
This is a special case of Theorem 2.8 from [Tro10]):
−2
Our first lemma shows that one can restrict the optimization to a net of size nO(log(d2 )δ ) :
Lemma 4. For any p ∈ ∆n there exists q ∈ ∆n (k) with
r
kp − qkY ≤

7

9 ln(d2 )
.
k

(14)

Proof. Sample i1 , . . . , ik according to p and set q = (ei1 +. . .+eik )/k. Define Ȳ :=
Observe that E[Zj ] = 0 and kZj k ≤ 1. Then Lemma 3 implies that
k
1X
kp − qkY =
Zj ≤ δ.
k j=1

with positive probability if k > 8 ln(d)/δ 2 . Setting δ =
q ∈ ∆n (k) satisfying Eq. (14).

Pn

i=1

pi Yi and Zj = Ȳ −Yij .

(15)

p
9 ln(d2 )/k we find that there exists a choice of

The second lemma shows that one can decide efficiently if an element of the net is a valid solution. A
similar result is in [SW12].
Lemma 5. Given p ∈ ∆n and ε > 0, we can decide in time poly(d1 , d2 , n) whether the following set is
nonempty
SX ∩ {q : kp − qkY ≤ ε}.
(16)
Proof. Both are convex sets, defined by semidefinite constraints. So we can test for feasibility with a SDP
of size poly(d1 , d2 , n). Indeed this is manifest for SX in Eq. (11), while {q : kp − qkY ≤ ε} can be written as
(
)
X
X
{q : kp − qkY ≤ ε} = (q1 , . . . , qn ) : qi ≥ 0, −εI ≤
pi Yi −
qi Yi ≤ εI .
(17)
i

i

We are ready to prove Theorem 2:
Proof of Theorem 2. Whatever the output x is, x ≤ hSep (M )+δ/2. On the other hand, let q = arg maxq∈S kqkY ,
so that kqkY = hSep (M 0 ). By Lemma 4, there exists p ∈ ∆n (k) with kp − qkY ≤ δ/2. Thus our algorithm
will output a value that is ≥ hSep (M ) − δ. We conclude that the algorithm achieves an additive error of δ
2
in time poly(d1 , d2 )nO(log(d2 )/δ ) .

2.1

Sparsification

We now consider the case where n  poly(d1 , d2 ). It turns out that we can modify the algorithm such that
its running time is polynomial in n by first sparsifying the number of local terms of the measurement. This
results in the following theorem.
Pn
P
Theorem 6. Let M = i=1 Xi ⊗ Y
i be such that
i Xi ≤ I, Xi ≥ 0, 0 ≤ Yi ≤ I. Algorithm 8 runs in time
poly(n) exp O δ −2 log d1 log(d1 d2 ) and outputs α ∈ Dd1 and β ∈ Dd2 such that
hSep (M ) ≥ tr(M (α ⊗ β)) ≥ hSep (M ) − δ,

(18)

The key element of the theorem is the following Lemma.
Pn
Lemma 7. Given a 1-LOCC measurement M =
i=1 Xi ⊗ Yi and some ε > 0 there exists a 1-LOCC
0
P
n
measurement M 0 = j=1 Xj0 ⊗ Yj0 with kM − M 0 k ≤ ε and n0 ≤ poly(d1 , d2 )/ε2 . If the decomposition of
M is explicitly given then M 0 and its decomposition can be found in time poly(d1 , d2 , n) using a randomized
algorithm.
The modified algorithm is the following:

8

Algorithm 8 (Algorithm for computing hSep (M ) for one-way LOCC M =

P

i

Xi ⊗ Yi ).

Input: {Xi }ni=1 , {Yi }ni=1 .
Output: States α ∈ Dd1 and β ∈ Dd2 .
1. Use Lemma 7 to replace M =

Pn

i=1

Xi ⊗ Yi with M 0 =

Pn0

i=1

Xi0 ⊗ Yi0 satisfying kM − M 0 k ≤ δ/2.

2. Run Algorithm 1 on M 0 .
The proof of correctness is straightforward.
Proof of Theorem 6. Whatever the output x is, x ≤ hSep (M 0 ) ≤ hSep (M ) + δ/2. On the other hand, let
q = arg maxq∈S kqkY , so that kqkY = hSep (M 0 ). By Lemma 4, there exists p ∈ ∆n (k) with kp − qkY ≤ δ/2.
Thus our algorithm will output a value that is ≥ hSep (M 0 ) − δ/2 ≥ hSep (M ) − δ. We conclude that the
2
algorithm achieves an additive error of δ in time poly(n)(d1 d2 )O(log(d2 )/δ ) .
It remains only to prove Lemma 7. This requires a careful use of the matrix Hoeffding bound (Lemma ??).
The details are in Appendix A.

2.2

Multipartite

We now consider the generalization of the problem to the multipartite case. We consider measurements on
a l-partite vector space Cd1 ⊗ . . . ⊗ Cdl . Following Li and Smith [LS14], we define
P the class of fully one-way
d1
,
LOCC measurements on Cd1 ⊗ . . . ⊗ Cdl recursively as all measurements M = i Xi ⊗ Mi , where Xi ∈ H+
P
d2 ···dl
d2
dl
, and each Mi is a fully one-way LOCC measurement in C ⊗ . . . ⊗ C .
i Xi ≤ I, Mi ∈ H+
Ref. [LS14] recently strengthened the result of [BH13] (from parallel one-way LOCC to fully one-way
LOCC measurement) and proved that the SoS hierarchy approximates
hSep(d1 ,...,dl ) (M ) :=

max

α1 ∈Dd1 ,...,αl ∈Ddl

tr[(α1 ⊗ . . . ⊗ αl )M ]

(19)

to within additive error δ in time exp(O(log2 (d)l3 /δ 2 )), with d := maxi∈[l] di . Here we show that our previous
algorithm for the bipartite case can be extended to the multipartite setting to give the same run time.
Theorem 9. Algorithm 10 above runs in time exp(O(l3 ln2 (d)/δ 2 ) and outputs states αi , i ∈ [l], satisfying
hSep(d1 ,...,dl ) (M ) ≥ tr[M (α1 ⊗ . . . ⊗ αl )] ≥ hSep(d1 ,...,dl ) (M ) − δ.

9

(20)

Algorithm 10 (Algorithm for computing hSep(d1 ,...,dl ) (M ) for fully one-way LOCC M ).
(m)

dm
such that
Input: {Xi1 ,...,im : m ∈ [l], i1 ∈ [n1 ], . . . , im ∈ [nm ]} ⊂ H+

M=

n1
X

(1)

Xi1 ⊗

i1 =1

n2
X

(2)

Xi1 ,i2 ⊗ · · · ⊗

i2 =1

nm
X

(m)

Xi1 ,i2 ,...,im

im =1

Output: States αi ∈ Ddi , i ∈ [l].
1. Use Lemma 7 to replace M =

Pn1

i1 =1

(1)

Xi1 ⊗Mi1 with M 0 =

Pn01

(1) 0
0
i1 =1 (Xi1 ) ⊗Mi1

satisfying kM −M 0 k ≤

(m)

δ/2l. Here Mi1 is a shorthand for the collection {Xi1 ,...,im } for m ≥ 2 and likewise for Mi0 . Redefine
(m)
M, {Xi1 ,...,im }, {ni }

appropriately.

2. Initialize the variables α1 , . . . , αl to ∅.
3. Enumerate over all p ∈ ∆n (k), with k = 9l2 ln(d)/δ 2 . For each p,
(a) Check (using Lemma 5) whether there exists q ∈ SX (1) with k

P

i (pi

− qi )Mi k ≤ δ/2l.

(b) If no such q exists then do not evaluate this value of p any further. Otherwise let β1 be the
(1)
density matrix found in the SDP in Lemma 5 satisfying qi = tr[β1 Xi ].
P
(m0 −1)
(m0 )
(c) For m0 ∈ {2, . . . , m}, i2 ∈ [n2 ], . . . , im0 ∈ [nm0 ], define X̃i2 ,...,im0 := i1 qi1 Xi1 ,i2 ,...,im0 .
(m0 )

(d) Recursively call Algorithm 10 on input {X̃i1 ,...,im0 }. Denote the output by β2 , . . . , βl .
(e) If tr[M (β1 ⊗ · · · ⊗ βl )] > tr[M (α1 ⊗ · · · ⊗ αl )] then replace α1 , . . . , αl with β1 , . . . , βl .

2.3

The need for an explicit decomposition

The input
P to our algorithm is not only a 1-LOCC measurement M but an explicit decomposition of the form
M = i Xi ⊗ Yi with each Xi ≥ 0. Previous algorithms for hSep were mostly based on the SoS hierarchy
(or its restriction to the separability problem also known as k-extendible hierarchy) [DPS04]. Running these
requires only knowledge of M and not its decomposition. The decomposition appears in the analysis of
[BCY11, LW14, BC11, BH13, Yan06], but not the algorithm.
On the other hand, previous algorithms did not yield an explicit rounding, i.e. a separable state σ with
tr M σ ≈ hSep (M ). The only exception to this [BH13] also required an explicit decomposition in order to
produce a rounding.
P
In general any bipartite measurement M can be written in the form i Xi ⊗ Yi , with individual terms
that are not necessarily positive semidefinite. Finding some P
such decomposition is straightforward, e.g. using
the operator Schmidt decomposition or even writing M = ijkl Mijkl |ii hj| ⊗ |ki hl|. Our algorithm can be
readily modified toPincorporate non-positive Xi (along the lines of Section 4), but the run-time will then
include a factor of i kXi k1 in the exponent. In general this will be O(1) only if M is close to 1-LOCC and
the decomposition is close to the correct one.
P
This raises an interesting
i Xi ⊗ Yi that (apP open question: given M , find a decomposition M =
proximately) minimizes i kXi k1 . We are not aware of nontrivial algorithms or hardness results for this
problem.

10

3

Generalized algorithm for arbitrary norms

An important step in the algorithm of the previous section was the identity,
hSep(d1 ,d2 ) (M ) = max kpkY ,

(21)

p∈SX

P
valid for any one-way LOCC M = i Xi ⊗ Yi . This equation suggests ways of generalizing the algorithm.
In this section we consider the setting where the operators {Y1 , . . . Yn } belong to some Banach space B with
norm k · kB . In analogy with Eq. (11), given Y = {Y1 , . . . Yn } we define the (B, Y ) norm in Rn as
n
X

kakB,Y :=

.

ai Yi

i=1

(22)

B

The goal is then to estimate
max kpkB,Y ,

(23)

p∈SX

where, as before, SX is given by Eq. (11).
Also this generalization is of interest in quantum information theory. As we discuss more in the next
subsection, it includes as a particular case the well-studied problem of computing the maximum output
α-norms of an entanglement-breaking channel. Consider a general entanglement-breaking quantum channel
Λ : Dd1 → Dd2 given by [HSR04]:
X
Λ(ρ) :=
tr(Xi ρ)Yi ,
(24)
i

with Yi ≥ 0, tr(Yi ) = 1, Xi ≥ 0, and

P

i

Xi = I. Then

max kΛ(ρ)kα = max kpkSα ,Y .

ρ∈Dd1

(25)

p∈SX

In order to find an algorithm for computing Eq. (23), we need to replace the quantum Hoeffding bound
(Lemma 3) by more sophisticated concentration bounds. Since in Lemma 5 all we needed was a bound in
expectation, the right concept will turn out to be the Rademacher type-γ constant of the space B, which we
now define:
Definition 11. We say a Banach space B has Rademacher type-γ constant C if for every Z1 , . . . , Zk ∈ B
and Rademacher random variables ε1 , . . . , εk (i.e. independent and uniformly distributed on ±1) ,

E

ε1 ,...,εk

k
X
i=1

γ

≤ Cγ

εi Zi
B

k
X

γ

kZi kB .

(26)

i=1

√
It is known that Schatten-α spaces with norm kXkα := tr(|X|α )1/α have type-2 constant α − 1 for
α ≥ 2 [BCL94], and type-α constant 1 for every α ∈ [1, 2] [KPT00, Thm 3.3].
For a reader unfamiliar with the type-γ constant, we suggest verifying that the type-2 constant of `2
is 1. A more nontrivial calculation√is using the Hoeffding bound or its operator version to verify that the
n
type-2 constant of `n∞ or S∞
is O( log n). (This also follows from the fact that the S∞ and Slog(n) norms
are within a constant multiple of each other on the space of n-dimensional matrices.)
For sparsification (the analogue of Lemma 7) we will actually need a slightly stronger condition than a
bound on the type-γ constant:
Definition 12. The modulus of uniform smoothness of a Banach space B is defined to be the function


kx + τ ykB + kx − τ ykB
− 1 : kxkB = kykB = 1 .
(27)
ρB (τ ) := sup
2
11

By the triangle inequality, ρB (τ ) ≤ τ for all B. But when limτ →0 ρBτ(τ ) = 0 then we say that B is
uniformly smooth. For example, if B = `2 then ρB (τ ) = τ 2 /2, whereas ρ`1 (τ ) = τ . More generally [BCL94]
2
(building on [TJ74]) proved that ρSα (τ ) ≤ α−1
2 τ for α > 1. We say that B has modulus of smoothness of
γ
power type γ if ρB (τ ) ≤ Cτ for some constant C. This implies (using an easy induction on k) that the
type-γ constant is ≤ C, and indeed this was how the type-γ constant was bounded in [TJ74, BCL94].
The algorithm for approximating the optimization problem given by Eq. (23) is the following:
Algorithm 13 (Algorithm for computing maxp∈SX kpkB,Y for B of type-γ constant C and modulus of
uniform smoothness ρB (τ ) ≤ sτ 2 , with X := {Xi } and Y := {Yi }).
Input: {Xi }ni=1 , {Yi }ni=1
Output: p ∈ S
1. Use Lemma 22 to replace X = {Xi } and Y = {Yi } with X 0 := {Xi0 } and Y 0 := {Yi0 }.
2. Enumerate over all p ∈ ∆n (k), with k =

2C γ
δγ

maxi kYi kγB

1/(γ−1)

.

(a) For each p, check (using Lemma 21) whether there exists q ∈ S with kp − qkB,Y ≤ δ.
(b) If so, compute kpkY .
3. Output p such that kpkB,Y is the maximum.
We have:
Theorem 14. Let B be a Banach space with norm k · kB . Suppose the type-γ constant of B is C and that
2
there is s > 0 such that the modulus of uniform smoothness satisfies ρB (τ ) ≤ sτP
. Suppose one can compute
k · kB in time T . Consider {Xi }ni=1 with Xi d × d matrices satisfying Xi ≥ 0,
Xi ≤ I, and {Yi }ni=1 with
Yi ∈ B. Algorithm 13 runs in time
 

γ
 γ−1
−1
poly(T, d, s) exp O
Cδ max kYi kB
log(d)
(28)
i

and outputs p such that
max kpkB,Y ≥ kpkB,Y ≥ max kpkB,Y − δ,

p∈SX

p∈SX

(29)

p
d2
. Then the type-2 constant is O( log(d2 )), maxi kYi k ≤ 1, and Theorem
As an example, suppose B is S∞
2 shows one can compute maxp∈SX kpkY in time exp(O(δ −2 log(d1 ) log(d1 d2 ))).
In the next subsection we discuss a few particular cases of the theorem worth emphasizing. Then we
prove the theorem.

3.1
3.1.1

Consequences of Theorem 14
Restricted one-way LOCC measurements

The next lemma shows that for subclasses of one-way LOCC measurements one has a PTAS for computing
hSep . The class include in particular one-way LOCC measurements in which Bob’s measurements are low
rank.
P
P
Corollary 15. Let M = i Xi ⊗ Yi be such that Xi ≥ 0, i Xi ≤ I and kYi k2 ≤ r. Then one can compute
α ∈ Dd1 and β ∈ Dd2 such that
hSep (M ) ≥ tr(M (α ⊗ β)) ≥ hSep (M ) − δ
O(δ −2 r)

in time d1

.
12

(30)

Proof. We use Theorem 14 and Algorithm 13 to estimate the optimal p and then find α and β by semidefinite
programming.
P If instead we use the multipartitePversion of the algorithm (see Algorithm 10), we find that for M =
i Xi ⊗ Yi1 ⊗ . . . ⊗ Yil , with Xi ≥ 0,
i Xi ≤ I and kYi k2 ≤ r, we can compute α ∈ Dd and β1 , . . . , βl ∈ Dd
such that
hSep (M ) ≥ tr(M α ⊗ β1 ⊗ . . . ⊗ βl ) ≥ hSep (M ) − δ
(31)
in time dO(δ
3.1.2

−2 3

l r)

.

Maximum output norm of entanglement-breaking channels

The next corollary shows that for all α > 1, there is a PTAS for computing the maximum output Schatten-α
norm of an entanglement-breaking channel.
Corollary
16. Let Λ : Dd1P→ Dd2 be an entanglement-breaking channel with decomposition Λ(ρ) :=
P
tr(X
ρ)Y
i
i (where Xi ≥ 0,
i
i Xi = I, Yi ∈ Dd2 ).
O (δ −2 α)

1. For every α ≥ 2 one can compute in time poly(d2 )d1

a number r such that

max kΛ(ρ)kα ≥ r ≥ max kΛ(ρ)kα − δ,

ρ∈Dd1

(32)

ρ∈Dd1


O

2. For every 1 < α ≤ 2 one can compute in time poly(d2 )d1

1

(αδ−α ) α−1



max kΛ(ρ)kα ≥ r ≥ max kΛ(ρ)kα − δ,

ρ∈Dd1

ρ∈Dd1

a number r such that
(33)

√
Proof. Part 1 follows from Theorem 14 and the fact that Sα , with α ≥ 2, has type-2 constant α − 1
2
[BCL94] and ρSα (τ ) ≤ α−1
2 τ for α > 1. Part 2, in turn, follows from Theorem 14 and the fact that for Sα ,
with α ≥ 2, has type-α constant one [KPT00, Thm 3.3].
We note that computing maximum output α-norms for general quantum channels is harder.
 In particular
it was shown in [HM10, HM13] that there is no algorithm that run in time exp O log2−ε d for any ε > 0
and can decide if maxρ kΛ(ρ)k is one or smaller than δ (for any fixed δ > 0) for a general quantum channel
Λ : Dd → Dd , unless the exponential time hypothesis (ETH) is wrong (meaning there is a subexponential
time algorithm for 3-SAT).
The result of [HM10] is one example of many that found dΘ̃(log d) upper or lower bounds for related
optimization problems [LMM03, BKW14, HM10]. In a few cases [ALSV13b, SW12, DKLP06b] poly-time
approximate schemes (PTASs) are known. Our results here fall into this second class. We hope that the
geometric perspective from our paper can lead to a better understanding of what distinguishes these cases.
What is known about hardness results for entanglement-breaking channels? Using the results of [BBH+ 12]
one can show that to determine if
maxρ kΛ(ρ)k is ≥ C/d or ≤ c/d (for any two constants C > c > 0) cannot
be done in time exp O log2−ε d assuming ETH. So one cannot hope to find a polynomial-time algorithm
for a multiplicative approximation of the maximum output norm.
Note that the complexity of the algorithm blows up when α → 1. This is not only an artifact of the proof.
Computing the quantity for α close to one allow us to estimate the von Neumann minimum output entropy
of the channel. However to estimate it we need a number of samples of order O(d) and so the net-based
approach we explore in this paper does not lead to efficient algorithms.

13

3.1.3

Hypercontractive norms

Our third corollary concerns the problem of computing hypercontractive norms, in particular computing the
2 → s norm of a d × d matrix A, for s > 2, defined as
kAk2→s := max kAxks .

(34)

kxk2 =1

This norms are important in several applications, e.g. bounding the mixing time of Markov chains and
determining if a graph is a small-set expander [BBH+ 12]. In [BBH+ 12] it was also shown that to compute
any constant-factor multiplicative approximation to the 2 → 4 norm of a n × n matrix is as hard as solving
3-SAT with O(log2 (n)) variables. In Appendix B we extend the approach of [BBH+ 12] to show hardness
results for multiplicatively approximating all 2 → q norms, for even q ≥ 4.
In [BBH+ 12] it was shown that the result of [BCY11] implies that for any d × d matrix A the Sum-of−2
Squares hierarchy computes in time dO(log(d)δ ) an additive approximation x s.t.
kAk42→4 ≤ x ≤ kAk42→4 + δkAk22→2 kAk22→∞ ,

(35)

where kAk2→2 is the largest singular value of A and kAk2→∞ the largest 2-norm of any row of A.
Using Theorem 14 we can improve this algorithm in two ways: First we can compute an approximation
to k.k2→s for any s > 2. Second the running time for fixed error is polynomial, instead of quasipolynomial.
Corollary 17. For any s ≥ 2 one can compute in time dO(sδ

−2

)

a number x such that

kAk22→s ≥ x ≥ kAk22→s − δkAk22→2 .
P
Proof. Let Xi := A† |ii hi| A/||A||22→2 . Note Xi ≥ 0 and i Xi ≤ I. We can write
X
s/2
s/2
kAks2→s = max
hψ| A† |ii hi| A |ψi
= ||A||s2→2 max kpks/2 .
|ψi∈`2

Since `s has type-2 constant

√

p∈SX

i

p∈SX



(37)

s − 1, by Theorem 14 we can estimate
max kpks/2 =

in time exp O sδ −2 log(d)

(36)

kAk22→s
kAk22→2

(38)

with additive error δ.

Although the corollary above gives an approximation for every s > 2 that can be computed in polynomial
time for every fixed error, it gives a worse approximation to the 2 → 4 than [BBH+ 12] (given by Eq. (35)).
We now show a second corollary that strictly improves the result of [BBH+ 12] for 2 → 4 and generalizes it
to 2 → s norms for every even ≥ 4.
Corollary 18. For any even s ≥ 4 one can compute in time dO(sδ
kAks2→s

≥x≥

kAks2→s

−

−2

)

a number x such that

s−2
δkAk22→2 kAk2→∞
.

(39)

Proof. Define

 †
⊗ 2s −1
A† |ii hi| A
A |ii hi| A
Xi :=
and
Yi :=
.
||A||22→2
||A||22→∞
P
Observe that Xi , Yi ≥ 0, i Xi ≤ I and Yi ≤ I. Additionally
X
s−2
kAks2→s = kAk22→2 kAk2→∞
hSeps/2 (n) (
Xi ⊗ Yi )
i

This last term can be approximated to additive error ε in time
exp(O(s3 /ε2 ))
using the multipartite results of Section 3.1.1.
14

(40)

(41)

3.2

Proof of Theorem 14

The proof of Theorem 14 will follow from three lemmas, the first showing that it is enough to search over
a net of small size, the second showing that one can decide membership of {q : kp − qkB,Y ≤ δ} efficiently
(assuming that k.kB can be computed efficiently), and the third giving a sparsification for the number of
{Xi }ni and {Yi }ni=1 .
We first show how the type-γ constant gives a concentration bound. This uses a standard argument.
Lemma 19 (Symmetrization Lemma). Suppose we are given p ∈ ∆n , Zi , . . . , Zn elements of a Banach space
B with norm k · kB , and ε1 , . . . , εk Rademacher distributed random variables. Then for every γ ≥ 1

E

i1 ,...,ik ∼p⊗k

k
1X
Zi − E Zi
k j=1 j i∼p

γ

≤2

E

E

i1 ,...,ik ∼p⊗k ε1 ,...,εk
B

k
1X
ε j Z ij
k j=1

γ

.

(42)

B

Proof.

E

i1 ,...,ik ∼p⊗k

k
1X
(Zi − E Zi )
k j=1 j i∼p

γ

=

E

i1 ,...,ik ∼p⊗k

B

≤

=

E

k
1X
(Zi − E [Zi0 ])
k j=1 j i0j ∼p j

E

i1 ,...,ik ∼p⊗k i01 ,...,i0k ∼p⊗k

E

k
X

1
k

E

E

E

i1 ,...,ik ∼p⊗k ε1 ,...,εk

(43)
B
γ

(Zij − Zi0j )

j=1

E

i1 ,...,ik ∼p⊗k i01 ,...,i0k ∼p⊗k ε1 ,...,εk

≤2

γ

(44)
B

1
k

k
1X
εj Zij
k j=1

k
X
j=1

γ

εj (Zij − Zi0j )

(45)
B

γ

.

(46)

B

(47)

Then we have the following generalization of Lemma 5:
Lemma 20. Let the Banach space B have type-γ constant C. Then for any p ∈ ∆n there exists q ∈ Nk with

kp − qkB,Y ≤

2C γ
γ
E kYi kB
k γ−1 i∼p

1/γ
.

(48)

Proof. Sample i1 , . . . , ik according to p and set q = (ei1 + . . . + eik )/k. Then Definition 11 and Lemma 20

15

give
γ


E

i1 ,...,ik ∼p⊗k

kp − qkB,Y

≤

E

i1 ,...,ik ∼p⊗k

=

kp − qkγB,Y
k
1X
Yi − E Yi
k j=1 j i∼p

E

i1 ,...,ik ∼p⊗k

≤ 2

E

E

i1 ,...,ik ∼p⊗k ε1 ,...,εk
γ

≤
=

2C
kγ

E

i1 ,...,ik

∼p⊗k

k
X

1
k

k
X

B
γ

.

εj Yij

j=1

Yij

γ

B

γ
B

i=1

2C γ
γ
E kYi kB .
k γ−1 i∼p

(49)

The first inequality follows from the convexity of x 7→ xγ , the second inequality from Lemma 19, and the
third from the fact that B has type-γ constant C.
The next lemma is an analogue of Lemma 5:
Lemma 21. Let the Banach space B be such that k.kB can be computed in time T . Given p ∈ ∆n and ε > 0,
we can decide in time poly(T, d, n) whether the following set is nonempty
SX ∩ {q : kp − qkB,Y ≤ ε}

(50)

Proof. Since we have an efficient algorithm for k · kB we can efficiently test membership in the set {q :
kp − qkB,Y ≤ ε}. Thus we can determine if Eq. (50) is nonempty using the ellipsoid algorithm [GLS93].
We now state an analogous sparsification result of Lemma 7 for the more general case we consider in this
section. The proof is in Appendix A.
LemmaP22. Suppose Λ is a map from d P
× d Hermitian matrices to a Banach space B and is given by
n
n
Λ(ρ) = i=1 hXi , ρiYi where each Xi ≥ 0, i=1 Xi ≤ I and each kYi kB ≤ 1. Suppose that B has modulus
Pk
0
0
0
of smoothness ρB (τ ) ≤ sτ 2 . Then there exists Λ0 such that Λ0 (ρ) =
i=1 hXi , ρiYi where each Xi ≥ 0,
Pk
0
0
2
2
i=1 Xi ≤ I and each kYi kB ≤ 1. Additionally k ≤ cd (d + s)/δ for some constant c > 0,
max k(Λ0 − Λ)(ρ)kB ≤ δ

ρ∈Dd

(51)

and Λ0 can be found efficiently.
With the lemmas in hand the proof of Theorem 14 follows along the same lines as Theorem 6.

4

Algorithm for injective tensor norm

In this section we present one further generalization, this time on the input space. While this final generalization does not have natural applications in quantum information (to our knowledge), it does give perspective
on why it is natural to consider 1-LOCC measurements and entanglement-breaking channels.
First, we introduce some more definitions. Suppose that k · kA and k · kB are two norms. For Λ an
operator from A → B define the operator norm
kΛkA→B := sup kΛ(a)kB .
a∈B(A)

16

(52)

Define the injective tensor norm A ⊗inj B by
kxkA⊗inj B =

sup ha ⊗ b, xi.

(53)

a∈B(A∗ )
b∈B(B∗ )

Here A∗ is the space of functions from A to R, and kãkA∗ := supa∈B(A) ã(a). For example, if A = B = `2
then A ⊗inj B is the usual operator norm for matrices, i.e. largest singular value. More generally A∗ ⊗inj B
is isomorphic to the operator norm on maps from A → B. Finally if A, B, C are Banach spaces then define
the factorization norm A → B → C for x ∈ L(A, C) by
kΛkA→C→B =

inf

Λ1 ∈L(C,B)
Λ2 ∈L(A,C)
Λ=Λ1 Λ2

kΛ1 kC→B kΛ2 kA→C .

(54)

We can now (informally) state our generalized estimation theorem. Given an operator Λ ∈ B(A → `1 → B)
we can estimate kΛkA→B efficiently.
For example, consider hSep , which we considered in Section 2. In our new notation
hSep (M ) = kM kS∞ ⊗inj S∞ = kM̂ kS1 →S∞ ,

(55)

where M̂ is the map defined by M̂ (X) = trA [M (X ⊗ I)]. The requirement that M is 1-LOCC is roughly
equivalent to the requirement that
kM̂ kS1 →`1 →S∞ ≤ 1.
(56)
Theorem 23. Suppose A, B are d-dimensional Banach spaces. Suppose kΛkA→`n1 →B ≤ 1 and that
Pn a good
∗
∗
∗
∗
∈
A
and
y
,
.
.
.
,
y
∈
B
are
given
such
that
Λ
=
factorization
is
known;
i.e.
x
,
.
.
.
,
x
1
n
n
1
i=1 yi xi ,
Pn
∗
supa∈A i=1 |xi (a)| ≤ 1 and maxi kyi kB ≤ 1. Suppose further that algorithms exist for computing the
A and B norms running in times TA , TB respectively. Let λ denote the type-γ constant of B. Then we can
estimate kΛkA→B to accuracy ε in time
TA TB poly(d)nc(λ/δ)

γ
γ−1

.

(57)

The algorithm follows similar lines to the earlier algorithms. It lacks only the sparsification step since
we do not know how to extend Lemma 22 to this case.
Algorithm 24 (Algorithm for computing kΛkA→B ).
Input: {xi }ni=1 , {yi }ni=1
Output: p ∈ S
γ

1. Enumerate over all p ∈ Nk , with k = (2λ/δ) γ−1 .
(a) For each p, check whether there exists q ∈ S with kp − qkB,Y ≤ δ.
(b) If so, compute kpkY .
2. Output p such that kpkB,Y is the maximum.
The proof of Theorem 23 is almost the same as that of Theorem 14. The only new ingredient is checking
whether p ∈ SX . This is equivalent to asking whether ∃a ∈ B(A) such that pi = x∗i (a). This is a convex
program which can be decided in time poly(d)TA using the ellipsoid algorithm along with our assumption
that k · kA can be computed in time TA .

17

Acknowledgments
We thank Jop Briet, Pablo Parrilo and Ben Recht for interesting discussions. FGSLB is supported by
EPSRC. AWH was funded by NSF grants CCF-1111382 and CCF-1452616, ARO contract W911NF-12-10486 and a Leverhulme Trust Visiting Professorship VP2-2013-041. Part of this work was done while A.W.
was visiting UCL.

A

Sparsification

In this appendix we prove two Lemmas about sparsification: one (Lemma 7) for the problem of hSep and
the second (Lemma 22) for the estimate S1 → B norms. While the former is a special case of the latter, it
is also far more self-contained (requiring only the operator Hoeffding bound), so we recommend reading it
first.
Proof of Lemma 7. Assume initially that each kYi k = 1. This is possible because we can always drop terms
with Yi = 0 and then rewrite M as
n
X
Yi
.
(58)
kYi kXi ⊗
kY
ik
i=1
P
Redefining Xi appropriately we see that i Xi ≤ I still holds.
Pn
i ⊗Yi )
i
. Sample i1 , . . . , in0 according to p and
and Wi = Xip⊗Y
Now write M = i=1 pi Wi with pi = tr(X
tr(M )
i
define
n0
n0
X
X
W ij
Xi /pi
A=
and
B=
.
(59)
0
n
n0
j=1
j=1
We would like to guarantee that
kA − M k ≤ δ
kB − Id1 k ≤ δ

(60a)
(60b)

for some δ to be chosen later. We can use Lemma 3 here. To do so, note that
kWi k ≤ tr Wi ≤ tr M ≤ d1 d2
tr M
kXi /pi k ≤
≤ tr M ≤ d1 d2 , using the assumption that kYi k = 1
tr Yi
Now we find that the probability that Eq. (60) fails to hold is




n0 δ 2
n0 δ 2
≤ d1 d2 exp − 2 2 + d1 exp − 2 2 .
8d1 d2
8d1 d2

(61a)
(61b)

(62)

Taking n0 = 8d21 d22 log(2d1 d2 )/δ 2 we have that (60) holds with positive probability. Fix the corresponding
i1 , . . . , in0 . Choose M 0 = A/(1 + δ). Together with Eq. (60) this means that M 0 is a valid 1-LOCC
measurement. By Eq. (60a) we can achieve our result by choosing δ = ε/3. Indeed
kM 0 − M k

=
≤
≤
≤

A
−M
1+δ
A
− A + kA − M k
1+δ


1
(1 + δ) + δ
1−
1+δ
2δ + δ 2 ≤ ε.

18

(63)

We now turn to the proof of Lemma 22, covering the case of general Banach spaces with bounded modulus
of smoothness.
We will need the following Azuma-type inequality from Naor [Nao12], who attributes it to Pisier. We
will state a weaker Hoeffding-type formulation that suffices for our purposes.
Lemma 25 (Theorem 1.5 of [Nao12]). Suppose X1 , . . . , Xk are independent random variables on B(B) for
B a Banach space with ρB (τ ) ≤ sτ 2 . Then
#
"
k
2
1X
(64)
Xi ≥ δ ≤ es+2−ckδ .
Pr
k i=1
Proof of Lemma
Pn 22. First we introduce notation. For a matrix X, define the map X̂ by X̂(A) := hX, Ai.
Thus Λ = i=1 Yi X̂i .
Pn
As in Lemma 7 we first drop terms with Yi = 0 and rewrite Λ = i=1 kYYiikB · kYi kB X̂i . Redefine Xi , Yi
appropriately and assume from now on that each kYi kB = 1.
Define pi = tr[Xi ]/d. Note that p ∈ Rn+ and kpk1 ≤ 1. Sample i1 , . . . , ik according to p and let them take
P
Pk
Xi
value 0 with probability 1 − i pi . Set Λ00 = j=1 Yj0 X̂j0 where Yj0 = Yij and Xj0 = kpij . (Set Xj0 = Yj0 = 0
j

if ij = 0.) These
mean that E[Λ00 ] = Λ.
Pchoices
n
0
Let X̄ :=
i=1 Xi and observe that 0 ≤ X̄ ≤ I. Additionally E[Xj ] = X̄/k. Thus if we define
0
Zj := kXj − X̄ then E[Zj ] = 0 and kZj k ≤ d. The operator Hoeffding bound (Lemma 3) implies that
Pk
Pk
k k1 j=1 Zj k ≤ δ with probability ≥ 1 − d exp(−kδ 2 /8d2 ). When this occurs we have k j=1 Xj0 − X̄k ≤ δ
and thus
k
X
Xj0 ≤ (1 + δ)I.
(65)
j=1

Next we attempt to bound the LHS of Eq. (51). First we can relax Dd to B(S1 ) and obtain
max k(Λ00 − Λ)(ρ)kB ≤ kΛ00 − ΛkS1 →B = kΛ00 − E[Λ00 ]kS1 →B .

(66)

ρ∈Dd

This formulation allows to apply the symmetrization trick (Lemma 19) to obtain

E

max k(Λ00 − Λ)(ρ)kB ≤ 2

i1 ,...,ik ∼p⊗k ρ∈Dd

E

E

i1 ,...,ik ∼p⊗k ε1 ,...,εk

k
X̂i
1X
εj Yij j
k j=1
pij

(67)
S1 →B

We will bound this last quantity for any fixed i1 , . . . , ik . For ρ ∈ B(S1 ), define qj := hXij , ρi/kpij . Denote
the set of feasible q by SX,~i where this notation emphasizes the dependence on both X and i1 , . . . , ik . Then
P
j |qj | ≤ 1, each |qj | ≤ d/k and

k
X̂i
1X
εj Yij j
k j=1
p ij
{z
}
|
=:Λ0ε

= max

q∈SX,~i

k
X
j=1

εj Yij qj

.
B

S1 →B

Now let us fix ρ (or equivalently q). Observe that kYij qj kB ≤ d/k. Then Lemma 25 implies that


k
X
ckδ 2
Pr 
εj Yij qj
≥ δ  ≤ es+2− d2 .
ε1 ,...,εk

(68)

j=1

B

19

(69)

According to Lemma II.2 of [HLSW04] there exists a net of pure states ρ1 , . . . , ρm ∈ Dd such that m ≤
2d
10P
and for any pure state ρ, we have minl kρ − ρl k1 ≤ 1/2. Say that ε1 , . . . , εk is a good sequence if
k j εj Yij hXij , ρl i/kpij k ≤ δ for all l ∈ [m]. By Eq. (69) and the union bound the probability that
2

2

ε1 , . . . , εk is bad (i.e. not good) is ≤ 102d es+2−ckδ /d . For a bad sequence we still have that Eq. (68) is
≤ d by the triangle inequality. For a good sequence, let α denote Eq. (68) and let β be the corresponding
maximum with ρ restricted to the set {ρ1 , . . . , ρm }. By our assumption that the sequence is good we have
β ≤ δ. Observe that α = maxρ∈B(S1 ) kΛ0ε (ρ)kB and by convexity (and symmetry of the k · kB norm) this
max is achieved for ρ a pure state. Let ρl satisfy kρ − ρl k1 ≤ 1/2. Then
1
kΛ0ε (ρ)kB ≤ kΛ0ε (ρl )kB + kΛ0ε (ρ − ρl )kB ≤ β + α · .
2

(70)

Maximizing the LHS over ρ we obtain α ≤ β + α/2, or equivalently α ≤ 2β ≤ 2δ. Thus Eq. (67) is
≤ 4δ + 2d102d es+2−

ckδ 2
d2

.

(71)

Redefining c, this is ≤ 5δ when k ≥ cd3 /δ 2 .
Since Eq. (67) controls the expectation with respect to i1 , . . . , ik , we conclude that for at least half of the
i1 , . . . , ik , the LHS of Eq. (51) is ≤ 10δ. Since Eq. (65) holds with high probability (≥ 1 − d exp(−cd/8))
it follows that there exists a sequence of i1 , . . . , ik that simultaneously fulfills
P both criteria. Fix this choice.
Finally we choose Λ0 = Λ00 /(1 + δ) so that the normalization condition on j Xj0 is satisfied. This increases
the error by at most a further factor of δ. We conclude the proof by redefining δ to be 11δ.

B

Hardness of computing 2 → q norms

In this section we extend the hardness results of [BBH+ 12] (Theorem 9.4, part 2) for estimating the 2 → 4
norm to general 2 → q norms for even q ≥ 4.
The next lemma is an extension from Lemma 9.5 from [BBH+ 12].
Lemma 26. Let M ∈ L(Cd ⊗ Cd ) satisfy 0 ≤ M ≤ I. Assume that either (case Y ) hSep(d,d) (M ) = 1 or
(case N ) hSep(d,d) (M ) ≤ 1 − δ. Let k be a positive integer and q ≥ 4 an even positive integer. Then there
exists a matrix A of size d4kq × d2kq such that in case Y , kAk2→q = 1, and in case N , kAk2→q ≤ (1 − δ/2)k .
Moreover, A can be constructed efficiently from M .
Proof. Consider the following operator
1/2

1/2

1/2

1/2

N := (MA1 B1 ⊗ . . . ⊗ MAq/2 Bq/2 )PA1 ,...,Aq/2 ⊗ PB1 ,...,Bq/2 (MA1 B1 ⊗ . . . ⊗ MAq/2 Bq/2 ),

(72)

with PA1 ,...,Aq/2 the projector onto the symmetric subspace over A1 , ..., Aq/2 . We will first relate hSepq/2 (d2 ) (N )
to hSep(d,d) (M ), and then relate hSepq/2 (d2 ) (N ) to kAk2→q for a matrix A of size d4kq × d2kq .
First we show that in case Y , hSepq/2 (d2 ) (N ) = 1. Indeed since there are unit vectors x, y ∈ Cd satisfying
MAB (x ⊗ y) = x ⊗ y, we have
hSepq/2 (d2 ) (N )

=

max

v1 ,...,vq/2 ∈Cd2

(v1 ⊗ . . . ⊗ vq/2 )∗ N (v1 ⊗ . . . ⊗ vq/2 )

≥ (x⊗q/2 ⊗ y ⊗q/2 )∗ N (x⊗q/2 ⊗ y ⊗q/2 )
=

(x⊗q/2 ⊗ y ⊗q/2 )∗ PA1 ,...,Aq/2 ⊗ PB1 ,...,Bq/2 (x⊗q/2 ⊗ y ⊗q/2 ) = 1

In case N we show that hSepq/2 (d2 ) (N ) ≤ 1 − δ/2. Note that
PA1 ,...,Aq/2 ≤ PA1 A2 ⊗ IA3 ...Aq/2 .

20

(73)

Then
hSepq/2 (d2 ) (N )

=

max
v1 ,...,vq/2

≤

∈Cd2

(v1 ⊗ . . . ⊗ vq/2 )∗ N (v1 ⊗ . . . ⊗ vq/2 )
1/2

1/2

1/2

1/2

max (v1 ⊗ v2 )∗ (MA1 B1 ⊗ MA2 B2 )PA1 A2 ⊗ PB1 B2 (MA1 B1 ⊗ MA2 B2 )(v1 ⊗ v2 )

v1 ,v2 ∈Cd2

≤ 1 − δ/2,

(74)

where the last inequality follows from Lemma 9.6 of [BBH+ 12].
To construct a matrix A of size d4kq ×d2kq s.t. kAk2→q = hSepq/2 (d2 ) (N ) we follow the proof of Lemma 9.5
of [BBH+ 12], the only difference being that we apply Wick’s theorem to PA1 ,...Aq/2 , i.e. there is a measure
µ over unit vectors s.t.

Z
d + q/2 − 1
PA1 ,...,Aq/2 =
µ(dv)(vv ∗ )⊗q/2 .
(75)
q/2

The basic idea of the Lemma is to use the product test of [HM10] to force v1 , . . . , vq/2 to be product
states. Our proof can be summarized as saying that q/2 copies can enforce this more effectively than 2 copies
(assuming q/2 ≥ 2), and therefore we obtain soundness at least as sharp as in [BBH+ 12]. This analysis may
be wasteful, since using more copies should improve the effectiveness of the product test.
The main result of this section is the following analogue of Theorem 9.4, part 2, of [BBH+ 12]:
Theorem 27. Let φ be a 3-SAT instance with n variables and O(n) clauses and q ≥ 4 an even integer.
Determining whether φ is satisfiable can be reduced in polynomial time to determining
whether kAk2→q ≥ C
√
or kAk2→q ≤ c where 0 ≤ c < C and A is an m × m matrix, where m = exp(q n polylog(n) log(C/c)).
√
This gives nontrivial hardness for super-constant q, in fact up to Õ( log d), but not yet all the way up
to O(log d), where multiplicative approximations are known to be easy.
Proof. Corollary 14 of [HM10] gives a reduction from determining satisfiability of φ to distinguishing between
hSep(d,d) (M ) =√1 and hSep(d,d) (M ) ≤ 1/2, with 0 ≤ M ≤ I that can be constructed in time poly(d) from φ
with d = exp( n polylog(n)). Applying Lemma 26 gives the result.

References
[ABS10]

Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games
and related problems. In FOCS, pages 563–572, 2010.

[AIM14]

S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with multiple Merlins. In Computational
Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, June 2014, arXiv:1401.6848.

[ALSV13a] Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix
and its algorithmic applications: Approximate rank. In Proceedings of the 45th Annual ACM
Symposium on Symposium on Theory of Computing, STOC ’13, pages 675–684, 2013.
[ALSV13b] Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix
and its algorithmic applications: Approximate rank. In Proceedings of the Forty-fifth Annual
ACM Symposium on Theory of Computing, STOC ’13, pages 675–684. ACM, 2013.
[BaCY11]

Fernando G.S.L. Brandão, Matthias Christandl, and Jon Yard. A quasipolynomial-time algorithm for the quantum separability problem. In Proceedings of the 43rd annual ACM symposium
on Theory of computing, STOC ’11, pages 343–352, 2011, arXiv:1011.2751.

21

[BBH+ 12]

Boaz Barak, Fernando G.S.L. Brandão, Aram W. Harrow, Jonathan Kelner, David Steurer, and
Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In STOC ’12,
STOC ’12, pages 307–326, 2012, arXiv:1205.4484.

[BC11]

F.G.S.L. Brandão and M. Christandl. Detection of multiparticle entanglement: Quantifying the
search for symmetric extensions, 2011, arXiv:1105.5720.

[BCL94]

Keith Ball, Eric A. Carlen, and Elliott H. Lieb. Sharp uniform convexity and smoothness
inequalities for trace norms. Inventiones mathematicae, 115(1):463–482, 1994.

[BCY11]

F. G. S. L. Brandão, M. Christandl, and J. Yard. Faithful squashed entanglement. Commun.
Math. Phys., 306(3):805–830, 2011, arXiv:1010.1750.

[BH13]

Fernando G. S. L. Brandão and Aram W. Harrow. Quantum de Finetti theorems under local
measurements with applications. In Proceedings of the 45th annual ACM Symposium on theory
of computing, STOC ’13, pages 861–870, 2013, arXiv:1210.6367.

[BKS13]

Boaz Barak, Jonathan Kelner, and David Steurer. Rounding sum-of-squares relaxations. In
STOC ’14, STOC ’14, 2013, arXiv:1312.6652.

[BKW14]

M. Braverman, Y. K. Ko, and Omri Weinstein. Approximating the best Nash equilibrium in
no(log(n)) -time breaks the Exponential Time Hypothesis, 2014. ECCC TR14-092.

[BRS11]

Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming
hierarchies via global correlation. In FOCS, 2011, arXiv:1104.4680.

[BV11]

Aditya Bhaskara and Aravindan Vijayaraghavan. Approximating matrix p-norms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 497–511.
SIAM, 2011, arXiv:1001.2613.

[DF80]

P. Diaconis and D. Freedman. Finite exchangeable sequences. Annals of Probability, 8:745–764,
1980.

[DKLP06a] Etienne De Klerk, Monique Laurent, and Pablo A Parrilo. A PTAS for the minimization of
polynomials of fixed degree over the simplex. Theoretical Computer Science, 361(2):210–225,
2006.
[DKLP06b] Etienne De Klerk, Monique Laurent, and Pablo A Parrilo. A PTAS for the minimization of
polynomials of fixed degree over the simplex. Theoretical Computer Science, 361(2):210–225,
2006.
[DPS04]

Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. Complete family of separability criteria. Phys. Rev. A, 69:022308, Feb 2004, arXiv:quant-ph/0308032.

[GLS93]

M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization.
Springer-Verlag, 1993.

[Gur03]

Leonid Gurvits. Classical deterministic complexity of Edmonds’ problem and quantum entanglement. In STOC ’03, pages 10–19, 2003, arXiv:quant-ph/0303055.

[Har15]

Aram W. Harrow. Finding approximate Nash equilibria using LP hierarchies, 2015. in preparation.

[HLSW04] P. Hayden, D. W. Leung, P. W. Shor, and A. J. Winter. Randomizing quantum states: Constructions and applications. Commun. Math. Phys., 250:371–391, 2004, arXiv:quant-ph/0307104.
[HM10]

Aram W. Harrow and Ashley Montanaro. An efficient test for product states, with applications
to quantum Merlin-Arthur games. In FOCS ’10, pages 633–642, 2010, arXiv:1001.0017.
22

[HM13]

Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games
and tensor optimization. J. ACM, 60(1):3:1–3:43, February 2013, arXiv:1001.0017.

[HSR04]

M. Horodecki, P.W. Shor, and M.B. Ruskai. General entanglement breaking channels. Rev.
Math. Phys, 15(3):629–641, 2004, arXiv:quant-ph/0012127.

[KPT00]

Mikio Kato, Lars-Erik. Persson, and Yasuji Takahashi. Clarkson type inequalities and their
relations to the concepts of type and cotype. Collectanea Mathematica, 51(3):327–346, 2000.

[LMM03]

Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple
strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, EC ’03, pages
36–41. ACM, 2003.

[LRS+ 10]

Jason D Lee, Ben Recht, Ruslan R Salakhutdinov, Nathan Srebro, and Joel Tropp. Practical large-scale optimization for max-norm regularization. In J.D. Lafferty, C.K.I. Williams,
J. Shawe-Taylor, R.S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 1297–1305. Curran Associates, Inc., 2010.

[LS07]

Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. In In Proc. of the 39th Symposium on Theory of Computing (STOC, pages 699–708,
2007.

[LS09]

Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures & Algorithms, 34(3):368–394, 2009.

[LS14]

Ke Li and Graeme Smith. Quantum de Finetti theorem measured with fully one-way LOCC
norm, 2014, arXiv:1408.6829.

[LT91]

Michel Ledoux and Michel Talagrand. Probability in Banach spaces. Isoperimetry and processes.
Springer-Verlag, 1991.

[LW14]

Ke Li and Andreas Winter. Relative entropy and squashed entanglement. Commun. Math.
Phys., 326(1):63–80, 2014, arXiv:1210.3181.

[MWW09] William Matthews, Stephanie Wehner, and Andreas Winter. Distinguishability of quantum
states under restricted families of measurements with an application to quantum data hiding.
Commun. Math. Phys., 291(3):813–843, 2009, arXiv:0810.2327.
[Nao12]

Assaf Naor. On the Banach-space-valued Azuma inequality and small-set isoperimetry of
Alon-Roichman graphs. Combinatorics, Probability and Computing, 21:623–634, 7 2012,
arXiv:1009.5695.

[Pie07]

A. Pietsch. History of Banach Spaces and Linear Operators. Birkhäuser, 2007.

[Ste05]

Daureen Steinberg. Computation of matrix norms with applications to robust optimization.
Master’s thesis, Technion, 2005. Available on A. Nemirovski’s website http://www2.isye.gatech.
edu/∼nemirovs/.

[SW12]

Yaoyun Shi and Xiaodi Wu. Epsilon-net method for optimizations over separable states. In
Proceedings of the 39th International Colloquium Conference on Automata, Languages, and
Programming - Volume Part I, ICALP’12, pages 798–809, Berlin, Heidelberg, 2012. SpringerVerlag, arXiv:1112.0808.

[TJ74]

Nicole Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher
averages of the trace classes s{ p} (1 ≤ p < ∞). Studia Mathematica, 50(2):163–182, 1974.

[Tro10]

J. A. Tropp. User-friendly tail bounds for sums of random matrices, 2010, arXiv:1004.4389.
23

[Yan06]

D. Yang. A simple proof of monogamy of entanglement.
arXiv:quant-ph/0604168.

24

Phys. Lett., 360(1):249, 2006,

