Quantum evolutions

Question

I was reading Quantum Computation Explained to my Mother.

While considering the following problem:

Problem 1 Suppose we are given a mysterious boolean operator F (a black box) which takes one boolean value and returns another boolean value. We want to calculate Xor(F(False), F(True)), i.e. the boolean value returned by Xor when applied to the two possible results of F. But we are allowed to use the mysterious boolean operator F only once.

It then makes the following claim:

We assume we have access, for one use only, to a physical device which implements F as a quantum evolution. This quantum evolution U must take ‘True, False’ into ‘True, F(True)’ ‘False, False’ into ‘False, F(False)’

How come?

Answer 1

The word must is not correct, as you could do equally well taking (True,True) and (False, True) to those outputs. What they really mean is that you ought to make a construction that essentially accomplishes the same thing. What they are trying to accomplish is to encode an irreversible function in a reversible way. Let's clarify this:

Quantum mechanics is reversible. This arises from the restrictions on the matrix $U$: it is unitary! Unitary matrices are, among other things, invertible. Thus, from an information-theoretic perspective you can't possibly hope to directly encode any function into a unitary (quantum) evolution which involves the loss of information. But most practical computations involve irreversible bit operations which lose information. For example, of the logic gates OR, AND, and NOT, only NOT is reversible. Another example: I cannot determine from the sum of two numbers what the summands were.

Thus, if we are interested in performing some irreversible computation, we can't do it directly on a quantum computer; we need to do a larger, reversible computation, and recognize the irreversible thing we are interested in as living in this reversible computation somehow.

Fortunately, there is a simple trick to make this happen. The idea is to include the original question in the answer. This makes it quite easy to recover the question from the answer! This can be more carefully stated as follows: Given a function $f:X \rightarrow Y$ we construct an invertible function $F : X \times Y \rightarrow X \times Y$ such that $F(x, 0) = (x, f(x))$ for some specially chosen $0 \in Y$. It is an exercise to see that this is always possible: the trick is to see it can be extended to all $F(x, y)$ while maintaining invertibility.

So far so good: we see that we can make irreversible computations (encoded as non-invertible functions) hidden as slices of reversible computations (encoded as invertible functions). The last step is to translate from the invertible function $F$ to the quantum evolution $U$. To do this, we consider every possible classical input and output of $F$ as a pure (basis) state in the state space of the quantum system. Thus $F$ takes pure states to pure states in an invertible way. It turns out that this means $F$ has a matrix representation as a permutation matrix, which is a special type of unitary matrix (and hence a valid quantum evolution) which only has 0-1 entries. Thus, to summarize: a quantum evolution $U$ is obtained as the permutation matrix associated to the 1-1 correspondence $F$ represents.

We understand that $U$ implements $f$ in the following sense. To compute $f(x)$, first prepare the input state $\left\vert x, 0 \right>$. Next, apply $U$. Now we have the output state $\left\vert x, f(x) \right>$. Finally, measure $f(x)$.

The paper you ask about gives the construction for the case $X = Y = \{true, false\}$.

Answer 2

My interpretation is that the author is saying that for a Boolean function $f:\{0,1\}\to \{0,1\}$, "a quantum evolution" which implements this function is a unitary operator $U_f$ such that $U_f| x \rangle \otimes | y \rangle = | x \rangle \otimes | y \oplus f(x) \rangle$. (I assume he is only considering unitaries rather than CPTP maps, as this makes more sense in the context of Deutsch's algorithm). Here the second qubit is the output qubit. The reason two qubits are required is that not all boolean functions are reversible, and the ancilla is required in order to satisfy unitarity by making the evolution reversible. I believe this is the situation the author was trying to get across, as this is indeed how the oracle functions in the Deutsch algorithm.

Thus, the unitary has not fully been prescribed, but is of the general form $U_f = \sum_{x,y = 0}^1 \phi_{xy} |x\rangle\langle x| \otimes |y \otimes f(x) \rangle\langle y|$ where $\phi_{xy}$ are roots of unitary. This is the most general description of a unitary which implements the required functionality.

As Shaun mentioned, the algorithm would also work with an oracle which flipped the outputs, but that would no longer be the oracle for the same boolean function, and the whole point of the algorithm is to show that classical and quantum strategies require different numbers of calls to the same oracle.