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:
- The class
is not contained in
.
- 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:
-
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.
-
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.
-
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:
- On input
, construct the circuit
. (poly-time)
- Using the hypothesis
, construct the “easy witness” circuit
. (subexp time)
- Build the uniform Grover circuits for
.
- Since we are treating the circuits as uniform, there is a fixed nondeterministic Turing machine
that runs in time
and accepts
.
- 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]
In part 2 of the “Proof Sketch” section, “sch” should be “such”.
The name “Szemer{é}di” should not contain the braces.
Thanks!
Prof. Lipton,
I find it quite fascinating how you link the technical subject matter of each post to a person and their quotes/doings. This post, I particularly enjoyed, what with all the quotes from Yogi Berra. How you write such imaginative and technical posts multiple times each week is beyond me. But it entices me to check your blog every day for new entries!
Anonymous reader.
Does the unproven lemma imply your result without your clever trick? I take it that it does not, so you might still have an interesting conditional result, even though you wanted a groundbreaking unconditional result. Ryan’s breakthrough came from reducing circuit lower bounds (hard to think about) to the algorithmic question of designing subexp algorithms for circtuit-sat (easier to think about?). Maybe your lemma is easier to think about in a similar way?