*[This post was created from latex using a script written by Luca Trevisan — many thanks!]*

In 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 bounds for classes of quantum circuits.

Here I want to introduce a class of *languages* (which is computer science speak for “class of problems”) which can be decided by quantum computers capable of measuring quantum boolean functions defined by special circuits (*not* quantum circuits) which I’ll provisionally call *subspace circuits*. Using these special circuits I’ll define an hierarchy of languages. Since is already taken (see this paper for the definition) we’ll refer to our resulting -like hierarchy as subspace-.

**The AC hierarchy**

Suppose we have a (classical) computer which is able to compute the AND, OR, or NOT, of arbitrarily many boolean variables at unit cost, i.e., in one clock cycle. The number is called the *fan-in* of the gate, and since this number is allowed to be arbitrarily large, the fan-in is said to be *unbounded*. It then makes sense to ask what sorts of questions can be answered by such computers when they can execute circuits comprised of several such ANDs and ORs in succession. This brings us to the definition of the hierarchy:

Definition 1Let be boolean variables and let . We define to be the class of languages that can be decided byuniform familiesof circuits with unbounded fan-in, polynomial size, and depth (thus constant depth if ).

Even the case of the above is interesting, and it’s precisely this class we’ll try and understand in the quantum setting.

Before moving on let’s consider an example.

Example 1Let be boolean variables. Consider the circuit

This circuit involves one big OR of a bunch of ANDs (computed in parallel). Thus this circuit has depth 2 and the problem it decides belongs to . In general every DNF formula belongs to .

An important result in classical complexity theory due originally to Furst, Saxe, and Sipser (later refined by Yao, with optimal result due to Håstad) shows that PARITY is *not* in . (The PARITY of bits calculates if there is an even number of ‘s) This is the result we are hoping to generalise in this series of posts.

**Subspace circuits**

What I want to introduce here is a hierarchy of languages which can be decided by special hypothetical quantum computers which can compute *subspace joins*, *subspace intersections*, and *subspace complements* at unit cost. For want of a better word we’ll call a composition of these operations a *subspace circuit*. We argued in the previous post (and intend to continue arguing about in future posts) that these putative quantum computers aren’t too implausible: a standard quantum computer should be able to simulate them with a polynomial overhead.

To make the definition a little easier to state I’ll set up some notation. Let be the hilbert space of qubits (isomorphic to ) and let be subspace projectors in (the set of bounded operators on ). We call this collection of projectors *literals* — these are meant to be very simple, i.e., each is meant to be a projector which acts nontrivially on one or two qubits. We say that the subspace defined by the subspace join

has *fan-in* . Similarly the subspace defined by the intersection

has *fan-in* . We’ll often use the notation to denote the *subspace complement* .

Example 2Consider qubits. Let , . Note that . Consider the following subspace

This subspace is the spanned by two strings (assuming that is even), namely, and . Physicists will recognise this subspace as the ground-eigenspace of the Ising model.

Suppose that we have a set of subspaces defined by joins or intersections of literals. If we compute the subspace join

or subspace intersection

of the ‘s then we say that the subspace is defined by a subspace circuit of depth . I hope that the general definition is now clear: a *subspace circuit* of depth is then a sequence subspace joins and subspace intersections of a collection of literals.

Suppose that is a subspace defined by a subspace circuit of depth . Then there is a natural quantum boolean function associated with this subspace projector, namely, When we say that is defined by a subspace circuit, we mean this QBF.

**The subspace-AC hierarchy**

I hope the definition should be fairly obvious now

Definition 2 (First try)Let denote the hilbert space of qubits and let . We define subspace- to be the class of languages that can be decided by measuring on QBFs defined byuniform familiesof subspace circuits with unbounded fan-in, polynomial size, and depth (thus constant depth if ).

Ok there is obviously a problem with this definition because measuring a QBF on an initial state is not deterministic. So we need to revise the definition to take account of this:

Definition 3 (Second try)Let denote the hilbert space of qubits and let . Then the language is in subspace- if there exists a QBF defined by auniform familyof subspace circuits with unbounded fan-in, polynomial size, and depth (thus constant depth if ) such that

and

In words: a class of problems is in the class subspace- if there is some QBF defined by a subspace circuit of depth such that when is measured on the all-zeros state it yields (i.e., “it accepts”) significantly more often than it yields (i.e., “it rejects”).

**Discussion**

Why would anyone want to define subspace circuits? For the physicists: one answer, I think, is that subspace circuits provide an extremely concise way to specify ground eigenspaces. These subspaces are notoriously difficult to understand, and if this analogy between AND and subspace intersection etc. plays out then I hope we can learn more about the general structure of ground eigenspaces of locally interacting quantum spin systems.

For computer scientists: since LOCAL HAMILTONIAN is complete for {\sf QMA} it is certainly tempting to hope that any results for the hierarchy afforded by subspace- will lead to new insight into the structure of {\sf QMA}-complete problems.

I hope it is now becoming clear what I’m trying to do in this series of posts: I’m trying to pursue what I feel is close analogy between AND and OR gates and subspace intersections and joins. Lots is known about circuits comprised of ANDs and ORs and I’m hoping that these results will generalise semi-easily!

In the next posts I want to start the study of subspace- in earnest and try to start generalising some results about .