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$. enter image description here

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?

  • 3
    $\begingroup$ $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? $\endgroup$
    – glS
    May 3, 2020 at 15:45
  • $\begingroup$ Isn't it in the reverse order? $j=j_t 2^{t-1} + \dots + j_1 2^0$? This is where I am confused. $\endgroup$
    – usercs
    May 3, 2020 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Jun 3, 2020 at 7:38

1 Answer 1


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.


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.