WIXLIB

2Mathematical preliminariesincluding Σ, Γ, and Λ, while lower case Roman letters near the beginningof the alphabet, including a, b, c, and d, will be used to denote symbolsin alphabets. Examples of alphabets include the binary alphabet {0, 1}, then-fold Cartesian product {0, 1}n of the binary alphabet with itself, and thealphabet {1, . . . , n}, for n being a fixed positive integer.For any alphabet Σ, one denotes by CΣ the set of all functions from Σto the complex numbers C. The set CΣ forms a vector space of dimension Σ over the complex numbers when addition and scalar multiplication aredefined in the following standard way:1. Addition: for vectors u, v CΣ , the vector u v CΣ is defined by theequation (u v)(a) u(a) v(a) for all a Σ.2. Scalar multiplication: for a vector u CΣ and a scalar α C, the vectorαu CΣ is defined by the equation (αu)(a) αu(a) for all a Σ.A vector space defined in this way will be called a complex Euclidean space.1The value u(a) is referred to as the entry of u indexed by a, for each u CΣand a Σ. The vector whose entries are all zero is simply denoted 0.Complex Euclidean spaces will be denoted by scripted capital letters nearthe end of the alphabet, such as W, X , Y, and Z. Subsets of these spaceswill also be denoted by scripted letters, and when possible this book willfollow a convention to use letters such as A, B, and C near the beginning ofthe alphabet when these subsets are not necessarily vector spaces. Vectorswill be denoted by lowercase Roman letters, again near the end of thealphabet, such as u, v, w, x, y, and z.When n is a positive integer, one typically writes Cn rather than C{1,.,n} ,and it is also typical that one views a vector u Cn as an n-tuple of theform u (α1 , . . . , αn ), or as a column vector of the form α1 . u . ,(1.1)αnfor complex numbers α1 , . . . , αn .For an arbitrary alphabet Σ, the complex Euclidean space CΣ may beviewed as being equivalent to Cn for n Σ ; one simply fixes a bijectionf : {1, . . . , n} Σ(1.2)and associates each vector u CΣ with the vector in Cn whose k-th entry1Many quantum information theorists prefer to use the term Hilbert space. The term complexEuclidean space will be preferred in this book, however, as the term Hilbert space refers to amore general notion that allows the possibility of infinite index sets.

31.1 Linear algebrais u(f (k)), for each k {1, . . . , n}. This may be done implicitly when thereis a natural or obviously preferred choice for the bijection f . For example,the elements of the alphabet Σ {0, 1}2 are naturally ordered 00, 01, 10,11. Each vector u CΣ may therefore be associated with the 4-tuple(u(00), u(01), u(10), u(11)),or with the column vector (1.3)u(00) u(01) , u(10) (1.4)u(11)when it is convenient to do this. While little or no generality would belost in restricting one’s attention to complex Euclidean spaces of the formCn for this reason, it is both natural and convenient within computationaland information-theoretic settings to allow complex Euclidean spaces to beindexed by arbitrary alphabets.Inner products and norms of vectorsThe inner product hu, vi of two vectors u, v CΣ is defined ashu, vi Xu(a) v(a).(1.5)a ΣIt may be verified that the inner product satisfies the following properties:1. Linearity in the second argument:hu, αv βwi αhu, vi βhu, wi(1.6)hu, vi hv, ui(1.7)hu, ui 0(1.8)for all u, v, w CΣ and α, β C.2. Conjugate symmetry:for all u, v CΣ .3. Positive definiteness:for all u CΣ , with equality if and only if u 0.It is typical that any function satisfying these three properties is referred toas an inner product, but this is the only inner product for vectors in complexEuclidean spaces that is considered in this book.

