P ≠ NP?

I don't have much to say on this one yet, but it's too important to stay silent on. Someone is claiming to have proved that P ≠ NP, which wouldn't be new but for the fact that the claimant is actually a credible computer scientist, such that Stephen Cook is saying it may be a correct proof. Since not everyone here is a complexity-head, let me spell out the significance of that: Cook was one of the people behind the Cook-Levin Theorem, which established the existence of NP-complete problems. Without Cook, then, the P vs. NP problem would be much less relevant, so his opinion on the matter should carry no small amount of weight. Of course, this is a science, so that can't be the last word-- hence the question mark in the title. It'll be interesting to see what light the morning brings to this one.

Many others have written on the issue, including: R. J. Lipton, Dave Bacon and Joe Fitzsimmons.

What are the complex numbers?

Now that we have ideas about states and probabilities under our belt, we're ready to build up yet another step towards understanding what a quantum state is: the complex numbers.

First, as is typical for me, I'd like to go off on a tangent. In mathematics, we often consider sets of some kind of object, such as the integers (which we write as ℤ) or the real numbers, written as ℝ. We can then add operations on these sets, such as addition and multiplication. A very useful property for a set to have with respect to an operation is that of closure, by which we mean that an operation doesn't take you outside of a set. For example, if you add any two integers, you get another integer, and so ℤ is said to be closed under addition. Similarly, ℤ is closed under multiplication and subtraction. Where it breaks down, however, is when we consider division; the specific counter-example of ⅔ shows that not all integers can be divided to produce another integer. For that, we must take a step back to the rational numbers, written ℚ. The rational numbers can be taken as the set of numbers produced by dividing integers with each other (except zero, for which we must always make an exception). One can then show by direct calculation that if you divide two rational numbers (that is, two fractions), you get another rational number, and so ℚ is closed under division.

Where, then, do numbers like come into the picture? One can prove that (that is, that there is no way of writing as a fraction), and yet the number comes up in a very natural way from looking at polynomial functions of integers, which we write as ℤ[x]. When we study such functions, we are very often interested in the roots of polynomials, since they tell us quite a lot about how such functions behave. For instance, consider f(x) = x² - 1. We can obviously factor this as f(x) = (x - 1)(x + 1), which gives us by the zero factor theorem that f(x) = 0 has two solutions at x = ±1. Notice that if we have n factors of the form (x - a), we obtain a term like xⁿ from multiplying all of the xs together, and so we should expect that a polynomial of degree n (that is, whose largest power of x is xⁿ) will have n roots. This fails if we restrict ourselves, however, to ℤ, since the function g(x) = x² - 2 has roots , which are not integers or even rationals. The solution, then, is to broaden our perspective to all real numbers, written ℝ.

This idea of including roots of polynomials is related to, but not precisely the same as, the concept of closure. It is often useful to consider sets of numbers such that all polynomials must have roots from within that set. We still, however, cannot say that ℝ has this property. Consider the polynomial x² + 1 as a counter example. Obviously, , but what does mean? As is customary in mathematics, we can generalize our notion of a square root by defining a new number i such that . We shall call this number the imaginary unit, as it has some surprising properties that we may not expect out of real numbers. The set of all complex numbers, that is, numbers that are a sum of a real and an imaginary part, such as z = a + ib, is written as ℂ. It turns out that this set does in fact include all of its polynomial roots, while still remaining closed under all the typical operations, indicating that in some sense, ℂ is large enough to encapsulate all of our typical arithmetic. Any set smaller than ℂ will not be expressive enough to capture all of the arithmetic operations we might wish to perform in our study of quantum states.

While a post on all the wondrous properties of ℂ would be far beyond my modest goal for the afternoon, one property in particular is too wonderful to go unmentioned. When we define the imaginary unit i, we also define how our typical arithmetic carries over, so that (a + ib) + (c + id) = (a + c) + i(b + d) doesn't surprise us. This does not, however, let us immediately make sense of expressions like for some real number θ. For that, we must use a mathematical tool such as power series to extend our typical definition of to include complex exponents. When we do so, we obtain a beautiful formula which serves to define what means:

Notice that this allows us to relate complex numbers to angles in a simple and straightforward way. One immediate consequence of this definition is that complex numbers tell us about rotations, whereas real numbers tell us about scales. Since , the "size" of (which we can define formally as |a + ib|² = a² + b²) is always one. This property shall be very useful to us in considering quantum mechanics and information, where we shall interpret complex rotations as a phase between two wavefunctions.

For now, though, I shall leave off this brief introduction to complex numbers, having (hopefully) demonstrated both a bit of their utility and of their beauty. Until next time!