2
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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

$\endgroup$

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.