[Frustratingly the latex interpreter for wordpress seems a little inconsistent. Some of the equations on this post (and the previous post) don’t parse properly, despite being well-formed latex expressions (I think!). To see the formula source just hover the mouse cursor above the “formula doens’t parse” box.]

In this first of a series of posts I want to discuss a (quantum) boolean function inspired approach to developing lower bounds for quantum circuits. Many of the ideas I discuss here will not be fully baked: I’ll probably state mostly conjectures and supply “proofs” in the form of vague handwavy generalisations of classical approaches. Please feel free to comment or contribute on any of the material in this (or any other) post! The results in this series of posts is currently joint work with Ashley Montanaro.

At this stage I envisage that a series of posts roughly along the following lines

- Developing a quantum generalisation of disjunctive normal form.
- Establish some bounds on the
*influence*of a QBF defined by quantum disjunctive normal forms (qDNF). - Establish a quantum generalisation of the classical circuit complexity class
**AC**(call it^{0}**qAC**perhaps? Quack-naught?), and relate it, via Kitaev’s construction, to the standard quantum circuit model.^{0} - Establish some kind of quantum generalisation of Håstad’s switching lemma for qDNFs.
- Generalise a proof that parity is not in
**AC**.^{0}

The end result, hopefully, will be nontrivial result that says something like:

**Conjecture**. PARITY is not in **qAC ^{0}**.

Actually, I hope that we’ll gain a lot more, including results on quantumly learning quantum circuits.

### Disjunctive normal form

Before we embark on the first objective in our task list it is probably worthwhile to review classical disjunctive normal form. Classically a *disjunction* is just the OR operation. So if we have two boolean variables and their disjunction defines a boolean formula

We say that is in *disjunctive normal form* (DNF) if it is a disjunction of conjunctions:

where are literals and . Disjunctive normal form (and conjunctive normal form) plays a key role in computational complexity theory thanks to the Cook-Levin theorem.

Before we move on to quantising this notion I’ll preprocess the classical definition a bit by formulating it in “quantum” language. To begin with, we need to explain how a disjunction and a conjunction is represented quantumly. Recally that boolean functions are quantum observables, hence we implement them as hermitian operators. Additionally, thanks to the boolean nature of , a natural way to implement quantumly (as a *phase oracle*) is via a hermitian operator which is also unitary, i.e., as We do this as follows. Let denote a boolean string of bits, and denote the result of computing (here we are making the “great notational switch”, i.e., all boolean variables are assumed to take their values in ). To each of the possible strings we associate a basis vector such that . This prescription provides us with a complete orthonormal basis for the hilbert space of qubits. The quantum operator corresponding to is now defined as

(We are overloading notation quite a bit here: is both the classical boolean function and the quantum operator — the quantum boolean function — corresponding to ) Unless otherwise noted, from now on, when I talk about a boolean functions I will actually mean the quantum boolean function (i.e., the matrix with on the diagonal).

Ok, so let’s move on to working how disjunctions and conjunctions should be represented quantumly. To do this it is convenient to talk about the *accepting subspace* of a (quantum) boolean function . This is defined to be the subspace which the projector

projects onto (i.e., the eigenspace of ). Here, as seems to be usual, TRUE is reprented as Now, let’s first think about conjunctions. The simplest conjunction is that of two boolean variables and i.e., as . This can be represented quantumly as

So, ok, that works, but it isn’t really helpful for generalisations. I’d like to argue that the natural way to think about this conjunction is as

where and and denotes the projector onto the *subspace intersection* of the subspaces corresponding to and In this case this is easy, i.e., because the operators and commute. Similarly, the natural way to implement a disjunction quantumly is via the subspace join operation

(the wordpress latex interpreter is a bit cranky, I just can’t get it to display this equation consistently!…) where is the projector onto the smallest subspace containing both and

I would now like to argue that these implementations of conjunctions and disjunctions are the most natural ones to quantise.

### Quantum disjunctive normal form

Let’s now move on to defining quantum disjunctive normal form. The idea here is pretty simple: suppose that are QBFs. Then we define their *conjunction* and disjunction to be

*c* and .

We say that a QBF is in *quantum disjunctive normal form* if it can be written as

where are a collection of QBFs and .

Before we move on I want to introduce some notation. Suppose is defined by the above qDNF formula. We say that has *size* (it involves conjunctions). Let’s write . We say that the *conjunctive clause* has *width* if where is the smallest subset of qubits upon which an operator acts nontrivially. Finally, we say that the clause has rank . We say that has *maxrank* . For classical DNF formulae *r*=1 always, but quantumly things can be quite a bit different!

To end this post I want to derive a result about approximations of qDNF formulae.

### Approximating qDNF formulae

**Proposition 1**. If a QBF has a size-, maxrank- qDNF formula then is -close to a width- qDNF.

*Proof*. Recall that we measure closeness using the normalised -norm .

The first step of the proof is to drop all terms whose width is greater that . Let be the QBF represented by the resulting qDNF. Now it is easy to see that according to the positive semidefinite ordering, and so and commute. Thus

After some simple manipulations we end up with

where and . Now note that and the inequality :

,

where denotes the set of conjunctive clauses which are dropped. Since the width of each clause in is greater than we have that

◊

That’s it for today. Any observations, comments, or suggestions are welcome!

*[Updated February 4, 2009: I found, via Terence Tao’s weblog, workarounds for many of my latex woes!]*

[…] 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 […]

[…] boolean 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) […]

Undeniably consider that that you stated.

Your favourite reason seemed to be at the internet the easiest thing to

remember of. I say to you, I certainly get irked while

folks consider issues that they plainly don’t recognise about.

You managed to hit the nail upon the highest and defined out the entire

thing with no need side effect , other people could take a signal.

Will likely be back to get more. Thank you