# Quantum Fourier Transform and roots of unity.

I need to find $QFT_{6}$ for the state quantum state $\frac{1}{\sqrt2}(|0\rangle + |3\rangle)$. I received a very sufficient answer recently on simplifying nth roots of unity, but I am having a lot of trouble applying it to this problem. I have obtained the $QFT_6$ matrix below, and multiplied it by the shown state:

$$\begin{pmatrix} \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\\ \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega & \frac{1}{\sqrt6}\omega^2 & \frac{1}{\sqrt6}\omega^3 & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^5\\ \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega^2 & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^6 & \frac{1}{\sqrt6}\omega^8 & \frac{1}{\sqrt6}\omega^{10}\\ \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega^3 & \frac{1}{\sqrt6}\omega^6 & \frac{1}{\sqrt6}\omega^9 & \frac{1}{\sqrt6}\omega^{12} & \frac{1}{\sqrt6}\omega^{15}\\ \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega^4 & \frac{1}{\sqrt6}\omega^8 & \frac{1}{\sqrt6}\omega^{12} & \frac{1}{\sqrt6}\omega^{16} & \frac{1}{\sqrt6}\omega^{20}\\ \frac{1}{\sqrt6} & \frac{1}{\sqrt6}\omega^5 & \frac{1}{\sqrt6}\omega^{10} & \frac{1}{\sqrt6}\omega^{15} & \frac{1}{\sqrt6}\omega^{20} & \frac{1}{\sqrt6}\omega^{25}\\ \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt2}\\ 0 \\ 0 \\ \frac{1}{\sqrt2}\\ 0 \\ 0 \end{pmatrix}$$ Right, well now I don't understand how to just express all of the omegas in terms of $\omega$ and $\omega^2$. Help would be much appreciated.

• Is $\omega$ a primitive third root of unity? If so then $$\begin{cases}1=\omega^3=\omega^6=\omega^9=\cdots \\ \omega=\omega^4=\omega^7=\omega^{10}=\cdots \\ \omega^2=\omega^5=\omega^8=\omega^{11}=\cdots\end{cases}$$ and so on. Additionally, $1+\omega+\omega^2=0$ by symmetry. These are all the relations you need to reduce polynomials in $\omega$ to the form $a+b\omega$. So ... do the work now! – anon Sep 23 '13 at 3:35
• Actually, $\omega$ is a primitive sixth root of unity. I edited my original post. Those identities don't change as a result, correct? If so, I will try to evaluate it from there. – cygorx Sep 23 '13 at 3:38
• The identities do change. Now it's $1=\zeta^6=\zeta^{12}=\cdots$ and so on, along with the relation $0=\Phi_6(\zeta)=\zeta^2-\zeta+1$. (The $\Phi_n$ are the so-called cyclotomic polynomials.) I advise using the letter $\zeta$ for a sixth root of unity. Usually $\omega$ is reserved for the primitive third root of unity in the upper half plane. – anon Sep 23 '13 at 3:40
• Whoa, wait. Things aren't exactly as cut dried as they once were. If $\omega$ were a 3rd root of unity, I could have simply plugged in one for the whole 4th column. My apologies if the answer is obvious, though I still don't quite get how I can use the sixth roots of unity's properties to use only (now using zeta as opposed to omega) $\zeta^2$ and $\zeta$. Thank you again. – cygorx Sep 23 '13 at 3:57
• You have $\zeta^6=1$ and $\zeta$ primitive so $\zeta^3=-1$. Thus $\zeta^4=-\zeta$ and $\zeta^5=-\zeta^2$. Finally $\zeta^2=\zeta-1$. Thus $\zeta^2,\zeta^3,\zeta^4,\zeta^5,\zeta^6$ can all be reduced to the form $a+b\zeta$. Combined with the cycling every six powers $1=\zeta^6=\zeta^{12}=\zeta^{18}=\cdots$ you should have all you need. This is one of those Lego/K'nex type of problems: we benefit greatly from just playing around with the stuff ourselves first before others spoil all the fun. It is also very useful to think geometrically about all of this - lots of symmetry arguments lurk. – anon Sep 23 '13 at 4:06

Position a regular hexagon on the unit circle with vertices at $\pm1$. Let $\zeta$ be the first complex root of unity counterclockwise from $1$. Then $\zeta^2$ is a third full rotation away from $1$, in other words it is a third root of unity. And $\zeta^3=-1$ since it sweeps out exactly half a rotation. Algebraically speaking we know $(\zeta^3)^2=1$ and $\zeta^3\ne1$ (since $\zeta$ is a primitive $6$th root) so $\zeta^3=-1$.

This tells us that $\zeta^4=-\zeta$ and $\zeta^5=-\zeta^2$. We already know $\zeta^6=1$. Can $\zeta^2$ be reduced?

Indeed it can. The theory of cyclotomic polynomials tells us that

$$\Phi_6(x)=\frac{(x^6-1)(x-1)}{(x^3-1)(x^2-1)}=\frac{x^3+1}{x+1}=x^2-x+1.$$

So $\zeta^2=\zeta-1$. Thus all of $\zeta^2,\zeta^3,\zeta^4,\zeta^5,\zeta^6$ can be written in the form $a+b\zeta$ with these relations.

One can also argue $\zeta^2=\zeta-1$ with a more geometric toolkit. Looking at the hexagon it is clear that $\zeta^2$ bisects the vectors representing $-1$ and $\zeta$, so $\zeta^2=r(\zeta-1)$ already; at this stage one shows $\zeta-1$ has modulus $1$ so $r=1$ hence $\zeta^2=\zeta-1$.

Finally with the cycling $1=\zeta^6=\zeta^{12}=\zeta^{18}=\cdots$ you should have all you need.