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 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-.

Quantum 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 functions. I hope to show how to connect the quantum circuit model with quantum boolean functions and also describe how the two operations: subspace join and subspace intersection we described in our discussion on quantum disjunctive normal forms are related to quantum circuits. Essentially I want to show that there is an efficient way to go between quantum circuits and qDNF formulae.

Influence 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 of posts are aimed at working out how this “natural” class, tentatively called qAC⁰,  should be defined; essentially I’ll just try and argue by analogy with the classical definition of AC⁰, as far as I can.

At the current time we have defined a representation of QBFs called quantum disjunctive normal form (qDNF). However, we haven’t actually related this to quantum circuits yet (it’s a representation, but there’s no guarantee that it has anything to do with natural quantum circuits), I intend to tackle this problem a little later. For the moment I think it might be interesting to develop a better understanding of qDNF formulae before moving on. To this end I want to discuss, in this post, a couple of (conjectured) results concerning the influence of qDNF formulae.

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.

Quantum boolean functions

In our recent paper Ashley and myself introduce the notion of a quantum boolean function (QBF) which is an operator which is simultaneously unitary and hermitian. Thus its eigenvalues are , which is where the “booleanness” comes from. (Recall that a boolean function on a set is any function .)

Why would anyone want to define such a thing? Well, we provide several arguments in our paper, the most compelling, I think, being that the theory of quantum boolean functions is at least as general as that of both quantum error correction and quantum algorithms for decision problems. Another motivation is that, as we argue over the next 40 or so pages, the theory of boolean functions generalises in many nice ways to the quantum world.

But, there are two important points on which the paper does not deliver, namely, on the promises that: (a) a complete theory of quantum boolean functions would provide quantum circuit lower bounds (eg. something like this); and (b) a quantum PCP theorem would emerge from this line of study. Classically the theory of boolean functions does supply many of the tools required for circuit lower bounds and various incarnations of the PCP theorem.

Highlights of the theory of QBFs

I feel that the main contribution we make toward the theory of QBFs is that of identifying a natural quantum version of fourier analysis for QBFs. Rather than review the theory of fourier analysis for boolean functions I’ll just refer you to the post by Gil Kalai on the entropy influence conjecture which contains a very readable account. Essentially, since the set of bits can be identified in a natural way with the finite group you can use the theory of fourier analysis over finite groups to study boolean functions.

Quantumly things are a bit weirder. A quantum boolean function on qubits is both a unitary and hermitian operator on the hilbert space . Now things are noncommutative and there is no really compelling way to identify a basis of with which doesn’t break some kind of desirable symmetry. Nonetheless, as we argue, there is a natural way to replace the characters of with natural set of operators in such a way that: (i) the standard fourier analysis for boolean functions is recovered when they are embedded as diagonal operators; and (ii) the nice results about the analysis of boolean functions generalise naturally. It would come as no surprise to anyone working in quantum information that this natural set of operators is given by the set of tensor products of the pauli matrices , , , and .

The quantum version of the fourier transform of a QBF is thus , where and with . If is a classical boolean function represented as a matrix with on the diagonal then we recover the classical fourier transform of where now the fourier coefficients are zero unless , whereupon is the classical fourier coefficient corresponding to the subset .

Some lessons learnt while thinking about QBFs

During the course of our research into QBFs we developed a couple of intuitions about them which is difficult to communicate in a paper, and which I think are valuable to share here.

1. Any result about boolean functions which is proved using only fourier analysis techniques, including those exploiting hypercontractivity, maps over essentially unmodified to the quantum domain by replacing the sum over subsets with the sum over products of pauli operators.
2. Any result which uses combinatorial techniques is probably either false quantumly, or difficult to prove.

I am very enthusiastic about the theory of quantum boolean functions and I hope that the theory of QBFs can, in time, deliver the promised results about quantum circuit lower bounds and quantum PCP, and in the following posts I want to expand on this in some depth.