# Would this quantum algorithm implementation work?

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.

• 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! – DaftWullie Dec 3 '18 at 7:56
• 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. – Craig Gidney Dec 3 '18 at 10:43
• 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? – Jack Ceroni Dec 3 '18 at 13:05
• In Nielsen and Chuang it says that in order to make this algorithm, $|y\rangle$ should be initialized as $|11...1\rangle$. – Jack Ceroni Dec 3 '18 at 13:07
• @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. – Craig Gidney Dec 3 '18 at 17:50