Archive

Posts Tagged ‘Matrix Analysis’

In Search of a 4-by-11 Matrix

October 1st, 2013

IMPORTANT UPDATE [January 30, 2014]: I have managed to solve the 4-by-11 case: there is no such matrix! Details of the computation that led to this result, as well as several other related results, are given in [4]. See Table 3 in that paper for an updated list of which cases still remain open (the smallest open cases are now 5-by-11 and 6-by-10).


After spinning my wheels on a problem for far too long, I’ve decided that it’s time to enlist the help of the mathematical and programming geniuses of the world wide web. The problem I’m interested in asks for a 4-by-11 matrix whose columns satisfy certain relationships. While the conditions are relatively easy to state, the problem size seems to be just slightly too large for me to solve myself.

The Problem

The question I’m interested in (for reasons that are explained later in this blog post) is, given positive integers p and s, whether or not there exists a p-by-s matrix M with the following three properties:

  1. Every entry of M is a nonzero integer;
  2. The sum of any two columns of M contains a 0 entry; and
  3. There is no way to append a (s+1)th column to M so that M still has property 2.

In particular, I’m interested in whether or not such a matrix M exists when p = 4 and s = 11. But to help illustrate the above three properties, let’s consider the p = 3, s = 4 case first, where one such matrix M is:

M = \begin{bmatrix}1 & -1 & 2 & -2 \\ 1 & -2 & -1 & 2 \\ 1 & 2 & -2 & -1\end{bmatrix}.

The fact that M satisfies condition 2 can be checked by hand easily enough. For example, the sum of the first two columns of M is [0, -1, 3]T which contains a 0 entry, and it is similarly straightforward to check that the other 5 sums of two columns of M each contain a 0 entry as well.

Checking property 3 is slightly more technical (NP-hard, even), but is still doable in small cases such as this one. For the above example, suppose that we could add a 5th column (which we will call z = [z1, z2, z3]T) to M such that its sum with any of the first 4 columns has a 0 entry. By looking at M’s first column, we see that one of z’s entries must be -1 (and by the cyclic symmetry of the entries of the last 3 columns of M, we can assume without loss of generality that z1 = -1). By looking at the last 3 columns of M, we then see that either z2 = 2 or z3 = -2, either z2 = 1 or z3 = 2, and either z2 = -2 or z3 = 1. Since there is no way to simultaneously satisfy all 3 of these requirements, no such column z exists.

What’s Known (and What Isn’t)

As I mentioned earlier, the instance of this problem that I’m really interested in is when p = 4 and s = 11. Let’s first back up and briefly discuss what is known for different values of p and s:

  • If s ≤ p then M does not exist. To see this, simply note that property 3 can never be satisfied since you can always append one more column. If we denote the (i,j)-entry of M by mij and the i-th entry of the new column z by zi, then you can choose zi = -mii for i = 1, 2, …, s.
  • Given p, the smallest value of s for which M exists is: (a) s = p+1 if p is odd, (b) s = p+2 if p = 4 or p ≡ 2 (mod 4), (c) s = p+3 if p = 8, and (d) s = p+4 otherwise. This result was proved in [1] (the connection between that paper and this blog post will be explained in the “Motivation” section below).
  • If s > 2p then M does not exist. In this case, there is no way to satisfy property 2. This fact is trivial when p = 1 and can be proved for all p by induction (an exercise left to the reader?).
  • If s = 2p then M exists. To see this claim, let the columns of M be the 2p different columns consisting only of the entries 1 and -1. To see that property 2 is satisfied, simply notice that each column is different, so for any pair of columns, there is a row in which one column is 1 and the other column is -1. To see that property 3 is satisfied, observe that any new column must also consist entirely of 1′s and -1′s. However, every such column is already a column of M itself, and the sum of a column with itself will not have any 0 entries.
  • If s = 2p – 4 (and p ≥ 3) then M exists. There is an inductive construction (with the p = 3, s = 4 example from the previous section as the base case) that works here. More specifically, if we let Mp denote a matrix M that works for a given value of p and s = 2p – 4, we let Bp be the matrix from the s = 2p case above, and 1k denotes the row vector with k ones, then
    M_{p+1} = \begin{bmatrix}M_p & B_p \\ 1_{2^p-4} & -1_{2^p}\end{bmatrix}

    is a solution to the problem for p’ = p+1 and s’ = 2p+1 – 4.
  • If 2p – 3 ≤ s ≤ 2p – 1 then M does not exist. This is a non-trivial result that follows from [2].

