Quantum Implications of Huang’s Sensitivity Theorem

Last year, Huang resolved a major open problem in the analysis of Boolean functions called the sensitivity conjecture [Hua19], which was open for nearly 30 years [NS94]. Surprisingly, Huang’s elegant proof takes less than 2 pages—truly a “proof from the book.” Specifically, Huang showed that for any total Boolean function, which is a function $f:\{0,1\}^{n}\to\{0,1\}$, we have

where $\operatorname{\mathsf{deg}}(f)$ is the real degree of $f$ and $\operatorname{\mathsf{s}}(f)$ is the (maximum) sensitivity of $f$. These measures and other measures appearing in this introduction are defined in Section 2.

In this note, we describe some implications of Huang’s resolution of the sensitivity conjecture to quantum query complexity. We observe that Huang actually proves a stronger claim, in which $\operatorname{\mathsf{s}}(f)$ in Eq. 1 can be replaced by $\operatorname{\lambda}(f)$, a spectral relaxation of sensitivity that we define later. This observation has several implications for quantum query complexity.

We use this observation to settle the optimal relation between the deterministic query complexity, $\operatorname{\mathsf{D}}(f)$, and quantum query complexity, $\operatorname{\mathsf{Q}}(f)$, for total functions. We know from the seminal results of Nisan [Nis91], Nisan and Szegedy [NS94] and Beals et al. [BBC⁺01] that any total Boolean function $f$ satisfies⁵⁵5This means that for total functions, quantum query algorithms can only outperform classical query algorithms by a polynomial factor. On the other hand, for partial functions, which are defined on a subset of $\{0,1\}^{n}$, exponential and even larger speedups are possible.

Grover’s algorithm [Gro96] shows that for the or function, a quadratic separation between $\operatorname{\mathsf{D}}$ and $\operatorname{\mathsf{Q}}$ is possible. This was the best known quantum speedup for total functions until the work of Ambainis et al. [ABB⁺17], who constructed a total function $f$ with

In this note, we show that the quartic separation (up to log factors) in Eq. 3 is actually the best possible:

We deduce Theorem 1 as a corollary of a new tight quadratic relationship between $\operatorname{\mathsf{deg}}(f)$ and $\operatorname{\mathsf{Q}}(f)$:

Observe that Theorem 2 is tight for the or function on $n$ variables, whose degree is $n$ and whose quantum query complexity is $\Theta(\sqrt{n})$ [Gro96, BBBV97]. Prior to this work, the best relation between $\operatorname{\mathsf{deg}}(f)$ and $\operatorname{\mathsf{Q}}(f)$ was a sixth power relation, $\operatorname{\mathsf{deg}}(f)=O(\operatorname{\mathsf{Q}}(f)^{6})$, which follows from Eq. 2.

As discussed earlier, our proof relies on the restatement of Huang’s result (Theorem 5), showing that $\operatorname{\mathsf{deg}}(f)\leq\operatorname{\lambda}(f)^{2}$, where $\operatorname{\lambda}(f)$ is the spectral relaxation of sensitivity defined in Section 3. We then show that the measure $\operatorname{\lambda}(f)$ lower bounds the original quantum adversary method of Ambainis [Amb02], which in turn lower bounds $\operatorname{\mathsf{Q}}(f)$.

We now show how Theorem 1 straightforwardly follows from Theorem 2 using two previously known connections between complexity measures of Boolean functions.

It remains to show the main result, Theorem 2, which we do in Section 3 using the proof of the sensitivity conjecture by Huang [Hua19] and the spectral adversary method in quantum query complexity [BSS03].

In Section 4, we also use Theorem 2 to prove the quantum analogue of the famous Aanderaa–Karp–Rosenberg conjecture. Briefly, this conjecture is about the minimum possible query complexity of a nontrivial monotone graph property, for graphs specified by their adjacency matrices.

There are variants of the conjecture for different models of computation. For example, the randomized variant of the Aanderaa–Karp–Rosenberg conjecture, attributed to Karp [SW86, Conjecture 1.2] and Yao [Yao77, Remark (2)], states that for all nontrivial monotone graph properties $f$, we have $\operatorname{\mathsf{R}}(f)=\Omega(n^{2})$. Following a long line of work, the current best lower bound is $\operatorname{\mathsf{R}}(f)=\Omega(n^{4/3}\log^{1/3}n)$ due to Chakrabarti and Khot [CK01].

The quantum version of the conjecture was raised by Buhrman, Cleve, de Wolf, and Zalka [BCdWZ99], who observed that the best one could hope for is $\operatorname{\mathsf{Q}}(f)=\Omega(n)$, because the nontrivial monotone graph property “contains at least one edge” can be decided with $O(n)$ queries using Grover’s algorithm [Gro96]. Buhrman et al. [BCdWZ99] also showed that all nontrivial monotone graph properties $f$ satisfy $\operatorname{\mathsf{Q}}(f)=\Omega(\sqrt{n})$. The current best lower bound is $\operatorname{\mathsf{Q}}(f)=\Omega(n^{2/3}\log^{1/6}n)$, which was credited to Yao in [MSS07]. We resolve this conjecture by showing an optimal $\Omega(n)$ lower bound.

Theorem 3 follows by combining Theorem 2 with a known quadratic lower bound on the degree of monotone graph properties.

Before proving Theorem 2, which is based on Huang’s proof, we reinterpret his result in terms of a new complexity measure of Boolean functions that we call $\operatorname{\lambda}(f)$: the spectral norm of the sensitivity graph of $f$.

Note that because $A_{f}$ is a real symmetric matrix, $\operatorname{\lambda}(f)$ is also the largest eigenvalue of $A_{f}$. Since $G_{f}$ is bipartite, the largest and smallest eigenvalues of $A_{f}$ are equal in magnitude.

Huang’s proof of the sensitivity conjecture can be divided into two steps:

1. 1.

   $\forall{f}:\operatorname{\mathsf{deg}}(f)\leq\operatorname{\lambda}(f)^{2}$

2. 2.

   $\forall{f}:\operatorname{\lambda}(f)\leq\operatorname{\mathsf{s}}(f)$

The second step is the simple fact that the spectral norm of an adjacency matrix is at most the maximum degree of any vertex in the graph, which equals $\operatorname{\mathsf{s}}(f)$ in this case.

We reprove the first claim, i.e., $\operatorname{\mathsf{deg}}(f)\leq\operatorname{\lambda}(f)^{2}$, for completeness.

Finally, we prove that $\operatorname{\lambda}(f)=O(\operatorname{\mathsf{Q}}(f))$. We rely on a variant of the adversary method introduced by Barnum, Saks, and Szegedy [BSS03] (see also [SS06]).

Barnum, Saks, and Szegedy [BSS03] proved that $\operatorname{\mathsf{Q}}(f)=\Omega(\operatorname{\mathsf{SA}}(f))$.

From Theorem 5 and Lemma 7 we immediately get Theorem 2.

The Aanderaa–Karp–Rosenberg conjectures are a collection of conjectures related to the query complexity of deciding whether an input graph specified by its adjacency matrix satisfies a given property in various models of computation.

Specifically, let the input be an $n$-vertex undirected simple graph specified by its adjacency matrix. This means we can query any unordered pair $\{i,j\}$, where $i,j\in[n]$, and learn whether there is an edge between vertex $i$ and $j$. Note that the input size is $\binom{n}{2}=\Theta(n^{2})$.

A function $f$ on $\binom{n}{2}$ variables is a graph property if it treats the input as a graph and not merely a string of length $\binom{n}{2}$. Specifically, the function must be invariant under permuting vertices of the graph. In other words, the function can only depend on the isomorphism class of the graph, not the specific labels of the vertices. A function $f$ is monotone (increasing) if for all $x,y\in\{0,1\}^{n}$, $x\leq y\implies f(x)\leq f(y)$, where $x\leq y$ means $x_{i}\leq y_{i}$ for all $i\in[n]$. For a monotone function, negating a $0$ in the input cannot change the function value from $1$ to $0$. In the context of graph properties, if the input graph has a certain monotone graph property, then adding more edges cannot destroy the property.

Examples of monotone graph properties include “$G$ is connected,” “$G$ contains a clique of size $k$,” “$G$ contains a Hamiltonian cycle,” “$G$ has chromatic number greater than $k$,” “$G$ is not planar”, and “$G$ has diameter at most $k$.” Many commonly encountered graph properties (or their negation) are monotone graph properties. Finally, we say a function $f:\{0,1\}^{n}\to\{0,1\}$ is nontrivial if there exist inputs $x$ and $y$ such that $f(x)\neq f(y)$.

The deterministic Aanderaa–Karp–Rosenberg conjecture, also called the evasiveness conjecture,⁶⁶6A function $f$ is called evasive if its deterministic query complexity equals its input size. states that for all nontrivial monotone graph properties $f$, $\operatorname{\mathsf{D}}(f)=\binom{n}{2}$. This conjecture remains open to this day, although the weaker claim that $\operatorname{\mathsf{D}}(f)=\Omega(n^{2})$ was proved over 40 years ago by Rivest and Vuillemin [RV76]. Several works have improved on the constant in their lower bound, and the best current result is due to Scheidweiler and Triesch [ST13], who prove a lower bound of $\operatorname{\mathsf{D}}(f)\geq(1/3-o(1))\cdot n^{2}$. The evasiveness conjecture has been established in several special cases including when $n$ is prime [KSS84] and when restricted to bipartite graphs [Yao88].

The randomized Aanderaa–Karp–Rosenberg conjecture asserts that all nontrivial monotone graph properties $f$ satisfy $\operatorname{\mathsf{R}}(f)=\Omega(n^{2})$. A sequence of increasingly stronger lower bounds, starting with a lower bound of $\Omega(n\log^{1/12}n)$ due to Yao [Yao91], a lower bound of $\Omega(n^{5/4})$ due to King [Kin88], and a lower bound of $\Omega(n^{4/3})$ due to Hajnal [Haj91], has led to the current best lower bound of $\Omega(n^{4/3}\log^{1/3}n)$ due to Chakrabarti and Khot [CK01]. There are also two lower bounds due to Friedgut, Kahn, and Wigderson [FKW02] and O’Donnell, Saks, Schramm, and Servedio [OSSS05] that are better than this bound for some graph properties.

