# Hadamard gate in Grover algorithm

What is the need to apply the Hadamard gate as the first step while designing the diffuser circuit in the implementation of Grover's algorithm? I know what the gate does but I cannot understand what specific purpose it serves in this case.

In our Grover’s algorithm, we:

1. Add the initial Hadamard gates ie put our circuit in equal superposition |s>
2. Apply the oracle

For the reflection (diffuser), we need to implement U = 2|s><s| - 1 As we want to add negative phase to every state orthogonal to |s>, we implement as follows:

Transform |s> to |0> by applying Hadamard gates (this is why we use it!) Apply a circuit to add negative phase to states orthogonal to |0> Transform |0> back to |s> using Hadamard gates

Without the Hadamards, we cannot add the negative phase to states orthogonal to |0> as it needs to be converted first.

Say we want to find a marked element in a database $$D$$. The simplification is based on the assumption that the database has a number of entries that's a power of $$2$$. Formally, one would use a operator $$U_{D}$$ that generates a superposition of all the elements in the database $$D$$.
For Example: Say the database consists the integers from $$\{0, 1, ..., 7\}$$. Then the Hadamard transform $$H^{\otimes 3}$$ performs the map $$U_D: |0\rangle \mapsto \sum_{i = 0}^{7} |i\rangle$$. Circuit with 0,1, ..., 7
If the database would instead be the integers $$\{0, 1, ..., 6\}$$, then one would use a different operator $$U_D: |0\rangle \mapsto \sum_{i = 0}^{6} |i\rangle$$. Circuit with 0,1, ..., 6, where $$U_D$$ is called "{0,...,6}".