Given p, the above results essentially tell us the largest and smallest values of s for which a solution M to the problem exists. However, we still don’t really know much about when solutions exist for intermediate values of s – we just have scattered results that say a solution does or does not exist in certain specific cases, without really illuminating what is going on. The following table summarizes what we know about when solutions do and do not exist for small values of p and s (a check mark ✓ means that a solution exists, a dash - means no solution exists, and ? means we don’t know).

s \ p 1 2 3 4 5
1 - - - - -
2 - - - -
3 - - - - -
4 - - -
5 - - - - -
6 - - -
7 - - - -
8 - -
9 - - - ?
10 - - - ?
11 - - - ? ?
12 - - -
13 - - - -
14 - - - -
15 - - - -
16 - - -
17 – 26 - - - -
27 - - - - ?
28 - - - -
29 - - - - -
30 - - - - -
31 - - - - -
32 - - - -

The table above shows why I am interested in the p = 4, s = 11 case: it is the only case when p ≤ 4 whose solution still is not known. The other unknown cases (i.e., p = 5 and s ∈ {9,10,11,27}, and far too many to list when p ≥ 6) would be interesting to solve as well, but are a bit lower-priority.

Some Simplifications

Some assumptions about the matrix M can be made without loss of generality, in order to reduce the search space a little bit. For example, since the values of the entries of M don’t really matter (other than the fact that they come in positive/negative pairs), the first column of M can always be chosen to consist entirely of ones (or any other value). Similarly, permuting the rows or columns of M does not affect whether or not it satisfies the three desired properties, so you can assume (for example) that the first row is in non-decreasing order.

Finally, since there is no advantage to having the integer k present in M unless -k is also present somewhere in M (i.e., if M does not contain any -k entries, you could always just replace every instance of k by 1 without affecting any of the three properties we want), we can assume that the entries of M are between -floor(s/2) and floor(s/2), inclusive.

Motivation

The given problem arises from unextendible product bases (UPBs) in quantum information theory. A set of pure quantum states |v_1\rangle, \ldots, |v_s\rangle \in \mathbb{C}^{d_1} \otimes \cdots \otimes \mathbb{C}^{d_p} forms a UPB if and only if the following three properties hold:

  1. (product) Each state |v_j\rangle is a product state (i.e., can be written in the form |v_j\rangle = |v_j^{(1)}\rangle \otimes \cdots \otimes |v_j^{(p)}\rangle, where |v_j^{(i)}\rangle \in \mathbb{C}^{d_i} for all i);
  2. (basis) The states are mutually orthogonal (i.e., \langle v_i | v_j \rangle = 0 for all i ≠ j); and
  3. (unextendible) There does not exist a product state |z\rangle with the property that \langle z | v_j \rangle = 0 for all j.

UPBs are useful because they can be used to construct quantum states with very strange entanglement properties [3], but their mathematical structure still isn’t very well-understood. While we can’t really expect an answer to the question of what sizes of UPBs are possible when the local dimensions d_1, \ldots, d_p are arbitrary (even just the minimum size of a UPB is still not known in full generality!), we might be able to hope for an answer if we focus on multi-qubit systems (i.e., the case when d_1 = \cdots = d_p = 2).

In this case, the 3 properties above are isomorphic in a sense to the 3 properties listed at the start of this post. We associate each state |v_j\rangle with the j-th column of the matrix M. To each state in the product state decomposition of |v_j\rangle, we associate a unique integer in such a way that orthogonal states are associated with negatives of each other. The fact that \langle v_i | v_j \rangle = 0 for all i ≠ j is then equivalent to the requirement that te sum of any two columns of M has a 0 entry, and unextendibility of the product basis corresponds to not being able to add a new column to M without destroying property 2.

Thus this blog post is really asking whether or not there exists an 11-state UPB on 4 qubits. In order to illustrate this connection more explicitly, we return to the p = 3, s = 4 example from earlier. If we associate the matrix entries 1 and -1 with the orthogonal standard basis states |0\rangle, |1\rangle \in \mathbb{C}^2 and the entries 2 and -2 with the orthogonal states |\pm\rangle := (|0\rangle \pm |1\rangle)/\sqrt{2}, then the matrix M corresponds to the following set of s = 4 product states in \mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2:

|0\rangle|0\rangle|0\rangle, \quad |1\rangle|-\rangle|+\rangle, \quad |+\rangle|1\rangle|-\rangle, \quad|-\rangle|+\rangle|1\rangle.

The fact that these states form a UPB is well-known – this is the “Shifts” UPB from [3], and was one of the first UPBs found.

