← The gene-interaction networks of easy fitness landscapes

Blogging community of computational and mathematical oncologists →

Closing the gap between quantum and deterministic query complexity for easy to certify total functions

July 20, 2019 by Artem Kaznatcheev 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: $D(f) = O(Q^2(f))$ . 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, $D(f) = O(Q^2(f))$ .

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 $f: \{0,1\} \rightarrow \{0,1\}$ . 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 $C(f) = C_b(f) = u$ and the smaller $C_{\bar{b}}(f) = v$ . Thus, we have that $u \geq v \geq 1$ (the last inequality follows from the fact that $f$ is non-constant). Now consider an input x such that f(x) = b and $C(f) = C_x(f)$ and let S be a minimal certificate of size |S| = u. Define $S^x$ as the set of all strings x’ such that x’ and x agree on all bits in S. More formally:

$S^x = \{ x' \; | \; \forall i \in S \; x'_i = x_i\}$

Since S is a certificate, we know that $f(S^x) = b$ , where we overloaded notation in the obvious way to serve as shorthand for $\forall x' \in S^x \; f(x') = b$ . Further,since f is total, we know that $|S^x| = 2^{n - u}$ .

Let x(i) be x with the i-th bit flipped. Consider an arbitrary $i \in S$ . If for all $x' \in S^{x(i)}$ 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:

$\forall i \in S, \; \exists y \in S^{x(i)} \; \text{s.t.} \; f(y) = \bar{b}.$

Let $Y_i = S^{x(i)} \cap f^{-1}(\bar{b})$ , we just showed that for every $i \in S$ , this set is non-empty.

Over all the $y \in Y_i$ consider the one with the smallest minimal certificate. In other words, for every $Y_i$ pick a y such that for all $y' \in Y_i \; C_y(f) \leq C_{y'}$ . From the definition of certificate complexity, we thus know that $C_y(f) \leq C_{\bar{b}}(f) = v$ . Let $S_y$ be a minimal certificate for y.

Imagine that $S \cap S_y = \emptyset$ then there exists a $z \in S^x \cup S^y_y$ . However, such a z is paradoxical since it is b-certified by S and $\bar{b}$ -certified by $S_y$ . Thus, $|S \cap S_y| \geq 1$ , in fact, they must overlap on a bit on which x and y differ. In other words, we must have $i \in S_y$ .

Now, consider the set $(S \cup S_y)^y$ . We will show that this is a subset of $Y_i$ . Since any $y' \in (S \cup S_y)^y$ agrees with y on $S_y$ , we have a $\bar{b}$ -certificate for y’. In other words, $f((S \cup S_y)^y) = \bar{b}$ . Further, since $\forall j \in S \; y_j = x(i)_j$ , we have that $(S \cup S_y)^y) \subseteq S^{x(i)}$ . Putting the two together, we prove the claim $(S \cup S_y)^y \subseteq Y_i$ .

Now we can do a simple calculation to lower bound the size of $Y_i$ :

$|Y_i| \geq |(S \cup S_y)^y| = 2^{n - |S\cup S_y|} \geq \frac{2^{n - u}}{2^{v - 1}}$

Further, notice that for each $y \in Y_i$ there exists an $x' \in S^x$ such that $y = x'(i)$ (i.e. they differ only on the i-th bit). Consider a bipartite graph with the left partition being $S^x$ and the right partition being the union of the $Y_i$ . Add an edge between $x'' \in S^x$ and $y'' \in \sum_{i \in S} Y_i$ 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:

$C_b(f) 2^{n - C_b(f) - C_{\bar{b}}(f) + 1}$

From this, we can conclude that the average degree of a vertex is greater than $\frac{2C_b(f)}{2^{C_{\bar{b}}(f)}}$ .

In particular there is some vertex $x^*$ such that the size of its neighbourhood (which is equal to its degree) $|N(x^*)| \geq \frac{2C_b(f)}{2^{C_{\bar{b}}(f)}}$ . Further for each $y'' \in N(x^*)$ we have $f(x^*) \neq f(y'')$ and each $y''$ differs from $x^*$ by exactly one bit. In other words, we have shown that the sensitivity $s(f) \geq s_{x^*}(f) \geq \frac{2C_b(f)}{2^{C_{\bar{b}}(f)}}$ .

Using either Ambainis’ method or the polynomial method, it is not hard to show that $Q_2(f) = \Omega(\sqrt{s(f)})$ , thus:

$Q_2(f) = \Omega(\sqrt{\frac{C_b(f)}{2^{C_{\bar{b}}(f)}}})$

For constant $C_{\bar{b}}$ it gives us what we desire: $D(f) = O(Q^2(f))$ for total functions $f$ with one of its certificates of constant size.

Filed under Analytic, Preliminary, Technical Tagged with cstheory, quantum information processing, query complexity

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.