4
$\begingroup$

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

1 Answer 1

3
$\begingroup$

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

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.