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 ${\dots}$ 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 ${n!}$ 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.
Arthur Clarke

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 ${\mathsf{CR}}$ is true.
• Use simulation, or another method, to show that this implies that a quantum result ${\mathsf{QR}}$ is true.
• Reach a contradiction by showing that ${\mathsf{QR}}$ is too good and violates some known result from quantum theory.

Thus, the classic result ${\mathsf{CR}}$ 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 ${(q,\delta,\epsilon)}$-locally decodable code encodes ${n}$-bit strings ${x}$ into ${m}$-bit code words ${C(x)}$. For any index ${i}$, the bit ${x_{i}}$ can be recovered with probability ${1/2 + \epsilon}$ with ${q}$ queries even if ${\delta m}$ bits have been corrupted. The theorem of Kerenidis and de Wolf is:

Theorem: Any ${(2,\delta,\epsilon)}$-locally decodable code has length ${m \ge 2^{\Omega (n)}}$.

Here is a outline of their proof reproduced here with de Wolf’s kind permission. Given a ${2}$-query LDC ${C:\{0,1\}^n \rightarrow {0,1}^m}$ we will proceed as follows to get a lower bound on ${m}$.

Assume that the classical 2-query decoder recovers the bit ${x_i}$ by choosing a random element ${(j,k)}$ from some perfect matching ${M_i}$ of ${[m]}$, it then queries bits ${j}$ and ${k}$ of the (possibly corrupted) codeword, and returns their XOR as its guess for ${x_i}$. 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”) ${|\phi_x> }$ equal to,

$\displaystyle 1/\sqrt{m} \sum_{j=1}^m (-1)^{C(x)_j} |j>$

This is the uniform superposition over all entries of the codeword ${C(x)}$ (with bits turned into signs). This state is an ${m}$-dimensional vector, so it has ${\log(m)}$ 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 ${M_i}$, for each ${i}$ of our choice, and hence allows us to make the same prediction as the classical ${2}$-query decoder.

Thus, we have a quantum state that allows us to predict each of the ${n}$ bits of ${x}$. It follows from a known quantum information theory result (the random access code lower bound of Ashwin Nayak) that the number of qubits is ${\Omega(n)}$. Accordingly, we have ${\log(m)=\Omega(n)}$, hence ${m \ge 2^{\Omega(n)}}$. 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.

Open Problems

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.

1. March 28, 2009 9:21 am

The method seems very promising but there is one big difference with the probabilistic method, which could – in the long run – make it that much less effective: The probabilistic method is ‘elementary’, in the sense that in many cases you can almost fully understand the proof without knowing too much advanced stuff. For instance, you can understand most of the requisite background for the probabilistic method in a few days. However, for the quantum method it seems to me that there’s a steep learning curve (If you think this is not the case, I’ll be really glad if you can point out some (short) resources for picking up the basics).

March 28, 2009 9:49 am

I think when Erdos and Spencer book came out the probabilistic method was new. My story about it tried to make that point. Now we all know the method and it seems simple. Perhaps the same will happen with the quantum method. Perhaps we need someone to write the book.

2. March 28, 2009 12:36 pm

This is a lovely post. I can’t resist mentioning one my fondest hopes when I was still working on quantum computing, namely, the idea that it would turn out to be more natural to prove lower bounds for quantum circuit size than classical circuit size. In particular, I hoped that it would be possible to formulate the problem of proving quantum lower bounds in a “smooth” way, a way that would allow the ideas of calculus to be applied. The motivation behind this hope was the elementary observation that it’s often easier to lower bound the value of a smooth function defined over the reals than over some discrete set, simply because the ideas of calculus are available in the first case. It turns out that this elementary observation has a natural analogue in the quantum world (see, e.g., http://arxiv.org/abs/quant-ph/0701004), which gives rise to some beautiful mathematical structures. Not surprisingly, though, I never succeeded in proving a lower bound this way.

March 30, 2009 8:06 am

Hello Michael, can you tell us what’s behind the “not surprisingly” in the last sentence of your comment ? Is there a fundamental flaw in this lower bound idea that you had, or is it “just” that the problem is mathematically difficult ?
Of course lower bound results are often difficult, but after all we already have lots of such results both in classical and quantum computing.

4. March 30, 2009 12:15 pm

Hi Pascal – Just mathematical difficulty. Indeed, with some technical caveats I won’t describe here (email me if you want an explanation), it is possible to establish that the minimal geodesic path lengths on a particular Riemannian manifold are equal to minimal quantum circuit size, up to polynomial factors. Thus, if it’s possible to establish bounds on quantum circuit size by any means, such bounds will necessarily simply bounds on the path length problem I was considering. I hoped, however, that the availability of the calculus of variations and similar tools would provide a powerful “in” to attack the minimal path length problem. Stated another way, I thought the minimal path length problem might be more natural than the circuit size problem. I still like the idea very much, but have moved on.

March 30, 2009 2:56 pm

Michael, that looks like a terrific idea. I hope there will be some follow-up work on it.

6. March 30, 2009 4:56 pm

Pascal – Thanks! I don’t know of much going on. There was some interest from geometers and control theorists early on, but I don’t know of any actively working on it. For non-geometers, I think the geometry may be a barrier to entry.

7. April 14, 2009 11:06 am

I would like to echo Michael Nielsen in saying this is a lovely post. In the engineering field of model order reduction too, we find that modern quantum methods provide us with powerful tools and ideas for solving purely classical problems. There is some sense, perhaps, in which we are coming to appreciate that the quantum theory of information and simulation represents the natural “complexification” of the classical theory of information and simulation.