[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 AC0 (call it qAC0 perhaps? Quack-naught?), and relate it, via Kitaev’s construction, to the standard quantum circuit model.
- Establish some kind of quantum generalisation of Håstad’s switching lemma for qDNFs.
- Generalise a proof that parity is not in AC0.
The end result, hopefully, will be nontrivial result that says something like:
Conjecture. PARITY is not in qAC0.
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!]