Over the past few years there have been quite a few results where methods of quantum computing have been used to prove or reprove results about classical objects. Among these are lower bounds on locally decodable codes (de Wolf, Kerenidis, Wehner), limitations on classical algorithms for local search problems (Aaronson), a proof that PP is closed under intersection (Aaronson), and ways to use quantum communication complexity to prove lower bounds on classical circuit depths (Kerenidis). Now we have more to add to this mix, with quant-ph/0505188, “Lower Bounds on Matrix Rigidity via a Quantum Argument” by Ronald de Wolf (CWI Amsterdam). The rigidity of a matrix is the number of entries in a matrix which need to be changed in order to bring the rank of the matrix down to a certain value. What Ronald does in this paper is show how to use a quantum argument to prove some lower bounds on the rigidity of the Hadamard matrix. Very nice!
Whenever I see one of these quantum proofs of classical problems, I think, well: why are these quantum proofs significantly or slightly easier? But perhaps this thinking is backwards. Because the universe is quantum mechanical, should we really be surprised that the language of this theory is so powerful? One often hears the statement that it is amazing that mathematics is so useful for describing the physical world. But really this disregards the fact that different parts of mathematics are and are not useful for describing the physical world. So in a realm like computer science, where you are explicitly reasoning about physical systems, should it really be a surprise that the mathematics of these physical systems (quantum theory) is the best way to attack the problems?
O brave new quantum world!
I’ve always thought it was kind of like how complex numbers simplify proofs of things that seem manifestly real. For example, the prime number theorem is much more easily proven with complex analysis than with real analysis. What do complex numbers have to do with primes? A priori, nothing. But once you understand the Zeta function, etc., it beings to make more sense in the new context…
But your argument is about physical systems, so it’s a nice interpretation.
“in a realm like computer science, where you are explicitly reasoning about physical systems”
I agree with this statement, but this is not a statement shared by most in computer science. I suspect that if it weren’t for quantum computing, we wouldn’t be able to make assertions like this.
The complex numbers should more properly be called “the complete numbers”. With that name it’s not so surprising that they might simplify a lot mathematics.
As for why quantum information theory might help prove theorems, actually it has not had as much application to non-quantum questions as you might expect. I think that the main reason that it has happened is that any area of mathematics can in principle be applied to any other; and a lot of people learn quantum theory anyway for quantum reasons. It certainly can help develop your intuition that quantum information theory is empirically true, and not just a mathematical construct.
If you want another example of applying quantum facts to non-quantum questions, see my paper math.PR/9909104 and the follow-up math-ph/0202035.
Perhaps the best analogy is to the use of randomness to prove things about purely deterministic objects — a tactic that doesn’t even raise an eyebrow anymore. Since the universe can be divided into (D)eterministic, (R)andomized, and (Q)uantum, and since R has told us so much about D, it would be astonishing if Q *didn’t* shed any light on D and R!
In the paper mentioned, Ronald suggest that there may be a “quantum method” analogous to the “probabilistic method.” Very interesting. Would Erdos be learning quantum theory if he were alive today?
> Would Erdos be learning quantum theory if he
> were alive today?
My guess is no.
Aw Scott, your such a pessimist! Hey I wonder if you can correlate pessimism/optimisim with number of results which are lower and upper bounds. Heh 😉