# 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?

• Mar 26, 2019 at 12:25

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. Mar 26, 2019 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? Mar 26, 2019 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. Mar 26, 2019 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, 2019 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. Mar 27, 2019 at 8:44