# 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 element-wise product. The sum over $z$ indicates all possible states of $x$ (we're in a superposition!). For a n-length 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 non-trivial 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 element-wise 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)^0|z\rangle{}}{\sqrt{2^3}}$

$H^{\bigotimes{}3}|000\rangle{} = \frac{\sum_z 1|z\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 non-trivial state, such as $|101\rangle{}$. Again, at first I calculate the element-wise 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 element-wise 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$.

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 0-indexed. 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.3535533905932737-8.65956056235493e-17j)
(-0.3535533905932739+8.659560562354935e-17j)
(0.3535533905932736-8.65956056235493e-17j)
(-0.35355339059327373+8.659560562354932e-17j)
(-0.35355339059327373+8.659560562354933e-17j)
(0.35355339059327395-8.659560562354937e-17j)
(-0.3535533905932737+8.659560562354932e-17j)
(0.3535533905932738-8.659560562354934e-17j)

Coming back to the example shown on Qiskits page, in step 3.1 they apply Hadamard on the following state:

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 sub-states above (so for $|000\rangle{}$, $|001\rangle{}$, etc.) and then sum them up¹. Some of them would then cancel each other out. This is why in their example, after step 3.1 the state looks so short:

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 non-zero 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 3-Qubit Grover search on a programmable quantum computer, Figgat et al.
• Quantum Algorithm Implementations for Beginners, Adedoyin et al.