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

Question

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$?

Answer 1

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}}$.