# Hadamard Gate Transformation for 3 or more QuBits
While trying to understand Grover's Algorithm, I started wondering how exactly the Hadamard gate transformation looks like for not just one QuBit or even two, but for three or more. Ekert et al. in their paper Basic concepts in quantum computation show with Equation 12 a very nice general formula for the Hadamard gate transformation:
$H^{\bigotimes{}n}x\rangle{} = \frac{\sum_z (1)^{x \cdot z}z\rangle{}}{\sqrt{2^n}}$,
where $\cdot$ is the elementwise product. The sum over $z$ indicates all possible states of $x$ (we're in a superposition!). For a nlength state there are $2^n$ possible states, so for 3 there are 8 states.
Assuming I'd like to apply Grover's algorithm to 3 QuBits as shown on the Qiskit page on Grover's algorithm, there is a point at which Hadamard is applied to 3 QuBits on a nontrivial state (not just $000\rangle{}$). This is where the formula above comes in. Let's first calculate it through for $000\rangle{}$. Below I calculate the elementwise products $x \cdot z$.
$\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} = 0*0 + 0*0 + 0*0 = 0$
$\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = 0*0 + 0*0 + 0*1 = 0 \\ ...$
As you can see, they all amount to 0 here. Now, the general equation from above becomes trivial (note: $n=3$ and $x=000\rangle{}$):
$H^{\bigotimes{}3}000\rangle{} = \frac{\sum_z (1)^0z\rangle{}}{\sqrt{2^3}}$
$H^{\bigotimes{}3}000\rangle{} = \frac{\sum_z 1z\rangle{}}{\sqrt{8}}$
In the last step all the sum was evaluated to its 8 possible states. This is probably very familiar looking now! Next, let's try this for a nontrivial state, such as $101\rangle{}$. Again, at first I calculate the elementwise products $x \cdot z$.
$\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} = 1*0 + 0*0 + 1*0 = 0$
$\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = 1*0 + 0*0 + 1*1 = 1 \\ ...$
I've again only shown the first two. But there is an important difference here already, the result of the elementwise product for states $x=101\rangle{}$ and $z=001\rangle{}$ is $1$! And this is where the negative signs come from when evaluating the whole sum, since $(1)^{1} = 1$.
$H^{\bigotimes{}3}101\rangle{} = \frac{1}{\sqrt{8}} (000\rangle{}  001\rangle{} + 010\rangle{}  011\rangle{}  100\rangle{} + 101\rangle{}  110\rangle{} + 111\rangle{})$If you want to calculate this by hand and compare, go right ahead. To make sure
your calculations are correct, here is a short code snippet using Qiskit, that
does basically all the calculations for you.
To customize it, change the index in circuit.initialize()
. E.g. Just imagine
the state from before as a binary number ($101_{2} ~= 5_{10}$), which means we
were looking at 5. Now set the number at index 5 to 1 in the list [0, 0, 0, 0, 0, 0, 0, 0]
.
import qiskit as qk
q = qk.QuantumRegister(3)
c = qk.ClassicalRegister(3)
circuit = qk.QuantumCircuit(q, c)
# We want 101, so the fifth. This is 0indexed. So the sixth place:
circuit.initialize([0, 0, 0, 0, 0, 1, 0, 0], [q[0], q[1], q[2]])
circuit.h(q[0])
circuit.h(q[1])
circuit.h(q[2])
print(circuit)
simulator = qk.BasicAer.get_backend('statevector_simulator')
job = qk.execute(circuit, simulator)
ket = job.result().get_statevector()
for amplitude in ket:
print(amplitude)
This will print the amplitudes multiplied with $\frac{1}{\sqrt{8}} ~= 0.3535$. Incidentally, negative signs are in the exact same places as in the result from our manual calculation above.
(0.35355339059327378.65956056235493e17j)
(0.3535533905932739+8.659560562354935e17j)
(0.35355339059327368.65956056235493e17j)
(0.35355339059327373+8.659560562354932e17j)
(0.35355339059327373+8.659560562354933e17j)
(0.353553390593273958.659560562354937e17j)
(0.3535533905932737+8.659560562354932e17j)
(0.35355339059327388.659560562354934e17j)
Coming back to the example shown on Qiskits page, in step 3.1 they apply Hadamard on the following state:
$\phi{}_{2}\rangle{} = \frac{1}{\sqrt{8}} (000\rangle{} + 001\rangle{} + 010\rangle{} + 011\rangle{} + 100\rangle{}  101\rangle{}  110\rangle{} + 111\rangle{})$This is the pointe of this blog post: To calculate the resulting state (after Hadamard gate transformation), you would have to calculate $H(z\rangle{})$ for each of the substates above (so for $000\rangle{}$, $001\rangle{}$, etc.) and then sum them up^{1}. Some of them would then cancel each other out. This is why in their example, after step 3.1 the state looks so short:
$\phi{}_{3a}\rangle{} = \frac{1}{2} (000\rangle{} + 011\rangle{} + 100\rangle{}  111\rangle{})$Anyways, this is it for this post. I hope I could give some more intuition into the Hadamard gate transformation with more than just 1 or 2 QuBits. Maybe the script above will also help you in your endeavours.
Update: I've created a script to prove that the states indeed cancel each other out. Find it here. Observe in the output at the very and that only 4 states have a nonzero amplitude. Those are exactly the four states that we end up with!
Also, for the interested reader here are a few related papers that may help in understanding:
 Complete 3Qubit Grover search on a programmable quantum computer, Figgat et al.
 Quantum Algorithm Implementations for Beginners, Adedoyin et al.

I got that idea from here. Notice how the Hadamard gate transformation evolves on a complex state: $H(\frac{1}{\sqrt{2}}0\rangle{} + \frac{1}{\sqrt{2}}1\rangle{}) = \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}0\rangle{} + \frac{1}{\sqrt{2}}1\rangle{}) + \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}0\rangle{}  \frac{1}{\sqrt{2}}1\rangle{}) = \frac{1}{2}(0\rangle{} + 1\rangle{}) + \frac{1}{2}(0\rangle{}  1\rangle{}) = 0\rangle{}$ ↩