Since, my remarks in the last post about classical computational complexity got me into such hot water with those who are much smarter than I am, I thought I’d post another of the less often expressed reasons for studying quantum computation from my notes:
It is often remarked upon by mathematicians and physicists that there is a mysterious harmony between these two disciplines. Indeed both fields have benefitted immensely from each other. The same can not be said, I think, for computer science. A good question to ask is why this is true? One idea floating around in research land is that the reason for the lack of such deep connections has been that this is because the wrong model of computation has been studied. It makes sense that if the universe obeys the laws of quantum theory, then we shouldn’t be surprised if a theory of computation based on classical theory doesn’t make connection to the physics of these devices. And going one further step it also seems likely that if we use the theory of computation which is more relevant to the way our world works, then we just might be able to prove and reason about these computers in a simpler manner. A rough analog might be that between real analysis and complex analysis: certainly those of you who have had a class on real analysis and complex analysis remember how “easier” everything is in complex analysis than in real analysis. Might quantum computers lead to a similar shift? Right now there are only a few results that I can point to along these directions, for example Scott Aaronson’s has a very eloquent proof that the complexity class PP is closed under intersection which begins by first showing that PP is equal to a model of quantum computing in which one can post-selection the outcome of the quantum computation and then is extremely simple due to the properties of the quantum model of computation to show closure under intersction. Might not more of the theory of computational complexity be as easy if we focus on the model of quantum computation?
Can you give an example of something that is “easier” in complex analysis than real analysis? I had the opposite experience, and I wonder if this is not at the heart of the difference between classical/quantum complexity (or maybe I just had a bad teacher…): because I was already familiar with the ideas of real analysis (from calculus, say, but also because I had been using real numbers all my life), I found real analysis much more intuitive. Similarly, because I “grew up” with classical physics, it is much easier for me to understand classical physics (and hence classical computation) than quantum physics/computation.
Fun example: integrate x sin x/(x^4+4) from minus infinity to infinity. Using residues in complex analysis this is easily seen to be pi Sin(1) over 2 e. Using what you learn in real analysis…
More generally, the notion of differentiability in functions of one complex variable are stricter than in functions of one real variable. Thus statements like “for all..” are usually easier to show in complex analysis. Lots of other things are nicer: like the fact that the complex numbers are albegraically complete (polynomials with complex coefficients have complex roots, while polynomials with real coefficients have complex roots.) Complex differentiatiable functions are always infinitely differentiable and always have power series. Etc. etc.
I agree that when you first learn complex analysis it seems daunting. But a truely good deep real analysis course can be really painful. (Flashback to my freshman year learning about Dedikind cuts, ack!)
Dude, I think you’re making too much of my PostBQP=PP result. 🙂
There are results about reals that are most easily proved using complex numbers, but there are also many, many results about complex numbers that I’d prove by writing z as x+yi.
Also, I think there is a deep harmony between math and classical CS. One example is the (to me) unexpectedly large number of beautiful complexity theorems that hinge on properties of polynomials of finite fields: IP=PSPACE, the PCP theorem, PRIMES in P, …
Hence the word “rough” before the word “analogy.”
Also I think I am in love with complex analysis because I’m a physicist. We need to worry about those countour integrals in the complex plane 😉
I wonder if the connection is deeper than the fact that ultimately we do experiments, and the needle points to 4. So we need a formalism that gives us 4 for an answer, which means math? Simple I know. Similarly with “physics=information”. QM for example tells us we know nothing till we measure it, so a theory of QM is basically a theory of the amount/value of “information” about the system under consideration.
I know there are deep thinkers that go way beyond this, but I wonder if the above isn’t the first significant digit….
Related: See this comment, and the one preceding it, before it is sent packing for lack of relevance to the post. (I did save copies.)