next up previous
Next: Full Adder Cuántico Up: Computertas Cuánticas Previous: El teorema de no

La transformada de Welsh-Hadamard

La transformada de Welsh-Hadamard, o Hadamard (en corto) ya fue presentada en las compuertas de 1 qubit, si recordamos esto da la compuerta

$\displaystyle H_2 = \frac{1}{\sqrt{2}}
\left(
\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right)
$

La compuerta de Hadamard se puede generalizar para espacios vectoriales de tamaño $ 2^n$. En particular la fórmula inductiva esta dada por

$\displaystyle H_{2^n} = \left\{
\begin{array}{cl}
1 & \textrm{si} \; n = 0 \\
...
... & -H_{2^{n-1}}
\end{array}\right) & \textrm{si} \; n > 1
\end{array}
\right.
$

Teorema 3.6.1   Una compuerta de Welsh-Hadamard de tamaño $ 2^n$ es igual al producto tensor de $ n$ compuertas de Hadamard de tamaño 2, tal que

$\displaystyle H_{2^n} = \underbrace{H_2 \otimes H_2 \otimes \cdots \otimes H_2}_{n \; \textrm{veces}}
$

Proof. Por inducción, para $ n=1$ sabemos que

$\displaystyle H_{2^1} = H_2 = \underbrace{H_2}_{1 \; \textrm{vez}}
$

Ahora bien, suponemos que

$\displaystyle H_{2^n} = \underbrace{H_2 \otimes H_2 \otimes \cdots \otimes H_2}_{n \; \textrm{veces}}
$

entonces

$\displaystyle H_{2^{n+1}} \stackrel{def}{=}
\frac{1}{\sqrt{2}}
\left(
\begin{array}{cr}
H_{2^n} & H_{2^n} \\
H_{2^n} & -H_{2^n}
\end{array}\right) =
$

$\displaystyle \frac{1}{\sqrt{2}}
\left(
\begin{array}{cr}
1 & 1 \\
1 & -1
\end{array}\right) \otimes H_{2^n} =
$

$\displaystyle H_2 \otimes H_{2^n} =
$

$\displaystyle H_2 \otimes \underbrace{H_2 \otimes H_2 \otimes \cdots \otimes H_2}_{n \; \textrm{veces}} =
$

$\displaystyle \underbrace{H_2 \otimes H_2 \otimes H_2 \otimes \cdots \otimes H_2}_{n+1 \; \textrm{veces}}
$

$ \qedsymbol$

Estas propiedades conducen al siguiente teorema, el cual es muy util en algunos algoritmos cuánticos.

Teorema 3.6.2   La transformada de Welsh-Hadamard cumple con

$\displaystyle H_{2^n}\vert\underbrace{00\cdots0}_{n \; \textrm{veces}}\rangle = \frac{1}{\sqrt{2^n}}\sum_{k = 0}^{2^n-1} \vert k\rangle
$

$\displaystyle H_{2^n}\vert j\rangle = \frac{1}{\sqrt{2^n}}\sum_{k = 0}^{2^n-1} (-1)^{\vec{k}\cdot\vec{j}}\vert k\rangle
$

Donde $ \vec{k}$ y $ \vec{j}$ son los vectores que contienen la representación binaria de $ k$ y de $ j$ y su multiplicación es el producto interno de ambos.

Proof. Por inducción, el caso base para $ n=1$ debe demostrar que

$\displaystyle H_2\vert b\rangle = \frac{1}{\sqrt{2}}\sum_{j=0}^1 (-1)^{\vec{j}\cdot\vec{b}}\vert j\rangle
$

para todo $ b \in \{0,1\}$. Es fácil corroborar este caso y lo dejamos como ejercicio al lector.

Para el caso inductivo, asumimos como hipótesis de inducción que

$\displaystyle H_{2^n}\vert j\rangle = \frac{1}{\sqrt{2^n}}\sum_{k = 0}^{2^n-1} (-1)^{\vec{k}\cdot\vec{j}}\vert k\rangle
$

y debemos demostrar que

$\displaystyle H_{2^{n+1}}\vert m\rangle = \frac{1}{\sqrt{2^n}}\sum_{i = 0}^{2^{n+1}-1} (-1)^{\vec{i}\cdot\vec{m}}\vert i\rangle
$

para efectuar esta prueba es importante resaltar varios puntos Supondremos, sin perdida de generalidad, de que $ \vert m\rangle = \vert b\rangle\otimes\vert j\rangle$ con $ b \in \{0,1\}$ y $ \vert j\rangle$ un vector base de $ n$ qubits, esto tambien implica que la representacion binaria de $ m = \vec{m}$ se puede expresar como $ \vec{m} = b\vec{j}$ donde $ \vec{j}$ es la representación binaria del vector base $ j$. Ahora bien

$\displaystyle H_{2^{n+1}}\vert m\rangle = (H_2\otimes H_{2^n})(\vert b\rangle\otimes\vert j\rangle) =
$

$\displaystyle (H_2\vert b\rangle) \otimes (H_{2^n}\vert j\rangle) =
$

$\displaystyle \left(\frac{1}{\sqrt{2}}\sum_{i=0}^1 (-1)^{i\cdot b}\vert i\rangl...
...rt{2^n}}\sum_{k = 0}^{2^n-1} (-1)^{\vec{k}\cdot\vec{j}}\vert k\rangle\right) =
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\sum_{i=0}^1\sum_{k = 0}^{2^n-1} (-1)^{i\cdot b}(-1)^{\vec{k}\cdot\vec{j}}
\vert i\rangle\otimes\vert k\rangle =
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\sum_{i=0}^1\sum_{k = 0}^{2^n-1} (-1)^{(i\vec{k})\cdot(b\vec{j})}
\vert i\rangle\otimes\vert k\rangle =
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\left(\left[
\sum_{k = 0}^{2^n-1} (-1)^...
...(1\vec{k})\cdot(b\vec{j})}
\vert 1\rangle\otimes\vert k\rangle
\right]\right)=
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\left(
\sum_{k = 0}^{2^n-1} (-1)^{(0\ve...
...m_{k = 0}^{2^n-1} (-1)^{(1\vec{k})\cdot(b\vec{j})}
\vert k+2^n\rangle
\right)=
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\left(
\sum_{k = 0}^{2^n-1} (-1)^{\vec{...
...2^n-1} (-1)^{(\overrightarrow{k+2^n})\cdot\vec{m}}
\vert k+2^n\rangle
\right)=
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\left(
\sum_{i = 0}^{2^n-1} (-1)^{\vec{...
...
\sum_{i = 2^n}^{2^{n+1}-1} (-1)^{\vec{i}\cdot\vec{m}}
\vert i\rangle
\right)=
$

$\displaystyle \frac{1}{\sqrt{2^{n+1}}}
\sum_{i = 0}^{2^{n+1}-1} (-1)^{\vec{i}\cdot\vec{m}}
\vert i\rangle
$

$ \qedsymbol$


next up previous
Next: Full Adder Cuántico Up: Computertas Cuánticas Previous: El teorema de no
Jose Castro 2004-10-06