Erdös and the Quantum Method
Proving theorems with the quantum method
Paul Erdos needs no introduction to our community, but I will give him one anyway. He won the AMS Cole Prize in 1951 and in 1983 the Wolf Prize. He is famous for so many things: an elementary proof of the Prime Number Theorem, the solver of countless open problems, the creator of countless more open problems, and his ability to see to the core of a problem. There are, by the way, several versions of how he and Atle Selberg found their respective elementary proofs of the Prime Number Theorem, and more importantly where the credit should go and to whom. See this for a history of the proofs.
Our friends at Wikipedia have a story about Erdos’s use of amphetamines, but the version I heard from Ron Graham is a bit different. Ron bet Erdos $500 dollars that he could not stop taking the drug for a month. Exactly one month later Erdos met Ron, took his $500 dollars in winnings, and immediately popped a pill. Erdos said to Ron, “I felt mortal.”
Perhaps my favorite story about Erdos is the “dinner conversation story.” Apparently Erdos was at a conference and found himself seated at a table of experts all from some arcane area of mathematics–let’s call it area A. Paul knew nothing about their area. Nothing. The rest of the table was having a lively discussion about the big open question in their area A. Erdos, of course, could not follow any of the discussion, since he knew none of the terms from A. Slowly, by asking lots of questions, “what does that term mean?” and “why is that true?” and so on, Erdos began to understand the open problem of area A. Once he finally understood the problem, once the definitions and basic facts had been made clear to him, he was able to solve their open problem. Right there. Right then.
During the rest of the dinner Paul explained his solution to the table of experts–who I am sure had mixed feelings. Whether true or not, I think this story captures one of Erdos’s abilities. The ability to cut to the core of an open problem, and more often than not the core was a combinatorial problem. Not always. But very often. And when it was combinatorial there was a good chance that he could solve it.
A personal story–alas my Erdos number is only 2–is about the time I told Erdos about the “Planar Separator Theorem”. This is of course joint work with Bob Tarjan–I plan to discuss separator theorems of all kinds in another post. After listening politely to me nervously explain the theorem, I was quite junior at the time, Paul smiled and said, “that is not to be expected.” I took this as a compliment. It made my day.
The Probabilistic Method
Erdos and the Quantum Method? What am I talking about? Actually Erdos is famous, of course, for the probabilistic method. I believe similar methods had been used by others, again I am not trying to be a perfect historian; but Erdos certainly deserves credit for making the probabilistic method a standard tool that everyone working in theory must know. The method is amazingly powerful, clearly many of today’s results would be unprovable without the method.
You probably, no pun intended, know the general method: If you wish to construct an object with some property often a “random” object can be proved to have the property with positive probability. If this is the case, then there must exist some object with the desired property. The best current explanation of this method is the great book of Noga Alon and Joel Spencer.
However, the first book on the probabilistic method was the thin small blue book of Erdos and Spencer. The book consisted of a series of chapters, each gave another example of the probabilistic method. There was no motivation, no exercises, no overview, no frills. Just chapter after chapter of “We will prove X. Consider a random object They used the chilling phrase in the book: “it follows by elementary calculation that this formula is true”, that always scared me. Often such statements could be checked in a hour or two, while I remember one that took me a few days. The ”elementary calculation”, in this case, used Stirling’s approximation for out to four terms. I loved the book.
I still remember my first use of the probabilistic method to solve an open problem. A year before studying the book I was asked about a certain open problem by Arnie Rosenberg of IBM Yorktown. I never got anywhere on it, and eventually forgot about it. After studying the book, one day I ran into Andy Yao at a coffee shop near MIT, and asked him what he was working on. He stated the problem, and it sounded familar. I suddenly realized two things: one it was the problem Arnie had asked me a year earlier, and second that I knew how to solve it. The answer was the probabilistic method. In about two days Andy and I had worked out all the details and we had solved the problem.
The Quantum Method
I have my doubts about the future of Quantum Computing. But I always think of:
Clarke’s First Law: When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
So my doubts are probably wrong. However, whether or not quantum computers are ever built is not important once you realize that there is a new proof method based on quantum theory. There is a small but growing collection of theorems that have nothing to do with quantum computation, yet are proved by quantum arguments. This is extremely important. This–to me–changes everything. If quantum theory becomes a new technology for proving theorems, then we have to become experts in it or be left behind.
There is an uncanny parallel with the probabilistic method. The amazing part of the probabilistic method is that it can solve problems that have nothing to do with probability theory. The statement of the theorems do not talk about random objects. The only place randomness is used is inside the proof itself. This is the magic of the method. Take a pure statement that is completely deterministic, and prove by probability theory that the statement is true. That is where the power of the probabilistic method lies, in my opinion.
This is beginning to happen with quantum theory. There are now a small number of theorems that can be proved by using quantum arguments. The statements of the theorems have nothing to do with anything quantum. Nothing. I believe that such quantum arguments could parallel the probabilistic method, and help solve many currently open problems. It is early and we do not yet know if this new method could be as powerful as the probabilistic method, but time will tell.
The quantum method yields proofs that look something like this:
- Assume, by way of contradiction, that some classic result is true.
- Use simulation, or another method, to show that this implies that a quantum result is true.
- Reach a contradiction by showing that is too good and violates some known result from quantum theory.
Thus, the classic result is false. Very cool.
Examples of The Quantum Method
One of major players in this new area is Ronald de Wolf. He has been able to prove a number of theorems using the quantum method, I will highlight one of his results on locally decodable codes. His other results include: a result on the degrees of symmetric functions, and another on a lower bound on matrix rigidity. The key in all of these is that the results have nothing in their statements about quantum theory. The degree of the symmetric function is a classic measure, and matrix rigidity is the classic notion. And so on. Again, notice the parallel with the probabilistic method.
The quantum method is in its infancy, as de Wolf has pointed out to me. There are a few examples, yet there is no underlying structure, there is still no sense where the method will go. Will we look back, in a few years, and see a few isolated results, or is this the beginning of a new chapter in theory? Only time will tell, but as an outsider I am excited by the initial results. Others are working on results that may also fall under this umbrella: apparently Scott Aaronson is one of them. Of course I am not surprised, since Scott is one of the experts on all things quantum. Let’s turn to one important example of the quantum method due to Iordanis Kerenidis and de Wolf. They prove a lower bound on the size of certain codes. An error-correcting code is said to be a locally decodable code (LDC) if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message with an adaptive decoding algorithm. A -locally decodable code encodes -bit strings into -bit code words . For any index , the bit can be recovered with probability with queries even if bits have been corrupted. The theorem of Kerenidis and de Wolf is:
Theorem: Any -locally decodable code has length .
Here is a outline of their proof reproduced here with de Wolf’s kind permission. Given a -query LDC we will proceed as follows to get a lower bound on .
Assume that the classical 2-query decoder recovers the bit by choosing a random element from some perfect matching of , it then queries bits and of the (possibly corrupted) codeword, and returns their XOR as its guess for . It was already known from Jonathan Katz and Luca Trevisan that this “normal form” can be achieved, at the expense of reducing the success probability by a small amount. Now consider the quantum state (“quantum code for x”) equal to,
This is the uniform superposition over all entries of the codeword (with bits turned into signs). This state is an -dimensional vector, so it has qubits. There is a quantum measurement (slightly technical but not hard) that, when applied to this state, gives us the XOR of the two bits of a random element from , for each of our choice, and hence allows us to make the same prediction as the classical -query decoder.
Thus, we have a quantum state that allows us to predict each of the bits of . It follows from a known quantum information theory result (the random access code lower bound of Ashwin Nayak) that the number of qubits is . Accordingly, we have , hence . The exponential lower bound matches–up to the small constant factors in the exponent–to the Hadamard code, which is a 2-query LDC. This is still the only super-polynomial lower bound known for LDC’s.
The obvious open questions are can we use the quantum method to solve other open problems? Or to get cleaner proofs of old theorems? Or to extend and sharpen known theorems? I do not understand the limits of this new method, but here are some potential problems that could be attacked with the quantum method:
- Circuit lower bounds.
- Data structure lower bounds.
- Coding theory lower bounds.
- Separation theorems, i.e. P=NP.
- Other suggestions?
One more point: de Wolf suggested that “ very metaphorically, quantum physics stands to complex numbers as classical physics stands to real numbers.” I pointed out to him that there is a famous quote due to Jacques Hadamard that is relevant: The shortest path between two truths in the real domain passes through the complex domain.
Finally, I would like to thank de Wolf for his generous help with this post. As usual all opinions, errors, and mistakes, are mine.