4Mathematical preliminariesThe Euclidean norm of a vector u CΣ is defined askuk qhu, ui sX u(a) 2 .(1.9)a ΣThe Euclidean norm possesses the following properties, which define themore general notion of a norm:1. Positive definiteness: kuk 0 for all u CΣ , with kuk 0 if and only ifu 0.2. Positive scalability: kαuk α kuk for all u CΣ and α C.3. The triangle inequality: ku vk kuk kvk for all u, v CΣ .The Cauchy–Schwarz inequality states that hu, vi kuk kvk(1.10)for all u, v CΣ , with equality if and only if u and v are linearly dependent.The collection of all unit vectors in a complex Euclidean space X is calledthe unit sphere in that space, and is denoted S(X ) u X : kuk 1 .(1.11)The Euclidean norm represents the case p 2 of the class of p-norms,defined for each u CΣ askukp for p , andXa Σ u(a) p! p1 kuk max u(a) : a Σ .(1.12)(1.13)The above three norm properties (positive definiteness, positive scalability,and the triangle inequality) hold for k·k replaced by k·kp for any choice ofp [1, ].Orthogonality and orthonormalityTwo vectors u, v CΣ are said to be orthogonal if hu, vi 0. The notationu v is also used to indicate that u and v are orthogonal. More generally,for any set A CΣ , the notation u A indicates that hu, vi 0 for allvectors v A.A collection of vectors{ua : a Γ} CΣ ,(1.14)indexed by an alphabet Γ, is said to be an orthogonal set if it holds that

