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 **qAC ^{0}**, should be defined; essentially I’ll just try and argue by analogy with the classical definition of

**AC**, as far as I can.

^{0}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 on a boolean function is the probability that ’s value is undefined if the value of is unknown, formally defined as

,

where flips the th bit of . (We are putting the uniform measure on the space of all bit strings.) The *total influence* is just the sum of the influences .

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 has a width DNF, then .

*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 th subsystem to be

,

where is any operator, denotes the partial trace over subsystem , and is the identity matrix. Using this the quantum influence of variable is defined as

.

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 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 be defined by a width- qDNF. (Should we worry about the maxrank?) Then the total influence of satisfies .

*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

where is the *rejecting subspace* given by

where are the conjunctive clauses and we’ve used the fact for projectors that . 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 as follows. The derivative operator becomes

so that

.

Thus the total influence can be written

.

So the conjecture concerns how the projector 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- qDNF cannot compute, eg., PARITY, because PARITY has total influence . 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.

[…] functions and quantum circuits In this post I want to continue the series (parts 1 and 2 here) of posts on lower bounds for natural classes of quantum circuits via quantum boolean […]

[…] this post I want to continue the series of posts (see here and here and here) on quantum boolean functions, quantum disjunctive normal form, and (hopefully) lower […]