References

  1. N. Johnston. The minimum size of qubit unextendible product bases. In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2013. E-print: arXiv:1302.1604 [quant-ph], 2013.
  2. L. Chen and D. Ž. Ðjoković. Separability problem for multipartite states of rank at most four. J. Phys. A: Math. Theor., 46:275304, 2013. E-print: arXiv:1301.2372 [quant-ph]
  3. C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, and B. M. Terhal. Unextendible product bases and bound entanglement. Phys. Rev. Lett., 82:5385–5388, 1999. E-print: arXiv:quant-ph/9808030
  4. N. Johnston. The structure of qubit unextendible product bases. E-print: arXiv:1401.7920 [quant-ph], 2014.

Separability-Preserving Operators in Entanglement Theory

June 14th, 2011

One of the key concepts in quantum information theory is the difference between separable states and entangled states. A pure quantum state (that is, a unit vector) v ∈ CnCn is said to be separable if it can be written as v = a ⊗ b for some a,b ∈ Cn; otherwise v is called entangled. In this post we will investigate what operators preserve the set of separable pure states, as well as what operators entangle all separable pure states.

Separable Pure State Preservers and Entangling Gates

In the design of quantum algorithms, entangling gates play a very important role. Entangling gates are unitary operators that are able to generate entanglement. A bit more specifically, a unitary operator U ∈ Mn ⊗ Mn (where Mn is the space of n × n complex matrices) is called an entangling gate if there exists a separable pure state v = a ⊗ b ∈ CnCn such that Uv is entangled. Conversely, we will say that a unitary operator U preserves separability if Uv is separable whenever v is separable.

In order to answer the question of what unitaries preserve separability, it is instructive to consider some simple examples (this is often a useful way to formulate conjectures regarding preserver problems). For example, it is clear that if U = A ⊗ B for some unitary operators A, B ∈ Mn, then U preserves separability (because U(a ⊗ b) = Aa ⊗ Bb is separable). Another example of a unitary operator that preserves separability is the swap (or flip) operator S defined on separable states by S(a ⊗ b) = b ⊗ a (the action of S on the rest of CnCn is determined by extending linearly). It turns out that these are essentially the only operators that preserve separability [1,2,3]:

Theorem 1. Let U ∈ Mn ⊗ Mn be a unitary operator. Then U preserves separability (i.e., U is not an entangling gate) if and only if there exist unitary operators A, B ∈ Mn such that either U = A ⊗ B or U = S(A ⊗ B).

As we already saw, the “if” direction of the above result is trivial – the meat and potatoes of the theorem comes from the “only if” direction (as is typically the case with results about linear preservers). Theorem 1 was first proved in [1] essentially by case analysis and checking the action of a separability-preserving unitary on a basis of CnCn, and was subsequently re-proved using similar techniques (but with different motivations and connections) in [2]. The result was proved in [3] by using the vector-operator isomorphism and the fact that a linear map Φ : Mn → Mn preserves the set of rank-1 operators if and only if there exist A, B ∈ Mn such that either Φ(X) ≡ AXB or Φ(X) ≡ AXtB [4].

Theorem 1 also follows as a simple corollary of several related results that have recently been proved in [5,6]. A version of Theorem 1 for multipartite systems (i.e., systems that are the tensor product of more than two copies of Cn) can be found in [3] and [7].

Universal Entangling Gates

A universal entangling gate is, as its name suggests, a stronger form of an entangling gate – it is a unitary operator U such that U(a ⊗ b) is entangled for all a, b ∈ Cn (contrast this with entangling gates, which require only that U(a ⊗ b) is entangled for some a, b ∈ Cn). The structure of universal entangling gates is much less well-understood than that of entangling gates, though we can still at least say when they exist.

It is not difficult to convince yourself that universal entangling gates can’t exist in small dimensions. Let’s begin by supposing n = 2. The set of pure states in C2C2 can be regarded as a 7-dimensional real manifold (7 = 2 × (n × n) – 1, where we subtract one because pure states all have unit length), while the set of separable pure states in C2C2 can be regarded as a 5-dimensional real manifold (5 = (2 × n – 1) + (2 × n – 1) – 1, where the final one is subtracted because the overall phase of the first system relative to the second system is irrelevant). Thus, if U ∈ M2 ⊗ M2 were a universal entangler, it would have to send a 5-dimensional manifold into the 7 – 5 = 2 remaining dimensions of the space, which seems unlikely. Similarly, if n = 3 and U ∈ M3 ⊗ M3 were a universal entangler, it would have to send a 9-dimensional manifold into the 17 – 9 = 8 remaining dimensions of the space, which also seems unlikely.

