I am trying to implement the order finding algorithm on Cirq finding the minimal positive $r$ for coprime $x$ and $N$ satisfying the equation $x^r \ = \ 1$(mod$ \ N$). In my case, I have set $x \ = \ 2$ and $N \ = \ 3$, so the algorithm should output $r \ = \ 2$. In order to implement the unitary, I simply observed that if we initialize the input that is being acted upon by the controlled-unitary matrices as a collection of $|1\rangle$ states, the unitary operation for this algorithm, $U|y\rangle \ = \ |2^jy \ $mod($3)\rangle$ acts trivially, in all circumstances, since $|y\rangle \ = \ |11\rangle \ = \ |3\rangle$. I feel as though I am missing a very important point, or maybe am not understanding the algorithm correctly, because when I try to implement the algorithm with no unitary gate (since it is supposedly trivial), the algorithm does not work.

  • $\begingroup$ You need $N$ to be a composite number. $N=3$ is prime, and therefore has no smaller prime factors, so there's nothing that the factoring algorithm can do! $\endgroup$ – DaftWullie Dec 3 '18 at 7:56
  • $\begingroup$ Circuit constructions for modular arithmetic aren't guaranteed to behave correctly on numbers outside the range [0, N). You have N=3 but are trying to operate on 3, which is not less than 3 and therefore out of range. $\endgroup$ – Craig Gidney Dec 3 '18 at 10:43
  • 1
    $\begingroup$ Ok, thank you. What exactly does the $|y\rangle$ input represent within the circuit though? Can it just be any eigenvector of the unitary for the controlled-gate, like the standard phase estimation algorithm? $\endgroup$ – Jack Ceroni Dec 3 '18 at 13:05
  • $\begingroup$ In Nielsen and Chuang it says that in order to make this algorithm, $|y\rangle$ should be initialized as $|11...1\rangle$. $\endgroup$ – Jack Ceroni Dec 3 '18 at 13:07
  • $\begingroup$ @JackCeroni You might be confused by an ambiguity in the notation. In Figure 5.4 of Nielsen and Chuang, the |1> refers to initializing the register to contain the little-endian representation of the integer 1, not to setting all bits to 1. Only the least significant bit is supposed to be 1. $\endgroup$ – Craig Gidney Dec 3 '18 at 17:50

Your Answer

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

Browse other questions tagged or ask your own question.