Proof that Operations are Unitary

If the above matrices not unitary, they will not be physically realizable, at least for systems with time independent Hamiltonians, which are the only ones being considered here. It must be shown that each of the above operations is unitary. As a reminder, a unitary matrix is one whose inverse is the same as the transpose of its complex conjugate, and unitary matrices represent reversible operators that preserve normalization.

The Walsh-Hadamard transformation is one of the fundamental unitary transformations used in quantum computing. The proof is simply a great deal of linear algebra, showing W² = I (since W is real and symmetric) and is omitted for brevity.

The rotation matrix R with R_ij = 0 if i $\not=$j, and R_ii = e^{$\sqrt{{-1}}$$\phi_{{i}}$}. Here $\phi_{{i}}^{}$ is an arbitrary real number.

It is easy to see R's complex conjugate transposed is the inverse of R. When R is multiplied by it's complex conjugate, the only non-zero elements are on the diagonal, and when the diagonal elements are multiplied the powers of e will cancel, resulting in e⁰ = 1 on the diagonal, the identity matrix. [Grover96]

To show the inversion about average matrix A is unitary, recall that A may be written as A = - I + 2P where:

• I is the identity matrix
• P is the matrix with each element is equal to 1/N

Recall that P² = P.

A is real and symmetric, so A is its own transposed complex conjugate, and we must show A² = I.

A² = (- I + 2P)² = I² -2P - 2P + 4P² = I - 4P + 4P = I

[Grover96]