next up previous
Next: About this document ... Up: La Transformada de Fourier Previous: La Transformada de Fourier

Derivación del circuito de la QFT

Utilizaremos la equación 3.7 para derivar la forma que debe tener el circuito de la QFT, antes de esto haremos ciertas suposiciones notacionales
  1. $ k \in \{0, 1, \ldots, 2^n-1\}$ y el ket $ \vert k\rangle$ corresponde a una secuencia de $ n$ qubits tal que

    $\displaystyle \vert k\rangle = \vert k_1k_2\cdots k_n\rangle = \vert k_1\rangle \otimes \vert k_2\rangle \otimes \cdots \otimes \vert k_n\rangle
$

    $\displaystyle k = k_12^{n-1}+k_22^{n-2}+ \cdots + k_{n-1}2 + k_n = \sum_{s=1}^{n}k_s2^{n-s}
$

    con $ k_s \in \{0, 1\}$.
  2. $ j \in \{0, 1, \ldots, 2^n-1\}$ y el ket $ \vert j\rangle$ corresponde a una secuencia de $ n$ qubits tal que

    $\displaystyle \vert j\rangle = \vert j_0j_1\cdots j_{n-1}\rangle = \vert j_0\rangle \otimes \vert j_1\rangle \otimes \cdots \otimes \vert j_{n-1}\rangle
$

    $\displaystyle j = j_02^{n-1}+j_12^{n-2}+ \cdots + j_{n-2}2 + j_{n-1} = \sum_{s=0}^{n-1}j_s2^{n-(s+1)}
$

    con $ j_s \in \{0, 1\}$.
Con estas definiciones el circuito cuántico de la transformada de Fourier debe cumplir con

$\displaystyle \emph{QFT}\vert j\rangle = \frac 1 {\sqrt{2^n}}\sum_{k=0}^{2^n-1}w^{jk}\vert k\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
...m_{k_n \in \{0,1\}}
w^{j\sum_{s=1}^nk_s2^{n-s}}\vert k_1k_2\cdots k_n\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
...,1\}}
e^{(2i\pi j(\sum_{s=1}^nk_s2^{n-s}))/2^n}\vert k_1k_2\cdots k_n\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
...\in \{0,1\}}
e^{(2i\pi j\sum_{s=1}^nk_s2^{-s})}\vert k_1k_2\cdots k_n\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
... k_1\rangle \otimes \vert k_2\rangle \otimes \cdots \otimes \vert k_n\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
... k_1\rangle \otimes \vert k_2\rangle \otimes \cdots \otimes \vert k_n\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
...prod_{s=1}^n e^{2i\pi jk_s2^{-s}}\right) \bigotimes_{s=1}^n \vert k_s\rangle =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\sum_{k_1 \in \{0,1\}}\sum_{k_2 \in \{0,1\}}\...
...0,1\}}
\bigotimes_{s=1}^n \left( e^{2i\pi jk_s2^{-s}}\vert k_s\rangle\right) =
$

$\displaystyle \frac 1 {\sqrt{2^n}}\bigotimes_{s=1}^n \sum_{k_s \in \{0,1\}}\left( e^{2i\pi jk_s2^{-s}}\vert k_s\rangle\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\sum_{k_s \in \{0,1\}}\left( e^{2i\pi jk_s2^{-s}}\vert k_s\rangle\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left( e^{2i\pi j\times 0 \t...
...^{-s}}\vert\rangle +
e^{2i\pi j\times 1 \times 2^{-s}}\vert 1\rangle\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left( \vert\rangle + e^{2i\pi j2^{-s}}\vert 1\rangle\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left( \left(\begin{array}{c...
...+
e^{2i\pi j2^{-s}} \left(\begin{array}{c} 0  1 \end{array}\right)\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left(\begin{array}{c} 1  e^{2i\pi j2^{-s}} \end{array}\right)$ (3.8)

Ahora analizando el término

$\displaystyle e^{2i\pi j2^{-s}} = e^{2i\pi (\sum_{m=0}^{n-1}j_m2^{n-(m+1)})2^{-s}} =
$

$\displaystyle e^{2i\pi \sum_{m=0}^{n-1}j_m2^{n-s-(m+1)}} =
$

$\displaystyle e^{2i\pi \sum_{m=0}^{n-1}j_m2^{(n-s-1)-m}} =
$

$\displaystyle e^{\sum_{m=0}^{n-1}2i\pi j_m2^{(n-s-1)-m}} =
$

$\displaystyle \prod_{m=0}^{n-1}e^{2i\pi j_m2^{(n-s-1)-m}} =
$

$\displaystyle \prod_{m=0}^{n-s-1}e^{2i\pi j_m2^{(n-s-1)-m}} \times \prod_{m=n-s}^{n-1}e^{2i\pi j_m2^{(n-s-1)-m}}$ (3.9)

Ahora bien, notese que el término de la izquierda es $ e^{2i\pi M}$ donde $ M$ es entero, y esta expresión es igual a 1. Asi que la ecuacion 3.9 da igual a

$\displaystyle \prod_{m=n-s}^{n-1}e^{2i\pi j_m2^{(n-s-1)-m}}
$

y la ecuación 3.8 expresando $ j$ en notación binaria es igual a

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left(\begin{array}{c} 1  \prod_{m=n-s}^{n-1}e^{2i\pi j_m2^{(n-s-1)-m}}
\end{array}\right) =
$

$\displaystyle \bigotimes_{s=1}^n \frac 1 {\sqrt{2}}\left(\begin{array}{c} 1  e^{2i\pi 0.j_{n-s}j_{n-s+1}\cdots j_{n-1}}
\end{array}\right) =
$


next up previous
Next: About this document ... Up: La Transformada de Fourier Previous: La Transformada de Fourier
Jose Castro 2004-10-06