The quantum Aanderaa–Karp–Rosenberg conjecture states that all nontrivial monotone graph properties $f$ satisfy $\operatorname{\mathsf{Q}}(f)=\Omega(n)$. This is the best lower bound one could hope to prove since there exist properties with $\operatorname{\mathsf{Q}}(f)=O(n)$, such as the property of containing at least one edge. In fact, for any $\alpha\in[1,2]$ it is possible to construct a graph property with quantum query complexity $\Theta(n^{\alpha})$ using known lower bounds for the threshold function [BBC⁺01].

As stated in the introduction, the question was first raised by Buhrman, Cleve, de Wolf, and Zalka [BCdWZ99], who showed a lower bound of $\Omega(\sqrt{n})$. This was improved by Yao to $\Omega(n^{2/3}\log^{1/6}n)$ using the technique in [CK01] and Ambainis’ adversary bound [Amb02]. Better lower bounds are known in some special cases, such as when the property is a subgraph isomorphism property, where we know a lower bound of $\Omega(n^{3/4})$ due to Kulkarni and Podder [KP16].

As stated in Theorem 3, we resolve the quantum Aanderaa–Karp–Rosenberg conjecture and show an optimal $\Omega(n)$ lower bound. The proof combines Theorem 2 with a quadratic lower bound on the degree of nontrivial monotone graph properties. With some work, the original quadratic lower bound on the deterministic query complexity of nontrivial monotone graph properties by Rivest and Vuillemin [RV76] can be modified to prove a similar lower bound for degree. We were not able to find such a proof in the literature, and instead combine the following two claims to obtain the desired claim.

First, we use the result of Dodis and Khanna [DK99, Theorem 2]:

Here $\operatorname{\mathsf{deg}}_{2}(f)$ is the minimum degree of a Boolean function when represented as a polynomial over the finite field with two elements, $\mathbb{F}_{2}$. We combine this with a standard lemma that shows that this measure lower bounds $\operatorname{\mathsf{deg}}(f)$. A proof can be found in [O’D09, Proposition 6.23]:

Combining these with Theorem 2, we get that all nontrivial monotone graph properties $f$ satisfy $\operatorname{\mathsf{Q}}(f)=\Omega(n)$, which is the statement of Theorem 3.

We saw that $\operatorname{\lambda}(f)$ lower-bounds both $\operatorname{\mathsf{Adv}}(f)$, and thus $\operatorname{\mathsf{Q}}(f)$, and also the sensitivity $\operatorname{\mathsf{s}}(f)$. One might conjecture that $\operatorname{\lambda}(f)$ lower-bounds all the complexity measures in Figure 1, including $\widetilde{\operatorname{\mathsf{deg}}}(f)$.

If 1 we true, Theorem 5 would imply that $\operatorname{\mathsf{deg}}(f)=O(\widetilde{\operatorname{\mathsf{deg}}}(f)^{2})$, settling a longstanding conjecture posed by Nisan and Szegedy [NS94]. The current best relation between the two measures is $\operatorname{\mathsf{deg}}(f)=O(\widetilde{\operatorname{\mathsf{deg}}}(f)^{6})$. The following conjecture is weaker, and might be easier to tackle first.

Another longstanding open problem is to show a quadratic relation between deterministic query complexity and block sensitivity:

If this conjecture were true, it would optimally resolve several relationships in Table 1, and would imply, for example, $\operatorname{\mathsf{D}}(f)=O(\operatorname{\mathsf{R}}(f)^{2}))$ and $\operatorname{\mathsf{D}}(f)=O(\operatorname{\mathsf{\widetilde{deg}}}(f)^{4})$.

After settling the best relation between $\operatorname{\mathsf{D}}(f)$ and $\operatorname{\mathsf{Q}}(f)$, the next pressing question is to settle the best relation between $\operatorname{\mathsf{R}}(f)$ and $\operatorname{\mathsf{Q}}(f)$. Recently, the fourth author [Tal19] showed a power $8/3$ separation between $\operatorname{\mathsf{R}}(f)$ and $\operatorname{\mathsf{Q}}(f)$, while the best known relationship is a power $4$ relationship (this work). We conjecture that both these bounds can be improved.

We note that there are candidate constructions based on the work of [AA18, ABK16, Tal19] that are conjectured to satisfy $\operatorname{\mathsf{Q}}(f)\geq\operatorname{\mathsf{R}}(f)^{3-o(1)}$. In particular, it suffices to prove a conjectured bound on the Fourier spectrum of deterministic decision trees [Tal19] to prove 5.

Finally, for the special case of monotone total Boolean functions $f$, Beals et al. [BBC⁺01] already showed in 1998 that $\operatorname{\mathsf{D}}(f)=O(\operatorname{\mathsf{Q}}(f)^{4})$. It would be interesting to know whether this can be improved, perhaps all the way to $\operatorname{\mathsf{D}}(f)=O(\operatorname{\mathsf{Q}}(f)^{2})$.