# In Shor's algorithm, how is ${\rm QFT}_n|x\rangle$ split into its even and odd components?

I am auditing a course on quantum computing. Since this is not paid, I dont have any staff support to ask questions. Therefore I am asking the stackoverflow community to help me with it. This is regarding QFT for Shor's algorithm.

The instructor created the following equation to transform integer into binary. The term $$y_0$$ is 0 when the integer is even and it is 1 when the integer is odd.

$$y \equiv (y_{n-1}, y_{n-2}, \dots,y_1, y_0) \equiv 2y' + y_0.$$

Below is QFT equation, which I understand.

$$QFT_n |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \mathbb{Z}_{2^n}} \omega^{xy}|y\rangle.$$

Then he said that he is breaking the equation into two parts. The left term is even and the right term is odd.

$$= \frac{1}{\sqrt{2^n}} \bigg[ \sum_{y' \in \mathbb{Z}_{2^{n-1}}} \omega^{2xy'}|y'0\rangle + \sum_{y' \in \mathbb{Z}_{2^{n-1}}} \omega^{x(2y'+ 1)}|y'1\rangle \bigg].$$

I would appreciate if someone can clarify the following:

• How did we get $$\mathbb{Z}_{2^{n-1}}$$?
• How did the term $$2y' + y_0$$ become $$|y'0\rangle$$?

We can think of the set $$\mathbb{Z}_{2^n}$$ as the set of all binary sequences of length $$n$$ and we can write it as

$$\mathbb{Z}_{2^n} = S^n_0 \cup S^n_1\tag1$$

where $$S^n_b=\{(y',b) |y\in\mathbb{Z}_{2^{n-1}}\}$$ is the set of binary sequences of length $$n$$ that end in $$b$$, for $$b\in\{0,1\}$$. Note that $$S_0\cap S_1=\emptyset$$. Moreover, if $$y\in S^n_0$$ then

$$y=(y', 0) = 2y'\tag2$$

for some $$y'\in\mathbb{Z}^{2^{n-1}}$$ and if $$y\in S^n_1$$ then

$$y=(y', 1) = 2y'+1\tag3$$

for some $$y'\in\mathbb{Z}^{2^{n-1}}$$.

Using the observations above we can clarify the transformation in question as

\begin{align} QFT_n |x\rangle &= \frac{1}{\sqrt{2^n}} \sum_{y \in \mathbb{Z}_{2^n}} \omega^{xy}|y\rangle \\ &= \frac{1}{\sqrt{2^n}} \left[ \sum_{y \in S_0} \omega^{xy}|y\rangle + \sum_{y \in S_1} \omega^{xy}|y\rangle \right] \\ &= \frac{1}{\sqrt{2^n}} \left[ \sum_{y' \in \mathbb{Z}_{2^{n-1}}} \omega^{2xy'}|y'0\rangle + \sum_{y' \in \mathbb{Z}_{2^{n-1}}} \omega^{x(2y'+ 1)}|y'1\rangle \right] \end{align}

where in the second step we used $$(1)$$ to split the sum and in the last step we used $$(2)$$ and $$(3)$$ to change the variable from $$y\in\mathbb{Z}_{2^n}$$ to $$y'\in\mathbb{Z}_{2^{n-1}}$$.

• thanks a lot! this makes lots of sense now! Really appreciate it! Jun 2 at 15:39