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:

enter image description here

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.


1 Answer 1


This looks right, although I would emphasise that it is not really best practice to have to ask this question at this stage. The whole point of doing a particularly simple example is so that you can confirm that it's doing what you've already calculated analytically. It's quite important to do the analytic bit first to avoid confirmation bias.

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$.

  • $\begingroup$ Thank you for your answer. Just one question, you say that I am getting these solutions for 4 bit strings in my output, what exactly do you mean by that (since I have a 7 bit register)? $\endgroup$ Commented Dec 5, 2018 at 12:13
  • $\begingroup$ 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). $\endgroup$
    – DaftWullie
    Commented Dec 5, 2018 at 12:52

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.