How to prove that the query oracle is unitary?

Question

The query oracle: $O_{x}|i\rangle|b\rangle = |i\rangle|b \oplus x_{i}\rangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?

Answer 1

Notice that $\mathcal O_x$ is a permutation matrix.

The matrix elements are $$\langle j, c\rvert\mathcal O_x\lvert i,b\rangle =\delta_{ij}\langle c\rvert b\oplus x_i\rangle =\delta_{ij}\delta_{c,b\oplus x_i}.$$ In other words, $\mathcal O_x$ is diagonal with respect to the first register, and, for each block corresponding to a given $i$, connects all and only the indices $b,c$ such that $b\oplus c=x_i$ (remember that here $b,c,x_i\in\mathbb Z_2^{\otimes n}$ are length-$n$ bit strings). Also, notice that for a given $b$ there is no more than one $c$ such that $b\oplus c=x_i$ (more precisely, there isn't any such $c$ if $x_i=0$, and there is exactly one if $x_i\neq 0$).

It follows that $\mathcal O_x$ is a (real) permutation matrix, and such matrices are always unitarily diagonalizable with unit eigenvalues (and therefore unitary). In this case, we have that the eigenvalues of $\mathcal O_x$ are $\pm1$, and the eigenvectors are, in the case $x_i\neq 0$, $$\lvert i\rangle\otimes(\lvert b\rangle\pm\lvert b\oplus x_i\rangle)$$ for all $i$ and $b$. If $x_i=0$ then $\mathcal O_x$ is the identity, and therefore its spectrum is trivial${}^\dagger$.

This shows explicitly that $\mathcal O_x$ is unitarily diagonalizable with unit eigenvalues, and therefore is unitary.

---

${}^\dagger$ I'm actually being a bit sloppy for the sake of simplicity here. This analysis holds for each different block of $\mathcal O_x$ corresponding to a given $i$. More precisely, I should say that $\mathcal O_x$ is block-diagonal as it doesn't connect spaces with $i\neq j$ on the first register, and each block is either the identity in the subspace in which it acts if $x_i=0$, or a permutation matrix that connects different pairs of basis states if $x_i\neq 0$.

Answer 2

Apply it twice: $$ O_xO_x|i\rangle|b\rangle=O_x|i\rangle|b\oplus x_i\rangle=|i\rangle|b\oplus x_i\oplus x_i\rangle=|i\rangle|b\rangle $$ Hence, $O_x$ is its own inverse, and therefore reversible.

To prove unitarity, it makes more sense to prove that $O_x$ has eigenvectors $$ |i\rangle(|0\rangle+|1\rangle)\quad\text{and}\quad|i\rangle(|0\rangle-|1\rangle) $$ for all $i$ with eigenvalues $1$ and $(-1)^{x_i}$ respectively. These are all orthonormal, and span the full Hilbert space. Consequently, the eigenvalues of $O_x$ are all $\pm 1$, and therefore $O_x^\star=O_x$ (where $^\star$ represents the Hermitian conjugate). Thus, $$ O_xO_x^\star=\mathbb{I}, $$ as required for a unitary.