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 \pm1, which is where the “booleanness” comes from. (Recall that a boolean function on a set X is any function f:X\rightarrow \{0,1\}.)

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 n bits can be identified in a natural way with the finite group (\mathbb{Z}/2\mathbb{Z})^{\times n} 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 onn qubits is both a unitary and hermitian operator on the hilbert space \mathbb{C}^{2^n}. Now things are noncommutative and there is no really compelling way to identify a basis of \mathbb{C}^{2^n} with (\mathbb{Z}/2\mathbb{Z})^{\times n} which doesn’t break some kind of desirable symmetry. Nonetheless, as we argue, there is a natural way to replace the characters of (\mathbb{Z}/2\mathbb{Z})^{\times n} 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 {\sigma^0=(\begin{smallmatrix}1&0\\ 0&1\end{smallmatrix})}, {\sigma^1=(\begin{smallmatrix}0&1\\1&0\end{smallmatrix})}, {\sigma^2=(\begin{smallmatrix}0&-i\\i&0\end{smallmatrix}}), and {\sigma^3=(\begin{smallmatrix}1&0\\ 0&-1\end{smallmatrix})}.

The quantum version of the fourier transform of a QBF f is thus f = \sum_{\mathbf{s}} \widehat{f}(\mathbf{s}) \chi_{\mathbf{s}}, where \chi_{\mathbf{s}} = \sigma_1^{s_1}\otimes \cdots \otimes \sigma_n^{s_n} and \mathbf{s} = s_1s_2\cdots s_n with s_j \in \{0,1,2,3\}. If f is a classical boolean function represented as a matrix with \pm1 on the diagonal then we recover the classical fourier transform of f where now the fourier coefficients \widehat{f}(\mathbf{s}) are zero unless \mathbf{s}\in \{0,3\}^{\times n}, whereupon \widehat{f}(\mathbf{s}) is the classical fourier coefficient corresponding to the subset S = \mbox{supp}(\mathbf{s}).

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.


3 Responses to Quantum boolean functions

  1. Gil Kalai says:

    Dear Tobias, this is very interesting! What are the basic examples of noise-stable quantum Boolean functions? (analogous to majority and weighted majority in the Boolean case)?

  2. tobiasosborne says:

    Dear Gil,

    That is a really interesting question! Naturally, because classical Boolean functions are trivially quantum Boolean functions, majority is a noise-stable QBF. But this is really boring as an answer. At the moment I don’t have a proof but I think the following construction will result in interesting noise-stable QBFs.

    The idea is based on the following construction for majority {f}: one can think of majority as identifying the set {S} of strings which are within hamming distance {(n-1)/2} (supposing that n is odd) of the string {00\cdots 0}. (Majority evaluates to {0} on this set and to {1} on the complement on this set.) Now, this construction is totally general: we can construct many noise-stable functions in this way. One just starts with some string {\mathbf{x} = x_1x_2\cdots x_n} and constructs the set {S_\mathbf{x} = \{\mathbf{y}\,|\, d(\mathbf{x},\mathbf{y}) \le (n-1)/2\}} of strings within a hamming distance {(n-1)/2} away from {\mathbf{x}}. This, in turn, defines a noise stable function {f_{\mathbf{x}}} via {f_\mathbf{x}(\mathbf{y}) = 0} if {d(\mathbf{x},\mathbf{y}) \le (n-1)/2}. Of course this function is trivially related to majority by first applying some bit flips on the input and then calculating majority. So the set of noise-stable functions {f_{\mathbf{x}}} defined by this process are totally boring classically.

    However, when we quantise this construction things are much more interesting as there are many ways to quantise the hamming ball notion. I’ll describe what I mean in terms of a quantum hamming ball generalisation due (I think) to Andreas Winter.

    Suppose we have some quantum state {|\psi\rangle} of n qubits. We define the quantum hamming ball {A_0} of radius zero to be the subspace spanned by {|\psi\rangle}. We then define the quantum hamming ball {A_1} of radius {1} to be a subspace containing {A_0} and also containing states which are locally different from {|\psi\rangle}. We define what this means precisely in terms of displacement operators: for any projection {A}, we define the displacement operator: \displaystyle  \mathcal{D}(A) \equiv \bigvee_{j=1}^n\bigvee_{\alpha = 0}^3 \sigma_j^\alpha A \sigma_j^{\alpha}, \ \ \ \ \ (1)
    where {\sigma_j^{\alpha}} is the pauli sigma matrix acting on qubit {j}. Thus, the displacement operator takes the subspace join of the subspace {A} and all subspaces related to it by conjugation via a single pauli sigma matrix. We also define the {k}th displacement operator via \displaystyle  \mathcal{D}^{(j)}(A) \equiv \bigvee_{j_1 < j_2 < \ldots < j_k}\bigvee_{\alpha_1, \alpha_2, \ldots, \alpha_k = 0}^3 (\sigma_{j_1}^{\alpha_1}\otimes \sigma_{j_2}^{\alpha_2} \otimes \cdots \otimes\sigma_{j_k}^{\alpha_k}) A (\sigma_{j_1}^{\alpha_1}\otimes \sigma_{j_2}^{\alpha_2} \otimes \cdots \otimes\sigma_{j_k}^{\alpha_k}). \ \ \ \ \ (2)
    Note that {\mathcal{D}^{(j)}(A)} is not a linear operator.

    It is relatively easy to establish the following lemma

    Lemma 1 Let {A} be a subspace. Then \displaystyle  \mathcal{D}^{(j)}(A) = {\mathcal{D}\circ\mathcal{D}\circ \cdots \circ \mathcal{D}}(A). \ \ \ \ \ (3)

    Proof: The result follows upon noting that the hilbert space join operation, also known as the subspace sum operation, is associative: {A\vee (B\vee C) = (A\vee B)\vee C}. ◻

    Remark 2 Note that the space of all subspaces of {\mathcal{H}} does not form a lattice under the subspace join and intersection operations.

    Using the displacement operator we define the quantum hamming ball of radius {t} to be the subspace {A_t \equiv \mathcal{D}^{(t)}(A)}

    So now we have all the prerequisite tools to define a (conjectured) class of noise-stable QBFs: take any quantum state {|\psi\rangle} and construct the ball (which is a subspace) {A_{(n-1)/2}}, where {A = |\psi\rangle \langle \psi|}. Then define the QBF \displaystyle  f = \mathbb{I}-2A_{(n-1)/2}. \ \ \ \ \ (4)
    The set of such QBFs is not trivially related to majority, but I am willing to conjecture that such QBFs are noise stable.

    (I’ll be posting more about the quantum hamming ball in the future when I’ll discuss some joint work with Andreas Winter on a quantum generalisation of Talagrand’s inequality.)

  3. Gil Kalai says:

    Dear Tobias, many (belated) thanks for the reply. There are various reasons for looking now again on noise stability for non monotone Boolean functions and quantum functions. One reason are exciting conjectures related to works of Khot and Moshkovitz, other reasons comes from correlation inequalities that started from Talagrand’s inequality (I believe the same one), and yet another reason comes from the following (still a bit vague) conjecture: “There are no (uniformly) noise-stable quantum error correcting codes.” (In contract to majority functions which are uniformly noise-stable but gives higher and higher quality as a function of the number of qubits used for the encoding.)

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: