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

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

  • 1
    $\begingroup$ thanks a lot! this makes lots of sense now! Really appreciate it! $\endgroup$ Jun 2, 2021 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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