Indeed, this type of argument was made rigorous via methods of algebraic geometry in [8], where the following result was proved:

Theorem 2. There exists a universal entangling gate in Mn ⊗ Mn if and only if n ≥ 4.

Despite knowing when universal entangling gates exist, we still don’t have a characterization of such operators, nor do we even have many explicit examples (does anyone have an explicit example for 3 ⊗ 4 or 4 ⊗ 4 systems?). Similar techniques to those used in the proof of Theorem 2 should also shed light on when universal entangling gates exist in multipartite systems Mn1 ⊗ Mn2 ⊗ … ⊗ Mnk, but to my knowledge this calculation has not been explicitly carried out.

References:

  1. M. Marcus and B. N. Moyls, Transformations on tensor product spaces. Pacific Journal of Mathematics 9, 1215–1221 (1959).
  2. F. Hulpke, U. V. Poulsen, A. Sanpera, A. Sen De, U. Sen, and M. Lewenstein, Unitarity as preservation of entropy and entanglement in quantum systems. Foundations of Physics 36, 477–499 (2006). E-print: arXiv:quant-ph/0407118
  3. N. Johnston, Characterizing Operations Preserving Separability Measures via Linear Preserver Problems. To appear in Linear and Multilinear Algebra (2011). E-print: arXiv:1008.3633 [quant-ph]
  4. L. Beasley, Linear operators on matrices: the invariance of rank k matrices. Linear Algebra and its Applications 107, 161–167 (1988).
  5. E. Alfsen and F. Shultz, Unique decompositions, faces, and automorphisms of separable states. Journal of Mathematical Physics 51, 052201 (2010). E-print: arXiv:0906.1761 [math.OA]
  6. S. Friedland, C.-K. Li, Y.-T. Poon, and N.-S. Sze, The automorphism group of separable states in quantum information theory. Journal of Mathematical Physics 52, 042203 (2011). E-print: arXiv:1012.4221 [quant-ph]
  7. R. Westwick, Transformations on tensor spaces. Pacific Journal of Mathematics 23, 613–620 (1967).
  8. J. Chen, R. Duan, Z. Ji, M. Ying, J. Yu, Existence of Universal Entangler. Journal of Mathematical Physics 49, 012103 (2008). E-print: arXiv:0704.1473 [quant-ph]

Isometries of Unitarily-Invariant Complex Matrix Norms

August 15th, 2010

Recall that a unitarily-invariant matrix norm is a norm on matrices X ∈ Mn such that

One nice way to think about unitarily-invariant norms is that they are the matrix norms that depend only on the matrix’s singular values. Some unitarily-invariant norms that are particularly well-known are the operator (spectral) norm, trace norm, Frobenius (Hilbert-Schmidt) norm, Ky Fan norms, and Schatten p-norms (in fact, I would say that the induced p-norms for p ≠ 2 are the only really common matrix norms that aren’t unitarily-invariant – I will consider these norms in the future).

The core question that I am going to consider today is what linear maps preserve singular values and unitarily-invariant matrix norms. Clearly multiplication on the left and right by unitary matrices preserve such norms (by definition). However, the matrix transpose also preserves singular values and all unitarily-invariant norms – are there other linear maps on complex matrices that preserve these norms? For a more thorough treatment of this question, the interested reader is directed to [1,2].

Linear Maps That Preserve Singular Values

We first consider the simplest of the above questions: what linear maps Φ : Mn → Mn are such that the singular values of Φ(X) are the same as the singular values of X for all X ∈ Mn? In order to answer this question, recall Theorem 1 from my previous post, which states [3] that if Φ is an invertible map such that Φ(X) is nonsingular whenever X is nonsingular, then there exist M, N ∈ Mn with det(MN) ≠ 0 such that

In order to make use of this result, we will first have to show that any singular-value-preserving map is invertible and sends nonsingular matrices to nonsingular matrices. To this end, notice (recall?) that the operator norm of a matrix is equal to its largest singular value. Thus, any map that preserves singular values must be an isometry of the operator norm, and thus must be invertible (since all isometries are easily seen to be invertible).

Furthermore,  if we use the singular value decomposition to write X = USV for some unitaries U, V ∈ Mn and a diagonal matrix of singular values S ∈ Mn, then det(X) = det(USV) = det(U)det(S)det(V) = det(UV)det(S). Because UV is unitary, we know that |det(UV)| = 1, so we have |det(X)| = |det(S)| = det(S); that is, the product of the singular values of X equals the absolute value of its determinant. So any map that preserves singular values also preserves the absolute value of the matrix determinant. But any map that preserves the absolute value of determinants must preserve the set of nonsingular matrices because X is nonsingular if and only if det(X) ≠ 0. It follows from the above result about invertibility-preserving maps that if Φ preserves singular values then there exist M, N ∈ Mn with det(MN) ≠ 0 such that either Φ(X) = MXN or Φ(X) = MXTN.

