# How to prove that the query oracle is unitary?

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?

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

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.

• Thanks, I now understand $O_{x}$ is its own inverse but how does that make it unitary? For a unitary matrix, one would need to show that its inverse is equal to its conjugate transpose, $MM^{*}=I$. I think we further need to show $O_{x}$ is Hermitian, then it will be done. – Divyat Mar 26 at 13:56
• One more doubt, I think the answer still assumes that $O_{x}$ is normal matrix, as then with real eigenvalues we can claim it to be Hermitian. Please tell whether it is okay to assume oracle as normal or some justifications for it? – Divyat Mar 26 at 15:52
• This explanation is not quite correct, because you assumed that $O_x$ is diagonalizable, but it is not follow from $O_x^2=I$. The thing is $O_x$ maps basis vectors to basis vectors. Since $O_x^2=I$ then $Q_x$ is a permutation of basis vectors. – Danylo Y Mar 26 at 16:17
• I actually asked some time ago on math.SE whether one can deduce that $\sqrt A$ is diagonalizable from the fact that $A$ is, see here. As far as I understood the answers, $A^2=I$ is not enough to imply that $A$ is unitarily diagonalizable, a counterexample being $\begin{pmatrix}\cos\theta & 2\sin\theta \\ \sin\theta/2 & -\cos\theta\end{pmatrix}$, which is a square root of the identity, but not (unitarily) diagonalizable, and not unitary, even though its eigenvalues are $\pm 1$. – glS Mar 26 at 18:01
• Fair enough, I was being a bit glib, particularly initially with regards to the difference between reversible and unitary, because usually its the reversibility aspect people are interested in. – DaftWullie Mar 27 at 8:44