# Do these outputs seem normal for the order finding algorithm?

I'm sorry for posting so many questions about this specific problem, but I just want to make sure that I am implementing an algorithm correctly. I am simulating the order finding algorithm (finding minimal $$r$$ for $$x^r \ = \ 1$$mod($$N)$$). Right now, I am trying to implement the case of $$x \ = \ 2$$ and $$N \ = \ 5$$. I am getting outputs that look somewhat like this:

When I pass these results through the continued fraction algorithm, I'm getting the expected results of the algorithm, however, these results seem weird, as they are basically just every combination of $$1$$ and $$0$$ for the first two qubits. I just want to make sure that I am actually implementing the algorithm correctly, and not just getting lucky with my results. Again, I'm very sorry for all the questions about this specific problem.

Anyway, let's see what we should get. I'm going to assume a first register (the one that we do the Fourier transform etc on) contains $$t$$ qubits. I'm guessing that $$t=7$$ from your output. We start with the system in $$|0\rangle^{\otimes t}|1\rangle$$, and apply the Hadamard transform to the first register: $$\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|1\rangle.$$ Then we apply the modular exponentiation $$\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|2^j\text{ mod }5\rangle.$$ We can simply this as $$\frac{1}{\sqrt{2^t}}\sum_{k=0}^3\left(\sum_{j=0}^{2^{t-2}-1}|k+4j\rangle\right)|2^k\text{ mod }5\rangle.$$
Now, instead of simply applying the inverse Quantum Fourier Transform, I prefer to think about its action on states. The QFT (not inverse), transforms basis states $$|x\rangle\rightarrow|\psi_x\rangle=\frac{1}{\sqrt{2^t}}\sum_{y=0}^{2^t-1}\omega^{xy}|y\rangle$$ where $$\omega=e^{2\pi i/2^t}$$, so we want to describe our states such as $$|0\rangle+|4\rangle+|8\rangle+|12\rangle+\ldots$$ in terms of $$|\psi_x\rangle$$ to know what values of $$x$$ we might get as output from the inverse QFT. But we can easily observe that $$|0\rangle+|4\rangle+|8\rangle+|12\rangle+\ldots=\frac{1}{2}\sum_{x=0}^3|\psi_{2^{t-2}x}\rangle.$$ Hence, for the $$k=0$$ case, we get each of the 4 answers $$0,2^{t-2},2^{t-1},3\times 2^{t-2}$$ with equal probability. These are the 4 bit strings that you're seeing on output. Similarly, the other 3 values of $$k$$ can be decomposed also in terms of $$\{|\psi_{2^{t-2}x}\rangle\}_{x=0}^3$$, just with different multiplicative factors (fourth roots of unity), the point being that these 4 vectors all have period 4 and they form a basis for the states $$|0\rangle$$ to $$|3\rangle$$.
• I mean that there are 4 answers, each of which is a bit string. In this case, you're talking about the 7 bit representations of the numbers 0 (0000000), $2^{t-2}$ (0100000), $2^{t-1}$ (1000000) and $3\times 2^{t-2}$ (1100000). – DaftWullie Dec 5 '18 at 12:52