We will now prove that M and N must each in fact be unitary. To this end, pick any unit vector x ∈ Cn and let c denote the Euclidean length of Mx:

By the fact that Φ must preserve singular values (and hence the operator norm) we have that if y ∈ Cn is any other unit vector, then

Because y was an arbitrary unit vector, we have that N* = (1/c)U, where U ∈ Mn is some unitary matrix. It can now be similarly argued that M = cV for some unitary matrix V ∈ Mn. By simply adjusting constants, we have proved the following:

Theorem 1. Let Φ : Mn → Mn be a linear map. Then the singular values of Φ(X) equal the singular values of X for all X ∈ Mn if and only if there exist unitary matrices U, V ∈ Mn such that

Isometries of the Frobenius Norm

We now consider the problem of characterizing isometries of the Frobenius norm defined for X ∈ Mn by

That is, we want to describe the maps Φ that preserve the Frobenius norm. It is clear that the Frobenius norm of X is just the Euclidean norm of vec(X), the vectorization of X. Thus we know immediately from the standard isomorphism that sends operators to bipartite vectors and super operators to bipartite operators that Φ preserves the Frobenius norm if and only if there exist families of operators {Ai}, {Bi} such that Σi Ai ⊗ Bi is a unitary matrix and

It is clear that any map of the form described by Theorem 1 above can be written in this form, but there are also many other maps of this type that are not of the form described by Theorem 1. In the next section we will see that the Frobenius norm is essentially the only unitarily-invariant complex matrix norm containing isometries that are not of the form described by Theorem 1.

Isometries of Other Unitarily-Invariant Norms

One way of thinking about Theorem 1 is as providing a canonical form for any map Φ that preserves all unitarily-invariant norms. However, in many cases it is enough that Φ preserves a single unitarily-invariant norm for it to be of that form. For example, it was shown by Schur in 1925 [4] that if Φ preserves the operator norm then it must be of the form described by Theorem 1. The same result was proved for the trace norm by Russo in 1969 [5]. Li and Tsing extended the same result to the remaining Schatten p-norms, Ky Fan norms, and (p,k)-norms in 1988 [6].

In fact, the following result, which completely characterizes isometries of all unitarily-invariant complex matrix norms other than the Frobenius norm, was obtained in [7]:

Theorem 2. Let Φ : Mn → Mn be a linear map. Then Φ preserves a given unitarily-invariant norm that is not a multiple of the Frobenius norm if and only if there exist unitary matrices U, V ∈ Mn such that

References:

  1. C.-K. Li and S. Pierce, Linear preserver problems. The American Mathematical Monthly 108, 591–605 (2001).
  2. C.-K. Li, Some aspects of the theory of norms. Linear Algebra and its Applications 212213, 71–100 (1994).
  3. J. Dieudonne, Sur une generalisation du groupe orthogonal a quatre variables. Arch. Math. 1, 282–287 (1949).
  4. I. Schur, Einige bemerkungen zur determinanten theorie. Sitzungsber. Preuss. Akad. Wiss. Berlin 25, 454–463 (1925).
  5. B. Russo, Trace preserving mappings of matrix algebra. Duke Math. J. 36, 297–300 (1969).
  6. C.-K. Li and N.-K. Tsing, Some isometries of rectangular complex matrices. Linear and Multilinear Algebra 23, 47–53 (1988).
  7. C.-K. Li and N.-K. Tsing, Linear operators preserving unitarily invariant norms of matrices. Linear and Multilinear Algebra 26, 119–132 (1990).

An Introduction to Linear Preserver Problems

August 5th, 2010

The theory of linear preserver problems deals with characterizing linear (complex) matrix-valued maps that preserve certain properties of the matrices they act on. For example, some of the most famous linear preserver problems ask what a map must look like if it preserves invertibility or the determinant of matrices. Today I will focus on introducing some of the basic linear preserver problems that got the field off the ground – in the near future I will explore linear preserver problems dealing with various families of norms and linear preserver problems that are actively used today in quantum information theory. In the meantime, the interested reader can find a more thorough introduction to common linear preserver problems in [1,2].

Suppose Φ : Mn → Mn (where Mn is the set of n×n complex matrices) is a linear map. It is well-known that any such map can be written in the form

