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?


2 Answers 2


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\}$.

  • 1
    $\begingroup$ I would like to add that, while this is correct from a linear algebra perspective, if you actually try to construct the quantum operator U by enumerating all the basis vectors and explicitly computing the matrix, you'll run in exponential time, negating any performance benefit from quantum computation. In the problem above the operator U is assumed to be already provided as a black-box, but in the general case, if you have a logic circuit that computes $x\rightarrow F(x)$, you can construct in polynomial time a reversible logic circuit that computes $(x,y)\rightarrow (x,y\oplus F(x))$ [cont] $\endgroup$ Mar 26, 2011 at 16:02
  • 1
    $\begingroup$ [cont] using only reversible gates. This circuit is also a valid quantum circuit that computes the desired operator $U$. $\endgroup$ Mar 26, 2011 at 16:03
  • 1
    $\begingroup$ Okay, so the must is a qualified must. That is, if we want to convert our non-invertible operator to an invertible operator using the method described and we choose False to be our 0, then the device must take ‘True, False’ into ‘True, F(True)’ ‘False, False’ into ‘False, F(False)’ $\endgroup$
    – Casebash
    Mar 27, 2011 at 1:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.