The Choi-Jamiolkowski isomorphism is an isomorphism between linear maps from M_n to M_m and operators living in the tensor product space M_n ⊗ M_m. Given any linear map Φ : M_n → M_m, we can define the Choi matrix of Φ to be

It turns out that this association between Φ and C_Φ defines an isomorphism, which has become known as the Choi-Jamiolkowski isomorphism. Because much is already known about linear operators, the Choi-Jamiolkowski isomorphism provides a simple way of studying linear maps on operators — just study the associated linear operators instead. Thus, since there does not seem to be a list compiled anywhere of all of the known associations through this isomorphism, I figure I might as well start one here. I’m planning on this being a two-parter post because there’s a lot to be said.

1. All Linear Maps / All Operators

By the very fact that we’re talking about an isomorphism, it follows that the set of all linear maps from M_n to M_m corresponds to the set of all linear operators in M_n ⊗ M_m. One can then use the singular value decomposition on the Choi matrix of the linear map Φ to see that we can find sets of operators {A_i} and {B_i} such that

To construct the operators A_i and B_i, simply reshape the left singular vectors and right singular vectors of the Choi matrix and multiply the A_i operators by the corresponding singular values. An alternative (and much more mathematically-heavy) method of proving this representation of Φ is to use the Generalized Stinespring Dilation Theorem [1, Theorem 8.4].

2. Hermicity-Preserving Maps / Hermitian Operators

The set of Hermicity-Preserving linear maps (that is, maps Φ such that Φ(X) is Hermitian whenever X is Hermitian) corresponds to the set of Hermitian operators. By using the spectral decomposition theorem on C_Φ and recalling that Hermitian operators have real eigenvalues, it follows that there are real constants {λ_i} such that

Again, the trick is to construct each A_i so that the vectorization of A_i is the i^th eigenvector of C_Φ and λ_i is the corresponding eigenvalue. Because every Hermitian operator can be written as the difference of two positive semidefinite operators, it is a simple corollary that every Hermicity-Preserving Map can be written as the difference of two completely positive linear maps — this will become more clear after Section 4. It is also clear that we can absorb the magnitude of the constant λ_i into the operator A_i, so we can write any Hermicity-preserving linear map in the form above, where each λ_i = ±1.

3. Positive Maps / Block Positive Operators

A linear map Φ is said to be positive if Φ(X) is positive semidefinite whenever X is positive semidefinite. A useful characterization of these maps is still out of reach and is currently a very active area of research in quantum information science and operator theory. The associated operators C_Φ are those that satisfy

In terms of quantum information, these operators are positive on separable states. In the world of operator theory, these operators are usually referred to as block positive operators. As of yet we do not have a quick deterministic method of testing whether or not an operator is block positive (and thus we do not have a quick deterministic way of testing whether or not a linear map is positive).

4. Completely Positive Maps / Positive Semidefinite Operators

The most famous class of linear maps in quantum information science, completely positive maps are maps Φ such that (id_k ⊗ Φ) is a positive map for any natural number k. That is, even if there is an ancillary system of arbitrary dimension, the map still preserves positivity. These maps were characterized in terms of their Choi matrix in the early ’70s [2], and it turns out that Φ is completely positive if and only if C_Φ is positive semidefinite. It follows from the spectral decomposition theorem (much like in Section 2) that Φ can be written as

Again, the A_i operators (which are known as Kraus operators) are obtained by reshaping the eigenvectors of C_Φ. It also follows (and was proved by Choi) that Φ is completely positive if and only if (id_n ⊗ Φ) is positive. Also note that, as there exists an orthonormal basis of eigenvectors of C_Φ, the A_i operators can be constructed so that Tr(A_i^*A_j) = δ_ij, the Kronecker delta. An alternative method of deriving the representation of Φ(X) is to use the Stinespring Dilation Theorem [1, Theorem 4.1] of operator theory.

5. k-Positive Maps / k-Block Positive Operators

Interpolating between the situations of Section 3 and Section 4 are k-positive maps. A map is said to be k-positive if (id_k ⊗ Φ) is a positive map. Thus, complete positivity of a map Φ is equivalent to Φ being k-positive for all natural numbers k, which is equivalent to Φ being n-positive. Positivity of Φ is the same as 1-positivity of Φ. Since we don’t even have effective methods for determining positivity of linear maps, it makes sense that we don’t have effective methods for determining k-positivity of linear maps, so they are still a fairly active area of research. It is known that Φ is k-positive if and only if

Operators of this type are referred to as k-block positive operators, and SR(x) denotes the Schmidt rank of the vector x. Because a vector has Schmidt rank 1 if and only if it is separable, it follows that this condition reduces to the condition that we saw in Section 3 for positive maps in the k = 1 case. Similarly, since all vectors have Schmidt rank less than or equal to n, it follows that Φ is n-positive if and only if C_Φ is positive semidefinite, which we saw in Section 4.

