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.

  • $\begingroup$ 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! $\endgroup$ – anon Sep 23 '13 at 3:35
  • $\begingroup$ 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. $\endgroup$ – cygorx Sep 23 '13 at 3:38
  • $\begingroup$ 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. $\endgroup$ – anon Sep 23 '13 at 3:40
  • $\begingroup$ 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. $\endgroup$ – cygorx Sep 23 '13 at 3:57
  • $\begingroup$ 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. $\endgroup$ – 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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.