Influence of quantum disjunctive normal form formulae

This is the second post in a series of posts aimed at developing lower bounds for a natural class of quantum circuits. The first couple of posts are aimed at working out how this “natural” class, tentatively called qAC0,  should be defined; essentially I’ll just try and argue by analogy with the classical definition of AC0, as far as I can.

At the current time we have defined a representation of QBFs called quantum disjunctive normal form (qDNF). However, we haven’t actually related this to quantum circuits yet (it’s a representation, but there’s no guarantee that it has anything to do with natural quantum circuits), I intend to tackle this problem a little later. For the moment I think it might be interesting to develop a better understanding of qDNF formulae before moving on. To this end I want to discuss, in this post, a couple of (conjectured) results concerning the influence of qDNF formulae.

Influence of boolean variables

The classical definition of the influence of variable $j$ on a boolean function $f$ is the probability that $f$’s value is undefined if the value of $j$ is unknown, formally defined as

$I_j(f) = \mathbb{P}_x[f(x)\not=f(x\oplus e_j)]$,

where $x \oplus e_j$ flips the $j$th bit of $x$. (We are putting the uniform measure on the space of all $2^n$ bit strings.) The total influence $\mathbb{I}(f)$ is just the sum of the $n$ influences $I_j(f)$.

The influence plays an important role in the analysis of boolean functions, providing a useful tool to understand the behaviour of classes of boolean functions. There are many good sources about the influence, including, Gil Kalai’s posts on influence, and this, and this. I wouldn’t be able to do it justice here.

In this post I want to focus on one particular classical result, namely, the influence of DNF formulae, and to see if it can be generalised somehow. The reason for this is that certain boolean functions like PARITY have a huge total influence, and if you can show that some class of circuits cannot have a large influence you automatically learn that this class cannot compute PARITY. The particular result I want to generalise here is the following

Proposition 1. If a function $f:\{-1,+1\}^{\times n}\rightarrow \{-1,+1\}$ has a width $w$ DNF, then $\mathbb{I}(f) \le 2w$.

Proof. This is left as an exercise in O’Donnell’s notes, but, irritatingly, I can’t see how to immediately prove it…

Influence of quantum variables

Now I want to set up the main conjecture of this post. To do this I’ll need to introduce the quantum generalisation of the influence of a variable. As we argue in our paper, a natural generalisation of the influence can be cooked up as follows. We define the derivative operator on the $j$th subsystem to be

$d_j(f) = f-\mbox{tr}_j(f)\otimes \frac{\mathbb{I}_j}{2}$,

where $f$ is any operator, $\mbox{tr}_j$ denotes the partial trace over subsystem $j$, and $\mathbb{I}_j$ is the $2\times 2$ identity matrix. Using this the quantum influence of variable $j$ is defined as

$I_j(f) = \frac{1}{2^n}\mbox{tr}(d_j(f)^2)$.

There are a couple of nice things to note about the quantum influence. Firstly, it reduces to exactly the classical influence for classical boolean functions embedded as diagonal operators. Secondly, in terms of our noncommutative fourier expansion, the quantum influence has a rather compelling expression. Thirdly, there are several alternative expressions (see lemma 67 in our paper) for $d_j(f)$ that might be useful. (I haven’t seen these in the classical literature, and maybe they might be useful in some contexts?)

So now we come to the main conjecture of this post

Conjecture 1. Let $f$ be defined by a width-$w$ qDNF. (Should we worry about the maxrank?) Then the total influence of $f$ satisfies $\mathbb{I}(f) \le 2w$.

Proof ideas. Seeing as how I don’t even know how to prove this result classically I don’t have much of a clue how to generalise the classical proof to the quantum setting. I’m guessing the classical proof is combinatorial in nature? If so, it’ll probably be impossible to quantise. However, it might be more fruitful to approach this problem directly from a quantum perspective.

I’ll just briefly describe one reformulation of the conjecture which might be easier to deal with. To do this I’ll write our qDNF as

$f = -\mathbb{I} + 2R$

where $R$ is the rejecting subspace given by

$R = \bigwedge_{j=1}^m (\mathbb{I}-c_j)$

where $c_j$ are the conjunctive clauses and we’ve used the fact for projectors that $P\vee Q = \mathbb{I} - (\mathbb{I}-P)\wedge(\mathbb{I}-Q)$. This gets rid of the nasty subspace joins and puts everything in terms of subspace intersections which are nicer.

We now rewrite the influence of $f$ as follows. The derivative operator becomes

$d_j(f) = 2(R-\mbox{tr}_j(R)\otimes \frac{\mathbb{I}_j}{2})$

so that

$I_j(f) = \frac{1}{2^n}\mbox{tr}(d_j(f)^2) = \frac{4}{2^n}\mbox{tr}(R) - \frac{2}{2^n}\mbox{tr}(\mbox{tr}_j(R)^2)$.

Thus the total influence can be written

$\mathbb{I}(f) = \frac{4n}{2^n}\mbox{tr}(R) - \frac{2}{2^n}\sum_{j=1}^m\mbox{tr}(\mbox{tr}_j(R)^2)$.

So the conjecture concerns how the projector $R$ onto the rejecting space changes when we trace out a qubit… At this point I’m out of ideas…

Implications of conjecture 1.

One nice thing about conjecture 1, if true, would be the corollary that width-$w$ qDNF cannot compute, eg., PARITY, because PARITY has total influence $n$. This is a pretty fundamental starting point for this whole research program! Thus I think conjecture 1 is a great place to start this whole program: it is a small enough conjecture that it looks provable (or disprovable!) and it would go a long way toward provide the basic building block of the larger quantum circuit lower bound approach.