Update [October 23, 2009]: Part II of this post is now online.

References:

1. V. I. Paulsen, Completely Bounded Maps and Operator Algebras, Cambridge Studies in Advanced Mathematics 78, Cambridge University Press, Cambridge, 2003.
2. M.-D. Choi, Completely Positive Linear Maps on Complex Matrices, Lin. Alg. Appl, 285-290 (1975).

It’s time for a random dose of statistics courtesy of The Internet Movie Database. Let’s consider all movies that have been released theatrically over the last 60 years and see whether there is a trend in their perceived quality over time. That is, do new movies generally receive higher or lower scores on IMDb than old movies?

Before looking at the numbers though, we need some rules to clarify what types of movies we are considering:

• We only consider theatrically-released films — no straight-to-video movies or TV movies.
• Short films that were released theatrically (such as Pixar’s Presto) are included.
• We only consider movies that have received 1000 or more votes. This restriction is to prevent movies with only a handful of votes from skewing the results too much.
• The theatrical release date of the movie must have been at least as recent at 1950.

IMDb contains 10034 movies that satisfy the above criteria. The average score (on a scale of 1 to 10) of those movies is 6.38 and the median score is 6.6. The average score per release year is given by the following graph:

As you can see, older movies (1950 – 1975) have abnormally high scores, as do very recent movies (2000 – 2009). These differences are indeed statistically significant. For example, the p-value associated with the test that the mean score in 1950 is the same as the mean score in 1989 is less than 10^-19. The p-value associated with the test that the mean score in 2008 is the same as the mean score in 1989 is about 0.0021. Other nearby years give similar p-values.

So this tells us that, in general, particularly old movies receive the highest scores, followed by newly-released movies, followed by “semi-old” movies from the 1980’s and 1990’s. So why the differences? Were movies from the 1980’s really just that bad? Possibly, but the more likely explanation is that movies from the 1950’s  through 1970’s have artificially higher scores because people don’t generally go back and watch the crummy movies of the last generation, so they get forgotten and do not have 1000 votes on IMDb. Will people be watching Disaster Movie in forty years? I sure hope not.

On the other hand, particularly recent movies tend to draw a fair amount of hype and fanboyism. Remember when The Dark Knight had a score of 9.8 and was at #1 on the IMDb top 250? Now, one year later, it has a score of 8.9 and is located at #9 on the top 250. It will likely dwindle a little further down over the coming years as well.

The Best and Worst of Each Year

While we’re looking at ratings of movies over the years, I suppose I might as well provide a list of the best and worst movie of each year (based on the votes of IMDb users), since such a list is not available on the IMDb website itself to my knowledge. Keep in mind that, as before, only movies with 1000 or more votes are considered. Enjoy!

Downloads:

• IMDb rating data [.zip of an Excel spreadsheet — 341KB]
• IMDb rating data [tab-delimited plaintext — 0.97MB]

In [1], a family of matrix norms (called Schmidt norms) are studied and some of their uses in quantum information theory are explored. The interested reader is of course welcome to read the results presented in that paper, but for the more casual reader I present here one very crucial preliminary, the Schmidt decomposition theorem, and a proof that the Schmidt norms actually are (as their name suggests) norms.

Schmidt Decomposition Theorem

The Schmidt decomposition theorem says that any complex vector v ∈ Cⁿ ⊗ Cⁿ can be written as

where k ≤ n, {α_j} ⊆ R is a family of non-negative real scalars, and {e_j}, {f_j} ⊆ Cⁿ are two orthonormal sets of vectors. I won’t prove the theorem here — a proof can be found on its Wikipedia page (it’s basically the singular value decomposition in disguise). For our purposes the most important thing to realize is that, for some vectors v, we can write v in its Schmidt decomposition with k < n. The least k such that v can be written in the form above is called the Schmidt rank of v, and we denote it by SR(v). Every vector v has SR(v) ≤ n.

Schmidt Matrix Norms

The Schmidt k-norm of a matrix X ∈ M_n is defined to be

That might look like a horribly complex definition upon first glance, but it’s not so hard to get your head around when you realize that the Schmidt k-norm for k = n is simply the standard operator norm of X. It is clear then that the Schmidt k-norm for k < n must be a smaller quantity. Indeed, from a quantum information perspective, the norm measures how much the operator represented by X can stretch pure states that “aren’t very entangled.” The interested reader can learn about the various properties and applications of these norms in [1] — what I present here is simply a proof that the Schmidt k-norm is indeed a norm (since this is not explicitly done in the paper).

Proof that the Schmidt k-norm is a norm. It is clear from the definition that the absolute value of a constant pulls out of the Schmidt norms and that the Schmidt norms satisfy the triangle inequality. The only challenging property of the norm to verify is that the Schmidt norm of X being zero implies X = 0.

