# Quantum Phase Estimation Circuit and Modular Exponentiaton

In Nielsen and Chuang, it is stated that the effect of phase estimation circuit is mapping state $$|j\rangle |u\rangle$$ to $$|j\rangle U^j |u\rangle$$.

Here is my solution: Consider the first $$CU^{2^0}$$. Let $$|j\rangle = |j_1j_2\dots j_t\rangle$$. It maps the state $$|j\rangle |u\rangle$$ to state $$|j\rangle U^{j_t2^0}|u\rangle$$.If $$j_t=0$$, then nothing happens. Otherwise, $$U^{2^0}$$ is applied.

Continuing like this I get the following quantum state:

$$|j\rangle U^{j_12^{t-1}} \cdots U^{j_t2^0}|u\rangle$$

Then it should be true that $$U^{j_12^{t-1}} \cdots U^{j_t2^0} = U^j$$ but I cannot see how this follows. I am studying order finding algorithm and modular exponentiation part heavily depends on this observation. Can someone help?

• $j_i$ are by definition the base-2 digits of $j$, thus $j=j_1 2^{t-1} + j_2 2^{t-2} + ... + j_t 2^0$. Is this what you are asking?
– glS
May 3, 2020 at 15:45
• Isn't it in the reverse order? $j=j_t 2^{t-1} + \dots + j_1 2^0$? This is where I am confused. May 3, 2020 at 22:24
• There are different conventions for the ordering of the bits when converting to binary. For example, "big endian" or "little endian", which is worth keeping an eye on. Jun 3, 2020 at 7:38

Thanks to comment by @gIS, I realized that I was mixing up the order. If I write $$j$$ as $$|j_1\dots j_t\rangle$$, of course it will be equal to $$j_12^{t-1} \cdots j_t2^0$$. I was confused about the numbering of the qubits.