## 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 $\vee$ and subspace intersection $\wedge$ 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.

### QBFs from quantum algorithms for decision problems

One of the primary motivations to think about QBFs is that they are intimately related to quantum algorithms for decision problems. The idea is as follows. Suppose that $\mathcal{U} = U_1U_2\cdots U_l$ is a quantum circuit of depth $l$, where $U_j$, $j \in [l]$, are chosen from primitive universal set of quantum gates, eg., CNOT, Hadamard, and T. And suppose that $\mathcal{U}$ is intended to decide whether some question has a yes or no answer. The way this is usually done is to initialise the quantum computer into the state

$|00\cdots 0\rangle$

apply the quantum circuit to yield

$\mathcal{U}|00\cdots0\rangle$

and then measure the resulting state to find out the answer: by adding extra qubits one can always arrange for the answer to be in some prespecified qubit, say the $n$th one. If the answer is “yes” then the $n$th qubit is meant to be in the state $|1\rangle$ and, otherwise, in the state $|0\rangle$.

How is this related to QBFs? The answer is that there is a natural QBF $f$ associated with any quantum circuit for a decision problem. The way to do this is to think terms of the Heisenberg picture. Recall that in quantum mechanics we obtain information about the quantum state of the system by making measurements of hermitian operators $M$ on the system. If the system first undergoes dynamics according to some quantum circuit $\mathcal{U}$ then, in the Schroedinger picture, we measure $M$ on $\mathcal{U}|00\cdots 0\rangle$ to obtain our information. But this is completely equivalent to measuring $\mathcal{U}^\dag M \mathcal{U}$ on the initial state $|00\cdots 0\rangle$. What we’ve down here is pulled back the dynamics due to the circuit onto the observable; this is the Heisenberg picture: we always pull back the dynamics onto the final observables.

In the case of a decision problem there is only one observable we actually care about, namely, the operator $\sigma_n^z = \left(\begin{smallmatrix} 1 & 0 \\ 0 & -1 \end{smallmatrix}\right)$ which tells us if the answer is yes (i.e. we measure ${-1}$) or no (i.e. we measure ${1}$). So to work out if the answer is yes or no measure $\sigma_n^z$ on $\mathcal{U}|00\cdots 0\rangle$. This is equivalent, in the Heisenberg picture, to measuring $f = \mathcal{U}^\dag \sigma_n^z\mathcal{U}$ on $|00\cdots 0\rangle$. The observable $f$ is our QBF.

### Quantum circuits for qDNFs

A classical boolean function $f$ can be represented as a disjunctive normal form formula. This provides a way to actually compute $f$ which is efficient if the formula isn’t too large. Let’s now have a go at finding a quantum circuit for a qDNF formula. It turns out that this isn’t so easy, as, unlike in the classical case, the individual clauses don’t always commute (I’ll explain what this means presently). Before we get onto this I want to show how any QBF $f$ can be represented with a qDNF formula

$f = \mathbb{I}-2\bigvee_{j=1}^{m} c_j$

where every clause commutes ${[c_j, c_k] = 0}$. It turns out that is “easy”! Just work out the eigenvalue decomposition of $f$

$f = \sum_{j=1}^{2^n} \lambda_j |\lambda_j\rangle\langle \lambda_j|$

and, arrange for the eigenvalues $\lambda_j \in \{-1,+1\}$ to be in increasing order, i.e., so that all the ${-1}$ eigenvalues appear first followed by the ${+1}$ eigenvalues. Now let ${c_j = |\lambda_j\rangle\langle\lambda_j|}$. If ${m}$ is the dimension of the accepting space, i.e., the number of negative eigenvalues, then we have the desired result. One thing to note, however, is that the support of the conjunctive clauses ${c_j}$ is vast, it is ${[n]=\{1,2,\ldots, n\}}$. Anyways, this argument at least shows that to every quantum circuit for a decision problem there is at least one qDNF formula for the corresponding “decision” QBF ${f}$.

Naturally you might complain that the qDNF obtained above is horribly inefficient as one might (and probably does) need exponentially many clauses, and, worse, each clause may be really difficult to write down, as they are ${2^n\times 2^n}$ matrices. I’ll address these problems a bit later when I hope to show, using Kitaev’s construction that if ${f}$ arises from an efficient quantum circuit then there is an efficient qDNF representation for ${f}$.

Let’s now move on to proving the other direction, namely, finding quantum circuits which allow us to compute a QBF $f$ represented as a qDNF formula. Well, by compute what we really mean is measure on some arbitrary input state ${|\psi\rangle}$. The interesting thing is that I think, in general, there may be no efficient way to measure a qDNF formula ${f}$ exactly, even if the qDNF formula is rather compact. The problem, as we see, comes from the fact that the clauses ${c_j}$ don’t commute. Nonetheless, it should be possible to at least systematically approximate the measurement statistics ${\langle \psi|f|\psi\rangle}$ of ${f}$ efficiently.

