Operator to Create Equal Superposition of States

An equal superposition of states is created by the application of the well known Walsh-Hadamard operator. The matrix representing the Walsh-Hadamard operator for an $n$ bit quantum register is a $2^{n} \times 2^{n}$ matrix whose elements are defined to be: $W_{ij} = 2^{-n/2}(-1)^{\bar{i} \cdot \bar{j}}$, where $\bar{i}$ is the binary representation of $i$, and $\bar{i} \cdot \bar{j}$ is the bitwise dot product of the $n$ bit strings $i$ and $j$, $i$ and $j$ range from 0 to $(N-1)$, [Grover96] Put another way, $W_{ij} = \pm 2^{-n/2}$, where the sign is positive if the bitwise AND of $i$ and $j$ has an even number of 1's and negative otherwise. [Grover00]

The reason the Walsh-Hadamard operator inverts the sign (or rotates the phase $\pi$ radians) in certain states is to allow it to be reversible. We are asking for an operator which places a quantum system in an equal superposition of states. For a classical probabilistic system this would necessarily be a irreversible process, as the resultant state would be the same for any input. Since the amplitudes of a quantum state can be complex, the probability of measuring the a system in a given state is the absolute square of the amplitude in the given state. Thus the Walsh-Hadamard operation can encode information in the phases of the states to make it reversible, while still placing the register in a state where if measured any basis state will be found with equal probability. [Grover00]

We may assume that prior to step 1 of our algorithm that our state is prepared to be identically in one of the $N = 2^{n}$ basis states. Assume that we place our register initially in the state where each of the bits is zero, then the state vector for our $n$ bit register is: $\Psi = (1, 0, 0, \ldots 0)^{T}$. As a reminder, the state vector $\Psi$ has $N = 2^{n}$ components, representing each of the states our $n$ bit quantum register can be measured in. After application of the Walsh-Hadamard transformation the j'th element of the state vector is $W_{0j} = 2^{n/2}(-1)^{\bar{0} \cdot \bar{j}}$, note that the bitwise dot product of the zero vector and any $j$ vector is 0, thus the sign of each amplitude is positive.

The result is an equal superposition of each state, all with positive amplitude. This was attained by performing the Walsh-Hadamard operator to the register prepared solely in the first state.

Note that this can be done for a $n$ bit quantum register in $O(n) = O(\lg N)$ time, although to simulate this on a classical computer we must perform no less than $O(N)$ operations. Here we see an example of the kind of exponential slowdown in classical simulation of quantum systems that Feynman observed.