To prove this, assume that we are in the k = 1 case (if we can show that this property holds for k = 1, it immediately follows that the same property must hold for k > 1). Then recall that we can write X as the sum of elementary tensors, so we can write

Furthermore, we may write X in this way using matrices B_j that are linearly independent (see, for example, Proposition 24 of [2], or simply note that you could choose them to be a family of matrix units). Thus, if the Schmidt 1-norm of X equals zero, then it follows that for any v₁, v₂, w₁, and w₂:

Since this holds for any v₂ and w₂, it follows that

Because we chose the B_j matrices to be linearly independent, it follows that c_j = 0 for all j. By referring back to the definition of c_j, we see that this then implies A_j = 0 for all j, so X = 0 as desired. QED.

References:

1. N. Johnston and D. W. Kribs, A family of norms with applications in quantum information theory. Journal of Mathematical Physics 51, 082202 (2010). arXiv:0909.3907 [quant-ph]
2. Johnston, N., Kribs, D. W., and Paulsen, V., Computing stabilized norms for quantum operations. Quantum Information & Computation 9 1 & 2, 16-35 (2009). arXiv:0711.3636v1 [quant-ph]

In quantum information theory, semidefinite programs are often useful, as one is often interested in the behaviour of linear maps over convex sets. For example, they have very recently been used to compute the completely bounded norm of a linear map [1], prove that QIP = PSPACE [2], and bound a new family of norms of operators [3]. However, if you were to look at the standard form of a semidefinite program provided on the Wikipedia page linked above, you would likely only see some very superficial connections with the standard form of quantum semidefinite programs in references [1-3] — this post aims to bridge that gap and show that the two forms are indeed equivalent (or at the very least outline the key steps in proving they are equivalent).

The “Quantum” Form

Let M_n denote the space of n×n complex matrices. Assume that we are given Hermitian matrices A = A^* ∈ M_n and B = B^* ∈ M_m, as well as a Hermicity-preserving linear map Φ : M_n → M_m (i.e., a map such that Φ(X) is Hermitian whenever X is Hermitian). Then we can define a “quantum” semidefinite program to be the following pair of optimization problems:

In the dual problem, Φ^† refers to the dual map of Phi — that is, the adjoint map in the sense of the Hilbert-Schmidt inner product. It is not surprising that many problems in quantum information theory can be formulated as an optimization problem of this type — completely positive maps (a special class of Hermicity-preserving maps) model quantum channels, positive semidefinite matrices represent quantum states, and the trace of a product of two positive semidefinite matrices represents an expectation value.

The Standard Form

In the more conventional set up of semidefinite programming, we are given matrices D and {G_i} ∈ M_r and a complex vector c ∈ C^s. The associated semidefinite program is given by the following pair of optimization problems:

The interested reader should read on Wikipedia about how semidefinite programs generalize linear programs and how their theory of duality works. It is also important to note that semidefinite programs can be solved efficiently to any desired accuracy by a variety of different solvers, using a number of different algorithms. Thus, once we show that quantum semidefinite programs can be put into this standard form, we will be able to efficiently solve quantum semidefinite programs.

Converting the Quantum Form to the Standard Form

Define a linear map Ψ : M_n → (M_m ⊕ M_n) by

Then the requirement that Ψ(P) ≤ B and P ≥ 0 is equivalent to

The dual map Ψ^† is given by

By putting these last few steps together, we see that our original quantum semidefinite program is of the following form:

The inequality in the dual problem was able to be replaced by equality because of the flexibility that was introduced by the arbitrary positive operator R. Now let {E_a} and {F_a} be families of left and right generalized Choi-Kraus operators for Ψ. Denote the (k,l)-entry of P by p_kl and the (i,j)-entry of E_a or F_a by e_aij or f_aij, respectively. Then

where

Finally, defining x := vec(P) and c := vec(A) (where vec refers to the vectorization of a matrix, which stacks each of its columns on top of each other into a column vector) shows that the quantum primal problem is in the form of the standard primal problem. Some simple linear algebra can be used to show that the quantum dual form reduces to the standard dual form as well.

Downloads:

• QuantumSDP.pdf — PDF version of this blog post

References:

1. J. Watrous, Semidefinite programs for completely bounded norms. Preprint (2009). arXiv:0901.4709 [quant-ph]
2. R. Jain, Z. Ji, S. Upadhyay, J. Watrous, QIP = PSPACE. Preprint (2009). arXiv:0907.4737 [quant-ph]
3. N. Johnston and D. W. Kribs, A family of norms with applications in quantum information theory. Journal of Mathematical Physics 51, 082202 (2010). arXiv:0909.3907 [quant-ph]

