Plaintext
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238
www.theoryofcomputing.org
Semidefinite Programs for
Completely Bounded Norms
John Watrous
Received: February 6, 2009; published: November 19, 2009.
Abstract: The completely bounded trace and spectral norms in finite dimensions are
shown to be expressible by semidefinite programs. This provides an efficient method by
which these norms may be both calculated and verified, and gives alternate proofs of some
known facts about them.
ACM Classification: F.2.1, G.1.6
AMS Classification: 81P45, 90C22, 15A60
Key words and phrases: completely bounded norm, diamond norm, semidefinite programming, quan-
tum information
1 Introduction
Linear mappings from one space of operators (or matrices) to another play an important role in quantum
information theory. Quantum channels in particular, which model general discrete-time changes in
quantum systems, are represented by mappings of this sort.
It is natural to consider distances between quantum channels, so as to quantify the similarity with
which they act on quantum states. One way to define such a notion is to define a suitable norm on the
space of mappings in which channels of a given size are represented. Then, the distance between two
channels is defined as the norm of their difference. A natural question that arises is: what norms give rise
to the most physically meaningful notions of distance? As is argued in [16], the answer to this question
may depend on the problem at hand—but perhaps the most natural and widely applicable choice within
quantum information theory is the completely bounded trace norm, also known as the diamond norm.
This norm was first used in the setting of quantum information by Kitaev [21], who used it mainly as a
tool in studying quantum error correction and fault-tolerance. It is equivalent, up to taking the adjoint of
a mapping, to its spectral norm variant, which is usually known simply as the completely bounded norm.
2009 John Watrous
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2009.v005a011
J OHN WATROUS
The completely bounded norm, as well as variants that include the completely bounded trace norm, have
been studied in operator theory for many years. (See [26] for historical comments and further details.)
The definition of the completely bounded trace and spectral norms, which can be found in the section
following this introduction, may seem unnecessarily complicated at first glance. It turns out, however,
that they are quite natural and satisfy many remarkable properties. They are, in particular, much easier to
reason about and to work with than the seemingly simpler norms induced by the trace norm and spectral
norm, primarily because the completely bounded variants of these norms respect the structure of tensor
products while the induced norms do not. The physical importance of this property within the setting
of quantum information theory has been discussed in several sources [1, 2, 9, 11, 16, 21, 28, 29, 30, 31,
32, 37]. Additional references that highlight the properties and uses of completely bounded norms in
quantum information include [14, 19, 27].
One obvious question that comes to mind about the completely bounded trace and spectral norms is:
can they be efficiently computed? Unlike the norms of operators that are most typically encountered in
quantum information theory, which are trivially computable from spectral or singular value decomposi-
tions, the computation of completely bounded norms is not known to be straightforward. To the author’s
knowledge there were only two papers written prior to this one, namely [38] and [20], that presented
methods to compute the completely bounded spectral or trace norm of a given mapping. Both papers
describe iterative methods, and analyze the complexity of each iteration of these methods, but do not
analyze their rates of convergence. So, although these papers may describe potentially efficient methods,
they do not include complete proofs of their efficiency.
The purpose of this paper is to explain how the completely bounded trace norm of a given map-
ping (and therefore its completely bounded spectral norm as well) can be expressed as the optimal
value of a semidefinite program whose size is polynomial in the dimension of the spaces on which the
mapping acts. Using known algorithms for solving semidefinite programs, one obtains a deterministic
polynomial-time algorithm for calculating these norms. This approach also has the obvious practical
advantage that it is more easily implemented through the use of existing semidefinite programming op-
timization libraries, and allows one to take advantage of the extensive work that has been done to solve
semidefinite programs efficiently and accurately in practice. Moreover, through semidefinite program-
ming duality, one obtains a means by which a certificate of the value of the completely bounded trace or
spectral norm of a given mapping may be quickly verified.
In a recent paper written independently from this one, Ben-Aroya and Ta-Shma [5] have found
a different (but related) way to efficiently compute the completely bounded trace norm using convex
programming.
The essence of the semidefinite programming formulation of the completely bounded trace norm
that is described in this paper appears, at least to some extent, in the paper [23]; although it was not
made explicit or considered in full generality therein. The present paper aims to present this formulation
explicitly and without any discussion of the quantum interactive proof system model of computation
that was the primary focus of [23]. A second semidefinite programming formulation of the completely
bounded trace norm is also presented, based on the competitive quantum game framework of [18].
This formulation is slightly simpler, but is valid only for mappings that are the difference between two
quantum channels—which happens to be an important special case in quantum information.
Semidefinite programming is useful not only as a computational tool, but as an analytic tool as
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 218
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
well. The last section of this paper gives two examples along these lines that are derived from the more
general semidefinite programming formulation of the completely bounded trace norm. The first example
concerns an alternate characterization of the completely bounded trace norm and the second illustrates a
precise sense in which two known characterizations of the fidelity function (given by Uhlmann’s theorem
and Alberti’s theorem) are dual statements to one another.
2 Background
The two subsections that follow aim to provide the reader with an account of the background knowledge
assumed in the remainder of the paper. The first subsection discusses well-known concepts from finite-
dimensional operator or matrix theory, and is mainly intended to make clear the notation and terminology
that is used throughout the paper. It also includes the definitions of the completely bounded norms that
are the main focus of this paper. The second subsection discusses semidefinite programming.
Linear algebra and basic operator theory
The scripted letters X, Y, Z, and W will denote vector spaces of the form Cn for n ≥ 1, whose elements
are identified with n-dimensional column vectors. On any such space X = Cn , an inner product is defined
as
n
hu, vi = ∑ u j v j ,
j=1
and the Euclidean norm is defined as p
kuk = hu, ui
for all u ∈ X. The unit sphere in X is denoted
S(X) = {u ∈ X : kuk = 1} ,
and the j-th elementary unit vector in X is denoted e j .
For X = Cn and Y = Cm , the complex vector space consisting of all linear mappings (or operators)
of the form A : X → Y is denoted L (X, Y) and is identified with the set of m × n complex matrices in
the usual way. For each A ∈ L (X, Y), we define A∗ ∈ L (Y, X) to be the unique operator that satisfies
hv, Aui = hA∗ v, ui for all u ∈ X and v ∈ Y. In terms of matrices, A∗ is simply the conjugate transform of A.
By identifying a given vector u ∈ X with the linear mapping α 7→ αu, the linear functional u∗ ∈ L (X, C)
is defined in the same way. More explicitly, u∗ satisfies u∗ v = hu, vi for all v ∈ X. For each pair of
indices i, j we write Ei, j = ei e∗j , which is the operator whose matrix representation has a 1 in entry
(i, j) and zeroes in all other entries. An inner product on L (X, Y) is defined as hA, Bi = Tr(A∗ B) for all
A, B ∈ L (X, Y). The notation L (X) is shorthand for L (X, X), and the identity operator on X, which is an
element of L (X), is denoted 1X .
The following special types of operators are discussed throughout the paper.
1. An operator X ∈ L (X) is Hermitian if X = X ∗ . The set of such operators is denoted Herm (X).
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 219
J OHN WATROUS
2. An operator P ∈ L (X) is positive semidefinite if it is Hermitian and all of its eigenvalues are non-
negative. The set of such operators is denoted Pos (X). The notation P ≥ 0 also indicates that P is
positive semidefinite, and more generally the notations X ≤ Y and Y ≥ X indicate that Y − X ≥ 0 for
Hermitian operators X and Y .
3. An operator P ∈ L (X) is positive definite if it is both positive semidefinite and invertible. (Equiva-
lently, P is positive definite if it is Hermitian and all of its eigenvalues are positive.) The set of such
operators is denoted Pd (X). The notation P > 0 also indicates that P is positive definite, and the
notations X < Y and Y > X indicate that Y − X > 0 for Hermitian operators X and Y .
4. An operator ρ ∈ L (X) is a density operator if it is both positive semidefinite and has trace equal to
1. The set of such operators is denoted D (X).
5. An operator U ∈ L (X) is unitary if U ∗U = 1X . The set of such operators is denoted U (X).
A useful notion concerning positive semidefinite operators is that of a purification. For any positive
semidefinite operator P ∈ Pos (X), and any space Y satisfying dim(Y) ≥ rank(P), there must exist a
vector of the form u ∈ X ⊗ Y that satisfies P = TrY (uu∗ ), where TrY denotes the partial trace on Y.
The vector u is called a purification of P. Given any two purifications u, v ∈ X ⊗ Y of a given positive
semidefinite operator P ∈ Pos (X), it necessarily holds that there exists a unitary operator U ∈ U (Y) such
that v = (1X ⊗U)u. This fact is often referred to as the unitary equivalence of purifications.
Three operator norms are discussed in this paper: the trace norm, Frobenius norm, and spectral
norm, defined as
√ p
kAk1 = Tr A∗ A , kAk2 = hA, Ai , and kAk∞ = max kAuk ,
u∈S(X)
respectively, for each A ∈ L (X, Y). These norms correspond precisely to the 1-norm, 2-norm, and ∞-
norm of the vector of singular values of A, which explains the notation used to denote them.
Some specific properties of the above norms that will be needed in this paper will now be sum-
marized. (Readers interested in a more comprehensive discussion are referred to [6].) First, for every
operator A it holds that
kAk∞ ≤ kAk2 ≤ kAk1 ,
which is clear from the description of these norms in terms of the singular values of A. Next, it holds
that trace and spectral norms are dual, which means that
kAk1 = max{|hB, Ai| : kBk∞ ≤ 1}
kAk∞ = max{|hB, Ai| : kBk1 ≤ 1}
for all A ∈ L (X, Y), and with B ranging over operators within the same space. By convexity it is sufficient
to restrict the maximizations in these equations to those choices of B that are extreme points in the
(compact and convex) sets being maximized over. In particular, for operators of the form X ∈ L (X) it
holds that
kX k1 = max |hU, Xi| .
U∈U(X)
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 220
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
Various other properties follow from the duality of the trace and spectral norms, including the inequality
|hA, Bi| ≤ kAk1 kBk∞ , (2.1)
along with the monotonicity of the trace norm: for every operator of the form A ∈ L (X ⊗ Y) it holds that
kAk1 ≥ kTrY (A)k1 . (2.2)
Finally, we note that
kA∗ Ak∞ = kAA∗ k∞ = kAk2∞ (2.3)
for every choice of an operator A.
Linear mappings from one space of operators to another are very important in the theory of quantum
information. The space of all linear mapping of the form Φ : L (X) → L (Y) is denoted T (X, Y). The
adjoint mapping to Φ ∈ T (X, Y) is the unique mapping Φ∗ ∈ T (Y, X) for which
hY, Φ(X)i = hΦ∗ (Y ), Xi
for all X ∈ L (X) and Y ∈ L (Y). The identity mapping from L (X) to itself is denoted 1L(X) .
The following special types of mappings will be referred to later in the paper:
1. Φ ∈ T (X, Y) is Hermiticity-preserving if Φ(X) ∈ Herm (Y) for every X ∈ Herm (X).
2. Φ ∈ T (X, Y) is completely positive if it holds that
(Φ ⊗ 1L(W) )(P) ∈ Pos (Y ⊗ W)
for every choice of W = Ck and P ∈ Pos (X ⊗ W).
3. Φ ∈ T (X, Y) is trace-preserving if Tr(Φ(X)) = Tr(X) for every X ∈ L (X).
4. Φ ∈ T (X, Y) is a quantum channel if it is both completely positive and trace-preserving.
Assume hereafter that X = Cn and Y = Cm . The Choi–Jamiołkowski representation J(Φ) ∈ L (Y ⊗ X)
of a mapping Φ ∈ T (X, Y) is the operator defined as
J(Φ) = ∑ Φ(Ei, j ) ⊗ Ei, j .
1≤i, j≤n
The mapping J is a linear bijection from T (X, Y) to L (Y ⊗ X). The operator J(Φ), written as an nm × nm
matrix, is one way that a mapping Φ ∈ T (X, Y) may be expressed in concrete terms. It holds that
1. Φ ∈ T (X, Y) is Hermiticity-preserving if and only if J(Φ) is Hermitian [13],
2. Φ ∈ T (X, Y) is completely positive if and only if J(Φ) is positive semidefinite [10], and
3. Φ ∈ T (X, Y) is trace-preserving if and only if TrY (J(Φ)) = 1X .
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 221
J OHN WATROUS
A pair of operators (A, B) in L (X, Y ⊗ Z) is a Stinespring pair for Φ ∈ T (X, Y) if it holds that
Φ(X) = TrZ (AXB∗ ) (2.4)
for all X ∈ L (X), and an expression of the form (2.4) is called a Stinespring representation of Φ.
The minimal dimension of Z for which a Stinespring representation of a given non-zero mapping
Φ ∈ T (X, Y) exists is always equal to rank(J(Φ)). It is straightforward to compute such a Stinespring
pair (A, B) from the Choi–Jamiołkowski representation of Φ ∈ T (X, Y); for any expression
r
J(Φ) = ∑ ul v∗l ,
l=1
it holds that
r m n r m n
A = ∑ ∑ ∑ ei ⊗ e j , ul Ei, j ⊗ el and B = ∑ ∑ ∑ ei ⊗ e j , vl Ei, j ⊗ el
l=1 i=1 j=1 l=1 i=1 j=1
forms a Stinespring pair of Φ.
It will be helpful later to observe that if Φ ∈ T (X, Y) is a given mapping, Z is taken to have the
minimal dimension dim(Z) = rank(J(Φ)) to admit a Stinespring pair of Φ, and if (A, B) is such a pair,
then it must hold that TrY (AA∗ ) and TrY (BB∗ ) are positive definite.
Now we will discuss norms of mappings of the form Φ ∈ T (X, Y). For each Φ ∈ T (X, Y), one
defines the induced norms:
kΦk1 = max {kΦ(X)k1 : X ∈ L (X) , kX k1 ≤ 1} ,
kΦk∞ = max {kΦ(X)k∞ : X ∈ L (X) , kX k∞ ≤ 1} ,
as well as completely bounded variants of these norms:
|||Φ|||1 = sup Φ ⊗ 1L(Ck ) and |||Φ|||∞ = sup Φ ⊗ 1L(Ck ) .
k≥1 1 k≥1 ∞
As was done in the introduction, we will refer to |||Φ|||1 as the completely bounded trace norm and to
|||Φ|||∞ as the completely bounded spectral norm. It follows from the duality of the trace and spectral
norms that |||Φ|||1 = |||Φ∗ |||∞ for every Φ ∈ T (X, Y).
It is common that |||Φ|||1 is denoted kΦk and called the diamond norm, and that |||Φ|||∞ is denoted
kΦkcb and called simply the completely bounded norm. We will not follow this notation (or terminology)
in this paper in the interest of making the connections of these norms to the trace and spectral norms
clear, as well as to stress the close relationship they share through the duality of the trace and spectral
norms.
For every mapping Φ ∈ T (X, Y) it holds that
|||Φ|||1 = Φ ⊗ 1L(X) 1 and |||Φ|||∞ = Φ ⊗ 1L(Y) ∞ .
These two equalities are equivalent (through the duality of the trace and spectral norms), and can be
proved in multiple ways. The second equality was evidently first proved by Smith [33], who considered
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 222
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
the general situation where X need not be finite-dimensional. For the finite-dimensional case, simple
proofs of the first equality (and therefore the second by duality) can be found in [16] and [36].
The completely bounded trace and spectral norms are both multiplicative with respect to tensor
products, meaning that
|||Φ ⊗ Ψ|||1 = |||Φ|||1 |||Ψ|||1 and |||Φ ⊗ Ψ|||∞ = |||Φ|||∞ |||Ψ|||∞
for any choice of mappings Φ and Ψ. A proof of this fact can be found in [22], for instance.
Next, let us note for convenience that for any mapping Φ ∈ T (X, Y) it holds that
n o
|||Φ|||1 = max (Φ ⊗ 1L(X) )(uv∗ ) 1 : u, v ∈ S(X ⊗ X) . (2.5)
This is a simple consequence of the convexity of norms along with the fact that the extreme points of
the unit ball with respect to the trace norm take the form uv∗ for unit vectors u and v. For a Hermiticity-
preserving mapping Φ ∈ T (X, Y), the expression (2.5) can be further simplified [16, 30] as
n o
|||Φ|||1 = max (Φ ⊗ 1L(X) )(uu∗ ) 1 : u ∈ S(X ⊗ X) .
This equation is generally not valid for non-Hermiticity-preserving mappings.
Finally, we note that small perturbations in the Stinespring representations of mappings cause small
perturbations in the completely bounded trace norm. In particular, if Φ0 , Φ1 ∈ T (X, Y) satisfy
Φ0 (X) = TrZ (A0 XB∗0 ) and Φ1 (X) = TrZ (A1 XB∗1 ) ,
then it holds that
|||Φ0 − Φ1 |||1 ≤ kA0 k∞ kB0 − B1 k∞ + kB1 k∞ kA0 − A1 k∞ . (2.6)
One may also exchange A0 with A1 and B0 with B1 in this inequality. The inequality (2.6) follows
easily from the inequalities (2.2) and (2.1), along with the triangle inequality. (This inequality was
proved in [24] for the special case that A0 = B0 and A1 = B1 , and the general case follows by identical
reasoning.)
Semidefinite programming
This section gives a brief overview of semidefinite programming, which is discussed in greater detail in
several sources (including [4, 7, 12, 25, 35], for instance).
A semidefinite program over X = Cn and Y = Cm is specified by a triple (Ψ,C, D), where
1. Ψ ∈ T (X, Y) is a Hermiticity-preserving mapping, and
2. C ∈ Herm (X) and D ∈ Herm (Y) are Hermitian operators.
The following two optimization problems are associated with such a semidefinite program:
Primal problem Dual problem
maximize: hC, Xi minimize: hD,Y i
subject to: Ψ(X) ≤ D , subject to: Ψ∗ (Y ) ≥ C ,
X ∈ Pos (X) . Y ∈ Pos (Y) .
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 223
J OHN WATROUS
Readers familiar with semidefinite programming will note that the above form of a semidefinite
program is different from the well-known standard form, but it is equivalent and better suited for this
paper’s needs. The form given above is, in essence, the one that is typically followed for general conic
programming [7].
With the above optimization problems in mind, one defines the primal feasible set P and the dual
feasible set D as
P = {X ∈ Pos (X) : Ψ(X) ≤ D} ,
D = {Y ∈ Pos (Y) : Ψ∗ (Y ) ≥ C} .
Operators X ∈ P and Y ∈ D are also said to be primal feasible and dual feasible, respectively. The
functions X 7→ hC, Xi and Y 7→ hD,Y i are called the primal and dual objective functions, and the optimal
values associated with the primal and dual problems are defined as follows:
α = sup hC, Xi and β = inf hD,Y i .
X∈P Y ∈D
(If it is the case that P = ∅ or D = ∅, the above definitions are to be interpreted as α = −∞ and β = ∞,
respectively.) The supremum and infimum cannot always be replaced by the maximum and minimum—
in some cases even finite values α and β may not be achieved for any choice of X ∈ P and Y ∈ D.
Semidefinite programs have associated with them a powerful theory of duality, which refers to the
special relationship between the primal and dual problems. The property of weak duality, which holds
for all semidefinite programs, is stated in the following theorem.
Theorem 2.1 (Weak duality). For every semidefinite program (Ψ,C, D) as defined above, it holds that
α ≤ β.
This property implies that every dual feasible operator Y ∈ D provides an upper bound of hD,Y i on the
value hC, Xi that is achievable over all choices of a primal feasible X ∈ P, and likewise every primal
feasible operator X ∈ P provides a lower bound of hC, Xi on the value hD,Y i that is achievable over all
choices of a dual feasible Y ∈ D.
It is not always the case that α = β for a given semidefinite program (Ψ,C, D), even when α and
β are finite. For most semidefinite programs that arise in practice, however, it is the case that α = β ,
which is a situation known as strong duality. There are different conditions under which this property is
guaranteed, one of which is given by the following theorem.
Theorem 2.2 (Slater-type condition for strong duality). The following two implications hold for every
semidefinite program (Ψ,C, D) as defined above.
1. Strict primal feasibility: If β is finite and there exists an operator X > 0 such that Ψ(X) < D, then
α = β and there exists Y ∈ D such that hD,Y i = β .
2. Strict dual feasibility: If α is finite and there exists an operator Y > 0 such that Ψ∗ (Y ) > C, then
α = β and there exists X ∈ P such that hC, Xi = α.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 224
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
One may consider a general computational problem that asks for the optimal primal and dual values
of a given semidefinite program, possibly up to some specified accuracy. The specific formulation of
this problem that this paper follows requires that we first define, for each choice of ε > 0, the following
sets:
Pε = {X ∈ Pos (X) : X + H ∈ P for all H ∈ Herm (X) satisfying kH k2 ≤ ε} ,
Dε = {Y ∈ Pos (Y) : Y + H ∈ D for all H ∈ Herm (Y) satisfying kH k2 ≤ ε} .
Intuitively speaking, Pε contains primal feasible operators that are not too close to the boundary of the
primal feasible set, and likewise for Dε . Having defined the sets Pε and Dε in this way, we now phrase
the problem of approximating the optimal value of a semidefinite program as a promise problem [15] as
follows:
Problem 2.3. The semidefinite programming approximation problem is as follows.
Input: A semidefinite program (Ψ,C, D) over X = Cn and Y = Cm , an accuracy parameter
ε > 0, and a positive integer R.
Promise: The set Pε is non-empty, and for every X ∈ P it holds that kX k2 ≤ R. (In the terminol-
ogy of [17], the primal feasible region P of (Ψ,C, D) is well-bounded, with parameters
ε and R.)
Output: A real number γ such that |γ − α | < ε, where α is the optimal value of the primal
problem associated with (Ψ,C, D).
The description of this problem does not explicitly state how the mapping Ψ is to be represented, but
we will assume it is specified by the matrix representation of J(Ψ). Other forms, including Stinespring
representations and Kraus representations, are easily converted to this form. It is also assumed that the
entries of J(Ψ), C, and D have rational real and imaginary parts.
The computational problem stated above can be solved in polynomial time using the ellipsoid
method [17], as the following theorem states.
Theorem 2.4. There exists an algorithm that solves the semidefinite programming approximation prob-
lem stated above that runs in time polynomial in n, m, log(R), log(1/ε), and the maximum bit-length of
the entries of J(Ψ), C, and D.
Here, the bit-length of a complex number z = (a/b) + i(c/d) is the number of bits needed to encode the
4-tuple (a, b, c, d), where a, b, c, and d are integers represented in binary notation.
It should be noted that one would typically not use the ellipsoid method to solve semidefinite pro-
gramming problems in practice, given that interior point methods [4, 12] are considered to be more
practical.
Note that the above problem asks only for an approximation to the optimal primal value, but the
simple transformation (Ψ,C, D) → (−Ψ∗ , −D, −C) shows that any algorithm for it also allows one to
approximate the optimal dual value. (Alternately, the ellipsoid method can be applied directly to the
dual problem.)
It is possible to approximate more general classes of semidefinite programs efficiently. For instance,
the bound kX k2 ≤ R need not hold for every primal feasible X, provided certain assumptions are known
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 225
J OHN WATROUS
about the size of the optimal solution. These generalizations are not important for this paper, and the
above problem can be more easily fit to the general presentation of [17] (which is described for the
specific setting of semidefinite programming in [25]).
3 A semidefinite program for the completely bounded trace norm
We will now describe and analyze a semidefinite program whose optimal (primal and dual) value is
|||Φ|||21 , where Φ ∈ T (X, Y) is an arbitrary mapping given by a Stinespring representation
Φ(X) = TrZ (AXB∗ )
for A, B ∈ L (X, Y ⊗ Z). It will be assumed that Z = Cr for r = rank(J(Φ)), which is the minimal
dimension for which such a Stinespring representation exists.
The primal and dual problems for the semidefinite program we will consider may be stated as fol-
lows:
Primal problem Dual problem
maximize: hBB∗ ,W i minimize: kA∗ (1Y ⊗ Z)Ak∞
subject to: TrY (W ) = TrY (AρA∗ ) , subject to: 1Y ⊗ Z ≥ BB∗ ,
ρ ∈ D (X) , Z ∈ Pos (Z) .
W ∈ Pos (Y ⊗ Z) .
These problems are associated with the semidefinite program that is more formally specified in the
following way. We define a Hermiticity-preserving mapping
Ψ : L (X ⊕ (Y ⊗ Z)) → L (C ⊕ Z)
as
X · Tr(X) 0
Ψ = .
· W 0 TrY (W − AXA∗ )
The adjoint mapping
Ψ∗ : L (C ⊕ Z) → L (X ⊕ (Y ⊗ Z))
is given by
λ 1X − A∗ (1Y ⊗ Z)A
∗λ · 0
Ψ = .
· Z 0 1Y ⊗ Z
(In these expressions of Ψ and Ψ∗ , the symbol · denotes an operator or vector of the appropriate dimen-
sions on which the output of these mappings does not depend.) We also define C ∈ Herm (X ⊕ (Y ⊗ Z))
and D ∈ Herm (C ⊕ Z) as
0 0 1 0
C= and D = .
0 BB∗ 0 0
Now, the primal and dual problem associated with (Ψ,C, D) may be expressed as follows:
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 226
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
Primal problem Dual problem
∗
maximize: hBB ,W i minimize: λ
∗
subject to: TrY (W ) ≤ TrY (AXA ) , subject to: λ 1X ≥ A∗ (1Y ⊗ Z)A
Tr(X) ≤ 1 , 1Y ⊗ Z ≥ BB∗ ,
X ∈ Pos (X) , λ ≥ 0,
W ∈ Pos (Y ⊗ Z) . Z ∈ Pos (Z) .
Notice that for any choice of a primal feasible operator
X M
, (3.1)
M∗ W
there exist operators P ∈ Pos (X) and Q ∈ Pos (Y ⊗ Z) such that Tr(X + P) = 1 and
TrY (W + Q) = TrY (A(X + P)A∗ ) .
The operator
X +P M
M∗ W + Q
is therefore primal feasible, and obtains at least the value achieved by (3.1) (by virtue of the fact that
BB∗ is positive semidefinite). This explains the equivalence of the two different statements for the primal
problem above, where the equality constraints in the first are replaced by inequality constraints in the
second. The two statements of the dual problems are obviously equivalent, because A∗ (1Y ⊗ Z)A is
positive semidefinite for positive semidefinite Z, and therefore
min λ ≥ 0 : λ 1X ≥ A∗ (1Y ⊗ Z)A = kA∗ (1Y ⊗ Z)Ak∞ .
Strong duality
We will now verify that strong duality holds for the above semidefinite program, using Theorem 2.2.
To begin, we will prove that the optimal primal value α is necessarily finite. By equations (2.1)
and (2.3), it holds that
hBB∗ ,W i ≤ kBB∗ k∞ kW k1 = kBk2∞ Tr(W )
for every positive semidefinite operator W . Whenever W is primal feasible it holds that
Tr(W ) ≤ Tr(AXA∗ ) = hA∗ A, Xi ≤ kA∗ Ak∞ kX k1 ≤ kAk2∞
for some X ∈ Pos (X) with Tr(X) ≤ 1. Thus, the optimal primal value satisfies
α ≤ kAk2∞ kBk2∞ ,
which shows that α is finite.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 227
J OHN WATROUS
Now, to verify strict dual feasibility, suppose that µ and λ are positive real numbers such that µ >
kBk2∞ and λ > µ kAk2∞ . Then it holds that
λ 0
>0
0 µ1Z
and
λ 1X − µA∗ A
λ 0 0 0 0
Ψ∗ = > ,
0 µ1Z 0 µ1Y ⊗ 1Z 0 BB∗
which illustrates strict dual feasibility. Thus, by Theorem 2.2, the optimal value α associated with the
primal problem is equal to the optimal dual value β , and is achieved for some choice of a primal feasible
operator.
Having already established strong duality, it is not really essential for this paper’s needs that strict
primal feasibility is proved. One may wonder, however, whether strict primal feasibility holds for the
semidefinite program above. Indeed it does, but it relies on the assumption
dim(Z) = rank(J(Φ)) .
This observation, which happens to imply that the optimal dual value is achieved for some dual feasible
operator, will follow from the discussion of computational efficiency below.
Optimal value
Now let us verify that the optimal value α = β of our semidefinite program is equal to |||Φ|||21 . To do this
we first define W = Ck for k = max{dim(X), dim(Y ⊗ Z)}. Given that dim(W) ≥ dim(X), it holds that
|||Φ|||21 = max |hU, TrZ ((A ⊗ 1W )uv∗ (B∗ ⊗ 1W ))i|2
u,v∈S(X⊗W)
U∈U(Y⊗W)
= max k(B∗ ⊗ 1W )(U ∗ ⊗ 1Z )(A ⊗ 1W )uk2
u∈S(X⊗W)
U∈U(Y⊗W)
= max u∗ (A∗ ⊗ 1W )(U ⊗ 1Z )(BB∗ ⊗ 1W )(U ∗ ⊗ 1Z )(A ⊗ 1W )u
u∈S(X⊗W)
U∈U(Y⊗W)
= max hBB∗ , TrW [(U ∗ ⊗ 1Z )(A ⊗ 1W )uu∗ (A∗ ⊗ 1W )(U ⊗ 1Z )]i .
u∈S(X⊗W)
U∈U(Y⊗W)
Now define two sets Q, R ⊆ Pos (Y ⊗ Z) as
Q = W ∈ Pos (Y ⊗ Z) : TrY (W ) = TrY (AρA∗ ) for some choice of ρ ∈ D (X) ,
R = TrW [(U ∗ ⊗ 1Z )(A ⊗ 1W )uu∗ (A∗ ⊗ 1W )(U ⊗ 1Z )] : u ∈ S(X ⊗ W) , U ∈ U (Y ⊗ W) .
Our interest in the set R is clear, for the equation above has established that
|||Φ|||21 = max hBB∗ ,W i .
W ∈R
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 228
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
The set Q, on the other hand, is of interest because the optimal value α of the primal problem for the
semidefinite program defined above is given by
α = max hBB∗ ,W i .
W ∈Q
To establish that α = |||Φ|||21 , it therefore suffices to prove that Q = R, which can be done as follows.
First consider an arbitrary choice of u ∈ S(X ⊗ W) and U ∈ U (Y ⊗ W), and let
W = TrW [(U ∗ ⊗ 1Z )(A ⊗ 1W )uu∗ (A∗ ⊗ 1W )(U ⊗ 1Z )] .
Then TrY (W ) = TrY (A TrW (uu∗ )A∗ ), and so it holds that W ∈ Q, which proves R ⊆ Q.
Now consider an arbitrary element W ∈ Q, and let ρ ∈ D (X) be a density operator satisfying
TrY (W ) = TrY (AρA∗ ). Given that we have chosen W to have dimension at least as large as that of
both X and Y ⊗ Z, there must exist vectors u ∈ S(X ⊗ W) and w ∈ Y ⊗ Z ⊗ W that purify ρ and W ,
respectively, meaning that ρ = TrW (uu∗ ) and W = TrW (ww∗ ). This implies that
TrY⊗W (ww∗ ) = TrY⊗W (A ⊗ 1W )uu∗ (A∗ ⊗ 1W ) ,
so by the unitary equivalence of purifications there must exist a unitary operator U ∈ U (Y ⊗ W) such
that (U ∗ ⊗ 1Z )(A ⊗ 1W )u = w. Therefore
W = TrW (ww∗ ) = TrW [(U ∗ ⊗ 1Z )(A ⊗ 1W )uu∗ (A∗ ⊗ 1W )(U ⊗ 1Z )] ,
which proves that W ∈ R, so that Q ⊆ R as required.
Computational efficiency
Now let us verify that the optimal value |||Φ|||21 of the semidefinite program described above can be
approximated by an efficient computation. By Theorem 2.4 our task is to argue that suitable parameters
R and ε for the promise in Problem 2.3 can be determined. For the sake of clarity, let us first summarize
our notation: we have X = Cn , Y = Cm , and Z = Cr , and Φ ∈ T (X, Y) is the mapping given by
Φ(X) = TrZ (AXB∗ )
for which we wish to approximate |||Φ|||21 . The semidefinite program that represents this quantity is
represented by the Hermiticity-preserving mapping Ψ ∈ T (X ⊕ (Y ⊗ Z), C ⊕ Z) and Hermitian operators
C ∈ Herm (X ⊕ (Y ⊗ Z)) and D ∈ Herm (C ⊕ Z) described previously.
At this point it is important to stress that we must make an assumption on the operators A and B,
which is that they are represented by matrices having rational real and imaginary parts. (This assumption
is only necessary for the present discussion of computational efficiency, and not the other parts of the
paper.) This is a natural assumption to make within a computational setting—and for an arbitrary choice
of A and B we note that one may simply approximate the entries of A and B by numbers having rational
real and imaginary parts, and then apply (2.6) to bound the error that results from this approximation.
Hereafter we will write N to refer to the total bit-length of the semidefinite program (Ψ,C, D), which
is polynomially related to n, m and the maximum bit-length of the entries of A and B.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 229
J OHN WATROUS
First, it is clear that every primal feasible operator has trace bounded by 1 + kAk2∞ . Given that the
Frobenius norm is upper-bounded by the trace for positive semidefinite operators, it therefore suffices to
choose R = 1 + kAk2∞ , which is obviously bounded by 2cN for some positive integer constant c.
The specification of ε is slightly more complicated. Consider first the operator TrY (AA∗ ). We
have chosen Z to have minimal dimension to admit a Stinespring representation of Φ, and from this
assumption it follows that TrY (AA∗ ) is positive definite. Using the assumption that the real and imaginary
parts of the entries of A are rational, along with the fact that nonzero roots of integer polynomials cannot
be too close to zero (see, for instance, Theorem 2.9 of [8]), one may derive a lower-bound on the smallest
eigenvalue of TrY (AA∗ ). For the purposes of this analysis, it suffices to note that there exists an integer
constant d0 ≥ 1 such that for δ = 2−d0 N we have that the smallest eigenvalue of TrY (AA∗ ) is at least δ ,
and therefore δ 1Z ≤ TrY (AA∗ ).
Now consider the operator
X 0
P=
0 W
where
3 3
X= 1X and W= 1Y ⊗ TrY (AA∗ ) ,
4n 8nm
along with any choice of a real number ε > 0 that satisfies
δ
ε≤ .
8nm
Let us note, in particular, that this bound holds for ε = 2−dN for some choice of a positive integer
constant d. It is our goal to show that every Hermitian operator whose distance from P is at most ε (with
respect to the Frobenius norm) lies within the primal feasible set A, and therefore that Aε is nonempty.
In other words, for any choice of operators H ∈ Herm (X), K ∈ Herm (Y ⊗ Z), and M ∈ L (Y ⊗ Z, X)
satisfying
H M
<ε,
M∗ K 2
we wish to prove that
X +H M
(3.2)
M∗ W +K
is primal feasible.
It is clear that ε1 < P, and therefore (3.2) is positive semidefinite. As kK k∞ < ε it follows that
1
W + K ≤ W + ε 1Y⊗Z ≤ 1Y ⊗ TrY (AA∗ )
2nm
and therefore
1
TrY (W + K) ≤ TrY (AA∗ ) .
2n
As kH k∞ ≤ ε it holds that
1
1X ≤ X − ε1X ≤ X + H
2n
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 230
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
and therefore
1
TrY (AA∗ ) ≤ TrY (A(X + H)A∗ ) .
2n
It follows that TrY (W + K) ≤ TrY (A(X + H)A∗ ) and therefore the above operator (3.2) is primal feasible
as required.
We have shown that the requirements of the promise in Problem 2.3 are met for R = 2cN and ε =
2 −dN for some positive integer constants c and d. By Theorem 2.4 the value |||Φ|||21 may therefore be
approximated to within error ε in time polynomial in n, m and the bit-length of the entries of A and B.
(It is possible of course to choose a smaller error, ε = 2−p(N) for any polynomial p for instance, if this
is desired.)
4 A simpler semidefinite program for quantum channel distance
A somewhat simpler semidefinite program exists for the completely bounded trace norm of the difference
between two quantum channels, which is a special case that is relevant to quantum information. This
case was discussed in [16], and shown to reduce to a convex optimization problem. The discussion that
follows is somewhat different, and is derived from the quantum games framework of [18].
Suppose hereafter in this section that Φ = Φ0 − Φ1 for quantum channels Φ0 , Φ1 ∈ T (X, Y), and
consider the semidefinite program whose primal and dual problems are as follows:
Primal problem Dual problem
maximize: hJ(Φ),W i minimize: kTrY (Z)k∞
subject to: W ≤ 1Y ⊗ ρ , subject to: Z ≥ J(Φ) ,
W ∈ Pos (Y ⊗ X) , Z ∈ Pos (Y ⊗ X) .
ρ ∈ D (X) .
As in the previous section, these problems can be matched to the formal description of a semidefinite
program (Ψ,C, D), for which strong duality is easily proved. Our goal will be to prove that the optimal
value of this semidefinite program is given by 12 |||Φ|||1 .
Given that Φ is a Hermiticity-preserving mapping, it holds that
|||Φ|||1 = max (Φ ⊗ 1L(X) )(uu∗ ) 1 .
u∈S(X⊗X)
For every u ∈ S(X ⊗ X) it holds that the operator (Φ ⊗ 1L(X) )(uu∗ ) is the difference between two density
operators, and therefore
P, (Φ ⊗ 1L(X) )(uu∗ ) : u ∈ S(X ⊗ X) , P ∈ Pos (Y ⊗ X) , P ≤ 1Y⊗X .
|||Φ|||1 = 2 max
Now, for every unit vector u ∈ S(X ⊗ X) there is a corresponding operator B ∈ L (X) with kBk2 = 1
such that
u = ∑ Ei, j , B ei ⊗ e j .
1≤i, j≤n
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 231
J OHN WATROUS
For this choice of B we have
(1Y ⊗ B)J(Φ)(1Y ⊗ B∗ ) = (Φ ⊗ 1L(X) )(uu∗ ) .
It follows that
|||Φ|||1 = 2 max h(1 ⊗ B∗ )P(1 ⊗ B), J(Φ)i
B,P
where the maximum is over all B ∈ L (X) with kBk2 = 1 and P ∈ Pos (Y ⊗ X) with P ≤ 1Y⊗X .
Now define sets Q and R as follows:
Q = R ∈ Pos (Y ⊗ X) : R ≤ 1Y ⊗ ρ for some ρ ∈ D (X) ,
R = (1Y ⊗ B∗ )P(1Y ⊗ B) : B ∈ L (X) , P ∈ Pos (Y ⊗ X) , kBk2 = 1, P ≤ 1Y⊗X .
It holds that
|||Φ|||1 = 2 sup hJ(Φ), Xi
X∈R
while the optimal value of the semidefinite program above is
α = sup hJ(Φ), Xi .
X∈Q
The fact that α = 21 |||Φ|||1 therefore follows from the equality Q = R, which can be proved by selecting
ρ or B so that ρ = B∗ B.
5 Connections with known results
This section describes two interesting connections between the semidefinite programming formulation
from Section 3 and known results, the first being directly about completely bounded norms, and the
second concerning the fidelity function.
Spectral norms of Stinespring representations
The following theorem gives an alternate characterization of the completely bounded trace norm (or
diamond norm). Proofs can be found in Kitaev, Shen and Vyalyi [22] and Paulsen [26]. These two
proofs use rather different techniques, and here the theorem is proved in a third way using semidefinite
programming duality.
Theorem 5.1. For every mapping Φ ∈ T (X, Y), it holds that
|||Φ|||1 = inf kAk∞ kBk∞ , (5.1)
(A,B)
where the infimum is over all Stinespring pairs (A, B) for Φ.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 232
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
Proof. For any Stinespring pair (A, B) of Φ, where A, B ∈ L (X, Y ⊗ Z), and for any choice of W = Ck ,
it holds that
(Φ ⊗ 1L(W) )(X) 1 = kTrZ [(A ⊗ 1W )X(B∗ ⊗ 1W )]k1
≤ k(A ⊗ 1W )X(B∗ ⊗ 1W )k1
≤ kAk∞ kX k1 kBk∞
for all X ∈ L (X ⊗ W), where the inequalities follow from (2.2) and (2.1), respectively. It follows that
|||Φ|||1 ≤ kAk∞ kBk∞ .
To prove that the infimum is no larger than |||Φ|||1 , first choose an arbitrary Stinespring pair (A, B)
of Φ, where A, B ∈ L (X, Y ⊗ Z). The optimal value for the dual problem stated in Section 3 does not
change if Z is restricted to be positive definite, provided we accept that an optimal solution may not be
achieved. We therefore have
|||Φ|||21 = inf kA∗ (1Y ⊗ Z)Ak∞ : 1Y ⊗ Z ≥ BB∗ , Z ∈ Pd (Z) .
Thus, for a given ε > 0, we may choose Z ∈ Pd (Z) such that
kA∗ (1Y ⊗ Z)Ak∞ ≤ (|||Φ|||1 + ε)2
and 1Y ⊗ Z ≥ BB∗ . This second inequality is equivalent to
1Y ⊗ Z −1/2 BB∗ 1Y ⊗ Z −1/2 ≤ 1.
∞
So now we have that
1Y ⊗ Z 1/2 A 1Y ⊗ Z −1/2 B ≤ |||Φ|||1 + ε ,
∞ ∞
and it holds that
1Y ⊗ Z 1/2 A, 1Y ⊗ Z −1/2 B
is a Stinespring pair for Φ. This establishes that the infimum equals |||Φ|||1 in the expression (5.1), which
completes the proof.
Connection with fidelity
Consider the semidefinite program from Section 3, for the special case where X = C. Replacing A and
B with vectors u, v ∈ Y ⊗ Z, and making simplifications, the problems become as follows:
Primal problem Dual problem
∗
maximize: hvv ,W i minimize: hTrY (uu∗ ), Zi
subject to: TrY (W ) ≤ TrY (uu∗ ) , subject to: 1Y ⊗ Z ≥ vv∗ ,
W ∈ Pos (Y ⊗ Z) . Z ∈ Pos (Z) .
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 233
J OHN WATROUS
As will be explained shortly, the quantity that is represented by the optimal value of these problems is
given by the fidelity function, which is defined as
√ p q√ √
F(P, Q) = P Q = Tr PQ P
1
for positive semidefinite operators P and Q. In particular, the optimal value (for the primal and dual
problems) is
F (TrY (uu∗ ), TrY (vv∗ ))2 . (5.2)
The fact that the optimal value of the primal problem coincides with the fidelity function as just
described follows from Uhlmann’s theorem [34], which is as follows.
Theorem 5.2 (Uhlmann’s theorem). Let Y and Z be finite-dimensional complex vector spaces, and let
P, Q ∈ Pos (Z) be positive semidefinite operators, both having rank at most dim(Y). Then for any choice
of v ∈ Y ⊗ Z satisfying TrY (vv∗ ) = Q, it holds that
F(P, Q) = max {|hu, vi| : u ∈ Y ⊗ Z, TrY (uu∗ ) = P} .
This theorem provides an alternate characterization of the fidelity function that is useful for establishing
many interesting properties of the fidelity. Among these is the fact that the fidelity is monotonic, meaning
F(P, Q) ≤ F(TrY (P), TrY (Q))
for every choice of P, Q ∈ Pos (X ⊗ Y). It is straightforward to apply this fact back to Uhlmann’s theorem
itself to obtain the following corollary, which is precisely the statement that the optimal primal value of
our semidefinite program is given by the fidelity–squared as claimed.
Corollary 5.3. Assume u, v ∈ Y ⊗ Z are vectors, and let P = TrY (uu∗ ) and Q = TrY (vv∗ ). Then
F(P, Q)2 = max hvv∗ ,W i : W ∈ Pos (Y ⊗ Z) , TrY (W ) ≤ P .
The optimal value of the dual problem is, of course, equal to (5.2) by strong duality. A different way
to evaluate the optimal dual value begins with the following simple proposition.
Proposition 5.4. For any vector v ∈ Y ⊗ Z and any positive definite operator Z ∈ Pd (Z) it holds that
1Y ⊗ Z ≥ vv∗ if and only if TrY (vv∗ ), Z −1 ≤ 1.
Proof. It holds that 1Y ⊗ Z ≥ vv∗ if and only if
1Y ⊗ Z −1/2 vv∗ 1Y ⊗ Z −1/2 ≤ 1Y⊗Z . (5.3)
Given that the operator on the left-hand-side of (5.3) is positive semidefinite and has rank equal to 1, we
have that (5.3) is equivalent to
1Y ⊗ Z −1/2 v ≤ 1 ,
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 234
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
which in turn is equivalent to
Tr 1Y ⊗ Z −1/2 vv∗ 1Y ⊗ Z −1/2 ≤ 1 .
As
Tr 1Y ⊗ Z −1/2 vv∗ 1Y ⊗ Z −1/2 = TrY (vv∗ ), Z −1 ,
the proof is complete.
We have that the optimal value of the dual problem does not change if Z is optimized over only
positive definite rather than positive semidefinite operators (again accepting that the optimal value may
not be achieved for such an operator). Combined with the proposition just proved, we find that the
optimal dual value is given by
β = inf hTrY (uu∗ ), Zi : Z ∈ Pd (Z) , hTrY (vv∗ ), Z −1 i ≤ 1 .
That this value is given by (5.2) follows from a different characterization of the fidelity due to Alberti [3].
Theorem 5.5 (Alberti’s theorem). Let P, Q ∈ Pos (Z) be positive semidefinite operators. Then
(F(P, Q))2 = inf hP, Zi hQ, Z −1 i .
Z∈Pd(Z)
We have therefore established a simple and precise sense in which Uhlmann’s theorem and Alberti’s
theorem are dual statements in finite dimensions, each implying the other.
Acknowledgments
Many of the key ideas presented in this paper are contained in the papers [23] and [18]. I thank Alexei
Kitaev and Gus Gutoski for discussions during and after the collaborations that produced those papers,
which helped to clarify these ideas. I also thank Bill Rosgen, Mary Beth Ruskai, and the anonymous
referees for helpful comments. This research was supported by Canada’s NSERC and the Canadian
Institute for Advanced Research (CIFAR).
References
[1] A. AC ÍN: Statistical distinguishability between unitary operations. Phys. Rev. Lett.,
87(17):177901, 2001. [PRL:10.1103/PhysRevLett.87.177901]. 218
[2] D. A HARONOV, A. K ITAEV, AND N. N ISAN: Quantum circuits with mixed states. In Proc. 30th
STOC, pp. 20–30. ACM Press, 1998. [STOC:10.1145/276698.276708]. 218
[3] P. A LBERTI: A note on the transition probability over C∗ -algebras. Lett. Math. Phys., 7(1):25–32,
1983. [doi:10.1007/BF00398708]. 235
[4] F. A LIZADEH: Interior point methods in semidefinite programming with applications to combina-
torial optimization. SIAM J. Optim., 5(1):13–51, 1995. [SIOPT:10.1137/0805002]. 223, 225
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 235
J OHN WATROUS
[5] A. B EN -A ROYA AND A. TA -S HMA: On the complexity of approximating the diamond norm.
arXiv.org e-Print 0902.3397, 2009. [arXiv:0902.3397]. 218
[6] R. B HATIA: Matrix Analysis. Springer, 1997. 220
[7] S. B OYD AND L. VANDENBERGHE: Convex Optimization. Cambridge University Press, 2004.
223, 224
[8] Y. B UGEAUD: Approximation by Algebraic Numbers, volume 160 of Cambridge Tracts in Mathe-
matics. Cambridge University Press, Cambridge, 2004. 230
[9] A. C HILDS , J. P RESKILL , AND J. R ENES: Quantum information and precision measure-
ment. J. Modern Opt., 47(2–3):155–176, 2000. [doi:10.1080/09500340008244034, arXiv:quant-
ph/9904021]. 218
[10] M.-D. C HOI: Completely positive linear maps on complex matrices. Linear Algebra Appl.,
10(3):285–290, 1975. [Elsevier:10.1016/0024-3795(75)90075-0]. 221
[11] G. D’A RIANO , P. P RESTI , AND M. PARIS: Using entanglement improves the
precision of quantum measurements. Phys. Rev. Lett., 87(27):270404, 2001.
[PRL:10.1103/PhysRevLett.87.270404]. 218
[12] E. DE K LERK: Aspects of Semidefinite Programming – Interior Point Algorithms and Selected
Applications, volume 65 of Applied Optimization. Kluwer Academic Publishers, Dordrecht, 2002.
223, 225
[13] J. DE P ILLIS: Linear transformations which preserve Hermitian and positive semidefinite opera-
tors. Pacific J. Math., 23(1):129–137, 1967. 221
[14] I. D EVETAK , M. J UNGE , C. K ING , AND M. B. RUSKAI: Multiplicativity of completely
bounded p-norms implies a new additivity result. Comm. Math. Phys., 266(1):37–63, 2006.
[doi:10.1007/s00220-006-0034-0]. 218
[15] S. E VEN , A. S ELMAN , AND Y. YACOBI: The complexity of promise problems with applications
to public-key cryptography. Inform. and Control, 61(2):159–173, 1984. [Elsevier:10.1016/S0019-
9958(84)80056-X]. 225
[16] A. G ILCHRIST, N. L ANGFORD , AND M. N IELSEN: Distance measures to compare real and ideal
quantum processes. Phys. Rev. A, 71(6):062310, 2005. [PRA:10.1103/PhysRevA.71.062310]. 217,
218, 223, 231
[17] M. G R ÖTSCHEL , L. L OV ÁSZ , AND A. S CHRIJVER: Geometric Algorithms and Combinatorial
Optimization. Springer–Verlag, second corrected edition, 1993. 225, 226
[18] G. G UTOSKI AND J. WATROUS: Toward a general theory of quantum games. In Proc. 39th STOC,
pp. 565–574. ACM Press, 2007. [STOC:10.1145/1250790.1250873]. 218, 231, 235
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 236
S EMIDEFINITE P ROGRAMS FOR C OMPLETELY B OUNDED N ORMS
[19] A. J EN ČOV Á: A relation between completely bounded norms and conjugate channels. Comm.
Math. Phys., 266(1):65–70, 2006. [doi:10.1007/s00220-006-0035-z]. 218
[20] N. J OHNSTON , D. K RIBS , AND V. PAULSEN: Computing stabilized norms for quantum opera-
tions. Quantum Inf. Comput., 9(1):16–35, 2009. 218
[21] A. K ITAEV: Quantum computations: Algorithms and error correction. Russian Math. Surveys,
52(6):1191–1249, 1997. [doi:10.1070/RM1997v052n06ABEH002155]. 217, 218
[22] A. K ITAEV, A. S HEN , AND M. V YALYI: Classical and Quantum Computation, volume 47 of
Graduate Studies in Mathematics. American Mathematical Society, 2002. 223, 232
[23] A. K ITAEV AND J. WATROUS: Parallelization, amplification, and exponential time simulation
of quantum interactive proof system. In Proc. 32nd STOC, pp. 608–617. ACM Press, 2000.
[STOC:10.1145/335305.335387]. 218, 235
[24] D. K RETSCHMANN , D. S CHLINGEMANN , AND R. W ERNER: A continuity theorem for Stine-
spring’s dilation. J. Funct. Anal., 255(8):1889–1904, 2008. [Elsevier:10.1016/j.jfa.2008.07.023].
223
[25] L. L OV ÁSZ: Semidefinite programs and combinatorial optimization. In Recent Advances in Algo-
rithms and Combinatorics, pp. 137–194. Springer, 2003. 223, 226
[26] V. PAULSEN: Completely Bounded Maps and Operator Algebras. Cambridge Studies in Advanced
Mathematics. Cambridge University Press, 2002. 218, 232
[27] D. P ÉREZ -G ARC ÍA , M. W OLF, C. PALAZUELOS , I. V ILLANUEVA , AND M. J UNGE: Un-
bounded violation of tripartite Bell inequalities. Comm. Math. Phys., 279(2):455–486, 2008.
[doi:10.1007/s00220-008-0418-4]. 218
[28] M. P IANI AND J. WATROUS: All entangled states are useful for channel discrimination. Phys.
Rev. Lett., 102(25):250501, 2009. [PRL:10.1103/PhysRevLett.102.250501]. 218
[29] B. ROSGEN: Distinguishing short quantum computations. In Proc. 25th Intern. Symp. Theor.
Aspects Comput. Sci., pp. 597–608. IBFI Schloss Dagstuhl, 2008. 218
[30] B. ROSGEN AND J. WATROUS: On the hardness of distinguishing mixed-state quantum computa-
tions. In Proc. 20th Ann. Conf. Comput. Complexity, pp. 344–354. IEEE Comp. Soc. Press, 2005.
[CCC:10.1109/CCC.2005.21]. 218, 223
[31] M. S ACCHI: Entanglement can enhance the distinguishability of entanglement-breaking channels.
Phys. Rev. A, 72(1):014305, 2005. [PRA:10.1103/PhysRevA.72.014305]. 218
[32] M. S ACCHI: Optimal discrimination of quantum operations. Phys. Rev. A, 71(6):062340, 2005.
[PRA:10.1103/PhysRevA.71.062340]. 218
[33] R. S MITH: Completely bounded maps between C∗ -algebras. J. London Math. Soc., 2(1):157–166,
1983. [doi:10.1112/jlms/s2-27.1.157]. 222
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 237
J OHN WATROUS
[34] A. U HLMANN: The “transition probability” in the state space of a ∗-algebra. Rep. Math. Phys.,
9(2):273–279, 1976. 234
[35] L. VANDENBERGHE AND S. B OYD: Semidefinite programming. SIAM Rev., 38(1):49–95, 1996.
[SIREV:10.1137/1038003]. 223
[36] J. WATROUS: Notes on super-operator norms induced by Schatten norms. Quantum Inf. Comput.,
5(1):58–68, 2005. 223
[37] J. WATROUS: Distinguishing quantum operations with few Kraus operators. Quantum Inf. Com-
put., 8(9):819–833, 2008. 218
[38] V. Z ARIKIAN: Alternating-projection algorithms for operator-theoretic calculation. Linear Alge-
bra Appl., 419(2–3):710–734, 2006. [Elsevier:10.1016/j.laa.2006.06.012]. 218
AUTHOR
John Watrous
Institute for Quantum Computing and School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada
watrous cs uwateroo ca
http://www.cs.uwaterloo.ca/∼watrous
ABOUT THE AUTHOR
J OHN WATROUS is an Associate Professor in the School of Computer Science at the Univer-
sity of Waterloo, and is a member of the University of Waterloo’s Institute for Quantum
Computing. He received his Ph. D. from the University of Wisconsin – Madison in
1998, under the supervision of Eric Bach.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 217–238 238