# Hadamard Gate (H-gate)
A gate that maps computational base to super position with phase shift.
## Switch computational basis and phase basis
$\begin{align}
& H|0 \rangle=|+\rangle:=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\
& H|1\rangle=|-\rangle:=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)
\end{align}$
It maps the superposition to basic state: $\begin{align}
& H|+\rangle=|0\rangle \\
& H|-\rangle=|1\rangle \\
\end{align}$where $|+\rangle := \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ and $|-\rangle:=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$
This means that $H^2=Identity$ i.e., it is Unitarian and Hermitian.
This also means that $HXH=Z$ and $HZH=X$.
## Computing $H^{\otimes n}|0^{\otimes n}\rangle$
Example:
$
\begin{align}
H^{\otimes 2}|0\rangle^{\otimes 2}&= (H\otimes H)(|0\rangle\otimes|0\rangle) \\
&= H|0\rangle\otimes H|0\rangle\\
&= \frac{1}{\sqrt 2}(|0\rangle+|1\rangle)\otimes\frac{1}{\sqrt 2}(|0\rangle+|1\rangle) \\
&=\frac{1}{2}(
|0\rangle\otimes|0\rangle+
|0\rangle\otimes|1\rangle+
|1\rangle\otimes|0\rangle+
|1\rangle\otimes|1\rangle) \\
&=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)\\
&=\frac{1}{\sqrt{2^2}}\sum_{x\in\{0,1\}^2}|x\rangle
\end{align}
$
## Computing $H^{\otimes n}|x\rangle$ for $x\in\{0,1\}^n$
Lemma: $H^{\otimes n}|x\rangle=\frac{1}{\sqrt N}\sum_{y\in\{0,1\}^n}(-1)^{\langle x,y\rangle}|y\rangle$ for $x\in\{0,1\}^n$.
Proof: $y$ bit is chosen as an element from either $A=(|0\rangle+|1\rangle)$ or $B=(|0\rangle-|1\rangle)$.
Scan the bits of $y$ from left to right.
if $y$ bit is 0 then it does not matter if it came from A or B it will have $+1$ multiplicand.
If $y$ bit is 1 then if it came from $A$ it will have $+1$ multiplicand. This happens when $x$ bit is $0$. if it came from B, it will have -1 multiplicand. This happens when $x$ bit is $1$.
To summarize only when $x$ and $y$ i-th bit is $1$ we get multiplicand of $-1$. This is equivalent to computing $(-1)^{x_i\cdot y_i}$. multiply all potential $(-1)$ multiplicands of $y$ is equivalent to $(-1)^{\sum_i x_iy_i}=(-1)^{\langle x,y \rangle}$
Example:
$
\begin{align}
H^{\otimes 2}|01\rangle&=H|0\rangle\otimes H|1\rangle\\
&= \frac{1}{2}(|0\rangle+|1\rangle)\otimes(|0\rangle-|1\rangle)= \\
&= \frac{1}{2}\big(|00\rangle-|01\rangle+|10\rangle-|11\rangle\big)= \\
&=\frac{1}{2}\big(
(-1)^{\langle 01,00 \rangle}|00\rangle
+(-1)^{\langle 01,01 \rangle}|01\rangle
+(-1)^{\langle 01,10 \rangle}|10\rangle
+(-1)^{\langle 01,11 \rangle}|11\rangle \\
&=\frac{1}{2}\big(
(-1)^0|00\rangle
+(-1)^1|01\rangle
+(-1)^0|10\rangle
+(-1)^1|11\rangle
\big)
\end{align}
$
## Definition of $|{\huge\chi}_x\rangle$
We define "chi of $x
quot;
$|{\huge\chi}_x\rangle:=H^{\otimes n}|x\rangle = \frac{1}{\sqrt N}\sum_{y\in\{0,1\}^n}(-1)^{\langle x,y\rangle}|y\rangle$
$H$ are unitarian and $|x\rangle$ are standard basis and orthogonal. Their image under $H$ must be also orthogonal i.e., $|{\huge\chi}_x\rangle$ are orthogonal for $x\in\{0,1\}^n$.
Example: $H^{\otimes 2}|01\rangle=|{\huge\chi}_{01}\rangle$
$
\begin{align}
H^{\otimes 2}|01\rangle &= H|0\rangle\otimes H|1\rangle \\
&= |+\rangle\otimes|-\rangle \\
&= \frac{1}{\sqrt 2}(|0\rangle + |1\rangle)\otimes\frac{1}{\sqrt 2}(|0\rangle - |1\rangle) \\
&= \frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)\\
\\
|{\huge\chi}_{01}\rangle &= \frac{1}{\sqrt 4}\sum_{y\in\{0,1\}^2}(-1)^{\langle y,01\rangle}|y\rangle = \frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)
\end{align}
$
Related: [[Bernstein–Vazirani algorithm]]
## Created 2025-12-03 14:30