1.1 Linear algebra5hua , ub i 0 for all choices of a, b Γ with a 6 b. A collection of nonzeroorthogonal vectors is necessarily linearly independent.An orthogonal set of unit vectors is called an orthonormal set, and whensuch a set forms a basis it is called an orthonormal basis. It holds that anorthonormal set of the form (1.14) is an orthonormal basis of CΣ if and onlyif Γ Σ . The standard basis of CΣ is the orthonormal basis given by{ea : a Σ}, whereea (b) for all a, b Σ. 1 0if a bif a 6 b(1.15)Direct sums of complex Euclidean spacesThe direct sum of n complex Euclidean spaces X1 CΣ1 , . . . , Xn CΣn isthe complex Euclidean spaceX1 · · · Xn CΣ1 t ··· t Σn ,(1.16)where Σ1 t · · · t Σn denotes the disjoint union of the alphabets Σ1 , . . . , Σn ,defined asΣ1 t · · · t Σn [ k {1,.,n}(k, a) : a Σk .(1.17)For vectors u1 X1 , . . . , un Xn , the notation u1 · · · un X1 · · · Xnrefers to the vector for which(u1 · · · un )(k, a) uk (a),(1.18)for each k {1, . . . , n} and a Σk . If each uk is viewed as a column vectorof dimension Σk , the vector u1 · · · un may be viewed as a column vector u1 . . . (1.19)unhaving dimension Σ1 · · · Σn .Every element of the space X1 · · · Xn can be written as u1 · · · unfor a unique choice of vectors u1 , . . . , un . The following identities hold for

6Mathematical preliminariesevery choice of u1 , v1 X1 , . . . , un , vn Xn , and α C:u1 · · · un v1 · · · vn (u1 v1 ) · · · (un vn ),(1.20)hu1 · · · un , v1 · · · vn i hu1 , v1 i · · · hun , vn i.(1.22)α(u1 · · · un ) (αu1 ) · · · (αun ),(1.21)Tensor products of complex Euclidean spacesThe tensor product of n complex Euclidean spaces X1 CΣ1 , . . . , Xn CΣnis the complex Euclidean spaceX1 · · · Xn CΣ1 ··· Σn .(1.23)For vectors u1 X1 , . . . , un Xn , the notation u1 · · · un X1 · · · Xnrefers to the vector for which(u1 · · · un )(a1 , . . . , an ) u1 (a1 ) · · · un (an ).(1.24)Vectors of the form u1 · · · un are called elementary tensors. They span thespace X1 · · · Xn , but not every element of X1 · · · Xn is an elementarytensor.The following identities hold for all vectors u1 , v1 X1 , . . . , un , vn Xn ,scalars α, β C, and indices k {1, . . . , n}:u1 · · · uk 1 (αuk βvk ) uk 1 · · · un α (u1 · · · uk 1 uk uk 1 · · · un )(1.25)hu1 · · · un , v1 · · · vn i hu1 , v1 i · · · hun , vn i.(1.26) β (u1 · · · uk 1 vk uk 1 · · · un ),Tensor products are often defined in a way that is more abstract (and moregenerally applicable) than the definition above, which is sometimes knownmore specifically as the Kronecker product. The following proposition is areflection of the more abstract definition.Proposition 1.1letLet X1 , . . . , Xn and Y be complex Euclidean spaces andφ : X1 · · · Xn Y(1.27)be a multilinear function, meaning a function for which the mappinguk 7 φ(u1 , . . . , un )(1.28)

1.1 Linear algebra7is linear for all k {1, . . . , n} and every fixed choice of vectors u1 , . . . , uk 1 ,uk 1 , . . . , un . There exists a unique linear mappingsuch thatA : X1 · · · Xn Y(1.29)φ(u1 , . . . , un ) A(u1 · · · un )(1.30)for all choices of u1 X1 , . . . , un Xn .If X is a complex Euclidean space, u X is a vector, and n is a positiveinteger, then the notations X n and u n refer to the n-fold tensor productof either X or u with itself. It is often convenient to make the identificationX n X1 · · · Xn ,(1.31)under the assumption that X1 , . . . , Xn and X all refer to the same complexEuclidean space; this allows one to refer to the different tensor factors inX n individually, and to express X1 · · · Xn more concisely.Remark A rigid interpretation of the definitions above suggests that tensorproducts of complex Euclidean spaces (or of vectors in complex Euclideanspaces) are not associative, insofar as Cartesian products are not associative.For instance, given alphabets Σ, Γ, and Λ, the alphabet (Σ Γ) Λ containselements of the form ((a, b), c), the alphabet Σ (Γ Λ) contains elementsof the form (a, (b, c)), and the alphabet Σ Γ Λ contains elements of theform (a, b, c), for a Σ, b Γ, and c Λ. For X CΣ , Y CΓ , andZ CΛ , one may therefore view the complex Euclidean spaces (X Y) Z,X (Y Z), and X Y Z as being different.However, the alphabets (Σ Γ) Λ, Σ (Γ Λ), and Σ Γ Λ canof course be viewed as equivalent by simply removing parentheses. For thisreason, there is a natural equivalence between the complex Euclidean spaces(X Y) Z, X (Y Z), and X Y Z. Whenever it is convenient,identifications of this sort are made implicitly throughout this book. Forexample, given vectors u X Y and v Z, the vector u v may betreated as an element of X Y Z rather than (X Y) Z.Although such instances are much less common in this book, a similarconvention applies to direct sums of complex Euclidean spaces.Real Euclidean spacesReal Euclidean spaces are defined in a similar way to complex Euclideanspaces, except that the field of complex numbers C is replaced by the fieldof real numbers R in each of the definitions and concepts in which it arises.

8Mathematical preliminariesNaturally, complex conjugation acts trivially in the real case, and thereforemay be omitted.Complex Euclidean spaces will play a more prominent role than real onesin this book. Real Euclidean spaces will, nevertheless, be important in thosesettings that make use of concepts from the theory of convexity. The spaceof Hermitian operators acting on a given complex Euclidean space is animportant example of a real vector space that can be identified with a realEuclidean space, as is discussed in the subsection following this one.1.1.2 Linear operatorsGiven complex Euclidean spaces X and Y, one writes L(X , Y) to refer tothe collection of all linear mappings of the formA : X Y.(1.32)Such mappings will be referred to as linear operators, or simply operators,from X to Y in this book. Parentheses are omitted when expressing theaction of linear operators on vectors when no confusion arises in doing so.For instance, one writes Au rather than A(u) to denote the vector resultingfrom the application of an operator A L(X , Y) to a vector u X .The set L(X , Y) forms a complex vector space when addition and scalarmultiplication are defined as follows:1. Addition: for operators A, B L(X , Y), the operator A B L(X , Y)is defined by the equation(A B)u Au Bu(1.33)for all u X .2. Scalar multiplication: for an operator A L(X , Y) and a scalar α C,the operator αA L(X , Y) is defined by the equation(αA)u αAu(1.34)for all u X .Matrices and their correspondence with operatorsA matrix over the complex numbers is a mapping of the formM :Γ Σ C(1.35)for alphabets Σ and Γ. For a Γ and b Σ the value M (a, b) is called the(a, b) entry of M , and the elements a and b are referred to as indices in this

1.1 Linear algebra9context: a is the row index and b is the column index of the entry M (a, b).Addition and scalar multiplication of matrices are defined in a similar wayto vectors in complex Euclidean spaces:1. Addition: for matrices M : Γ Σ C and N : Γ Σ C, the matrixM N is defined as(M N )(a, b) M (a, b) N (a, b)(1.36)for all a Γ and b Σ.2. Scalar multiplication: for a matrix M : Γ Σ C and a scalar α C,the matrix αM is defined as(αM )(a, b) αM (a, b)(1.37)for all a Γ and b Σ.In addition, one defines matrix multiplication as follows:3. Matrix multiplication: for matrices M : Γ Λ C and N : Λ Σ C,the matrix M N : Γ Σ C is defined as(M N )(a, b) XM (a, c)N (c, b)(1.38)c Λfor all a Γ and b Σ.For any choice of complex Euclidean spaces X CΣ and Y CΓ , there isa bijective linear correspondence between the set of operators L(X , Y) andthe collection of all matrices taking the form M : Γ Σ C that is obtainedas follows. With each operator A L(X , Y), one associates the matrix Mdefined asM (a, b) hea , Aeb i(1.39)for a Γ and b Σ. The operator A is uniquely determined by M , and maybe recovered from M by the equation(Au)(a) XM (a, b)u(b)(1.40)b Σfor all a Γ. With respect to this correspondence, matrix multiplication isequivalent to operator composition.Hereafter in this book, linear operators will be associated with matricesimplicitly, without the introduction of names that distinguish matrices fromthe operators with which they are associated. With this in mind, the notationA(a, b) hea , Aeb i(1.41)

10Mathematical preliminariesis introduced for each A L(X , Y), a Γ, and b Σ (where it is to beassumed that X CΣ and Y CΓ , as above).The standard basis of a space of operatorsFor every choice of complex Euclidean spaces X CΣ and Y CΓ , andeach choice of symbols a Γ and b Σ, the operator Ea,b L(X , Y) isdefined asEa,b u u(b)ea(1.42)for every u X . Equivalently, Ea,b is defined by the equationEa,b (c, d) 1 0if (c, d) (a, b)otherwise(1.43)holding for all c Γ and d Σ. The collection{Ea,b : a Γ, b Σ}(1.44)forms a basis of L(X , Y) known as the standard basis of this space. Thenumber of elements in this basis is, of course, consistent with the fact thatthe dimension of L(X , Y) is given by dim(L(X , Y)) dim(X ) dim(Y).The entry-wise conjugate, transpose, and adjointFor every operator A L(X , Y), for complex Euclidean spaces X CΣ andY CΓ , one defines three additional operators,A L(X , Y)andAT , A L(Y, X ),(1.45)as follows:1. The operator A L(X , Y) is the operator whose matrix representationhas entries that are complex conjugates to the matrix representation of A:A(a, b) A(a, b)(1.46)for all a Γ and b Σ.2. The operator AT L(Y, X ) is the operator whose matrix representationis obtained by transposing the matrix representation of A:AT (b, a) A(a, b)for all a Γ and b Σ.(1.47)

111.1 Linear algebra3. The operator A L(Y, X ) is the uniquely determined operator thatsatisfies the equationhv, Aui hA v, ui(1.48)A AT .(1.49)for all u X and v Y. It may be obtained by performing both of theoperations described in items 1 and 2:The operators A, AT , and A are called the entry-wise conjugate, transpose,and adjoint operators to A, respectively.The mappings A 7 A and A 7 A are conjugate linear and A 7 AT islinear:αA βB α A β B,(αA βB) αA βB ,(αA βB)T αAT βB T ,for all A, B L(X , Y) and α, β C. These mappings are bijections, eachbeing its own inverse.Each vector u X in a complex Euclidean space X may be identified withthe linear operator in L(C, X ) defined as α 7 αu for all α C. Throughthis identification, the linear mappings u L(C, X ) and uT , u L(X , C) aredefined as above. As an element of X , the vector u is simply the entry-wisecomplex conjugate of u, i.e., if X CΣ thenu(a) u(a)(1.50)for every a Σ. For each vector u X the mapping u L(X , C) satisfiesu v hu, vi for all v X .Kernel, image, and rankThe kernel of an operator A L(X , Y) is the subspace of X defined asker(A) {u X : Au 0},(1.51)im(A) {Au : u X }.(1.52)while the image of A is the subspace of Y defined asFor every operator A L(X , Y), one has thatker(A) ker(A A)andim(A) im(AA ),(1.53)as well as the equationdim(ker(A)) dim(im(A)) dim(X ).(1.54)

12Mathematical preliminariesThe rank of an operator A L(X , Y), denoted rank(A), is the dimension ofthe image of A:rank(A) dim(im(A)).(1.55)By (1.53) and (1.54), one may conclude thatrank(A) rank(AA ) rank(A A)(1.56)for every A L(X , Y).For any choice of vectors u X and v Y, the operator vu L(X , Y)satisfies(vu )w v(u w) hu, wiv(1.57)for all w X . Assuming that u and v are nonzero, the operator vu hasrank equal to one, and every rank one operator in L(X , Y) can be expressedin this form for vectors u and v that are unique up to scalar multiples.Operators involving direct sums of complex Euclidean spacesSuppose thatX1 CΣ1 , . . . , Xn CΣnandY1 CΓ1 , . . . , Ym CΓm(1.58)are complex Euclidean spaces, for alphabets Σ1 , . . . , Σn and Γ1 , . . . , Γm . Fora given operatorA L(X1 · · · Xn , Y1 · · · Ym ),(1.59)Aj,k L(Xk , Yj ) : 1 j m, 1 k n(1.60)there exists a unique collection of operators for which the equation Aj,k (a, b) A (j, a), (k, b)(1.61)holds for all j {1, . . . , m}, k {1, . . . , n}, a Γj , and b Σk . For allvectors u1 X1 , . . . , un Xn , one has thatA(u1 · · · un ) v1 · · · vm(1.62)for v1 Y1 , . . . , vm Ym being defined asvj nXAj,k uk(1.63)k 1for each j {1, . . . , m}. Conversely, for any collection of operators of theform (1.60), there is a unique operator A of the form (1.59) that obeys theequations (1.62) and (1.63) for all vectors u1 X1 , . . . , un Xn .

131.1 Linear algebraThere is therefore a bijective correspondence between operators of theform (1.59) and collections of operators of the form (1.60). With respect tothe matrix representations of these operators, this correspondence may beexpressed succinctly as A1,1 .A .Am,1 · · · A1,n. . . .· · · Am,n(1.64)One interprets the right-hand side of (1.64) as the specification of theoperator having the form (1.59) that is defined by the collection (1.60) inthis way.Tensor products of operatorsSuppose thatX1 CΣ1 , . . . , Xn CΣnandY1 CΓ 1 , . . . , Yn CΓ n(1.65)are complex Euclidean spaces, for alphabets Σ1 , . . . , Σn and Γ1 , . . . , Γn . Forany choice of operatorsA1 L(X1 , Y1 ), . . . , An L(Xn , Yn ),(1.66)one defines the tensor productA1 · · · An L(X1 · · · Xn , Y1 · · · Yn )(1.67)of these operators to be the unique operator that satisfies the equation(A1 · · · An

2 Basic notions of quantum information 58 2.1 Registers and states 58 2.1.1 Registers and classical state sets 58 2.1.2 Quantum states of registers 61 2.1.3 Reductions and puri cations of quantum states 67 2.2 Quantum channels 72 2.2.1 De nitions and basic notions concerning channels 72 2.2.2 Representations and characterizations of channels 77