Closing the gap between quantum and deterministic query complexity for easy to certify total functions
July 20, 2019 Leave a comment
Recently, trying to keep with my weekly post schedule, I’ve been a bit strapped for inspiration. As such, I’ve posted a few times on a major topic from my past life: quantum query complexity. I’ve mostly tried to describe some techniques for (lower) bounding query complexity like the negative adversary method and span programs. But I’ve never really showed how to use these methods to actually set up interesting bounds.
Since I am again short of a post, I thought I’d share this week a simple proof of a bound possible with these techniques. This is based on an old note I wrote on 19 April 2011.
One of the big conjectures in quantum query complexity — at least a half decade ago when I was worrying about this topic — is that quantum queries give you at most a quadratic speedup over deterministic queries for total functions. In symbols: . Since Grover’s algorithm can give us a quadratic quantum speed-up for arbitrary total functions, this conjecture basically says: you can’t do better than Grover.
In this post, I’ll prove a baby version of this conjecture.
Let’s call a Boolean total-function easy to certify if one side of the function has a constant-length certificate complexity. I’ll prove that for easy-to-certify total functions, .
This is not an important result, but I thought it is a cute illustration of standard techniques. And so it doesn’t get lost in my old pdf, I thought I’d finally convert it to a blog post. Think of this as a simple application of the adversary method.
Consider a non-constant total function . Let b be the output that corresponds to the part of the function that is harder to certify (for a definition of certificate complexity, see my old post). In other words, we will call the bigger certificate
and the smaller
. Thus, we have that
(the last inequality follows from the fact that
is non-constant). Now consider an input x such that f(x) = b and
and let S be a minimal certificate of size |S| = u. Define
as the set of all strings x’ such that x’ and x agree on all bits in S. More formally:
Since S is a certificate, we know that , where we overloaded notation in the obvious way to serve as shorthand for
. Further,since f is total, we know that
.
Let x(i) be x with the i-th bit flipped. Consider an arbitrary . If for all
we have f(x) = b then i is non-necessary for S to be a certificate, and we can remove it, contradicting the fact that we picked a minimal certificate. Thus:
Let , we just showed that for every
, this set is non-empty.
Over all the consider the one with the smallest minimal certificate. In other words, for every
pick a y such that for all
. From the definition of certificate complexity, we thus know that
. Let
be a minimal certificate for y.
Imagine that then there exists a
. However, such a z is paradoxical since it is b-certified by S and
-certified by
. Thus,
, in fact, they must overlap on a bit on which x and y differ. In other words, we must have
.
Now, consider the set . We will show that this is a subset of
. Since any
agrees with y on
, we have a
-certificate for y’. In other words,
. Further, since
, we have that
. Putting the two together, we prove the claim
.
Now we can do a simple calculation to lower bound the size of :
Further, notice that for each there exists an
such that
(i.e. they differ only on the i-th bit). Consider a bipartite graph with the left partition being
and the right partition being the union of the
. Add an edge between
and
if x” and y” differ by one bit. We already observed that for each y” there is an edge to S^x, thus the total number of edges to S^x is greater than:
From this, we can conclude that the average degree of a vertex is greater than .
In particular there is some vertex such that the size of its neighbourhood (which is equal to its degree)
. Further for each
we have
and each
differs from
by exactly one bit. In other words, we have shown that the sensitivity
.
Using either Ambainis’ method or the polynomial method, it is not hard to show that , thus:
For constant it gives us what we desire:
for total functions
with one of its certificates of constant size.