# Is this the correct quantum circuit for the order-finding algorithm?

The algorithm is being implemented on Cirq, with the goal of finding the smallest $$r$$ for cooprime numbers $$x$$ and $$N$$ satisfying the equation $$x^r \ = \ 1($$mod $$N)$$. I have set $$x \ = \ 2$$ and $$N \ = \ 3$$, so the algorithm should output $$r \ = \ 2$$.

This is the circuit that Cirq outputs for my code. Are there any mistakes that I'm making in the algorithm implementation, as I am getting some strange results: ## 1 Answer

The Fourier transform part (everything from the swaps onward) looks correct. The initialization (column of Hadamards) looks correct. But the part where you do controlled modular multiplications doesn't, because there's no operations controlled on the 2nd through fifth qubits that you are QFT-ing.

You also seem to expect the output to be the period, when actually the output is a number of the form $$2^n / (kp)$$ where $$p$$ is the period and $$k$$ is an integer and $$n$$ is the number of qubits in your QFT. This blog post may be helpful..

Here is my recommendation on how to proceed.

1. Start from Quirk's example period finding circuit: 2. In Quirk, adjust the circuit to apply to your case, where $$B=2$$ and $$R=3$$.

3. Replace the $$\times B^A \pmod{R}$$ operation with a series of controlled $$\times A \pmod{R}$$ operations, with a different $$A=\text{constant}$$ for each one.

4. Replace each $$\times A \pmod{R}$$ operation, one by one, with simple gates such as CNOTs and Toffolis.

5. Replace the inverse QFT with simple gates such as Hadamards and controlled phases.

6. Compare with the circuit you're trying to make in Cirq.

As you are making the circuit transformations, keep an eye on the output display. If the spikes have moved around or changed, you made a mistake when doing a decomposition.

• Thank you for your answer. However, wouldn't the operations from the second through fifth qubits be trivial? I outlined the mathematical reasoning in a question I posted yesterday: quantumcomputing.stackexchange.com/questions/4852/…. – Jack Ceroni Dec 4 '18 at 22:39
• Also, I'm passing the output through the continued fraction algorithm, I only provided the quantum part here because it is the part that seems not to be working. – Jack Ceroni Dec 4 '18 at 22:44
• I suppose that's true, since the operation has period 2 it's the identity for larger controls. Generally speaking you want to avoid taking advantage of information like that, since you're using the solution in order to formulate the computation to get the solution... oh well. If you're not getting the right answer, you might just have your endian-ness backwards. Try moving the control from the top qubit of the QFT to the bottom qubit of the QFT. – Craig Gidney Dec 4 '18 at 22:56
• The outputs from my circuit seem to match the Quirk circuit, so the algorithm should be working now. On a side note, when you refer to the period finding algorithm, is that the same thing as the order finding algorithm? – Jack Ceroni Dec 5 '18 at 4:46
• @JackCeroni yes – Craig Gidney Dec 5 '18 at 17:56