# 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 '20 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. – usercs May 3 '20 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. – DaftWullie Jun 3 '20 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.