where {Ai}, {Bi} ⊂ Mn are families of matrices (sometimes referred to as the left and right generalized Choi-Kraus operators of Φ (phew!)). But what if we make the additional restrictions that Φ is an invertible map and Φ(X) is nonsingular whenever X ∈ Mn is nonsingular? The problem of characterizing maps of this type (which are sometimes called invertibility-preserving maps) is one of the first linear preserver problems that was solved, and it turns out that if Φ is invertibility-preserving then either Φ or T ○ Φ (where T represents the matrix transpose map) can be written with just a single pair of Choi-Kraus operators:

Theorem 1. [3] Let Φ : Mn → Mn be an invertible linear map. Then Φ(X) is nonsingular whenever X ∈ Mn is nonsingular if and only if there exist M, N ∈ Mn with det(MN) ≠ 0 such that

In addition to being interesting in its own right, Theorem 1 serves as a starting point that allows for the simple derivation of several related results.

Determinant-Preserving Maps

For example, suppose Φ is a linear map such that det(Φ(X)) = det(X) for all X ∈ Mn. We will now find the form that maps of this type (called determinant-preserving maps) have using Theorem 1. In order to use Theorem 1 though, we must first show that Φ is invertible.

We prove that Φ is invertible by contradiction. Suppose there exists X ≠ 0 such that Φ(X) = 0. Then because Φ preserves determinants, it must be the case that X is singular. Then there exists a singular Y ∈ Mn such that X + Y is nonsingular. It follows that 0 ≠ det(X + Y) = det(Φ(X + Y)) = det(0 + Φ(Y)) = det(Y) = 0, a contradiction. Thus it must be the case that X = 0 and so Φ is invertible.

Furthermore, any map that preserves determinants must preserve the set of nonsingular matrices because X is nonsingular if and only if det(X) ≠ 0. It follows from Theorem 1 that for any determinant-preserving map Φ there must exist M, N ∈ Mn with det(MN) ≠ 0 such that either Φ(X) = MXN or Φ(X) = MXTN. However, in this case we have det(X) = det(Φ(X)) = det(MXN) = det(MN)det(X) for all X ∈ Mn, so det(MN) = 1. Conversely, it is not difficult (an exercise left to the interested reader) to show that any map of this form with det(MN) = 1 must be determinant-preserving. What we have proved is the following result, originally due to Frobenius [4]:

Theorem 2. Let Φ : Mn → Mn be a linear map. Then det(Φ(X)) = det(X) for all X ∈ Mn if and only if there exist M, N ∈ Mn with det(MN) = 1 such that

Spectrum-Preserving Maps

The final linear preserver problem that we will consider right now is the problem of characterizing linear maps Φ such that the eigenvalues (counting multiplicities) of Φ(X) are the same as the eigenvalues of X for all X ∈ Mn (such maps are sometimes called spectrum-preserving maps). Certainly any map that is spectrum-preserving must also be determinant-preserving (since the determinant of a matrix is just the product of its eigenvalues), so by Theorem 2 there exist M, N ∈ Mn with det(MN) = 1 such that either Φ(X) = MXN or Φ(X) = MXTN.

Now note that any map that preserves eigenvalues must also preserve trace (since the trace is just the sum of the matrix’s eigenvalues) and so we have Tr(X) = Tr(Φ(X)) = Tr(MXN) = Tr(NMX) for all X ∈ Mn. This implies that Tr((I – NM)X) = 0 for all X ∈ Mn, so we have NM = I (i.e., M = N-1). Conversely, it is simple (another exercise left for the interested reader) to show that any map of this form with M = N-1 must be spectrum-preserving. What we have proved is the following characterization of maps that preserve eigenvalues:

Theorem 3. Let Φ : Mn → Mn be a linear map. Then Φ is spectrum-preserving if and only if det(Φ(X)) = det(X) and Tr(Φ(X)) = Tr(X) for all X ∈ Mn if and only if there exists a nonsingular N ∈ Mn such that

References:

  1. C. K. Li, S. Pierce, Linear preserver problems. The American Mathematical Monthly 108, 591–605 (2001).
  2. C. K. Li, N. K. Tsing, Linear preserver problems: A brief introduction and some special techniques. Linear Algebra and its Applications 162164, 217–235 (1992).
  3. J. Dieudonne, Sur une generalisation du groupe orthogonal a quatre variables. Arch. Math. 1,
    282–287 (1949).
  4. G. Frobenius, Uber die Darstellung der endlichen Gruppen durch Linear Substitutionen. Sitzungsber
    Deutsch. Akad. Wiss. Berlin 994–1015 (1897).

The Other Superoperator Isomorphism