Let’s begin our discussion with a simple example: suppose we have a QBF ${f}$ defined by a qDNF formula with just two clauses ${c}$ and ${d}$

${f = \mathbb{I}-2c\vee d}$

Given this QBF essentially what we want to do is check if a given input state ${|\psi\rangle}$ is in the subspace defined by ${c\vee d}$ or not. Physically this ought to be easy: i.e. ${c}$ and ${d}$ are projectors, hence they are measurement operators, so, naively, all we need to do is perform the dichotomic measurement ${\{c, \mathbb{I}-c\}}$ followed by the measurement ${\{d, \mathbb{I}-d\}}$ and accept if we find the first outcome in either of the measurements. Unfortunately this doesn’t work because the operators ${c}$ and ${d}$ don’t necessarily commute: measuring the first operator may disturb the the outcome of the second measurement!

The way out of this problem is to focus instead on the rejecting subspace of ${f}$ which is given by

${R = (\mathbb{I}-c)\wedge(\mathbb{I}-d)}$.

Having gotten rid of the nasty subspace join we get to work on deciding if a state ${|\psi\rangle}$ lies in ${R}$ or not.

Notice that ${R}$ is the ground-eigenspace of the hamiltonian ${H = c + d}$. Now we can see that we are asking if a quantum state is in the ground space of some physical system, which is equivalent to measuring the energy of this system. So the answer is clear now: we measure the energy by measuring the operator ${H}$ and output ${1}$ if the energy is above ${0}$ and output ${1}$ otherwise. It is at this point that we encounter problems: we can only measure the energy of an hermitian operator to some finite precision with a finite quantum circuit. Thus the depth of the quantum circuit which implements this measurement will scale with the accuracy ${\epsilon}$ that we want. This quantum circuit is given by a discretisation of von Neumann’s measurement prescription, and is a fundamental building block in quantum algorithms, where it is known, in one guise, as phase estimation.

I’ll now briefly describe von Neumann’s measurement prescription as applied to our situation. Then I’ll sketch how to get a quantum circuit from this prescription. We begin with our quantum computer initialised in the input state ${|\psi\rangle}$ and we adjoin an ancilla subsystem (which is a continuous quantum degree of freedom, eg. a harmonic oscillator or a free particle on the line) initialised in ${|0\rangle}$. This ancilla system is our “meter” which is meant to indicate the energy of our quantum state. The further to the right the particle is located, the more energetic our state must be.

Thus our system is in the state

${|\psi\rangle|0\rangle}$.

We then evolve this system according to the hamiltonian

${K = H\otimes \widehat{p}},$

for a time $t$, where ${\widehat{p}}$ is the momentum operator. The system ends up in the state

${e^{itK}|\psi\rangle|0\rangle}$.

If we write ${|\psi\rangle}$ in the eigenbasis of ${H}$  as ${|\psi\rangle = \sum_{j=1}^{2^n} \psi_j |E_j\rangle}$ we see the system ends up in the state

${\sum_{j=1}^{2^n} \psi_j |E_j\rangle e^{itE_j\widehat{p}}|0\rangle}$,

But since ${D_x = {e^{ix\widehat{p}}}}$ is the displacement operator by distance ${x}$ we find that

${\sum_{j=1}^{2^n} \psi_j |E_j\rangle |tE_j\rangle}.$

Our actual measurement, which will have the right statistics, is then implemented by measuring the ancilla and outputting ${1}$ if the ancilla particle has been displaced from the origin at all. This measurement is described by the measurement ${\{P_{\le}, P_{>}\}}$ where ${P_{>}}$ is the projection operator on the ancilla particle which checks if the particle is strictly to the right of the origin.

Now, obviously the above procedure cannot be directly implemented on a quantum computer which only has access to qubits. (Even if we allowed the quantum computer to access a free quantum particle we’d need infinite energy to implement the measurement ${\{P_{\le}, P_{>}\}}$ as we’d need to resolve the particles position to infinite accuracy.) This problem has actually been solved and a very clean discretisation of the above procedure has been developed which clearly shows the tradeoff between desired accuracy and the fineness of the discretisation of the free particle’s position. Roughly speaking, the idea is to discretise the ancilla particle’s position and to simulate the time evolution due to the natural discretisation of ${K}$. I won’t go into the technical details at the moment.

The generalisation of this argument to any number of clauses should now be evident. There are quite a few tradeoffs that need to be investigated here involving the width of the clauses, the accuracy of the energy measurement, and the errors arising from the quantum circuit implementing the measurement. I haven’t investigated the details yet, but I hope I’ve convinced you that this procedure is efficient for a finite accuracy ${\epsilon}$ and width ${w}$.

So we’ve learnt how to efficiently make a measurement with a quantum computer which allows us to sample the statistics of a QBF ${f}$ represented compactly with a qDNF formula. We still have to discuss how to get compact qDNFs from compact quantum circuits. I’ll describe this later I hope.