<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-26T13:22:20.453Z
2011-03-26T13:22:20.453Z
Joe Fitzsimons
<p>The word <em>must</em> 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:</p>

<p>Quantum mechanics is <em>reversible</em>. 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 <em>most</em> 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. </p>

<p>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.</p>

<p>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. </p>

<p>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 <em>permutation matrix</em>, 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.  </p>

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

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

CC BY-SA 2.5
2011-03-26T16:02:00.613Z
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]
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-26T16:03:26.087Z
[cont] using only reversible gates. This circuit is also a valid quantum circuit that computes the desired operator $U$.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-03-27T01:52:01.567Z
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)’
Casebash
CC BY-SA 2.5
2011-03-26T08:11:18.193Z
2011-03-26T08:11:18.193Z
Shaun Harker
<p>I was reading <a href="http://arxiv.org/abs/quant-ph/0305045" rel="nofollow">Quantum Computation Explained to my Mother</a>.</p>

<p>While considering the following problem:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>It then makes the following claim:</p>

<blockquote>
  <p>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)’</p>
</blockquote>

<p>How come?</p>

<quantum-computing>
Quantum evolutions
Casebash
# Quantum evolutions

(Asked by: username_0 on 2011-03-26)

I was reading [Quantum Computation Explained to my Mother](http://arxiv.org/abs/quant-ph/0305045).

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?

**Tags:** quantum-computing


---

## 2 answers

### Answer by username_2 on 2011-03-26. Score: 6 | Accepted answer

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

> **Comments:**
> **username_3**: 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]  
> **username_3**: [cont] using only reversible gates. This circuit is also a valid quantum circuit that computes the desired operator $U$.  
> **username_0**: 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)’  

---

### Answer by username_1 on 2011-03-26. Score: 3

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.


---