November 20th, 2009

A few months ago, I spent two posts describing the Choi-Jamiolkowski isomorphism between linear operators from Mn to Mm (often referred to as “superoperators“) and linear operators living in the space Mn ⊗ Mm. However, there is another isomorphism between superoperators and regular operators — one that I’m not sure of any name for but which has just as many interesting properties.

Recall from Section 1 of this post that any superoperator Φ can be written as

\Phi(X)=\sum_iA_iXB_i.for some operators {Ai} and {Bi}. The isomorphism that I am going to focus on in this post is the one given by associating Φ with the operator

M_\Phi:=\sum_iA_i\otimes B_i^{T}.

The main reason that MΦ can be so useful is that it retains the operator structure of Φ. In particular, if you define vec(X) to be the vectorization of the operator X, then

{\rm vec}(\Phi(X))=M_\Phi{\rm vec}(X).

In other words, if you treat X as a vector, then MΦ is the operator describing the action of Φ on X. From this it becomes simple to compute some basic quantities describing Φ. For example, the induced Frobenius norm,

\big\|\Phi\big\|_F:=\sup_{\|X\|_F=1}\Big\{\big\|\Phi(X)\big\|_F\Big\},

is equal to the standard operator norm of MΦ. If n = m then we can define the eigenvalues {λ} and the eigenmatrices {V} of Φ in the obvious way via

\Phi(V)=\lambda V.

Then the eigenvalues of Φ are exactly the eigenvalues of MΦ, and the corresponding eigenvectors of MΦ are the vectorizations of the eigenmatrices of Φ. It is similarly easy to check whether Φ is invertible (by checking whether or not det(MΦ) = 0), find the inverse if it exists, or find the nullspace (and a pseudoinverse) if it doesn’t.

Finally, here’s a question for the interested reader to think about: why is the transpose required on the Bi operators for this isomorphism to make sense? That is, why can we not define an isomorphism between Φ and the operator

\sum_iA_i\otimes B_i?

The Equivalences of the Choi-Jamiolkowski Isomorphism (Part II)

October 23rd, 2009

This is a continuation of this post.
Please read that post to learn what the Choi-Jamiolkowski isomorphism is.

In part 1, we learned about hermicity-preserving linear maps, positive maps, k-positive maps, and completely positive maps. Now let’s see what other types of linear maps have interesting equivalences through the Choi-Jamiolkowski isomorphism. Recall that the notation CΦ is used to represent the Choi matrix of the linear map Φ.

6. Entanglement Breaking Maps / Separable Quantum States

An entanglement breaking map is defined as a completely positive map Φ with the property that (idn ⊗ Φ)(ρ) is a separable quantum state whenever ρ is a quantum state (i.e., a density operator). A separable quantum state σ is one that can be written in the form

\sigma=\sum_ip_i\sigma_i\otimes\tau_i,

where {pi} forms a probability distribution (i.e., pi ≥ 0 for all i and the pi‘s sum to 1) and each σi and τi is a density operator. It turns out that the Choi-Jamiolkowski equivalence for entanglement-breaking maps is very natural — Φ is entanglement breaking if and only if CΦ is separable. Because it is known that determining whether or not a given state is separable is NP-HARD [1], it follows that determining whether or not a given linear map is entanglement breaking is also NP-HARD. Nonetheless, there are several nice characterizations of entanglement breaking maps. For example, Φ is entanglement breaking if and only if it can be written in the form

\Phi(X)=\sum_iA_iXA_i^*,

where each operator Ai has rank 1 (recall from Section 4 of the previous post that every completely positive map can be written in this form for some operators Ai — the rank 1 condition is what makes the map entanglement breaking). For more properties of entanglement breaking maps, the interested reader is encouraged to read [2].

7. k-Partially Entanglement Breaking Maps / Quantum States with Schmidt Number at Most k

The natural generalization of entanglement breaking maps are k-partially entanglement breaking maps, which are completely positive maps Φ with the property that (idn ⊗ Φ)(ρ) always has Schmidt number [3] at most k for any density operator ρ. Recall that an operator has Schmidt number 1 if and only if it is separable, so the k = 1 case recovers exactly the entanglement breaking maps of Section 6. The set of operators associated with the k-partially entanglement breaking maps via the Choi-Jamiolkowski isomorphism are exactly what we would expect: the operators with Schmidt number no larger than k. In fact, pretty much all of the properties of entanglement breaking maps generalize in a completely natural way to this situation. For example, a map is k-partially entanglement breaking if and only if it can be written in the form

\Phi(X)=\sum_iA_iXA_i^*,

