Quantum disjunctive normal form

[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

1. Developing a quantum generalisation of disjunctive normal form.
2. Establish some bounds on the influence of a QBF defined by quantum disjunctive normal forms (qDNF).
3. 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.
4. Establish some kind of quantum generalisation of Håstad’s switching lemma for qDNFs.
5. 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 $A$ and $B,$ their disjunction defines a boolean formula

$f = A\vee B.$

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

$f = \bigvee_{j=1}^m (\bigwedge_{k=1}^{l_j} x_{a_k}),$

where $x_k$ are literals and $a_k \in [n] = \{1, 2, \ldots, n\}$. 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 $f$ are quantum observables, hence we implement them as hermitian operators. Additionally, thanks to the boolean nature of $f$, a natural way to implement $f$ quantumly (as a phase oracle) is via a hermitian operator which is also unitary, i.e., as $f^2 =\mathbb{I}.$ We do this as follows. Let $\mathbf{x} = x_1x_2\cdots x_n$ denote a boolean string of $n$ bits, and $f(\mathbf{x}) \in \{\pm1\}$ denote the result of computing $f$ (here we are making the “great notational switch”, i.e., all boolean variables are assumed to take their values in $\{\pm1\}$). To each of the possible $2^n$ strings $\mathbf{x}$ we associate a basis vector $|\mathbf{x}\rangle$ such that $\langle \mathbf{x}|\mathbf{y}\rangle = \delta_{\mathbf{x},\mathbf{y}}$. This prescription provides us with a complete orthonormal basis for the hilbert space $\mathbb{C}^{2^n}$ of $n$ qubits. The quantum operator corresponding to $f$ is now defined as

$f|\mathbf{x}\rangle = f(\mathbf{x})|\mathbf{x}\rangle.$

(We are overloading notation quite a bit here: $f$ is both the classical boolean function and the quantum operator — the quantum boolean function — corresponding to $f.$) Unless otherwise noted, from now on, when I talk about a boolean functions $f,$ I will actually mean the quantum boolean function $f$ (i.e., the $2^n \times 2^n$ matrix with $\pm1$ 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 $f$. This is defined to be the subspace which the projector

$P_{\mbox{acc}}(f) = \frac12(\mathbb{I}-f)$

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

$f = |00\rangle\langle 00| + |01\rangle\langle 01| +|10\rangle\langle 10| - |11\rangle\langle 11|.$

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

$f = \mathbb{I}-2P\wedge Q,$

where $P = P_{\mbox{acc}}(x_1)$ and $Q = P_{\mbox{acc}}(x_2),$ and $P\wedge Q$ denotes the projector onto the subspace intersection of the subspaces corresponding to $P$ and $Q.$ In this case this is easy, i.e., $P\wedge Q = PQ$ because the operators $P$ and $Q$ commute. Similarly, the natural way to implement a disjunction $g = x_1\vee x_2$ quantumly is via the subspace join operation

$g= \mathbb{I}-2P\vee Q,$

(the wordpress latex interpreter is a bit cranky, I just can’t get it to display this equation consistently!…) where $P\vee Q$ is the projector onto the smallest subspace containing both $P = P_{\mbox{acc}}(x_1)$ and $Q = P_{\mbox{acc}}(x_2).$

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 $f_j, j \in \{1, 2, \ldots, m\}$ are $m$ QBFs. Then we define their conjunction ${c}$ and disjunction ${d}$ to be

c ${=\mathbb{I}-2\bigwedge_{j=1}^{m}P_{\mbox{acc}}(f_j)}$ and ${d=\mathbb{I}-2\bigvee_{j=1}^{m}P_{\mbox{acc}}(f_j)}$.

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

$f$ $= \mathbb{I} - 2\bigvee_{j=1}^{m} (\bigwedge_{k=1}^{l_j} P_{\mbox{acc}}(f_{a_k})),$

where $f_j$ are a collection of $n$ QBFs and $a_k \in [n]$.

Before we move on I want to introduce some notation. Suppose $f$ is defined by the above qDNF formula. We say that $f$ has size $m$ (it involves $m$ conjunctions). Let’s write ${c_j=\bigwedge_{k=1}^{l_j}P_{\mbox{acc}}(f_{a_k})}$. We say that the conjunctive clause $c_j$ has width $w_j$ if $w_j = \mbox{supp}(c_j)$ where $\mbox{supp}(M) \in [n]$ is the smallest subset of qubits upon which an operator $M$ acts nontrivially. Finally, we say that the clause $c_j$ has rank ${r_j=\mbox{tr}(c_j)}$. We say that $f$ has maxrank ${r=\max_jr_j}$. 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 $f$ has a size-$s$, maxrank-$r$ qDNF formula then $f$ is $\epsilon$-close to a width-$\log\left(\frac{rs}{\epsilon}\right)$ qDNF.

Proof. Recall that we measure closeness using the normalised $2$-norm ${\|M\|_2\equiv\sqrt{\frac{1}{2^n}\mbox{tr}(M^\dag M)}}$.

The first step of the proof is to drop all terms whose width is greater that $\log\left(\frac{rs}{\epsilon}\right)$. Let $f'$ be the QBF represented by the resulting qDNF. Now it is easy to see that $P_{\mbox{acc}}(f) \ge P_{\mbox{acc}}(f')$ according to the positive semidefinite ordering, and so $f$ and $f'$ commute. Thus

$\|f-f'\|_2^2 = 2-\frac{2}{2^n}\mbox{tr}(f-f')$

After some simple manipulations we end up with

$\|f-f'\|_2^2 = \frac{4}{2^n}\mbox{tr}(P-P'),$

where $P = P_{\mbox{acc}}(f)$ and $P' = P_{\mbox{acc}}(f')$. Now note that $\mbox{tr}(P) = \mbox{dim}(P)$ and the inequality $\mbox{dim}(P\vee Q) \le \mbox{dim}(P) + \mbox{dim}(Q)$:

${\|f-f'\|_2^2\le\frac{4}{2^n}\sum_{j\in E}\mbox{dim}(c_j)}$,

where $E$ denotes the set of conjunctive clauses which are dropped. Since the width of each clause $c_j$ in $E$ is greater than $\log\left(\frac{rs}{\epsilon}\right)$ we have that

$\|f-f'\|_2^2 \le \frac{4}{2^n} rs 2^{n-\log\left(\frac{rs}{\epsilon}\right)} \le 4\epsilon.$

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!]

4 Responses to Quantum disjunctive normal form

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

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

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

4. yahoo.com says:

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