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?

  • 2
    $\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 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 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 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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.