Yogi Berra and Complexity Theory

More on a recent result on BQP and nondeterministic exponential time

Yogi Berra is a famous baseball player, who is probably better known for famous quotes than his stellar career. His quotes naturally fall into two categories: those that he said and those that he did not say. There is a book with the title: “I really didn’t say everything I said.”

Today Ken and I thought we would highlight a recent discussion that contains a result about quantum computation and its relationship to classical computation.

As Yogi has said: “It’s déjà vu all over again.” One reason we thought it would be okay to re-state the result is that we now are pretty sure that it is correct, and a paper is due out shortly. The work is joint with Ken and Atri. Another reason is that it builds and uses the framework of Ryan Williams’ recent result on his circuit lower bound on nondeterministic exponential time. A prediction:

Ryan’s framework for his proof will yield further insights into the structure of computation.

A second reason, though, is that our planned post “blew up”: We made too many wrong mistakes. Computer science may be 90% mental, but the other half is physical, and after a pitchy week we needed a rest. Even Napoleon had his Watergate. If the world was perfect, it wouldn’t be. In theory there is no difference between theory and practice, but in practice there is. Now it’s true that there are some people who, if they don’t already know, you can’t tell ’em—but though we thought we knew, we asked someone else just to be sure, and he found the bug. As a field we have deep depth. The moral is that you’ve got to be very careful if you don’t know where you are going, because you might not get there. (See this for the eight adapted Yogi Berra quotes in this paragraph and others in this introduction.)

Well when you come to a fork in the road, you should take it, so we’ll talk about both the above result and the broken idea. We’ll sketch our current proof of the result. Of course it might still have a bug, which would make this déjà vu all over again

Quantum vs Nondeterministic

The theorem we are restating is:

Theorem: At least one of the following is true:

 
1. The class is not contained in .
2. The class is not contained in circuits of polynomial size.

 

Here is a time constructible function: that means that given the value can be constructed in time by a deterministic Turing machine.

This theorem is interesting, we believe, for two reasons. For one it relates quantum computation directly to classical computation. Most would not be surprised to see that is not contained in even , or even not in the polynomial hierarchy. But we cannot prove that, so showing even that it is not contained in seems exciting. Of course the above theorem cannot establish even that. It does show that a consequence of the failure of this containment would be a result we believe, namely , but one that is probably also very hard to resolve.

The point is that you prove what you can. We would have preferred to prove one of the statements of the theorem, not their disjunction. Perhaps someone will be able to in the near future, or perhaps not. Thus we’re left with a fork in the road, but we’ll take it.

Proof Sketch

The proof sketch requires some knowledge of Ryan Williams’ technique. Ken has adapted it from his comment here.

Assume for sake of contradiction that the theorem is false, i.e. that is in and is in , for natural constructible time bounds we will quantify later. The goal is, given an arbitrary -time nondeterministic Turing machine , to simulate on any in nondeterministic time, violating the hierarchy theorem. Define:

 
1. stands for a succinct representation of clauses that are satisfiable iff accepts . is a circuit that on input outputs the three indices of variables in , with their signs.
2. stands for a poly-sized witness circuit that takes the index of a variable, and for some satisfying assignment independent of , outputs the value of . Under , Williams’ adaptation of Impagliazzo Kabanets Wigderson’s easy-witness construction shows that whenever , such a exists.
3. for each , is such that one of , , or satisfies . (Note the condition entails is a witness circuit and puts into .)

 

Along lines of Williams’ paper, one can take such that and have encoding size ; for we can get , but for the value of depends on the application of IKW. We can put as the size of instances of . Now we have by Williams’ construction (as a side note, this implies sharply by the Book-Greibach theorem). Moreover, his construction does this with only bits of nondeterminism.

This means that the exhaustive search is over a domain of size sharply. Thus applying Grover’s algorithm,

needs a search .

Now assume . Specifically we are applying this with , or more precisely in terms of the actual input length to , with . However, since padding translates upward for quantum just as well as classical, we could start with any lower natural or . Thus is in .

Here the terms in and the fact that the input to has length not get absorbed into the . Now we finally get the algorithm:

 
1. On input , construct the circuit . (poly-time)
2. Using the hypothesis , construct the “easy witness” circuit . (subexp time)
3. Build the uniform Grover circuits for .
4. Since we are treating the circuits as uniform, there is a fixed nondeterministic Turing machine that runs in time and accepts .
5. So run on input , and accept iff it accepts.

 

This gives , a contradiction.

So we have: is not in is not in .

The Other Idea and Its Error

I decided I will tell you about the cool idea that blew up—at least a bit. Ken and I thought we had proof of the following theorem:

“Theorem”: For any reasonable time constructible function at most ,

The “proof” was clever; it was based on the great previous work of Wolfgang Paul, Nick Pippenger, Endre Szemerédi and William Trotter, but used what we thought was a new trick. As we started to write up the proof up we circulated it to Rahul Santhanam, who kindly read it and noticed the mistake—which was taking for granted that alternating-machine based hierarchies based on fixed rather than “poly” time bounds would still have the downward-collapse property.

I learned several things from this failure that I want to share.

Write it up carefully: We spent a lot of time writing the proof up very carefully—indeed Ken “re-arranged” the paper twice while also dealing with a breaking news story. If we had not done this I think the error would have been very hard to spot.

Show the write-up to world experts: Santhanam knows more about this area than I do. He was able to spot the error very quickly, which saved us from spending more time on a broken idea. It also stopped us from telling others a result that was not proved.

Errors are in the “obvious steps”: I know this. I know this. I know this But “…déjà vu again.” I know that the likely place that can go wrong in any proof is the part where you say: is well known to be true. This is essentially where our mistake was—in a lemma that we just stated because it was so obvious. The detailed neat part of the proof is well written, easy to follow, and correct. The “this is well known” part was wrong—more exactly as Santhanam kindly said, it is open. We have contacted another expert in this area and might try to repair it. As Yogi Berra said, “It ain’t over till it’s over.”

Open Problems

The main technical question is: can we prove stronger results about the relationship of quantum computation and classic computation complexity classes? The other question is how can we avoid errors? I knew this but forgot: always check the parts of the “proof” that you think are “obvious.” They may not be.

 

[clarified “Yogi Berra” quotes; fixed typos]