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.
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 is a quantum circuit of depth , where , , are chosen from primitive universal set of quantum gates, eg., CNOT, Hadamard, and T. And suppose that 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
apply the quantum circuit to yield
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 th one. If the answer is “yes” then the th qubit is meant to be in the state and, otherwise, in the state .
How is this related to QBFs? The answer is that there is a natural QBF 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 on the system. If the system first undergoes dynamics according to some quantum circuit then, in the Schroedinger picture, we measure on to obtain our information. But this is completely equivalent to measuring on the initial state . 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 which tells us if the answer is yes (i.e. we measure ) or no (i.e. we measure ). So to work out if the answer is yes or no measure on . This is equivalent, in the Heisenberg picture, to measuring on . The observable is our QBF.
Quantum circuits for qDNFs
A classical boolean function can be represented as a disjunctive normal form formula. This provides a way to actually compute 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 can be represented with a qDNF formula
where every clause commutes . It turns out that is “easy”! Just work out the eigenvalue decomposition of
and, arrange for the eigenvalues to be in increasing order, i.e., so that all the eigenvalues appear first followed by the eigenvalues. Now let . If 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 is vast, it is . 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 .
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 matrices. I’ll address these problems a bit later when I hope to show, using Kitaev’s construction that if arises from an efficient quantum circuit then there is an efficient qDNF representation for .
Let’s now move on to proving the other direction, namely, finding quantum circuits which allow us to compute a QBF represented as a qDNF formula. Well, by compute what we really mean is measure on some arbitrary input state . The interesting thing is that I think, in general, there may be no efficient way to measure a qDNF formula exactly, even if the qDNF formula is rather compact. The problem, as we see, comes from the fact that the clauses don’t commute. Nonetheless, it should be possible to at least systematically approximate the measurement statistics of efficiently.
Let’s begin our discussion with a simple example: suppose we have a QBF defined by a qDNF formula with just two clauses and
Given this QBF essentially what we want to do is check if a given input state is in the subspace defined by or not. Physically this ought to be easy: i.e. and are projectors, hence they are measurement operators, so, naively, all we need to do is perform the dichotomic measurement followed by the measurement and accept if we find the first outcome in either of the measurements. Unfortunately this doesn’t work because the operators and 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 which is given by
Having gotten rid of the nasty subspace join we get to work on deciding if a state lies in or not.
Notice that is the ground-eigenspace of the hamiltonian . 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 and output if the energy is above and output 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 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 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 . 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
We then evolve this system according to the hamiltonian
for a time , where is the momentum operator. The system ends up in the state
If we write in the eigenbasis of as we see the system ends up in the state
But since is the displacement operator by distance we find that
Our actual measurement, which will have the right statistics, is then implemented by measuring the ancilla and outputting if the ancilla particle has been displaced from the origin at all. This measurement is described by the measurement where 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 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 . 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 and width .
So we’ve learnt how to efficiently make a measurement with a quantum computer which allows us to sample the statistics of a QBF 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.