I am studying the Quantum Fourier Transform and my question regards section 4 from this link. Specifically, I do not understand the step where they rewrite in fractional binary notation- could someone explain to me what that means? I tried to look it up but did not find anything relevant to this context.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A positive integer $y$ has a binary representation $y_{n-1}\ldots y_{0}$ where $y_k \in \{0,1\}$. For example, for $n=3$, the number $5$ in binary is $\color{red}{101}$. If we do a binary expansion of $5$, we get $$5 = 2^2*\color{red}1 + 2^1 *\color{red}0 + 2^0 * \color{red}1.$$ In general, we have $$ \tag{1} y = \sum_{k=0}^{n-1} 2^k y_k. $$
Similarly, $\frac{y}{2^n}$ is an integer $y$ divided by $2^n$, so it is a fraction, which also has a binary expansion in terms of fractions $2^{-k}$: $$\tag{2} \frac{y}{2^n} = \sum_{k=1}^{n} 2^{-k}y_k.$$
You can derive (2) from (1) by dividing (1) by $2^n$.
