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