Ttyjfyk

The query oracle: $O_x|irangle|brangle = |irangle|b oplus x_irangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?

Notice that $mathcal O_x$ is a permutation matrix.

The matrix elements are
$$langle j, crvertmathcal O_xlvert i,brangle
=delta_ijlangle crvert boplus x_irangle
=delta_ijdelta_c,boplus 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 $boplus c=x_i$ (remember that here $b,c,x_iinmathbb 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 $boplus c=x_i$ (more precisely, there isn't any such $c$ if $x_i=0$, and there is exactly one if $x_ineq 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_ineq 0$,
$$lvert irangleotimes(lvert branglepmlvert boplus x_irangle)$$
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 $ineq 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_ineq 0$.

Apply it twice:
$$
O_xO_x|irangle|brangle=O_x|irangle|boplus x_irangle=|irangle|boplus x_ioplus x_irangle=|irangle|brangle
$$
Hence, $O_x$ is its own inverse, and therefore reversible.

To prove unitarity, it makes more sense to prove that $O_x$ has eigenvectors
$$
|irangle(|0rangle+|1rangle)quadtextandquad|irangle(|0rangle-|1rangle)
$$
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=mathbbI,
$$
as required for a unitary.