One of the things that has bothered me severely with the status of Conway’s Game of Life on the internet (and the main reason that I started the LifeWiki) is the severe fragmentation of information about the game — there are tidbits of knowledge sprinkled all over the place, but it’s quite a task to find a complete collection of patterns of a specific type unless you already know where to look. Fortunately, this fragmentation problem just got knocked around quite a bit by the release of Golly 2.1.

Golly is an open-source, cross-platform application for exploring Conway’s Game of Life (and it is probably currently the most widely-used such program). Version 2.1 was just released this week, and it’s a particularly exciting update from my point of view because it introduces a feature that has been long-needed in the Game of Life world — access to online pattern collections.

The pattern collections that Golly 2.1 can access by default are as follows:

• The LifeWiki pattern archive
• David Eppstein’s database of gliders in Life-like cellular automata
• Alan Hensel’s pattern collections
• Jason Summers’ pattern collections

Additionally, Golly can directly download rules from the cellular automata Rule Table Repository and scripts from the Golly Scripts Database. So now all the interested Lifer has to do to find out about (for example) period 51 oscillators is open up the LifeWiki pattern archive, select “oscillators”, and either load a relevant pattern or click on the help link beside it to bring up the corresponding page at LifeWiki. Take that, fragmentation of information.

Anyway, other changes have of course been made for the new release of Golly as well — a complete list can be found here. Or just go right ahead and…

Download Golly

About once a year, the internet news fills up for a week or so with talk of how a new largest-known prime has just been found. This largest-known prime has invariably been found by GIMPS, a distributed computing project designed to find large Mersenne primes.  Of course, mainstream media doesn’t like reporting things unless they can give people the illusion of some sort of immediate practical purpose. So what to do when you can’t think of a practical use for some recently-discovered 10-million-digit prime numbers? Make one up, of course! Just say that they have applications in cryptography:

Scientists in the US and Germany have found the two largest prime numbers ever calculated in a discovery which could dramatically increase the effectiveness of cryptographic systems.

– v3.co.uk

The Source of the Myth: RSA Encryption

Like all good myths, the Mersenne prime cryptography myth is so widespread because it is so close to being true. The most widely-used form of encryption used on the internet is RSA encryption, which works by multiplying two huge prime numbers together to form an even larger number with exactly two prime factors. Since factoring numbers is believed to be computationally difficult, reversing this process is currently a very difficult problem, which leads to RSA providing reasonably strong encryption. The thing is, RSA typically uses primes that have a few hundred digits, not a few million digits. Some of the reasons for this are as follows:

1. You don’t need to use million-digit primes. Considering that even cracking RSA that uses 250-digit primes is an extremely difficult problem that hasn’t been completed yet, and the problem gets exponentially more difficult as you add more digits, even the most paranoid of people should be comfortable using primes with a couple thousand digits. You might argue that some big government agencies would want RSA to be as secure as possible for their transactions, so they might want to use million-digit primes, but any agency that is that worried about security shouldn’t be using public key cryptography in the first place.
2. Using primes with millions of digits actually decreases security. As of this writing, there are 26 known primes with more than one million digits, so to break RSA encryption that makes use of primes with millions of digits you can just test each one of the known million-digit primes to see if they are one of the factors. RSA only works because there are lots of primes with hundreds of digits to choose from (as in billions of billions of billions of them, and then some).
3. Manipulating numbers with millions of digits is slow. Internet-based public key cryptography systems need to be fast if they’re to be of any practical use, so it doesn’t make much sense to try to use a cryptography system that relies on multiplying and finding residues with numbers that take several megabytes just to store. Just imagine trying to do some online banking when you have to transmit this number along with every other piece of data that you send back to the server.

Not all media outlets are so bad as to directly say that the primes found by GIMPS are useful for cryptography, but the vast majority of them imply it at some point throughout the story. Consider the following examples, which are taken from stories about newly-discovered GIMPS primes:

Mersenne primes are important for the theory of numbers and they may help in developing unbreakable codes and message encryptions.

– BBC News

Current cryptographic systems rely on the challenge of factoring large primes.

– ScienceNews.org

While those tidbits of information are quite true (well, almost — see the comments), when taken in context they are entirely misleading and cause the reader to think that GIMPS primes have applications in today’s cryptography systems. It’s like running a story about a recent plane crash that includes a sentence about how it’s a good idea to wear a helmet when riding a bicycle.

So Why Do We Search for Huge Primes?

The main reason that we search for huge primes is simply for sport. It gives our idle CPU cycles something to do. Non-mathematicians seem to balk at that idea and call it a huge waste of CPU cycles/time, and they’re probably right, but so what? Have you ever played a video game? This is our version of going for a high score. If that doesn’t seem like a particularly good reason to you, perhaps one of the reasons given by GIMPS itself will satisfy you. One thing that you’ll notice though is that cryptography is not mentioned anywhere on that page.