where each operator Ai has rank no greater than k. For more information about k-partially entanglement breaking maps, the interested reader is pointed to [4]. Additionally, there is an interesting geometric relationship between k-positive maps (see Section 5 of the previous post) and k-partially entanglement breaking maps that is explored in this note and in [5].

8. Unital Maps / Operators with Left Partial Trace Equal to Identity

A linear map Φ is said to be unital if it sends the identity operator to the identity operator — that is, if Φ(In) = Im. It is a simple exercise in linear algebra to show that Φ is unital if and only if

{\rm Tr}_1(C_\Phi)=I_m,

where Tr1 denotes the partial trace over the first subsystem. In fact, it is not difficult to show that Tr1(CΦ) always equals exactly Φ(In).

9. Trace-Preserving Maps / Operators with Right Partial Trace Equal to Identity

In quantum information theory, maps that are trace-preserving (i.e., maps Φ such that Tr(Φ(X)) = Tr(X) for every operator X ∈ Mn) are of particular interest because quantum channels are modeled by completely positive trace-preserving maps (see Section 4 of the previous post to learn about completely positive maps). Well, some simple linear algebra shows that the map Φ is trace-preserving if and only if

{\rm Tr}_2(C_\Phi)=I_n,

where Tr2 denotes the partial trace over the second subsystem. The reason for the close relationship between this property and the property of Section 8 is that unital maps and trace-preserving maps are dual to each other in the Hilbert-Schmidt inner product.

10. Completely Co-Positive Maps / Positive Partial Transpose Operators

A map Φ such that T○Φ is completely positive, where T represents the transpose map, is called a completely co-positive map. Thanks to Section 4 of the previous post, we know that Φ is completely co-positive if and only if the Choi matrix of T○Φ is positive semi-definite. Another way of saying this is that

(id_n\otimes T)(C_\Phi)\geq 0.

This condition says that the operator CΦ has positive partial transpose (or PPT), a property that is of great interest in quantum information theory because of its connection with the problem of determining whether or not a given quantum state is separable. In particular, any quantum state that is separable must have positive partial transpose (a condition that has become known as the Peres-Horodecki criterion). If n = 2 and m ≤ 3, then the converse is also true: any PPT state is necessarily separable [6]. It follows via our equivalences of Sections 4 and 6 that any entanglement breaking map is necessarily completely co-positive. Conversely, if n = 2 and m ≤ 3 then any map that is both completely positive and completely co-positive must be entanglement breaking.

11. Entanglement Binding Maps / Bound Entangled States

A bound entangled state is a state that is entangled (i.e., not separable) yet can not be transformed via local operations and classical communication to a pure maximally entangled state. In other words, they are entangled but have zero distillable entanglement. Currently, the only states that are known to be bound entangled are states with positive partial transpose — it is an open question whether or not other such states exist.

An entanglement binding map [7] is a completely positive map Φ such that (idn ⊗ Φ)(ρ) is bound entangled for any quantum state ρ. It turns out that a map is entanglement binding if and only if its Choi matrix CΦ is bound entangled. Thus, via the result of Section 10 we see that a map is entanglement binding if it is both completely positive and completely co-positive. It is currently unknown if there exist other entanglement binding maps.

References:

  1. L. Gurvits, Classical deterministic complexity of Edmonds’ Problem and quantum entanglement, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 10-19 (2003). arXiv:quant-ph/0303055v1
  2. M. Horodecki, P. W. Shor, M. B. Ruskai, General Entanglement Breaking Channels, Rev. Math. Phys 15, 629–641 (2003). arXiv:quant-ph/0302031v2
  3. B. Terhal, P. Horodecki, A Schmidt number for density matrices, Phys. Rev. A Rapid Communications Vol. 61, 040301 (2000). arXiv:quant-ph/9911117v4
  4. D. Chruscinski, A. Kossakowski, On partially entanglement breaking channels, Open Sys. Information Dyn. 13, 17–26 (2006). arXiv:quant-ph/0511244v1
  5. L. Skowronek, E. Stormer, K. Zyczkowski, Cones of positive maps and their duality relations, J. Math. Phys. 50, 062106 (2009). arXiv:0902.4877v1 [quant-ph]
  6. M. Horodecki, P. Horodecki, R. Horodecki, Separability of Mixed States: Necessary and Sufficient Conditions, Physics Letters A 223, 1–8 (1996). arXiv:quant-ph/9605038v2
  7. P. Horodecki, M. Horodecki, R. Horodecki, Binding entanglement channels, J.Mod.Opt. 47, 347–354 (2000). arXiv:quant-ph/9904092v1