An AC hierarchy based on subspace circuits

[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 {f} defined by special circuits (not quantum circuits) which I’ll provisionally call subspace circuits. Using these special circuits I’ll define an {\mathbf{AC}} hierarchy of languages. Since {\mathbf{QAC^j}} is already taken (see this paper for the definition) we’ll refer to our resulting {\mathbf{AC}}-like hierarchy as subspace-{\mathbf{AC}}.

The AC hierarchy

Suppose we have a (classical) computer which is able to compute the AND, OR, or NOT, of arbitrarily many boolean variables {x_1, x_2, \ldots, x_m} at unit cost, i.e., in one clock cycle. The number {m} 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 {\mathbf{AC}} hierarchy:

Definition 1 Let {x_1, x_2, \ldots, x_n} be {n} boolean variables and let {j\in \mathbb{N}}. We define {\mathbf{AC^j}} to be the class of languages that can be decided by uniform families of circuits with unbounded fan-in, polynomial size, and depth {O(\log^j(n))} (thus constant depth if {j=0}).

Even the case {j=0} 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 1 Let {x_1, x_2, \ldots, x_{n}} be {n} boolean variables. Consider the circuit

\displaystyle  f(x_1, x_2, \ldots, x_{n}) = \bigvee_{j=1}^{n-1} (x_j\wedge x_{j+1}). \ \ \ \ \ (1)

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 {\mathbf{AC^0}}. In general every DNF formula belongs to {\mathbf{AC^0}}.

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 {\mathbf{AC^0}}. (The PARITY of {n} bits calculates if there is an even number of {+1}‘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 {\mathcal{H}} be the hilbert space of {n} qubits (isomorphic to {\mathbb{C}^{2^n}}) and let {c_1, c_2, \ldots, c_k} be {k} subspace projectors in {\mathcal{B}(\mathcal{H})} (the set of bounded operators on {\mathcal{H}}). 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 {P} defined by the subspace join

\displaystyle  P = \bigvee_{j=1}^{m} c_j

has fan-in {m}. Similarly the subspace {Q} defined by the intersection

\displaystyle  Q = \bigwedge_{j=1}^{m} c_j,

has fan-in {m}. We’ll often use the notation {\overline{P}} to denote the subspace complement {\overline{P} \equiv \mathbb{I}-P}.

Example 2 Consider {n} qubits. Let {c_j = \mathbb{I}_{1, \cdots, j-1}\otimes(|00\rangle_{j,j+1}\langle 00|+|11\rangle_{j,j+1}\langle 11|)\otimes \mathbb{I}_{j+2, \cdots, n}}, {j \in [n-1]}. Note that {\mbox{supp}(c_j) = \{j, j+1\}}. Consider the following subspace

\displaystyle  P = \bigwedge_{j=1}^{n-1} \overline{c_j}. \ \ \ \ \ (2)

This subspace is the spanned by two strings (assuming that {n} is even), namely, {|0101\cdots 1\rangle} and {|1010\cdots 0\rangle}. Physicists will recognise this subspace as the ground-eigenspace of the Ising model.

Suppose that we have a set of subspaces {\{P_j\}_{j=1}^{m}} defined by joins or intersections of literals. If we compute the subspace join

\displaystyle  J = \bigvee_{j=1}^m {P_j}

or subspace intersection

\displaystyle  I = \bigwedge_{j=1}^m {P_j}

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

Suppose that {P} is a subspace defined by a subspace circuit of depth {d}. Then there is a natural quantum boolean function {f} associated with this subspace projector, namely, {f = \mathbb{I}-2P} When we say that {f} 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 {\mathcal{H}} denote the hilbert space of {n} qubits and let {j\in \mathbb{N}}. We define subspace-{\mathbf{AC^j}} to be the class of languages that can be decided by measuring on {|00\cdots 0\rangle} QBFs defined by uniform families of subspace circuits with unbounded fan-in, polynomial size, and depth {O(\log^j(n))} (thus constant depth if {j=0}).

Ok there is obviously a problem with this definition because measuring a QBF {f} on an initial state {|00\cdots0\rangle} is not deterministic. So we need to revise the definition to take account of this:

Definition 3 (Second try) Let {\mathcal{H}} denote the hilbert space of {n} qubits and let {j\in \mathbb{N}}. Then the language {L} is in subspace-{\mathbf{AC^j}} if there exists a QBF {f} defined by a uniform family of subspace circuits with unbounded fan-in, polynomial size, and depth {O(\log^j(n))} (thus constant depth if {j=0}) such that

\displaystyle  \forall x \in L, \langle \mathbf{0}|f|\mathbf{0}\rangle \le -1/3, \ \ \ \ \ (3)


\displaystyle  \forall x \not\in L, \langle \mathbf{0}|f|\mathbf{0}\rangle \ge 1/3. \ \ \ \ \ (4)

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


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-{\mathbf{AC^j}} 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-{\mathbf{AC^j}} in earnest and try to start generalising some results about {\mathbf{AC^0}}.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: