This is a short note on the 1-qbit version of the Deutsch-Jozsa algorithm. Instead of describing the algorithm and explaining how it works, I’ve attempted to work backwards from the problem statement. This helped me understand the concept a little better.

# Problem Statement

Given a quantum implementation of a 1 bit function $f$, $U_f$, that performs the operation $U_f \left\vert x y \right\rangle = \left\vert x \right\rangle \left\vert f(x) \oplus y \right\rangle$, compute $f(0) \oplus f(1)$ with just one query to $U_f$. $\oplus$ is the binary XOR operation and the weird $\left\vert f(x) \oplus y \right\rangle$ bit in $U_f$ is a trick to convert a possibly irreversible $f$ to a reversible circuit (all quantum circuits are reversible so irreversible functions cannot be implemented as-is as quantum circuits).

# Construction

Let’s assume we’re looking for a quantum circuit that will give a deterministic answer for $f(0) \oplus f(1)$.

For this to happen, we’d want one qbit of the output of circuit to be $\left\vert 0 \right\rangle$ with probability $1$ if $f(0) \oplus f(1)$ is $0$ and for it to be $\left\vert 1 \right\rangle$ with probability $1$ if $f(0) \oplus f(1)$ is $1$. Without loss of generality, let this measured bit be the 0’th bit. Since $U_f$ deals with two bits, let’s also assume this measured bit is one out of two bits1 in the circuit.

The state of the system before measurement is then $\left\vert 0 \right\rangle \left( \alpha_{0} \left\vert 0 \right\rangle + \beta_{0} \left\vert 1 \right\rangle \right) + \left\vert 1 \right\rangle \left( \alpha_{1} \left\vert 0 \right\rangle + \beta_{1} \left\vert 1 \right\rangle \right)$ and we want $\alpha_0 = \beta_0 = 0$ when $a \neq b$, otherwise we want $\alpha_1 = \beta_1 = 0$.

[For brevity let $f(0)$ be $a$, $f(1)$ be $b$, and $\bar{a}$, $\bar{b}$ be their logical NOTs.]

A little bit of fiddling shows that this happens2 if $\alpha_{0} \left\vert 0 \right\rangle + \beta_{0} \left\vert 1 \right\rangle$ is $\left\vert a \right\rangle - \left\vert \bar{a} \right\rangle + \left\vert b \right\rangle - \left\vert \bar{b} \right\rangle$ and $\alpha_{1} \left\vert 0 \right\rangle + \beta_{1} \left\vert 1 \right\rangle$ is $\left\vert a \right\rangle - \left\vert \bar{a} \right\rangle - \left\vert b \right\rangle - \left\vert \bar{b} \right\rangle$. Therefore we somehow need to have the pre-measurement state be $\left\vert 0 \right\rangle \left( \left\vert a \right\rangle - \left\vert \bar{a} \right\rangle + \left\vert b \right\rangle - \left\vert \bar{b} \right\rangle \right)$ $+$ $\left\vert 1 \right\rangle \left( \left\vert a \right\rangle - \left\vert \bar{a} \right\rangle - \left\vert b \right\rangle + \left\vert \bar{b} \right\rangle \right)$.

[I’ve stopped renormalizing the probabilities since that’s not super important.]

Re-associating the desired end state, we see it is equal to $\left( \left\vert 0 \right\rangle + \left\vert 1 \right\rangle \right) \left( \left\vert a \right\rangle - \left\vert \neg a \right\rangle \right)$ $+$ $\left( \left\vert 0 \right\rangle - \left\vert 1 \right\rangle \right) \left( \left\vert b \right\rangle - \left\vert \neg b \right\rangle \right)$. This can be created from $\left\vert 0 \right\rangle \left( \left\vert a \right\rangle - \left\vert \neg a \right\rangle \right)$ $+$ $\left\vert 1 \right\rangle \left( \left\vert b \right\rangle - \left\vert \neg b \right\rangle \right)$ by applying the Hadamard gate to the first qbit.

This pre-Hadamard state expands to $\left\vert 0 \right\rangle \left\vert a \right\rangle$ $-$ $\left\vert 0 \right\rangle \left\vert \bar{a} \right\rangle$ $+$ $\left\vert 1 \right\rangle \left\vert b \right\rangle$ $-$ $\left\vert 1 \right\rangle \left\vert \bar{b} \right\rangle$, which is something we know how to compute! It is simply $\left\vert 0 \right\rangle \left\vert f(0) \right\rangle$ $-$ $\left\vert 0 \right\rangle \left\vert f(0) \oplus 1 \right\rangle$ $+$ $\left\vert 1 \right\rangle \left\vert f(1) \right\rangle$ $-$ $\left\vert 1 \right\rangle \left\vert f(1) \oplus 1 \right\rangle$ $=$ $U_f\left( \left\vert 0 \right\rangle \left\vert 0 \right\rangle - \left\vert 0 \right\rangle \left\vert 1 \right\rangle + \left\vert 1 \right\rangle \left\vert 0 \right\rangle - \left\vert 1 \right\rangle \left\vert 1 \right\rangle \right)$ $=$ $U_f\left( \left( \left\vert 0 \right\rangle + \left\vert 1 \right\rangle \right) \otimes \left( \left\vert 0 \right\rangle - \left\vert 1 \right\rangle \right) \right)$ $=$ $U_f\left( H \left\vert 0 \right\rangle \otimes H \left\vert 1 \right\rangle \right)$ where $H$ is the Hadamard gate. This yields the 1 qbit version of the Deutsch-Jozsa algorithm:

1. Let $\left\vert A \right\rangle = H \left\vert 0 \right\rangle$, $\left\vert B \right\rangle = H \left\vert 1 \right\rangle$
2. Let $\left\vert C \right\rangle, \left\vert D \right\rangle = U_f\left(\left\vert A \right\rangle, \left\vert B \right\rangle\right)$
3. Let $\left\vert E \right\rangle = H \left\vert C \right\rangle$
4. Measure $\left\vert E \right\rangle$
1. Of course, it is far from obvious that this has to be the case – it could be that the algorithm we were looking for requires more than two bits.

2. For example, if $a \neq b$ then $a = \bar{b}$ and so $\left\vert a \right\rangle - {\left\vert \bar{a} \right\rangle} + \left\vert b \right\rangle - \left\vert \bar{b} \right\rangle$ = $\left\vert a \right\rangle - {\left\vert \bar{a} \right\rangle} + \left\vert \bar{a} \right\rangle - \left\vert \bar{\bar{a}} \right\rangle$ = $0$