In a previous post I worked through the arithmetic of the Deutsch quantum algorithm to show that it works, but I avoided attempting to explain why any of it works. In this post I’ll explain one corner of the circuit: why the gate implementing the function tested by the algorithm outputs the exclusive-OR (XOR) of \(y\) and \(f(x)\): \(y \oplus f(x)\). See the picture below (Mermin, 2007, p. 42). The question is, why is that output not just \(f(x)\), since that’s what the circuit is supposed to compute?
There are two parts to the explanation. Firstly, quantum gates have to be reversible, because that’s how the physics works. The reason for that is far bigger than this blog post and I’m not a physicist. Try Richard Feynman’s (1985) explanation. If we believe Feynman, then the reason XOR appears in many algorithms is easy to grasp. Below I’ll expand the arithmetic provided by Mermin (2007, p. 37, the paragraph around equation 2.3).
Let’s start with the punchline.
Double application of \(U_f\) leads to the bottom register of the circuit evaluating to \([y \oplus f(x)] \oplus f(x)\), which is equivalent to \(y \oplus [f(x) \oplus f(x)]\) by the associativity of \(\oplus\). This simplifies to \(y\), as the table below shows for the four combinations of \(y\) and \(f(x)\):
| \(y\) | \(f(x)\) | \(\overbrace{f(x) \oplus f(x)}^{\textstyle z}\) | \(y \oplus z\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 |
Note how \(f(x) \oplus f(x)\) cancels out \(f(x)\), leaving \(y\), so the first and last column are equal. The XOR ensures that double application of \(U_f\) gives us \(y\) again!
Another way to write this without the table:
\([y \oplus f(x)] \oplus f(x)\)
= { associativity of \(\oplus\) }
\(y \oplus [f(x) \oplus f(x)]\)
= { since \(1 \oplus 1 = 0\oplus 0 = 0\) }
\(y \oplus 0\)
= { definition of \(\oplus\) }
\(y\).
Now we just have to show that
\(U_f U_f (|x\rangle \otimes |y\rangle)\)
sends us to
\(| x\rangle \otimes | y \oplus f(x) \oplus f(x)\rangle\)
so that the sums above are relevant:
\(U_f U_f (|x\rangle \otimes |y\rangle)\)
= { by application of \(U_f\) }
\(U_f (|x\rangle \otimes |y \oplus f(x)\rangle)\)
= { by application of \(U_f\) again }
\(|x\rangle \otimes |[y \oplus f(x)] \oplus f(x)\rangle\).
We’re done.
More on reversibility
The requirement that gates are reversible is often described by saying that quantum algorithms change the state of qubits using unitary transformations. A matrix \(U\) representing such a transformation is unitary if and only if \(U U^\dagger = I\), where \(I\) is the identity matrix and \(U^\dagger\) is the conjugate transpose of \(U\) (see Adedoyin et al., 2022). If the elements of \(U\) don’t have any imaginary parts then \(U^\dagger\) is just the transpose of \(U\).
Let’s try it for the most complicated (relatively speaking!) function from the Deutsch problem, \(U_{f_2}\):
As we saw, this is represented by the following matrix:
\(U_{f_2} = \mbox{CNOT} (I \otimes X) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)
Is it unitary?
\(U_{f_2} U_{f_2}^\dagger\)
=
\(\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)
=
\(\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\)
=
\(I\).
Yes.
References
Feynman, R. P. (1985). Quantum mechanical computers. Optics News, 11(2), 11–20.
Mermin, N. D. (2007). Quantum computer science: an introduction. Cambridge University Press.
J., A., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., Lemons, N., Lin, S., Malyzhenkov, A., Mascarenas, D., Mniszewski, S., Nadiga, B., O’Malley, D., Oyen, D., Pakin, S., … Lokhov, A. Y. (2022). Quantum Algorithm Implementations for Beginners. ACM Transactions on Quantum Computing, 3(4), 1–92.